顺序查找算法
实现思想:静态查找表用顺序存储结构表示时,顺序查找的查找过程为:从表中的最后一个数据元素开始,逐个同记录的关键字做比较,如果匹配成功,则查找成功;反之,如果直到表中第一个关键字查找完也没有成功匹配,则查找失败。
应用场景:顺序查找一般理解为线性查找,一般针对数组或是链表,针对线性的数据存储结构实现,是最简单的查找算法。
下面通过自己建立一个顺序表来进行数据查找。构建完整程序并进行代码逻辑分析。
typedef struct {
keyType key;//查找表中每个数据元素的值,注意KeyType可以是自定义数据类型或是普通数据类型
//如果需要,还可以添加其他属性
}ElemType;
这个结构体主要用来存储数据,当我们创建一个需要存储数值的顺序表的时候就循环向这个结构中的keyType类型存储数据
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));
}
}
上面的代码会根据你传入的数组长度参数,进行数据表的创建
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;
}
这是核心的查找接口,根据程序我们可以分析出会从数据表中最后一个数据依次往前面进行查询。
下面是整体程序
#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));
}
}
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);
printf("请输入要查找数据的关键字:\n");
int key;
scanf("%d",&key);
int location = search_seq(&st,key);
if(location == 0)
{
printf("查找失败\n");
}
else
{
printf("数据在查找表中的位置为:%d\n",location);
}
return 0;
}
得出结果:
输入表中的数据元素:
11 22 33 44 55 66
请输入要查找数据的关键字:
66