顺序查找
顺序查找又称为线性查找，对线性表和链表都适用。 线性表可以通过数组下标递增来顺序扫描每个元素，链表可以通过next指针依次扫描每一个元素。
::: tip 指针实现顺序表时，顺序表中是指针时，在定义顺序表的结构体后，需要对顺序表初始化，初始化时为指针申请堆空间，堆空间的使用类似于数组，和数组形式的区别是可以动态控制数组的大小。 :::
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//指针实现顺序表
typedef int Elemtype;
//定义顺序表
typedef struct
{
Elemtype* elem; //指针，类型自定，申请堆空间的起始地址存入elem
int TableLen; //存储在动态数组中元素的个数
}SSTable;
void ST_Init(SSTable& ST, int len)
{
ST.TableLen = len + 1; //需要多申请一个位置，原因是0号位置存放“哨兵”
ST.elem = (Elemtype*)malloc(sizeof(Elemtype) * ST.TableLen); //指针elem指向的每个元素都是Elemtype类型的（int）
int i;
srand(time(NULL)); //随机数生成
for (i = 1; i < ST.TableLen; i++) //0号位置是哨兵，随机数从1号位置开始
{
ST.elem[i] = rand() % 100; //%100使得生成的随机数在0-99之间
}
}
//打印顺序表
void ST_Print(SSTable ST)
{
int i;
for (i = 1; i < ST.TableLen; i++)
{
printf("%3d", ST.elem[i]); //类似于数组访问，elem相当于数组名
}
printf("\n");
}
int search_seq(SSTable ST, Elemtype key)
{
ST.elem[0] = key; //key存在0号位置，作为哨兵，哨兵的存在可有可无，哨兵存在的意义是循环判断条件不用写i>=0
int i;
for (i = ST.TableLen - 1; ST.elem[i] != key; i--);
return i;
}
int main()
{
SSTable ST;
ST_Init(ST, 10);
ST_Print(ST); //打印顺序表中的元素（顺序表中的元素位置从1开始）
Elemtype key;
printf("请输入要查找的key值\n");
scanf("%d", &key);
int pos; //查找函数返回的下标位置
pos = search_seq(ST, key);
if (pos)
{
printf("找到了，位置为%d\n", pos);
}
else
{
printf("没有找到\n");
}
return 0;
}折半查找
::: 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类型强制转换成其它类型。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int Elemtype;
typedef struct
{
Elemtype* elem; //整型指针
int TableElem; //存储在动态数组中的元素个数
}SSTable;
//随机树表初始化，没有使用哨兵
void InitTable(SSTable& ST, int len)
{
ST.TableElem = len;
ST.elem = (Elemtype*)malloc(sizeof(Elemtype));
int i = 0;
srand(time(NULL));
for (i; i < ST.TableElem; i++)
{
ST.elem[i] = rand() % 100;
}
}
//打印随机数
void PrintTable(SSTable ST)
{
int i = 0;
for (i; i < ST.TableElem; i++)
{
printf("%3d", ST.elem[i]);
}
printf("\n");
}
//二分查找
int binary_search(SSTable ST, Elemtype key)
{
int low = 0, high = ST.TableElem - 1;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (key < ST.elem[mid])
{
high = mid - 1;
mid = (low + high) / 2;
}
else if (key > ST.elem[mid])
{
low = mid + 1;
mid = (low + high) / 2;
}
else
{
return mid;
}
}
return -1;
}
//函数名compare中存放着函数入口地址，是函数指针类型
int compare(const void* left, const void* right)
{
return *(int*)left - *(int*)right; //从小到大排序，(int*)表示强制类型转换，*表示解引用，通过地址找到指针指向的元素
//如果是升序，即left比right大，返回正值；如果是降序，left比right小，返回负值；left和right相等，返回0
//return *(int*)right-*(int*)left; //从大到小排序
}
int main() {
SSTable ST;
int x;
scanf("%d", &x);
InitTable(ST, x);
PrintTable(ST);
qsort(ST.elem, ST.TableElem, sizeof(Elemtype), compare);
PrintTable(ST);
Elemtype key;
printf("input search key\n");
scanf("%d", &key);
int ret = binary_search(ST, key);
if (ret != -1)
{
printf("search success,location %d\n", ret);
}
else {
printf("seasrch faild\n");
}
return 0;
}
二叉排序树
二叉排序树又称二叉查找树。 ::: tip 二叉排序树或者是一棵空树，或者是具有下列特点的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树； ::: 二叉排序树的最大查找次数是树的高度。 二叉排序树的遍历使用中序遍历（其他遍历方式无意义）。 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。相当于将二叉排序树踩扁，自左向右遍历，此时二叉排序树中序遍历后结果是有序（由小到大）的。 注：二叉排序树不考虑树中存放相等的元素。 ::: warning 二叉排序树删除节点时的特殊情况：如果要删除的节点是根节点或含有左右子树的节点，可以将该节点的左子树最右侧的节点值（左子树中的最大数据）或右子树最左侧的节点值（右子树中的最大数据）替换到删除结点的位置，替换后左子树最右侧的节点或右子树最左侧的节点被删除，由下面的左子树或右子树顶上，重新组成的二叉树仍满足二叉排序树的要求。 （拿到左子树的最右侧节点的方法是先拿到左子树的根节点，然后循环不断向下拿到右孩子，右子树的最左节点类似。) ::: 如果没有找到删除的节点时，删除函数中根节点T变为NULL，return 0，程序结束。
#include <stdio.h>
#include <stdlib.h>
typedef int Keytype;
//存放树的节点
typedef struct BSTNode
{
Keytype data;
struct BSTNode* lchild;
struct BSTNode* rchild;
}BSTNode, * BiTree;
//非递归方式创建二叉排序树
//二叉排序树的节点插入
int BST_Insert(BiTree& T, Keytype k)
{
BiTree TreeNew = (BiTree)calloc(1, sizeof(BSTNode)); //节点进入后创建节点存储新申请的空间
TreeNew->data = k;
if (NULL == T)
{
T = TreeNew; //树为空时，新节点TreeNew作为树根
return 0;
}
BiTree p = T, parent = NULL; //树根存在时使用p从树根开始查找新节点TreeNew应该存放的位置
while (p)
{
parent = p; //parent为p的父节点
//不考虑元素相等的情况
if (k < p->data)
{
p = p->lchild; //p置为NULL
}
else if (k > p->data)
{
p = p->rchild; //p置为NULL
}
else
{
return -1; //元素相等
}
}
//while循环结束后p找到应该存放的位置
//判断新节点TreeNew放在parent的位置
if (k < parent->data)
{
parent->lchild = TreeNew; //小于放在父节点左边
}
else {
parent->rchild = TreeNew; //大于放在父节点右边
}
return 0;
}
//二叉排序树的创建
void CreatBSTree(BiTree& T, Keytype* str, int len) //数组名是指针，len表示，数组元素个数
{
//每次向二叉排序树中放入一个节点
int i;
for (i = 0; i < len; i++)
{
BST_Insert(T, str[i]); //引用支持子函数传递
//函数CreatBSTree使用引用符号，实际引用操作发生在函数CreatBSTree中的BST_Insert内
}
}
//二叉排序树的中序遍历
void InOrder(BiTree T)
{
if (NULL != T)
{
InOrder(T->lchild);
printf("%3d", T->data);
InOrder(T->rchild);
}
}
//查找
BiTree BST_Search(BiTree T, Keytype k)
{
while (NULL != T && k != T->data)
{
if (k < T->data)
{
T = T->lchild;
}
else {
T = T->rchild;
}
}
return T;
}
//通过递归实现删除
void DeleteNode(BiTree& T, Keytype key)
{
if (NULL == T)
{
return;
}
if (key < T->data) //要删除的节点比当前树根节点小
{
DeleteNode(T->lchild, key); //在左子树上删除，执行递归
}
else if (key > T->data) //要删除的节点比当前树根节点大
{
DeleteNode(T->rchild, key); //在右子树上删除，执行递归
}
else //找到要删除的节点
{
if (NULL == T->lchild) //要删除的节点左子树为空时，用该节点的右子树顶替该节点
{
BiTree TempNode = T; //使用临时指针TempNode指向原来指针T指向的空间，指针T指向的空间是要删除的节点的空间
T = T->rchild; //该节点的右子树顶替该节点
free(TempNode); //释放删除节点的空间
}
else if (NULL == T->rchild) //要删除的节点右子树为空时，用该节点的左子树顶替该节点
{
BiTree TempNode = T; //使用临时指针TempNode指向原来指针T指向的空间，指针T指向的空间是要删除的节点的空间
T = T->lchild; //该节点的左子树顶替该节点
free(TempNode); //释放删除节点的空间
}
else //左右子树都不为空时
{
//拿左子树中的最右节点，左子树中的最右节点就是左子树中的最大数据
BiTree TempNode = T->lchild;
while (NULL != TempNode->rchild) //一直向下拿到右孩子为空时停止
{
TempNode = TempNode->rchild;
}
T->data = TempNode->data; //左子树中的最大数据替换掉要删除的值
DeleteNode(T->lchild, TempNode->data);
//删除左子树中的最右节点，不是改变后的根节点，传T->lchild，即要在左子树的上找到要删除的值，并将该节点删除
}
}
}
int main()
{
BiTree T = NULL; //指向树根的指针
Keytype str[7] = { 54,20,66,40,28,79,58 };
CreatBSTree(T, str, 7);
InOrder(T); //二叉排序树中序遍历后结果是由小到大的
printf("\n");
BiTree search, parent;
search = BST_Search(T, 66, parent); //找到后返回查找值的位置和父节点
if (search)
{
printf("find key %d\n", search->data);
}
else {
printf("not find\n");
}
DeleteNode(T, 66);
InOrder(T);
printf("\n");
return 0;
} 20 28 40 54 58 66 79
find key 66
20 28 40 54 58 79题目分析
当两个有序序列中的元素个数为奇数时，只能舍弃中位数之前、之后的元素，不能舍弃中位数。
当序列中元素个数为偶数时，如舍弃到最后序列中只剩下两个元素时，此时a<b，元素a前没有可以舍弃的元素时，可以舍弃自己。即小于时舍弃中位数之前的元素包括中位数，大于时舍弃中位数之后的元素。
#include <stdio.h>
int MidSearch(int* A, int* B, int x)
{
// art简写为s，代表首位数字，end简写为d，代表末位数字，m代表中位数
int s1 = 0, d1 = x - 1, m1, s2 = 0, d2 = x - 1, m2; //0和4表示数组下标，m1=(s1+d1)/2，m2=(s2+d2)/2
while (s1 != d1 || s2 != d2) //循环结束条件是两个数组最后各剩下一个元素，即s1=d1和s2=d2
{
m1 = (s1 + d1) / 2;
m2 = (s2 + d2) / 2;
if (A[m1] == B[m2])
{
return A[m1]; //或者B[m2]，满足条件1
}
else if(A[m1] < B[m2]) //满足条件2
{
if ((s1 + d1) % 2 == 0) //数组中元素个数为奇数（s1起始位置为0）
{
s1 = m1; //舍弃数组A中间点m1之前的元素保留中间点m1
d2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2
}
else //数组中元素个数为偶数，m1<m2
{
s1 = m1 + 1; //舍弃数组A中间点m1之前的元素包括中间点m1
d2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2
}
}
else //A[m1]>B[m2]) //满足条件3（与条件2对称）
{
if ((s1 + d1) % 2 == 0) //数组中元素个数为奇数（s1起始位置为0）
{
d1 = m1; //舍弃数组A中间点m1之后的元素保留中间点m1
s2 = m2; //舍弃数组B中间点m2之后的元素保留中间点m2
}
else //数组中元素个数为偶数，m1<m2
{
d1 = m1; //舍弃数组A中间点m1之后的元素保留中间点m1
s2 = m2 + 1; //舍弃数组B中间点m2之后的元素包括中间点m2
}
}
}
return A[s1] < B[s2] ? A[s1] : B[s2]; //此时s1=d1，s2=d2，题目取中位数11，即较小的值A[s1]
//三目运算符，如果A[s1] < B[s2]表达式为真，取A[s1]，如果A[s1] > B[s2]表达式为假，取B[s2]
}
int main()
{
int A[] = { 11,13,15,17,19 };
int B[] = { 2,4,6,8,20 };
int mid = MidSearch(A, B, 5);
printf("mid=%d\n", mid);
}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。
#include <stdio.h>
#include <stdlib.h>
typedef int keytype;
typedef struct Node
{
keytype data;
struct Node* lchild;
struct Node* rchild;
}BSNode,*BiTree;
//插入
void BSTreeInsert(BiTree& T, keytype x)
{
BiTree NewNode = (BiTree)calloc(1, sizeof(BSNode));
NewNode->data = x;
if (NULL == T)
{
T = NewNode;
return;
}
BiTree p = T; //p从根开始寻找新节点存放位置
BiTree parent = NULL;
while (p)
{
parent = p;
if (x < p->data)
{
p = p->lchild;
}
else
{
p = p->rchild;
}
//不考虑查找树内元素相等的情况
}
//新节点放入位置
if (x < parent->data)
{
parent->lchild = NewNode;
}
else
{
parent->rchild = NewNode;
}
}
//创建二叉查找树
void BSTree(BiTree& T, keytype* str, int len)
{
int i = 0;
for (i; i < len; i++)
{
BSTreeInsert(T, str[i]);
}
}
//中序遍历
void InOrder(BiTree T,int arr[10])
{
static int i = 0;
if (NULL == T)
{
return;
}
InOrder(T->lchild,arr);
printf("%3d", T->data);
arr[i] = T->data;
i++;
InOrder(T->rchild,arr);
}
//折半查找
int binary_search(int* arr, keytype x)
{
int low = 0, high = 9, mid = (low + high) / 2;
while (low <= high)
{
if (x < arr[mid])
{
high = mid - 1;
}
else if (x > arr[mid])
{
low = mid + 1;
}
else
{
return mid;
}
mid = (low + high) / 2;
}
}
int main()
{
int str[10] = { 87,7,60,80,59,34,86,99,21,3 };
BiTree T = NULL;
BSTree(T, str, 10);
int arr[10] = {};
InOrder(T,arr);
printf("\n");
int a = 21;
int ret = binary_search(arr,a);
if (ret)
{
printf("%d", ret);
}
else
{
printf("没有找到");
}
return 0;
}::: warning 易错点： 1.中序遍历排好序后，将新的顺序输出并放进数组中，需要先打印出来，然后再放入数组。 2.放入数组时不使用新的函数，使用static变量。 原因：中序遍历执行递归时，打印数组时会打印多份数组同一位置数据，使用函数传出去时，也会对数组同一位置多次赋值。 :::
