为什么找别人做网站,兰州装修公司口碑排名推荐,个人怎么创建微信公众号,微信app制作公司查找
关于顺序查找和折半查找#xff0c;可点击此处进入旧金山大学提供的动画演示网站。
顺序查找
顺序查找又称线性查找。它对于顺序表和链表都是适用的。对于顺序表#xff0c;可通过数组下标递增来顺序扫描每个元素#xff1b;对于链表#xff0c;则通过指针next来…查找
关于顺序查找和折半查找可点击此处进入旧金山大学提供的动画演示网站。
顺序查找
顺序查找又称线性查找。它对于顺序表和链表都是适用的。对于顺序表可通过数组下标递增来顺序扫描每个元素对于链表则通过指针next来依次扫描每个元素。
本次顺序表用指针也就是申请一个堆空间使用方式和数组还是一致。
#include stdio.h
#include stdlib.h
#include time.htypedef 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.hvoid 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.htypedef 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;
}
