700字范文 > C语言静态查找表：顺序查找二分查找分块查找

C语言静态查找表：顺序查找二分查找分块查找

时间：2021-05-01 18:10:04

1 静态查找表

2 静态查找的三种方法

2.1 顺序查找

2.1.1 概念

2.1.2 分类

2.1.3 源代码示例

2.1.4 性能分析

2.2 二分查找

2.2.1 实现算法前提

2.2.2 实现思路（以升序为例）

2.2.3 源代码示例

2.2.4 性能分析

2.3 分块查找

2.3.1 概念

2.3.2 实现思路

2.3.3 特点

2.3.4 源代码示例

2.3.5 性能分析

3 三种算法性能比较

1 静态查找表

概念：静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。

2 静态查找的三种方法

2.1 顺序查找

2.1.1 概念

顺序查找又称静态查找，是最基本的查找方法之一。

2.1.2 分类

1.无监视哨：从表中一端开始，向另一端逐个将其关键码与待查找元素比较。若相等，则查找成功，返回给定值在表中存储位置；否则查找失败。

2.有监视哨：表中 0 位置存储待查找元素。从表尾向表头查找，若搜索到 0 位置，说明查找失败；否则查找成功。优点：查找过程中省略了每次查找的检测过程，直接返回元素下标，当 L.length >= 1000 时，与方法（1）相比进行一次查找所需平均时间几乎减少一半。

ps：监视哨也可设置在高下标处

2.1.3 源代码示例

2.1.4 性能分析

设表中有 n 个元素，给定值 x 与表中第 i 个元素相等，则定位元素 x 时，共查找 n - i + 1 次，即 Ci =n - i + 1。因此查找成功时，平均查找长度（Average search length）为：

设每个元素的查找概率相等，即

将代入可得：

2.2 二分查找

2.2.1 实现算法前提

要实现表的二分查找，必须使表有序（升序 / 降序）

2.2.2 实现思路（以升序为例）

取有序表中间元素为比较对象：

（1）若待查找元素 = 中间元素，则返回中间元素下标；

（2）若待查找元素 <中间元素，则在表左半部分查找；

（3）若待查找元素 > 中间元素，则在表右半部分查找

2.2.3 源代码示例

#include <stdio.h>#include <stdlib.h>#define MAXSIZE 100 // 表中最大元素个数typedef int ElemType; // 设置表中元素类型为整型typedef struct {ElemType data[MAXSIZE + 1]; // 下标0处存放监视哨，数组元素存储1~n单元int length;} SqList;void CreateSqList(SqList *L); // 创建表void ASCSort(SqList *L);// 对表进行升序排序int BinarySearch(SqList L, ElemType x); // 二分查找非递归算法int BinarySearch_Recursive(SqList L, int low, int high, ElemType x);// 二分查找递归算法int main(void){SqList L;int index;CreateSqList(&L);printf("元素总数为：%d\n", L.length);ASCSort(&L);index = BinarySearch(L, 3);if (index == 0)printf("查找失败！\n");elseprintf("查找成功，下标为：%d\n", index);index = BinarySearch_Recursive(L, 1, L.length, 8);if (index == 0)printf("查找失败！\n");elseprintf("查找成功，下标为：%d\n", index);return 0;}void CreateSqList(SqList *L) // 创建表{int i, n;printf("请输入元素个数：");scanf("%d", &n);while (n > MAXSIZE || n < 1) {printf("个数超出范围，重新输入：");scanf("%d", &n);}L->length = n;printf("请依次输入元素值：\n");for (i = 1; i <= L->length; i++)scanf("%d", &(L->data[i]));}void ASCSort(SqList *L) // 对表进行升序排序{int i, j, temp;for (i = 1; i <= L->length - 1; i++)for (j = i; j <= L->length; j++)if (L->data[i] > L->data[j]) {temp = L->data[i];L->data[i] = L->data[j];L->data[j] = temp;}printf("升序排序后：");for (i = 1; i <= L->length; i++)printf("%d, ", L->data[i]);printf("\n");}int BinarySearch(SqList L, ElemType x) // 二分查找非递归算法{int low, mid, high;low = 1;high = L.length;while (low <= high) {mid = (high + low) / 2;if (x == L.data[mid])return mid;else if (x < L.data[mid])high = mid - 1;else // (x > L.data[mid])low = mid + 1;}return 0;}int BinarySearch_Recursive(SqList L, int low, int high, ElemType x){int mid;if (low > high)return 0;else {mid = (high + low) / 2;if (x == L.data[mid])return mid;else if (x < L.data[mid])return BinarySearch_Recursive(L, low, mid - 1, x);else // (x > L.data[mid])return BinarySearch_Recursive(L, mid + 1, high, x);}}

2.2.4性能分析

查找图中任一元素的过程，即是从根节点到该元素的路径，比较次数 k 为该元素节点在树中的层次数。所以：

设每个元素的查找概率相等，即

，

2.3分块查找

2.3.1概念

分块查找又称索引顺序查找，是对顺序查找的一种改进。

2.3.2实现思路

将数据表分成若干块，然后为每块建立一个索引，将所有块组织起来建立一个索引表

（1）数据表：存储所有数据元素

（2）索引表(index_table)：表中每个索引有两个部分，关键码字段、指针字段

关键码字段：存储对应块中的最大元素

指针字段：存储对应块中起始元素位置

2.3.3特点

表中数据是分块有序的。即索引表中数据是有序的，数据表中数据不要求有序。

查找元素时，先根据索引表确定元素所在块数，然后再从数据表对应块中查找该元素。

2.3.4源代码示例

#include <stdio.h>#include <stdlib.h>#define MAXSIZE 100 // 表中最大元素个数#define BLOCKNUM 5 // 索引表中最大块数typedef int KeyType; // 设置索引表元素类型为整型typedef int DataType; // 设置记录的其他项为整型typedef struct // 数据表结构体{KeyType key; // 节点元素DataType data;// 节点的其他项} SqList[MAXSIZE + 1]; // 数据表0位置存储数据表的长度typedef struct // 索引表结构体{KeyType key; // 块的最大关键字int addr;// 块的起始地址} IndexTable[BLOCKNUM + 1]; // 索引表0位置存储数据表的长度void CreateSqList(SqList L, IndexTable id); // 创建表void TraverseSqList(SqList L, IndexTable id); // 遍历表int BlockSearch(SqList L, IndexTable id, KeyType x); // 查找块中元素值为x的元素int main(void){SqList L;IndexTable id;int index;CreateSqList(L, id);TraverseSqList(L, id);index = BlockSearch(L, id, -7);if (index == 0)printf("表中无此元素！\n");elseprintf("查找成功，元素下标为：%d\n", index);index = BlockSearch(L, id, 17);if (index == 0)printf("表中无此元素！\n");elseprintf("查找成功，元素下标为：%d\n", index);index = BlockSearch(L, id, 100);if (index == 0)printf("表中无此元素！\n");elseprintf("查找成功，元素下标为：%d\n", index);return 0;}void CreateSqList(SqList L, IndexTable id) // 创建表{int i, j, k, m, n;int elemnum, bnum; // 总元素个数；总块数int max = INT_MIN; // 块中最大元素printf("请输入元素个数( < 100)、块数( < 5 )：");scanf("%d%d", &elemnum, &bnum);while (elemnum < 1 || elemnum > MAXSIZE || bnum < 1 || bnum > BLOCKNUM ||bnum > elemnum) {printf("输入有误，重新输入：");scanf("%d%d", &elemnum, &bnum);}L[0].key = elemnum; // 数据表0位置存储数据表的长度id[0].key = bnum; // 索引表0位置存储索引表的长度n = elemnum / bnum; // 平均每块元素个数for (i = 1; i <= bnum - 1; i++) // 构造前 bnum - 1 块中的元素{printf("请输入块 %d 的 %d 个元素（最小元素不能小于 %d ）：", i, n, max);k = (i - 1) * n; // 第 i 块元素起始下标for (j = 1; j <= n; j++) {scanf("%d", &(L[k + j].key));if (max < L[k + j].key) // 获取第 i 块中最大元素max = L[k + j].key;}id[i].key = max;id[i].addr = k + 1;}k = (bnum - 1) * n;m = elemnum - k; // 最后一块元素个数printf("请输入块 %d 的 %d 个元素（最小元素不能小于 %d ）：", bnum, m, max);for (j = 1; j <= m; j++) // 构造最后一块中的元素{scanf("%d", &(L[k + j].key));if (max < L[k + j].key) // 获取最后一块中最大元素max = L[k + j].key;}id[i].key = max;id[i].addr = k + 1;}void TraverseSqList(SqList L, IndexTable id) // 遍历表{int i;printf("---------数据表信息---------\n");for (i = 1; i <= L[0].key; i++) // 遍历并输出表中元素printf("%d, ", L[i].key);printf("\n---------索引表信息---------");for (i = 1; i <= id[0].key; i++) // 遍历并输出索引表信息printf("\n%d, %d", id[i].key, id[i].addr);printf("\n----------------------------\n");}int BlockSearch(SqList L, IndexTable id, KeyType x) // 查找块中元素值为x的元素{int low1, high1, low2, high2, mid, i;low1 = 1;high1 = id[0].key; // 设置索引表二分查找上下区间while (low1 <= high1) // 查找元素所在块数{mid = (low1 + high1) / 2;if (x <= id[mid].key)high1 = mid - 1;elselow1 = mid + 1;}if (low1 <= id[0].key) // 若low1 > id[0].key，则关键子大于数据表中所有元素{low2 = id[low1].addr; // 元素所在块的最小下标if (low1 == id[0].key)high2 = L[0].key; // 元素所在块的最大下标elsehigh2 = id[low1 + 1].addr - 1;for (i = low2; i <= high2; i++) // 在指定块中查找元素并返回下标if (L[i].key == x)return i;}return 0; // 查找失败返回0}