写在前面
查找这一节，和我大二第一次学时不同的是，多了B树和B+树的相关理论，但理解起来还可以。对这部分并没有进行代码实现，觉得没有必要。
按照惯例，上一节地址：数据结构（5）—— 图
顺序查找和折半查找
注意点
顺序查找不用说了，暴力for循环就完了。折半查找的思想理解起来十分简单，每次选取中间的点，把一个有序序列分成两部分，然后分别对比，不断缩小范围直到找到或找不到。直接看代码吧。
代码
/*
* @Description: 顺序查找和折半查找
* @version: 1.0
* @Author: Liuge
* @Date: 2021-07-27 20:07:39
*/
#include<bits/stdc++.h>
typedef struct{
// 元素存储空间基址，0号留空当哨兵位，按实际长度分配
int *elem;
// 表的长度
int tableLen;
}SSTable;
// 顺序查找
int searchSeq(SSTable ST,int key){
ST.elem[0] = key;
int i=ST.tableLen;
// 加入一个count来计算比较次数
int count = 0;
for(;ST.elem[i] != key;--i,count++);
printf("顺序查找中比较了：%d 次
",count);
return i;
}
// 折半查找 升序的查找
int binarySearch(SSTable L,int key){
// 定义上下限
int low = 1;
int high = L.tableLen;
int mid;
// 同样定义一个count计算比较次数
int count = 0;
while(low <= high){
mid = (low + high) / 2;
if(L.elem[mid] == key){
count++;
printf("折半查找中比较了：%d 次
",count);
return mid;
}else if(L.elem[mid] > key){
count++;
high = mid -1;
}else{
count++;
low = mid + 1;
}
}
printf("折半查找中比较了：%d
",count);
return -1;
}
// 初始化
void initST(SSTable &ST,int length){
ST.tableLen = length;
ST.elem = (int *)malloc(sizeof(int) * (ST.tableLen) + 1);
printf("输入表中的数据元素：
");
for (int i=1; i<=length; i++) {
scanf("%d",&ST.elem[i]);
}
}
// 主函数测试
int main(){
SSTable ST;
initST(ST,5);
int index = searchSeq(ST,2);
if(index != 0){
printf("顺序查找成功！下标为：%d
",index);
}else{
printf("顺序查找失败！顺序表中不存在该元素！
");
}
int index2 = binarySearch(ST,2);
if(index2 != -1){
printf("折半查找成功！下标为：%d
",index2);
}else{
printf("折半查找失败！顺序表中不存在该元素！
");
}
}
哈希（散列）查找
注意点
与之前的查找算法不同的是，哈希查找首先需要构建一个哈希表，而在哈希表的构建过程中不可避免的会产生冲突，所以哈希表的核心是如何解决冲突。这里实现采用了最简单的一种方法：开放定址法里的线性探测法。这种方式是我们哈希查找最简单也是最常考的一种方式了，因此做了实现。所谓线性探测法，就是指如果这个区域发生了冲突，那就顺序往后看哪个地方为空就插入到哪里。非常好理解的思想，直接看代码实现。
代码
/*
* @Description: 哈希查找，用线性探测法避免冲突
* @version: 1.0
* @Author: Liuge
* @Date: 2021-07-30 20:27:39
*/
#include<bits/stdc++.h>
typedef struct {
// 存放关键值
int key;
// 存放所占位置
int id;
// 存放查找这个数据的查找次数
int num;
}Hash;
int getRand() {
// 设置随机数范围1-100
return rand() % 100 + 1;
}
// 创建Hash表
void createHash(Hash H[]) {
// 以系统时间为种子
srand((unsigned)time(NULL));
for (int i = 0; i < 19; i++){
// 全部初始化为-1
H[i].id = -1;
}
int temp,flag=1,count=0;
// Hash表储存14个数
for (int i = 1; i <= 14; i++) {
count = 0;
// 用随机数生成关键字值
temp = getRand();
printf("第%d个数：%d
",i,temp);
int k = temp % 14;
count++;
while (flag) {
if (H[k].id == -1)
{
H[k].id = i;
H[k].key = temp;
H[k].num = count;
break;
}
// 如果冲突,则通过线性探测法寻找下一个位置
else {
k = (k+1)%19;
count++;
}
}
}
}
int main() {
// 创建表长为19个元素的Hash表
Hash H[18];
createHash(H);
printf("*****线性探测法处理冲突*****
");
double sum=0;
for (int i = 0; i < 19; i++) {
if (H[i].id != -1) {
printf("%d ",H[i].key);
sum += H[i].num;
}
}
printf("
");
printf("插入时总比较次数：%0.0f
",sum);
printf("平均查找长度：%.2f
",sum / 14);
return 0;
}
总结
总的来说，这章内容并不算很多。最难的地方个人感觉就是B树和B+树那块了，二轮的时候好好做做。