/* 静态查找表(Static Search Table)是指对表里面的内容只作查找而不修改表中任何项的查找。
* 其对应的查找就是动态查找表(Dynamic Search Table)，如在表中插入或者删除一个节点等等
* 静态查找表常见的有顺序表的查找（顺序查找），有序表的查找（折半查找），索引顺序表（分块查找）
*/
/** 顺序查找（实现很简单，但是这里有一个编程技巧值得一看）*/
#include<stdlib.h>
//定义存储结构
typedef struct {//表中每一个记录的类型，当然还可以在结构中添加其他的键值;
int key;
//......key1,key2,....
}elemType;
typedef struct{
elemType* init;
int length;
}SSTable;
//建立一个顺序表
int createSTable(SSTable* t, int len){
int i;
if(!(t->init = (elemType*) malloc(sizeof(elemType)*(len+1)))) // 0单元将在以后作为“监视哨”
return -1;
t->length = len+1; //长度依然为len+1;
printf("输入表的序列值：\n");
for(i = 1; i < t->length; ++i)
scanf("%d",&t->init[i].key);
return 1;
}
//在顺序表表中查找一个key
int SeqSearch(SSTable* t, int key)...{
int i; // 选择0当作监视哨，因为在数组里面0单元处理比较麻烦，不小心就出错 t->init[0].key = key; // 0单元被当作监视哨，用来判断表是否查找完毕（技巧） for(i = t->length-1; t->init[i].key != key; --i); //从表尾到表头逆序的查找，利用"监视哨" return i;//找到了则返回key的下表索引，否则"刚好"返回i（此时i为零表明没有找到),又是技巧。 
}
//简单测试；
int main(void){
int n,key;
SSTable t;
printf("输入要建立的表的长度：\n");
scanf("%d",&n);
createSTable(&t,n);
printf("输入要查找的键值：\n");
scanf("%d",&key);
printf("要查找的键值的下标是：%d\n",SeqSearch(&t,key));
system("pause");
return 0;
}
/** 总结：运用“监视哨”的编程技巧，当n>=1000的时候，可以有效地减少“判断表是否查找完毕“的平均比较次数；
** 仅仅多用了一个0单元的空间就把平均比较次数降低到不用监视哨的1/2,very good,boy **/
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
评论人