一、静态查找表
（1）顺序表的查找
1）顺序表查找的结构
typedef struct{
ElemType * elem; //存储空间基址
int length; //表长
}SSTable;
顺序查找的过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较。（也就是说，在查找到时候从最后一个元素开始查找，在这个表中位置为0的位置空着，留给你要查找的元素）
在顺序表的查找中，需要有一个“哨兵”负责担任监视哨的任务。
ST.elem[0].key = key;
//判断查找的元素（也就是位置0放的位置）是不是和值相等2）查找的性能分析
查找的操作其实很简单，就是将你要找的值与表中元素一一比较，若不符合，则向前查找，直到找到或者表空为止。
因此顺序查找表的长度为：
【其中i = 1】
可以看做是：
（2）有序表的查找
有序表的查找，可以从小到大，或者从大到小。我们一般默认是从小到大查找。
1）折半查找
折半查找，查找方式有三个指针：low,high和mid。其中mid指示区间的中间位置，即mid=[(high+low)/2]
1.若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid；
2.若key与中间元素不相等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。（至 于是前半部分还是后半部分要看key与mid所指向元素的大小关系）
a.在查找表升序排列的情况下，若给定值key大于中间元素则所查找的元素只可能在后半部分。 此时让low=mid+1；
b.若给定值key小于中间元素则所查找的元素只可能在前半部分。此时让high=mid-1；
//折半查找
int Search Bin(SSTable L,ElemType key){
low = 1,high = ST.length;
while(low <= high){
mid=(low+high)/2; //取中间位置
if(L.elem[mid]==key)
return mid; //查找成功返回所在的位置
else if(L.elem[mid]>key){ //从前部分查找
high=mid-1;
}
else
low=mid+1; //从后部分查找
}
return 0; //失败返回0
}
二、索引顺序表的查找
索引顺序表也就是分块查找，许多情况下可能遇到这样的表：整个表中未必有序，但若划分成若干块后，每一块中的所有元素均大于或小于其后面的所有元素，称这种特性为分块有序，因此可以为该顺序表建立一个索引表，索引表中为每一块设置设置一索引项，每一索引项包括两部分：该块的起始地址和该块中最大(或最小)关键字的值（或是所限定的最大（小）关键字）。将这些索引项按顺序排列成一有序表，即为索引表。
三、二叉排序树和平衡二叉树
二叉树定义：
二叉排序树（又名二叉查找树）或者是一棵空树；或者是具有以下性质的二叉树：
1）若它的左子树不为空，则左子树上所有结点的值均小于它根节点的值
2）若它的右子树不为空，则右子树上所有结点的值均大于它根节点的值
3）它的左右子树也分别为二叉排序树
简单来说就是：左比根小，右比根大
1）二叉排序树的构造过程
首先我们使用画图的方式来描绘一下二叉排序树的插入过程，如图，我们要在一棵空的二叉排序树中插入一个数组6,2,7,4,0,3,1,5，如图所示：
首先我们插入第一个元素6，此时二叉排序树中还没有任何一个节点，因此我们应该新建一个节点，并将6存储进去，并将6认定为根节点，如图所示：
之后我们插入第二个元素2，此时二叉排序树已经不是一个空树了，因此我们需要首先找到适合它的位置，我们将2和6进行对比，判断谁大谁小，我们发现2更小，因此2应该被插入在6的左子树中，之后我们将2和根节点6的左子树进行对比，发现6的左子树是空的，因此这时我们将2存放在6的左子树根节点位置，如图所示：
之后是元素7,7显然大于6，因此我们要将7放在6的右子树中，经过探寻我们发现6的右子树根节点也是空的，因此我们需要将7放在右子树的根节点上，如图所示：
之后是元素4，我们首先将4和6对比，发现4是小于6的，因此4应该位于6的左子树上，之后我们将4和6的左子树根节点进行对比，发现4是大于2的，因此4应该被放在2的右子树上，而2的右子树为空，因此4直接被放置在2的右子树根节点上，如图所示：
之后是元素0，首先我们将0和元素6进行对比，发现0是小于元素6的，因此应该被放置在6的左子树上，之后我们将0和6的左子树根节点进行对比，发现其小于2，因此0应该被放置在2的左子树上，这时我们发现0是小于2的，因此0应该被放置在2的左子树上，同时我们发现2的左子树为空，因此我们将0放置在2的左子树根节点上，如图所示：
之后是元素3，我们发现元素3是小于6的，因此3应该被放置在6的左子树上，而这时我们就开始研究6的左子树，3大于2，因此3应该被放置在2的右子树上，这时我们开始研究2的右子树，而3是小于2的右子树根节点4的，因此3应该放置在4的左子树上，我们发现4的左子树为空，因此我们将3放置在4的左子树根节点上，如图所示：
之后是元素1，首先我们将1和6进行对比，发现1是小于6的，因此1应该被放置在6的左子树上，而1又小于2，因此应该被放置在2的左子树上，而1又大于0，因此应该被放置在0的右子树上，0的右子树为空，因此1应该被放置在0的右子树根节点上，如图所示：
之后我们研究最后一个元素5,5小于根节点6，因此我们应该将5放置在6的左子树上，而5大于2，因此我们应该将5放置在2的右子树上，5大于4，因此5应该被放置在4的右子树上，4的右子树为空，因此我们将5放置在4的右子树根节点上，如图所示：
整个的过程都是从中序这个节点前驱替代
2）平衡二叉树
定义：
左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1
方法：
从一组数中选三个，由小到大排序，取中间为新根，小的放左边，大的放右边
调之前：有左边，将左调到右
有右边，将右调到左
比如：
将它调整一下：
四、哈希表
不想比较，直接用函数。
根据关键码值（Key Value）直接进行访问的数据结构。
哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。
哈希表的关键思想是使用哈希函数，将键 key 映射到对应表的某个区块中。我们可以将算法思想分为两个部分：
1.向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
2.在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。
构造方法
直接定址法
除留余数法
数字分析法
平方取中法
折叠法
处理冲突方法
开放定址法：
先开n个房间，利用线性放入，如果找x在下面写上比较次数
比如：依次插入9 11 23 19 54
用数字除以表长取余数即可文章来源：https://www.toymoban.com/news/detail-813079.html
文章来源地址https://www.toymoban.com/news/detail-813079.html
到了这里，关于数据结构第九章的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
