定义
顺序查找即线性查找,
对于顺序表可通过数组下标递增来遍历每个元素。
对于链表可通过
next
指针来遍历。
测试逻辑
使用随机数测试
通过结构体变量作堆空间的申请存数据和标记数据个数,生成随机数后进行查找。
结构体
动态数组,标记数据源位置和待查找的数据源长度
typedef int ElemType;
typedef struct {
ElemType *elem; //整型指针,用作堆空间申请的起始地址
int TableLen; //存储动态数组里的元素个数
}SSTable;
初始化
for
循环生成数据,达到要求的数据个数后停止。其中使用哨兵来达到减少查找函数中判断代码复杂度的效果。
//初始化随机数据
void ST_Init(SSTable &ST,int len){
//多申请一个位置作哨兵使用
ST.TableLen=len+1;
ST.elem=(ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
int i;
srand(time(NULL));
for (i=1;i<ST.TableLen;i++){
ST.elem[i]=rand()%100;
}
}
查找
哨兵存key,从后往前遍历,查不到返回0
int SearchTable(SSTable ST,ElemType key){
ST.elem[0]=key; //key在0号位置,使用后可在循环时少写一个i>=0
int i;
for(i=ST.TableLen-1;ST.elem[i]!=key;i--); //从后往前找,如果没找到则i是零(false)
return i;
}
评论