顺序查找的实现

发布时间：2023-05-23 12:52:08 所属栏目：语言来源：

导读：通过前面对静态查找表的介绍，静态查找表即为只做查找操作的查找表。

静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上大同小异。
本节以静态

通过前面对静态查找表的介绍，静态查找表即为只做查找操作的查找表。

静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上大同小异。
本节以静态查找表的顺序存储结构为例做详细的介绍。

顺序查找的实现
静态查找表用顺序存储结构表示时，顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。

顺序查找的具体实现代码为：
#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct {
keyType key;//查找表中每个数据元素的值
//如果需要，还可以添加其他属性
}ElemType;
typedef struct{
ElemType *elem;//存放查找表中数据元素的数组
int length;//记录查找表中数据的总数量
}SSTable;
//创建查找表
void Create(SSTable **st,int length){
(*st)=(SSTable*)malloc(sizeof(SSTable));
(*st)->length=length;
(*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
printf("输入表中的数据元素：\n");
//根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据
for (int i=1; i<=length; i++) {
scanf("%d",&((*st)->elem[i].key));
}
}
//查找表查找的功能函数，其中key为关键字
int Search_seq(SSTable *st,keyType key){
st->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用
int i=st->length;
//从查找表的最后一个数据元素依次遍历，一直遍历到数组下标为0
while (st->elem[i].key!=key) {
i--;
}
//如果 i=0，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置
return i;
}
int main() {
SSTable *st;
Create(&st, 6);
getchar();
printf("请输入查找数据的关键字：\n");
int key;
scanf("%d",&key);
int location=Search_seq(st, key);
if (location==0) {
printf("查找失败");
}else{
printf("数据在查找表中的位置为：%d",location);
}
return 0;
}
可运行代码中设置了一个固定长度为 6 的顺序表，例如在查找表为{1,2,3,4,5,6}找到关键字为 1 的数据元素的位置，则运行效果为：
输入表中的数据元素：
1 2 3 4 5 6

请输入查找数据的关键字：

在程序中初始化创建查找表时，由于是顺序存储，所以将所有的数据元素存储在数组中，但是把第一个位置留给了用户用于查找的关键字。例如，在顺序表{1,2,3,4,5,6}中查找数据元素值为 7 的元素，则添加后的顺序表为：

顺序表中的监视哨

顺序表的一端添加用户用于搜索的关键字，称作“监视哨”。

放置好监视哨之后，顺序表遍历从没有监视哨的一端依次进行，如果查找表中有用户需要的数据，则程序输出该位置；反之，程序会运行至监视哨，此时匹配成功，程序停止运行，但是结果是查找失败。

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!