顺序查找C/C++代码实现

素颜马尾好姑娘i 2023-02-21 02:27 22阅读 0赞

## 设置哨兵的顺序查找： ##

顺序查找(SequentialSearch)的查找过程为：从表的一端开始，依次将记录的关键字和给定 值进行比较，若某个记录的关键字和给定值相等，则查找成功。

如果不设置哨兵在每次都需要比较是否查找完成，而在0号位设置哨兵可以免去查找过程中每一 步都要检测整个表是否查找完毕，大幅度提高算法效率。

## 算法效率： ##

时间复杂度为O(n)  
既适用于顺序结构， 也适用链式结构，但当n很大时， 不宜采用顺序查找。

## 代码如下： ##

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int KeyType;
    typedef int InfoType;
    
    //线性表的顺序存储
    typedef struct
    {
        
    	KeyType key;
    	InfoType otherinfo;
    }ElemType;
    typedef struct
    {
        
    	ElemType *R;		//储存空间基地址
    	int length;			//当前长度
    }SSTable;
    
    
    //顺序查找
    //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0 
    int  Search_Seq(SSTable ST, KeyType key)
    {
        
    	int i;
    	ST.R[0].key = key;				//哨兵
    	for (i = ST.length; ST.R[i].key != key; i--);		//从后往前找
    
    	return i;
    }
    
    
    int main()
    {
        
    	SSTable ST;
    	ST.R = (ElemType *)malloc(sizeof(ElemType));
    
    	//输入
    	ST.R[1].key = 13;
    	ST.R[2].key = 7;
    	ST.R[3].key = 3;
    	ST.R[4].key = 9;
    	ST.R[5].key = 20;
    	ST.R[6].key = 4;
    	ST.length = 6;
    
    	KeyType key;
    	printf("请输入要查找的记录：");
    	scanf("%d", &key);
    	int i = Search_Seq(ST, key);
    	printf("查找记录在表中的位置是（从1开始，0为未找到）：%d\n", i);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628134933909.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70