查找------顺序查找算法

用于查找的数据集合称为查找表，它们由同一类型的数据元素组成一个查找表，可以是一个数组或是链表的数据类型，那么静态查找，只能对一个查找表进行查找，而不能进行插入删除操作，查查表已经生成，不能改变，而动态查找表是对一个查找表进行操作查找的同时，需要动态的进行插入，删除操作。

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

顺序查找又称线性查找，主要用于线性表中进行查找，它的基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件，若查找到某个元素，关键字满足条件则查找成功返回元素在表中的位置，若已经到表的另一端，还未找到符合条件的元素则返回查找的失败的信息，为了提高查找速度，可在算法中设置哨兵----代检查知，他将放在查找方向的一端，免去了他的过程中，每一次比较完之后都要判断查找是否越界，从而节省了时间。

顺序查找的查找过程为：从表中的最后（前）一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败。

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

#include <stdio.h>
#include <stdlib.h>
#define keyType int
typedef struct {
    keyType key;//查找表中每个数据
    //如果需要，还可以添加其他属性
}ElemType;

typedef struct{
    ElemType *elem;//存放查找表中数据元素的数组
    int length;//记录查找表长度
}SSTable;

//查找表查找的功能函数，其中key为关键字
int Search_seq(SSTable *st,keyType key)
{
    st.elem[0].key=key;//将关键字作为一个数据元素存放到查找表的最后一个位置，起哨兵的作用
    int i ;
    //从查找表的第一个数据元素依次遍历，一直遍历到数组下标为st.length，即哨兵。
  
    for(i=0;i<=st.length;i++)
        if(st.elem[i].key!=key)
        return -1;
    //如果 i= -1，说明查找失败；反之，返回的是含有关键字key的数据元素在查找表中的位置
      else
      return i;
}

int main() {
    SSTable *st;
    Create(&st, 6);
    getchar();
    printf("请输入查找数据的关键字：
");
    int key;
    scanf("%d",&key);
    int l=Search_seq(st, key);
    if (l==0) {
        printf("查找失败");
    }else{
        printf("数据在查找表中的位置为：%d",location);
    }
    return 0;
}

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

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

图 1中哨兵的位置也可放在数据元素 5 的后面（这种情况下，整个查找的顺序应有逆向查找改为顺序查找）。

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