数据结构顺序查找中对"哨兵"理解
定义了查找的数据表类型,首先了解下这张表的结构体。
typedef struct{
int* data
;
int length
;
}SSTable
;
这里建表的时候是长度是按照正常分配的但是第一个位置空出来给哨兵的。
typeof search_(SSTable ST
,int key
){
ST
.data
[0] = key
;
int i
= ST
.TableLen
;
while(ST
.data
[i
] != key
){
i
--;
}
return i
}
比如一个查找表长度为5元素分别为{ ,1,2,3,4,5},第一个位置空留出来给要查找的值 假设为6,那么第一个位置赋值为6. 从后往前遍历,没有哨兵的情况下正常是要控制循环次数。防止数组溢出。有个i<length的判断。有哨兵的情况下只需要判断相等的情况就好了。如果没有查找的值6,到最后一次的对比的时候一定是相等的。退出循环返回下表值即可。不需要控制数组的长度。