顺序查找
顺序查找又称为线性查找，对线性表和链表都适用。 线性表可以通过数组下标递增来顺序扫描每个元素，链表可以通过next指针依次扫描每一个元素。
::: tip 指针实现顺序表时，顺序表中是指针时，在定义顺序表的结构体后，需要对顺序表初始化，初始化时为指针申请堆空间，堆空间的使用类似于数组，和数组形式的区别是可以动态控制数组的大小。 :::
1#include <stdio.h> 2#include <stdlib.h> 3#include <time.h> 4 5//指针实现顺序表 6typedef int Elemtype; 7//定义顺序表 8typedef struct 9{ 10 Elemtype* elem; //指针，类型自定，申请堆空间的起始地址存入elem 11 int TableLen; //存储在动态数组中元素的个数 12}SSTable; 13 14void ST_Init(SSTable& ST, int len) 15{ 16 ST.TableLen = len + 1; //需要多申请一个位置，原因是0号位置存放“哨兵” 17 ST.elem = (Elemtype*)malloc(sizeof(Elemtype) * ST.TableLen); //指针elem指向的每个元素都是Elemtype类型的（int） 18 int i; 19 srand(time(NULL)); //随机数生成 20 for (i = 1; i < ST.TableLen; i++) //0号位置是哨兵，随机数从1号位置开始 21 { 22 ST.elem[i] = rand() % 100; //%100使得生成的随机数在0-99之间 23 } 24} 25 26//打印顺序表 27void ST_Print(SSTable ST) 28{ 29 int i; 30 for (i = 1; i < ST.TableLen; i++) 31 { 32 printf("%3d", ST.elem[i]); //类似于数组访问，elem相当于数组名 33 } 34 printf("\n"); 35} 36 37int search_seq(SSTable ST, Elemtype key) 38{ 39 ST.elem[0] = key; //key存在0号位置，作为哨兵，哨兵的存在可有可无，哨兵存在的意义是循环判断条件不用写i>=0 40 int i; 41 for (i = ST.TableLen - 1; ST.elem[i] != key; i--); 42 return i; 43} 44int main() 45{ 46 SSTable ST; 47 ST_Init(ST, 10); 48 ST_Print(ST); //打印顺序表中的元素（顺序表中的元素位置从1开始） 49 Elemtype key; 50 printf("请输入要查找的key值\n"); 51 scanf("%d", &key); 52 int pos; //查找函数返回的下标位置 53 pos = search_seq(ST, key); 54 if (pos) 55 { 56 printf("找到了，位置为%d\n", pos); 57 } 58 else 59 { 60 printf("没有找到\n"); 61 } 62 return 0; 63}
折半查找
::: warning 折半查找又称二分查找，只适用于有序顺序表（升序或降序都可以）。 ::: 折半查找的基本思想：首先将给定值key与表中中间位置的元素比较，若相等则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值key大于中间元素，则所查找的元素只可能在后半部分），然后在缩小的范围内继续进行同样的查找，如此重复。直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。 ::: warning qsort只能用来排序数组，不能用来排序链表。 ::: qsort函数头文件：#include<stdlib.h> 函数原型：void qsort(void * base,size_t num,size_t size,int ( * compare)(const void * ,const void * )) base：指向要排序的数组的第一个元素的指针（数组地址）。 num：由 base 指向的数组中元素的个数（参与排序的目标数组元素个数）。 size：数组中每个元素的大小，以字节为单位（推荐使用sizeof(s[0]）这样的表达式）。 int ( * compare)(const void * ,const void * )是一个函数指针，需要编写实现compare函数，将函数名传递到qsort函数中作为参数调用。
::: tip 折半查找代码流程： 1、初始化顺序表，输入随机10个元素。 2、使用qsort进行排序，排序完毕后打印。 3、输入要查找的元素值，存入变量key 中。 4、通过二分查找查找对应key值，找到则输出在顺序表中的位置，没找到输出未找到。 :::
compar：用来比较两个元素的函数，即函数指针（回调函数）。 compare函数定义是int compare(const void * a,const void * b); 如果是升序，即a比b大，返回正值；如果是降序，即a比b小，返回负值；a和b相等则返回0。 a和b指向数组中的任意两个元素，qsort可以对多种类型的数组进行排序，在使用a和b之前需要先将a和b由void类型强制转换成其它类型。
1#include <stdio.h> 2#include <stdlib.h> 3#include <time.h> 4 5typedef int Elemtype; 6typedef struct 7{ 8 Elemtype* elem; //整型指针 9 int TableElem; //存储在动态数组中的元素个数 10}SSTable; 11//随机树表初始化，没有使用哨兵 12void InitTable(SSTable& ST, int len) 13{ 14 ST.TableElem = len; 15 ST.elem = (Elemtype*)malloc(sizeof(Elemtype)); 16 int i = 0; 17 srand(time(NULL)); 18 for (i; i < ST.TableElem; i++) 19 { 20 ST.elem[i] = rand() % 100; 21 } 22} 23//打印随机数 24void PrintTable(SSTable ST) 25{ 26 int i = 0; 27 for (i; i < ST.TableElem; i++) 28 { 29 printf("%3d", ST.elem[i]); 30 } 31 printf("\n"); 32} 33//二分查找 34int binary_search(SSTable ST, Elemtype key) 35{ 36 int low = 0, high = ST.TableElem - 1; 37 int mid; 38 while (low <= high) 39 { 40 mid = (low + high) / 2; 41 if (key < ST.elem[mid]) 42 { 43 high = mid - 1; 44 mid = (low + high) / 2; 45 46 } 47 else if (key > ST.elem[mid]) 48 { 49 low = mid + 1; 50 mid = (low + high) / 2; 51 52 } 53 else 54 { 55 return mid; 56 } 57 } 58 return -1; 59} 60 61//函数名compare中存放着函数入口地址，是函数指针类型 62int compare(const void* left, const void* right) 63{ 64 return *(int*)left - *(int*)right; //从小到大排序，(int*)表示强制类型转换，*表示解引用，通过地址找到指针指向的元素 65 //如果是升序，即left比right大，返回正值；如果是降序，left比right小，返回负值；left和right相等，返回0 66 //return *(int*)right-*(int*)left; //从大到小排序 67} 68 69int main() { 70 SSTable ST; 71 int x; 72 scanf("%d", &x); 73 InitTable(ST, x); 74 PrintTable(ST); 75 qsort(ST.elem, ST.TableElem, sizeof(Elemtype), compare); 76 PrintTable(ST); 77 Elemtype key; 78 printf("input search key\n"); 79 scanf("%d", &key); 80 int ret = binary_search(ST, key); 81 if (ret != -1) 82 { 83 printf("search success,location %d\n", ret); 84 } 85 else { 86 printf("seasrch faild\n"); 87 } 88 return 0; 89} 90
二叉排序树
二叉排序树又称二叉查找树。 ::: tip 二叉排序树或者是一棵空树，或者是具有下列特点的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； ::: 二叉排序树的最大查找次数是树的高度。 二叉排序树的遍历使用中序遍历（其他遍历方式无意义）。 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。相当于将二叉排序树踩扁，自左向右遍历，此时二叉排序树中序遍历后结果是有序（由小到大）的。 注：二叉排序树不考虑树中存放相等的元素。 ::: warning 二叉排序树删除节点时的特殊情况：如果要删除的节点是根节点或含有左右子树的节点，可以将该节点的左子树最右侧的节点值（左子树中的最大数据）或右子树最左侧的节点值（右子树中的最大数据）替换到删除结点的位置，替换后左子树最右侧的节点或右子树最左侧的节点被删除，由下面的左子树或右子树顶上，重新组成的二叉树仍满足二叉排序树的要求。 （拿到左子树的最右侧节点的方法是先拿到左子树的根节点，然后循环不断向下拿到右孩子，右子树的最左节点类似。) ::: 如果没有找到删除的节点时，删除函数中根节点T变为NULL，return 0，程序结束。
1#include <stdio.h> 2#include <stdlib.h> 3 4typedef int Keytype; 5//存放树的节点 6typedef struct BSTNode 7{ 8 Keytype data; 9 struct BSTNode* lchild; 10 struct BSTNode* rchild; 11}BSTNode, * BiTree; 12 13//非递归方式创建二叉排序树 14//二叉排序树的节点插入 15int BST_Insert(BiTree& T, Keytype k) 16{ 17 BiTree TreeNew = (BiTree)calloc(1, sizeof(BSTNode)); //节点进入后创建节点存储新申请的空间 18 TreeNew->data = k; 19 if (NULL == T) 20 { 21 T = TreeNew; //树为空时，新节点TreeNew作为树根 22 return 0; 23 } 24 BiTree p = T, parent = NULL; //树根存在时使用p从树根开始查找新节点TreeNew应该存放的位置 25 while (p) 26 { 27 parent = p; //parent为p的父节点 28 //不考虑元素相等的情况 29 if (k < p->data) 30 { 31 p = p->lchild; //p置为NULL 32 } 33 else if (k > p->data) 34 { 35 p = p->rchild; //p置为NULL 36 } 37 else 38 { 39 return -1; //元素相等 40 } 41 } 42 //while循环结束后p找到应该存放的位置 43 //判断新节点TreeNew放在parent的位置 44 if (k < parent->data) 45 { 46 parent->lchild = TreeNew; //小于放在父节点左边 47 } 48 else { 49 parent->rchild = TreeNew; //大于放在父节点右边 50 } 51 return 0; 52} 53 54//二叉排序树的创建 55void CreatBSTree(BiTree& T, Keytype* str, int len) //数组名是指针，len表示，数组元素个数 56{ 57 //每次向二叉排序树中放入一个节点 58 int i; 59 for (i = 0; i < len; i++) 60 { 61 BST_Insert(T, str[i]); //引用支持子函数传递 62 //函数CreatBSTree使用引用符号，实际引用操作发生在函数CreatBSTree中的BST_Insert内 63 } 64} 65 66//二叉排序树的中序遍历 67void InOrder(BiTree T) 68{ 69 if (NULL != T) 70 { 71 InOrder(T->lchild); 72 printf("%3d", T->data); 73 InOrder(T->rchild); 74 } 75} 76 77//查找 78BiTree BST_Search(BiTree T, Keytype k) 79{ 80 while (NULL != T && k != T->data) 81 { 82 if (k < T->data) 83 { 84 T = T->lchild; 85 } 86 else { 87 T = T->rchild; 88 } 89 } 90 return T; 91} 92 93//通过递归实现删除 94void DeleteNode(BiTree& T, Keytype key) 95{ 96 if (NULL == T) 97 { 98 return; 99 } 100 if (key < T->data) //要删除的节点比当前树根节点小 101 { 102 DeleteNode(T->lchild, key); //在左子树上删除，执行递归 103 } 104 else if (key > T->data) //要删除的节点比当前树根节点大 105 { 106 DeleteNode(T->rchild, key); //在右子树上删除，执行递归 107 } 108 else //找到要删除的节点 109 { 110 if (NULL == T->lchild) //要删除的节点左子树为空时，用该节点的右子树顶替该节点 111 { 112 BiTree TempNode = T; //使用临时指针TempNode指向原来指针T指向的空间，指针T指向的空间是要删除的节点的空间 113 T = T->rchild; //该节点的右子树顶替该节点 114 free(TempNode); //释放删除节点的空间 115 } 116 else if (NULL == T->rchild) //要删除的节点右子树为空时，用该节点的左子树顶替该节点 117 { 118 BiTree TempNode = T; //使用临时指针TempNode指向原来指针T指向的空间，指针T指向的空间是要删除的节点的空间 119 T = T->lchild; //该节点的左子树顶替该节点 120 free(TempNode); //释放删除节点的空间 121 } 122 else //左右子树都不为空时 123 { 124 //拿左子树中的最右节点，左子树中的最右节点就是左子树中的最大数据 125 BiTree TempNode = T->lchild; 126 while (NULL != TempNode->rchild) //一直向下拿到右孩子为空时停止 127 { 128 TempNode = TempNode->rchild; 129 } 130 T->data = TempNode->data; //左子树中的最大数据替换掉要删除的值 131 DeleteNode(T->lchild, TempNode->data); 132 //删除左子树中的最右节点，不是改变后的根节点，传T->lchild，即要在左子树的上找到要删除的值，并将该节点删除 133 } 134 } 135} 136 137int main() 138{ 139 BiTree T = NULL; //指向树根的指针 140 Keytype str[7] = { 54,20,66,40,28,79,58 }; 141 CreatBSTree(T, str, 7); 142 InOrder(T); //二叉排序树中序遍历后结果是由小到大的 143 printf("\n"); 144 BiTree search, parent; 145 search = BST_Search(T, 66, parent); //找到后返回查找值的位置和父节点 146 if (search) 147 { 148 printf("find key %d\n", search->data); 149 } 150 else { 151 printf("not find\n"); 152 } 153 DeleteNode(T, 66); 154 InOrder(T); 155 printf("\n"); 156 return 0; 157}
1 20 28 40 54 58 66 79 2find key 66 3 20 28 40 54 58 79
题目分析
当两个有序序列中的元素个数为奇数时，只能舍弃中位数之前、之后的元素，不能舍弃中位数。
当序列中元素个数为偶数时，如舍弃到最后序列中只剩下两个元素时，此时a<b，元素a前没有可以舍弃的元素时，可以舍弃自己。即小于时舍弃中位数之前的元素包括中位数，大于时舍弃中位数之后的元素。
1#include <stdio.h> 2 3int MidSearch(int* A, int* B, int x) 4{ 5 // art简写为s，代表首位数字，end简写为d，代表末位数字，m代表中位数 6 int s1 = 0, d1 = x - 1, m1, s2 = 0, d2 = x - 1, m2; //0和4表示数组下标，m1=(s1+d1)/2，m2=(s2+d2)/2 7 while (s1 != d1 || s2 != d2) //循环结束条件是两个数组最后各剩下一个元素，即s1=d1和s2=d2 8 { 9 m1 = (s1 + d1) / 2; 10 m2 = (s2 + d2) / 2; 11 if (A[m1] == B[m2]) 12 { 13 return A[m1]; //或者B[m2]，满足条件1 14 } 15 else if(A[m1] < B[m2]) //满足条件2 16 { 17 if ((s1 + d1) % 2 == 0) //数组中元素个数为奇数（s1起始位置为0） 18 { 19 s1 = m1; //舍弃数组A中间点m1之前的元素保留中间点m1 20 d2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2 21 } 22 else //数组中元素个数为偶数，m1<m2 23 { 24 s1 = m1 + 1; //舍弃数组A中间点m1之前的元素包括中间点m1 25 d2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2 26 } 27 } 28 else //A[m1]>B[m2]) //满足条件3（与条件2对称） 29 { 30 if ((s1 + d1) % 2 == 0) //数组中元素个数为奇数（s1起始位置为0） 31 { 32 d1 = m1; //舍弃数组A中间点m1之后的元素保留中间点m1 33 s2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2 34 } 35 else //数组中元素个数为偶数，m1<m2 36 { 37 d1 = m1; //舍弃数组A中间点m1之后的元素保留中间点m1 38 s2 = m2 + 1; //舍弃数组B中间点m2之后的元素包括中间点m2 39 } 40 } 41 } 42 return A[s1] < B[s2] ? A[s1] : B[s2]; //此时s1=d1，s2=d2，题目取中位数11，即较小的值A[s1] 43 //三目运算符，如果A[s1] < B[s2]表达式为真，取A[s1]，如果A[s1] > B[s2]表达式为假，取B[s2] 44} 45int main() 46{ 47 int A[] = { 11,13,15,17,19 }; 48 int B[] = { 2,4,6,8,20 }; 49 int mid = MidSearch(A, B, 5); 50 printf("mid=%d\n", mid); 51}
mid=11
练习
读取10个元素 87 7 60 80 59 34 86 99 21 3，然后建立二叉查找树，中序遍历输出3 7 21 34 59 60 80 86 87 99，针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出2。
1#include <stdio.h> 2#include <stdlib.h> 3 4typedef int keytype; 5typedef struct Node 6{ 7 keytype data; 8 struct Node* lchild; 9 struct Node* rchild; 10}BSNode,*BiTree; 11 12//插入 13void BSTreeInsert(BiTree& T, keytype x) 14{ 15 BiTree NewNode = (BiTree)calloc(1, sizeof(BSNode)); 16 NewNode->data = x; 17 if (NULL == T) 18 { 19 T = NewNode; 20 return; 21 } 22 BiTree p = T; //p从根开始寻找新节点存放位置 23 BiTree parent = NULL; 24 while (p) 25 { 26 parent = p; 27 if (x < p->data) 28 { 29 p = p->lchild; 30 } 31 else 32 { 33 p = p->rchild; 34 } 35 //不考虑查找树内元素相等的情况 36 } 37 //新节点放入位置 38 if (x < parent->data) 39 { 40 parent->lchild = NewNode; 41 } 42 else 43 { 44 parent->rchild = NewNode; 45 } 46} 47 48//创建二叉查找树 49void BSTree(BiTree& T, keytype* str, int len) 50{ 51 int i = 0; 52 for (i; i < len; i++) 53 { 54 BSTreeInsert(T, str[i]); 55 } 56} 57 58//中序遍历 59void InOrder(BiTree T,int arr[10]) 60{ 61 static int i = 0; 62 if (NULL == T) 63 { 64 return; 65 } 66 InOrder(T->lchild,arr); 67 printf("%3d", T->data); 68 arr[i] = T->data; 69 i++; 70 InOrder(T->rchild,arr); 71} 72 73//折半查找 74int binary_search(int* arr, keytype x) 75{ 76 int low = 0, high = 9, mid = (low + high) / 2; 77 while (low <= high) 78 { 79 if (x < arr[mid]) 80 { 81 high = mid - 1; 82 } 83 else if (x > arr[mid]) 84 { 85 low = mid + 1; 86 } 87 else 88 { 89 return mid; 90 } 91 mid = (low + high) / 2; 92 } 93} 94 95int main() 96{ 97 int str[10] = { 87,7,60,80,59,34,86,99,21,3 }; 98 BiTree T = NULL; 99 BSTree(T, str, 10); 100 int arr[10] = {}; 101 InOrder(T,arr); 102 printf("\n"); 103 int a = 21; 104 int ret = binary_search(arr,a); 105 if (ret) 106 { 107 printf("%d", ret); 108 } 109 else 110 { 111 printf("没有找到"); 112 } 113 return 0; 114}
::: warning 易错点： 1.中序遍历排好序后，将新的顺序输出并放进数组中，需要先打印出来，然后再放入数组。 2.放入数组时不使用新的函数，使用static变量。 原因：中序遍历执行递归时，打印数组时会打印多份数组同一位置数据，使用函数传出去时，也会对数组同一位置多次赋值。 :::