查找
关于顺序查找和折半查找，可点击此处进入旧金山大学提供的动画演示网站。
顺序查找
顺序查找又称线性查找。它对于顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，则通过指针next来依次扫描每个元素。
本次顺序表用指针，也就是申请一个堆空间，使用方式和数组还是一致。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
// 整型指针
ElemType *elem;
// 存储动态数组里面元素的个数
int table_len;
} SSTable;
/*
* 顺序表初始化
*/
void st_init(SSTable &ST, int len) {
// 多申请一个位置用来存哨兵
ST.table_len = len + 1;
ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);
// 筛子
srand(time(NULL));
// 随机数生成数据
for (int i = 1; i < ST.table_len; i++) {
// 生产的数字都在0-99中间
ST.elem[i] = rand() % 100;
}
}
/*
* 打印顺序表
*/
void st_print(SSTable ST) {
for (int i = 1; i< ST.table_len; i++) {
printf("%3d", ST.elem[i]);
}
printf("\n");
}
/*
* 查找元素位置
*/
int search_seq(SSTable ST, ElemType key) {
// 零号元素作为哨兵
// 遍历数组时 可以少写一个 i >= 0 的判断
ST.elem[0] = key;
int i;
// 从后往前找
// 如果找到 i刚好是对应的位置
for (i = ST.table_len - 1; ST.elem[i] != key; i--);
return i;
}
int main() {
SSTable ST;
// 一、顺序表初始化
st_init(ST, 10);
// 二、打印顺序表
st_print(ST);
// 存储元素
ElemType key;
printf("please input search key:\n");
scanf("%d", &key);
// 元素存储位置
int pos;
pos = search_seq(ST, key);
if (pos) {
printf("search elem success, location: %d\n", pos);
} else {
printf("search elem failed\n");
}
return 0;
}
折半查找
折半查找又称为二分查找，它仅适用于有序的顺序表。
折半查找的基本思想：首先将给定值key与表中间位置的元素比较。若相等，则查找成功，返回该元素的存储位置。若不等，则所需要查找的元素只能在中间元素以外的前半部分或后半部分（例如：在查找表升序排列时，若给定值key大于中间元素，则查找的元素只可能在后半部分），然后再缩小的范围内继续进行同样的查找，如此重复，直到找到为止。或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
针对顺序表有序，使用 qsort 来排序， qsort 的使用方法如下：
#include <stdlib.h>
void qsort(void *buf, size_t num, size_t size, int (*compare)(const void*, const void*));
- buf：要排序数组的起始地址，也可以是指针，申请了一块连续的堆空间。
- num：数组中元素的个数。
- size：数组中每个元素所占用的空间大小。
- compare：比较规则，需要我们传递一个函数名，这个函数由我们自己编写，返回值必须是 int 类型，形参是两个 void 类型指针，这个函数我们编写，但是由qsort内部调用，相当于我们传递一种行为给qsort。
折半查找不需要用到哨兵，因此不要受上一节顺序查找的影响，代码实战流程是：
- 我们初始化顺序表，随机10个元素。
- 使用 qsort 进行排序，排序完毕后，打印。
- 输入要查找的元素值，存入变量 key 中。
- 通过二分查找查找对应 key 值，找到则输入在顺序表中的位置，没找到输出未找到。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
// 整型指针
ElemType *elem;
// 存储动态数组里面元素的个数
int table_len;
} SSTable;
/*
* 顺序表初始化
*/
void st_init(SSTable &ST, int len) {
// 折半查找不使用0号位置作为哨兵
ST.table_len = len;
ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);
// 筛子
srand(time(NULL));
// 随机数生成数据
for (int i = 0; i < ST.table_len; i++) {
// 生产的数字都在0-99中间
ST.elem[i] = rand() % 100;
}
}
/*
* 打印顺序表
*/
void st_print(SSTable ST) {
for (int i = 0; i < ST.table_len; i++) {
printf("%3d", ST.elem[i]);
}
printf("\n");
}
/*
* 比较两个值的大小
*/
int compare(const void *left, const void *right) {
// 从大到小排序
// return *(ElemType *)right - *(ElemType *)left;
// 从小到大排序
return *(ElemType *)left - *(ElemType *)right;
}
/*
* 二分查找
*/
int binary_search(SSTable L, ElemType key) {
int low = 0, high = L.table_len, mid;
while (low <= high) {
mid = (low + high) / 2;
if (L.elem[mid] == key) {
// 找到了
return mid;
} else if (L.elem[mid] > key) {
high = mid - 1;
} else if (L.elem[mid] < key) {
low = mid + 1;
}
}
// 没有找到 不返回0是因为元素可能会在0号位置
return -1;
}
int main() {
SSTable ST;
// 一、顺序表初始化
st_init(ST, 10);
// 二、打印顺序表
st_print(ST);
// 三、排序
qsort(ST.elem, ST.table_len, sizeof(ElemType), compare);
st_print(ST);
// 存储元素
ElemType key;
printf("please input search key:\n");
scanf("%d", &key);
// 元素存储位置
int pos;
pos = binary_search(ST, key);
if (-1 != pos) {
printf("find success, pos = %d\n", pos);
} else {
printf("find failed\n");
}
return 0;
}
