数据布局 day 07

7. 树

7.3. 条理遍历

按照条理举行遍历

代码实现

以队列的头脑举行条理遍历，先让根节点入列，循环开始之后，根节点出列，然后被r拿到

1. void ShowLevelTree (tree_t *tree)
2. {
3.         tree_t* r = NULL;
4.         linqueue_t *p = (linkqueue_t*)malloc(sizeof(linkqueue_t));        // 创建队列p
5.         InLinkQueue(tree, p);        // 队列入列 InLinkQueue(tree_t* tree, linkqueue_t* p);
6.         while(!isEmptyLinkQueue(p))        // 队列判空 isEmptyLinkQueue(linkqueuep_t* p);
7.         {
8.                 r = OutLinkQueue(p);        // 出列 tree_t* OutLinkQueue(linkqueue_t* p);
9.                 printf("%-4d", r->data);
10.                 if(r->lchild != NULL)
11.                         InLinkQueue(r->lchild, p);        // 左孩子入列
12.                 if(r->rchild != NULL)
13.                         InLinkQueue(r->rchilld, p);        // 右孩子入列
14.         }
15.         free(p);
16. }

复制代码

8. 查询算法

8.1. 次序查找 seqSearch

根本思绪： 通过for循环，重新开始遍历整个数组，找到相应数据返回对应下标，找不到返回-1
缺陷： 当数据个数过多时，查找速率会变慢
代码实现

1. #include <stdio.h>
2. #define N 10
3. int seqSearch (int *p, int data)
4. {
5.         int post = 0;
6.         for(post = 0; post < N; post++)
7.                 if(p[post] == data)
8.                         return post;
9.         return -1;
10. }
11. int main()
12. {
13.         int a[N] = {12,34,45,23,54,2,4,65,23};
14.         printf("%d\n", seqSearch (a, 2));
15.         return 0;
16. }

复制代码

8.2. 二分法查找 binarySearch

又叫分半查找，拆半查找
条件条件： 数组中的元素必须是有序分列
根本思绪： 界说low，high，middle三个变量，分别指向第一个元素，末了一个元素，中央的元素，将middle指向的数据与查找数据比力，看看在哪个半区，看情况移动low和high，指向查找数据所在的半区的首尾
代码实现

1. #include <stdio.h>
2. #define N 10
4. int binarySearch (int *p, int data)
5. {
6.         // 定义变量并初始化
7.         int low = 0;
8.         int high = N-1;
9.         int middle = 0;
10.         // 查找data
11.         while(low <= high)
12.         {
13.                 middle = (low+high)/2;
14.                 if(p[middel] == data)
15.                         return middel;
16.                 else if(p[middle] > data)        // data在low和middle之间
17.                         high = middle-1;
18.                 else         // data 在high和middle之间
19.                         low = middle+1;
20.         }
21. }
22. int main()
23. {
24.         int a[N] = {12,34,45,23,54,2,4,65,23};
25.         printf("%d\n", binarySearch (a, 2));
26.         return 0;
27. }

复制代码

8.2. 分块查找 blockSearch

存储范例： 索引存储，索引表+源数据表
利用条件： 块间有序，块内无序
根本思绪： 先分块，通过对比查找数据，确定查找数据在哪个块里，然后遍历这个块，找到被查找数据。块简直承认以通过新界说的变量start和end确定
代码实现

1. #include <stdio.h>
2. #define N 19
4. // 定义索引表的结构体
5. typedef struct list
6. {
7.         int max;        // 源数据表块内的最大值
8.         int post;        // 源数据表分块的起始下标
9. }list_t;
11. int blockSearch (int* p, list_t* P, int data)
12. {
13.         int start = 1;        // 块的起始下标
14.         int end = 0;        // 块的结束下标
15.         int i = 0;        // 遍历计数
16.         for(;i<=3 ;i++)        // 确定data在哪个块里
17.         {
18.                 if(P[i]->max >= data)
19.                 {
20.                         start = P[i]->post
21.                         if(i == 3)
22.                                 end = N-1;
23.                         else
24.                                 end = P[i+1]->post;
25.                 }
26.         }
27.         start =end +1; // 找到最后没找到
28.         // 遍历这个块
29.         while(start <= end)
30.         {
31.                 if(p[start] == data)
32.                         return start;
33.                 else
34.                         start++;
35.         }
36.         return -1;
37. }
38. int main ()
39. {
40.         // 创建源数据表，分块取最大值
41.         int a[N] = {18, 10, 9, 8, 16, 20, 38, 42, 19, 50, 84, 72, 56, 55, 76, 100, 90, 88, 108};
42.                         //  0                                   5                                  10                                   15
43.         // 创建索引，获取分块和分块元素下标
44.         list_t A[4] = {{18,0}, {50,5}, {84,10}, {108,15}};
45.         blockSearch(a, A, 55);
46.         return 0;
47. }

复制代码

8.3. 哈希表 hash

存储范例： 散列存储
key简直定：

• 直接用干系数据作为key
  
• 找不重复的字段作为key
  
• 数据太长时可以取前几位，中央几位，后几位求和末了再取几位
  
• 终极目标只是低落关键字重复的大概性
  

创建一个数组hashlist，关键字大概的最大值作为元素个数，通过hashlist[key]来查询数据内容
9. 排序算法

9.1. 冒泡排序 bubSort

一步一步将较小的元素“浮”到数组顶端,将较大的元素一步一步“沉”到数组底端，小范围互换，均匀复杂度O(n2)
代码实现

1. void BubSort(int *p， int n)        // p：数组，n：元素个数
2. {
3.         int temp = 0;
4.         for(int i = 0; i < n; i++)
5.         {
6.                 for(int j = 0; j < n-1-i; j++)
7.                 {
8.                         if(p[j] > p[j+1])
9.                         {
10.                                 temp = p[j];
11.                                 p[j] = p[j+1];
12.                                 p[j+1] = temp;
13.                         }
14.                 }
15.         }
16. }

复制代码

9.2. 选择排序 selSort

一个一个比力已往，找到最小的元素放在第一个，反面每个找到的最小的数据都放在排好的末端，时间复杂度永久是O(n2)
代码实现

1. void selSort (int *p, int n)
2. {
3.         int k = 0;
4.         int temp = 0;
5.         for(int i = 0;i < n; i++)
6.         {
7.                  k = i;
8.                  for(int j = i; j < n; j++)
9.                  {
10.                          if (p[k] < p[j])
11.                                  k = j;
12.                  }
13.                  temp = p[k];
14.                  p[k] = p[i];
15.                  p[i] = temp;
16.         }
17. }

复制代码

9.3. 插入排序 inserSort

将未排序元素拿出来，依次与前面比力，直到找到比拿出来的元素小的元素，插入到较小的元素反面的位置，反面别的元素依次向后移动一个单元
代码实现

1. void inserSort (int *p, int n)
2. {
3.         int temp = 0;
4.         int j = 0;
5.         for(int i = 1; i < n; i++)
6.         {
7.                 temp = p[i];
8.                 for(j = i-1; j>=0 && p[j]>temp; j--)
9.                         p[j+1] = p[j];
10.                 p[j+1] = temp;
11.         }
12. }

复制代码

9.4. 快速排序 quickSort

以二分的头脑，大范围互换数据
代码实现

1. // 获取数组的下标的开头和结尾
2. void quickSort(int* arr, int start, int end)
3. {
4.         // 递归停止位置
5.         if(start == end)
6.                 return;
7.         int temp = 0;
8.         int i = start+1;
9.         int j = end;
10.         while(i < j)
11.         {
12.                 // end 小于基准值停止移动
13.                 while(i <= j && arr[j] >= arr[start])
14.                         j--;
15.                 // start 大于基准值停止移动
16.                 while(i <= j && arr[i] <= arr[start])
17.                         i++;
18.                 // 找到对应的值之后进行交换
19.                 temp =  arr[i];
20.                 arr[i] = arr[j];
21.                 arr[j] = temp;
22.         }
23.         // i 与 j 相等的位置就是基准值的位置
24.         temp = arr[start];
25.         arr[start] = arr[j];
26.         arr[j] = temp;
27.         quickSort(arr, start, j-1);        // 左边数组
28.         quickSort(arr, j+1, end);        // 右边数组
29. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。