顺序查找

学习时间2022.12.11

顺序查找

基本概念

• 定义：在一个已知无序（或有序）的队列中找出与给定的关键字相同的数的具体位置。 其原理是让关键字与队列中的数从开始一个一个地往后逐个比较，直到找到与给定的关键字相同的数。

知识点补充

• 生成随机数

  #include <time.h>
  time_t t;
  //初始化随机数发生器
  srand(time(&t));
  //输出0-100的随机数赋给num
  num = rand() % 100;
  

  • 函数声明：void srand(unsigned int seed)
  • 参数：seed -- 这是一个整型值，用于伪随机数生成算法播种。

代码实现

数据结构

typedef int ElemType;

typedef struct {
	ElemType* elem;//整型指针
	int TableLen;//动态数组元素个数
}SSTable;

函数声明

• 初始化数组
  • 哨兵作用：在查找方向的尽头设置哨兵元素，免去了查找过程中每次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但是总数据较多时，效率提高很明显，是非常好的编程技巧。

    void ST_init(SSTable &ST, int len){
        ST.TableLen = len + 1;//多申请一个空间，用作哨兵。工作中一般不使用
        //ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
        ST.elem = (ElemType*)calloc(ST.TableLen, sizeof(ElemType));
        //初始化随机数发生器
        srand(time(NULL));
        //输出0-100的ST.TableLen个随机数
        for (int i = 0; i < ST.TableLen; i++)
        {
            ST.elem[i] = rand() % 100;
        }
    }
  

• 查找给定元素值的位置

    int Search_Seq(SSTable ST, ElemType key) {
        //0处是哨兵，如果i返回值为0，则说明没有找到该key
        ST.elem[0] = key;
        int i;
        for (i = ST.TableLen - 1; ST.elem[i] != key; i--);
        return i;
    }
  

• 输出数组

    void ST_print(SSTable ST) {
        for (int i = 0; i < ST.TableLen; i++) {
            printf("%3d", ST.elem[i]);
        }
        printf("\n");
    }
  

main函数

int main(){
	SSTable ST;
	//pos用于存储顺序查找找到的元素位置
	int pos;
	ElemType key;
	ST_init(ST, 10);
	ST_print(ST);
	printf("请输入需要查找的元素key值：");
	scanf("%d", &key);
	pos = Search_Seq(ST, key);
	if (pos) {
		printf("您所查找的元素%d的位置为：第%d位\n", key, pos);
	}
	else {
		printf("您所查找的元素不存在\n");
	}
}