顺序查找算法详解(包含C语言实现代码)

  • 内容
  • 评论
  • 相关

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

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

本节以静态查找表的顺序存储结构为例做详细的介绍。

顺序查找的实现

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

顺序查找的具体实现代码为:

#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
请输入查找数据的关键字:
2
数据在查找表中的位置为:2

本文标题:顺序查找算法详解(包含C语言实现代码)

本文地址:http://www.hosteonscn.com/5255.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注