数据结构源码

约瑟夫环

#include<iostream>
using namespace std;
struct Node
{
 int number;
 int code;
 Node* next;
};
int number, code, person_number, start_code;
Node* head, * pre, * p;
int Size = 0;
void insert_node()
{
 if (Size == 0)
 {
  p = new Node;
  p->code = code;
  p->number = number;
  head = p;
  pre = p;
  Size++;
 }
 else
 {
  p = new Node;
  p->code = code;
  pre->next = p;
  p->number = number;
  pre = p;
  Size++;
 }
}
void Delete_node(Node* aim,Node* pre)
{
 pre->next = aim->next;
 cout << aim->number << " ";
 start_code = aim->code;
 delete aim;
 Size--;
}
int main()
{
 cin >> person_number >> start_code;
 for (int i = 1; i <= person_number; i++)
 {
  cin >> code;
  number = i;
  insert_node();
  if (i == person_number)
  {
   p->next = head;
  }
 }
 Node* q = head;
 while (q && q->next != head)
 {
  q = q->next;
 }
 pre = q;
 q = head;
 int i = 1;
 while (Size > 0)
 {
  int i = 1;
  if (start_code == 1)
  {
   Delete_node(q, pre);
   q = pre->next;
  }
  else
  {
   while (i != start_code - 1 && q)
   {
    q = q->next;
    i++;
   }
   Delete_node(q->next, q);
   pre = q;
   q = q->next;
  }
 }
 return 0;
}

哈夫曼树

代码见对拍模板的ZhengJie。

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;

priority_queue<int,vector<int>,greater<int> >q;
int n,ans=0;
int main()
{
 scanf("%d",&n);
 while(n--)
 {
  int t;
  scanf("%d",&t);
  q.push(t);
 }
 while(1)
 {
  int a=q.top();
  q.pop();
  if(q.empty())
   break;
  int b=q.top();
  q.pop();
  ans+=a+b;
  q.push(a+b);
 }
 printf("%d\n",ans);
}

哈夫曼树的wpl 就是 所有 非叶子结点的权之和
这样子就不用专门去求路径长度了
直接遍历一遍找出非叶子结点相加就好了

二叉树的建立

#include<iostream>
using namespace std;
struct Node
{
 char data;
 Node* LChild = NULL;
 Node* RChild = NULL;
};
char ch;
int flag = 1;
Node* head = new Node;
void CreateBiTree(Node*T)
{
 if (!(cin >> ch))
 {
  T = NULL;
  return;
 }
 if (ch == '#')
 {
  T->data = ' ';
  T = NULL;
 }
 else
 {
  T->data = ch;
  T->LChild = new Node;
  CreateBiTree(T->LChild);
  T->RChild = new Node;
  CreateBiTree(T->RChild);
 }
}
void InOrderTraverse(Node* T)
{
 if (T != NULL)
 {
  InOrderTraverse(T->LChild);
  if (T->data != ' ')
  {
   cout << T->data << " ";
  }
  InOrderTraverse(T->RChild);
 }
}
int main()
{
 CreateBiTree(head);
 InOrderTraverse(head);
 return 0;
}

将满二叉树转换为求和树

#include<iostream>
#include<string>
using namespace std;
int pre[1300], in[1300];
int node_number;
struct Node
{
    int data = 0;
    Node* left = NULL;
    Node* right = NULL;
    int sum = 0;
};
Node& get_tree(int pre_begin, int pre_end, int in_begin, int in_end)
{
    Node* node = new Node;
    node->data = pre[pre_begin];
    if (pre_begin > pre_end || in_begin > in_end)
    {
        node = NULL;
        return *node;
    }
    //int index = in.find(pre[pre_begin]);
    int index = 0;
    for (int i = 1; i <= node_number; i++)
    {
        if (in[i] == pre[pre_begin])
        {
            index = i;
            break;
        }
    }
    node->left = &(get_tree(pre_begin + 1, pre_begin + index - in_begin, in_begin, index - 1));//注意这里第一个参数是pre_begin+1,不要忘记加一
    node->right = &(get_tree(pre_begin + index - in_begin + 1, pre_end, index + 1, in_end));
    return *node;
}
void sumNode(Node& node)
{
    if (node.left == NULL && node.right == NULL)
    {
        node.sum = 0;
    }
    else if (node.left == NULL)
    {
        sumNode(*node.right);
        node.sum = node.right->sum + node.right->data;
    }
    else if (node.right == NULL)
    {
        sumNode(*node.left);
        node.sum = node.left->sum + node.left->data;
    }
    else
    {
        sumNode(*node.left);
        sumNode(*node.right);
        node.sum = node.left->sum + node.left->data + node.right->sum + node.right->data;
    }
}
void inodergo(Node* node)
{
    if (node == NULL)
        return;
    inodergo(node->left);
    if (node->data != 0)
    {
        cout << node->sum << " ";
    }
    inodergo(node->right);
}
int main()
{
    cin >> node_number;
    for (int i = 1; i <= node_number; i++)
    {
        cin >> pre[i];
    }
    for (int i = 1; i <= node_number; i++)
    {
        cin >> in[i];
    }
    Node head = get_tree(0, node_number, 0, node_number);
    sumNode(head);
    inodergo(&head);
    return 0;
}

hash

#include<iostream>
#include<map>
using namespace std;
int hash[105];
int mode, table_size;
int key;
int value;
int now_size;
map<int, int>M;
void hash_search(int key)
{
 for (int i = 0; i < table_size; i++)
 {
  if (::hash[i] == key)
  {
   cout << i << "\n";
   return;
  }
 }
}
void hash_function(int key)
{
 value = key % mode;
 if (M[key])
 {
  hash_search(key);
  return;
 }
 if (now_size == table_size - 1)
 {
  cout << "Table full\n";
  return;
 }
 while (::hash[value] != -1)
 {
  value = (value + 1)%table_size;
 }
 cout << value << "\n";
 ::hash[value] = key;
 M[key]++;
 now_size++;
}
int main()
{
 for (int i = 0; i <= 104; i++)
 {
  ::hash[i] = -1;
 }
 cin >> table_size >> mode;
 while (1)
 {
  cin >> key;
  if (key == -1)
  {
   break;
  }
  hash_function(key);
 }
 return 0;
}

STL实现小顶堆

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<functional>
using namespace std;
int elem_number;
vector<int>vec;
vector<int>::iterator it;
int main()
{
    cin >> elem_number;
    int elem;
    for (int i = 0; i < elem_number; i++)
    {
        cin >> elem;
        vec.push_back(elem);
    }
    make_heap(vec.begin(), vec.end(), greater<int>());//不加比较函数默认为大顶堆
    for (it = vec.begin(); it != vec.end(); it++)
    {
        cout << *it << " ";
    }
    return 0;
}

STL归并排序

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
int A_number, B_number;
vector<int>A;
vector<int>B;
vector<int>::iterator it;
vector<int>result;
int main()
{
 cin >> A_number >> B_number;
 int value;
 for (int i = 1; i <= A_number; i++)
 {
  cin >> value;
  A.push_back(value);
 }
 for (int i = 1; i <= B_number; i++)
 {
  cin >> value;
  B.push_back(value);
 }
 result.resize(A_number + B_number);
 merge(A.begin(), A.end(), B.begin(), B.end(),result.begin());
 for (it = result.begin(); it != result.end(); it++)
 {
  cout << *it << " ";
 }
 cout << "\n";
 return 0;
}

快排

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
vector<int>::iterator it;
int main()
{
 int sum = 0;
 int num;
 cin >> num;
 vector<int>vec;
 for (int i = 0; i < num; i++)
 {
  int temp;
  cin >> temp;
  vec.push_back(temp);
 }
 int index_head, index_tail;
 index_head = 0;
 index_tail = vec.size() - 1;
 int temp = vec[index_head];
 while (index_head < index_tail)
 {
  while (index_head < index_tail && vec[index_tail] >= temp)
  {
   --index_tail;
  }
  vec[index_head] = vec[index_tail];
  while (index_head < index_tail && vec[index_head] <= temp)
  {
   ++index_head;
  }
  vec[index_tail] = vec[index_head];
 }
 vec[index_head] = temp;
 for (int i = 0; i < vec.size(); i++)
 {
  cout << vec[i] << " ";
 }
 cout << "\n";
 return 0;
}

冒泡排序

#include<iostream>
using namespace std;
int database[105];
int data_number;
int cnt = 0;
int temp;
int main()
{
 cin >> data_number;
 for (int i = 1; i <= data_number; i++)
 {
  cin >> database[i];
 }
 for (int i = 1; i <= data_number; i++)
 {
  for (int j = 1; j+i <= data_number; j++)
  {
   if (database[j ] > database[j+1])
   {
    temp = database[j ];
    database[j ] = database[j+1];
    database[j+1] = temp;
    cnt++;
   }
  }
 }
 //for (int i = 1; i <= data_number; i++)
 //{
 // cout << database[i] << endl;
 //}
 cout << cnt << "\n";
 return 0;
}

希尔排序

#include<iostream>
using namespace std;
 
void print(int a[], int n)
{  
    for(int j= 0; j<n; j++)
 {  
           cout<<a[j] <<"  ";  
        }  
    cout<<endl;  
}
 
void shellSort(int a[], int n)  //a -- 待排序的数组, n -- 数组的长度
{
    int i,j,gap;   // gap为步长，每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组，对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap) 
            { 
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}
 
int main()
{  
    int a[10] = {8,1,9,7,2,4,5,6,10,3};  
    cout<<"初始序列：";  
    print(a,10);  
    shellSort(a,10);  
    cout<<"排序结果：";  
    print(a,10);  
    system("pause"); 
}

插入排序

#include<iostream>
using namespace std;
int database[105];
int data_number;
int main()
{
 cin >> data_number;
 for (int i = 1; i <= data_number; i++)
 {
  cin >> database[i];
 }
 for (int i = 1; i <= 3; i++)
 {
  int j = i+1;
  while (j > 1)
  {
   if (database[j] < database[j - 1])
   {
    int temp;
    temp = database[j];
    database[j] = database[j - 1];
    database[j - 1] = temp;
    j--;
   }
   else
   {
    break;
   }
  }
  for (int i = 1; i <= data_number; i++)
  {
   cout << database[i] << " ";
  }
  cout << "\n";
 }
 return 0;
}