数据结构day07

数据结构 day07 7. 树7.3. 层次遍历代码实现 8. 查询算法8.1. 顺序查找 seqSearch代码实现 8.2. 二分法查找 binarySearch代码实现 8.2. 分块查找 blockSearch代码实现 8.3. 哈希表 hash 9. 排序算法9.1. 冒泡排序 bubSort代码实现 9.2. 选择排序 selSort代码实现 9.3. 插入排序 inserSort代码实现

7. 树 7.3. 层次遍历

按照层次进行遍历

代码实现

以队列的思想进行层次遍历，先让根节点入列，循环开始之后，根节点出列，然后被r拿到

void ShowLevelTree (tree_t *tree) { tree_t* r = NULL; linqueue_t *p = (linkqueue_t*)malloc(sizeof(linkqueue_t)); // 创建队列p InLinkQueue(tree, p); // 队列入列 InLinkQueue(tree_t* tree, linkqueue_t* p); while(!isEmptyLinkQueue(p)) // 队列判空 isEmptyLinkQueue(linkqueuep_t* p); { r = OutLinkQueue(p); // 出列 tree_t* OutLinkQueue(linkqueue_t* p); printf("%-4d", r->data); if(r->lchild != NULL) InLinkQueue(r->lchild, p); // 左孩子入列 if(r->rchild != NULL) InLinkQueue(r->rchilld, p); // 右孩子入列 } free(p); } 8. 查询算法 8.1. 顺序查找 seqSearch

基本思路： 通过for循环，从头开始遍历整个数组，找到相应数据返回对应下标，找不到返回-1 缺陷： 当数据个数过多时，查找速度会变慢

代码实现 #include <stdio.h> #define N 10 int seqSearch (int *p, int data) { int post = 0; for(post = 0; post < N; post++) if(p[post] == data) return post; return -1; } int main() { int a[N] = {12,34,45,23,54,2,4,65,23}; printf("%d\n", seqSearch (a, 2)); return 0; } 8.2. 二分法查找 binarySearch

又叫分半查找，拆半查找 前提条件： 数组中的元素必须是有序排列 基本思路： 定义low，high，middle三个变量，分别指向第一个元素，最后一个元素，中间的元素，将middle指向的数据与查找数据比较，看看在哪个半区，看情况移动low和high，指向查找数据所在的半区的首尾

代码实现 #include <stdio.h> #define N 10 int binarySearch (int *p, int data) { // 定义变量并初始化 int low = 0; int high = N-1; int middle = 0; // 查找data while(low <= high) { middle = (low+high)/2; if(p[middel] == data) return middel; else if(p[middle] > data) // data在low和middle之间 high = middle-1; else // data 在high和middle之间 low = middle+1; } } int main() { int a[N] = {12,34,45,23,54,2,4,65,23}; printf("%d\n", binarySearch (a, 2)); return 0; } 8.2. 分块查找 blockSearch

存储类型： 索引存储，索引表+源数据表 使用条件： 块间有序，块内无序 基本思路： 先分块，通过对比查找数据，确定查找数据在哪个块里，然后遍历这个块，找到被查找数据。块的确认可以通过新定义的变量start和end确定

代码实现 #include <stdio.h> #define N 19 // 定义索引表的结构体 typedef struct list { int max; // 源数据表块内的最大值 int post; // 源数据表分块的起始下标 }list_t; int blockSearch (int* p, list_t* P, int data) { int start = 1; // 块的起始下标 int end = 0; // 块的结束下标 int i = 0; // 遍历计数 for(;i<=3 ;i++) // 确定data在哪个块里 { if(P[i]->max >= data) { start = P[i]->post if(i == 3) end = N-1; else end = P[i+1]->post; } } start =end +1; // 找到最后没找到 // 遍历这个块 while(start <= end) { if(p[start] == data) return start; else start++; } return -1; } int main () { // 创建源数据表，分块取最大值 int a[N] = {18, 10, 9, 8, 16, 20, 38, 42, 19, 50, 84, 72, 56, 55, 76, 100, 90, 88, 108}; // 0 5 10 15 // 创建索引，获取分块和分块元素下标 list_t A[4] = {{18,0}, {50,5}, {84,10}, {108,15}}; blockSearch(a, A, 55); return 0; } 8.3. 哈希表 hash

存储类型： 散列存储 key的确定：

直接用相关数据作为key找不重复的字段作为key数据太长时可以取前几位，中间几位，后几位求和最后再取几位最终目的只是降低关键字重复的可能性

创建一个数组hashlist，关键字可能的最大值作为元素个数，通过hashlist[key]来查询数据内容

9. 排序算法 9.1. 冒泡排序 bubSort

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

代码实现 void BubSort(int *p， int n) // p：数组，n：元素个数 { int temp = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < n-1-i; j++) { if(p[j] > p[j+1]) { temp = p[j]; p[j] = p[j+1]; p[j+1] = temp; } } } } 9.2. 选择排序 selSort

一个一个比较过去，找到最小的元素放在第一个，后面每个找到的最小的数据都放在排好的末尾，时间复杂度永远是O(n2)

代码实现 void selSort (int *p, int n) { int k = 0; int temp = 0; for(int i = 0;i < n; i++) { k = i; for(int j = i; j < n; j++) { if (p[k] < p[j]) k = j; } temp = p[k]; p[k] = p[i]; p[i] = temp; } } 9.3. 插入排序 inserSort

将未排序元素拿出来，依次与前面比较，直到找到比拿出来的元素小的元素，插入到较小的元素后面的位置，后面其余元素依次向后移动一个单位

代码实现 void inserSort (int *p, int n) { int temp = 0; int j = 0; for(int i = 1; i < n; i++) { temp = p[i]; j = i-1; while(j>=0 && p[j]>temp) { p[j+1] = p[j]; j--; } p[j+1] = temp; } }