【问题描述】
静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。对静态查找表可以用顺序表或线性链表进行表示，也可组织成有序的顺序表，或者是索引顺序表，相应的查找方法可采用顺序查找方法、折半查找方法和索引顺序查找的方法。设计一个有关静态查找表的建立、查找等基本操作的演示程序，并计算和分析查找成功时的平均查找长度。
【数据描述】
静态查找表的抽象数据类型定义：
ADT StaticSearchTable{
数据对象D: D是由具有相同特性的数据元素的集合。
数据关系R：数据元素同属一个集合。
基本操作P：
Create(&ST,n) 构造一个含有n个元素的静态查找表ST。
Destroy(&ST) 将一个已经存在的静态查找表ST销毁；
Search(ST,key) 在表ST中查找是否存在其关键字和给定的key相等的数据元素
Traverse(ST,visit()) 按某种次序对ST的每个元素进行访问
}ADT StaticSearchTable;
在本章以后各节的讨论中，涉及的关键字类型和数据元素类型统一约定如下；
typedef int KeyType; //定义关键字类型
typedef struct{ // 定义元素类型
KeyType key;
……
} ElemType;
【算法描述】
//静态查找表的顺序存储结构
typedef struct{
ElemType *elem;
int length;
}SSTable;
Status Create(SSTable &ST){
//建立一个含有n个元素的顺序表，表的长度n由键盘输入
Scanf(n);
if (!(ST.elem=(ElemType*) malloc( (n+1)*sizeof(ElemType))) return OVERFLOW;
For (i=1;i<=n;i++) scanf(ST.elem[i].key);//输入数据元素的关键字和其他数据项
ST.length=n;
Return OK;
}//Create
int Search(Sstable ST,KeyType key){
//在顺序表中查找其关键字等于key 的数据元素，若查找成功，返回该元素在表中的//位置，否则返回0；
ST.elem[0].key=key;//设置监视哨
For (i=ST.length;!EQ(ST.elem[i].key,key);i--);
Return i;
}
【C源程序】
#include <stdlib.h>
#include <stdio.h>
typedef int KeyType;
typedef struct {
KeyType key;
}ElemType;
typedef struct{
ElemType *elem;
int length;
}SSTable;
int create(SSTable * ST){
int i,n;
printf("\nPlease input the length of table:");
scanf("%d",&n);
ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
if (!ST->elem) return 0;
printf("\nPlease input %d data:",n);
for (i=1;i<=n;i++) scanf("%d",&(ST->elem[i].key));
ST->length=n;
return 1;
}
int search(SSTable ST,KeyType key,int *time){
/*在顺序表中查找其关键字等于key的数据元素，若找到，则函数值为该元素在表中的位置，否则为0 ，指针变量time记录所需和关键字进行比较的次数。 */
int i;
ST.elem[0].key=key;
*time=1;
for (i=ST.length;ST.elem[i].key!=key;i--,++*time);
return i;
}
main(){
SSTable ST;
KeyType key;
int i,time;
char ch;
if (create(&ST)){ /*创建成功*/
printf("\nCreate is complete");
/*可重复查询， */
do {
printf("\nInput the key you want to search:");
scanf("%d",&key);
i=search(ST,key,&time);
if (i!=0) /*查找成功，输出所在位置及key与元素关键字的比较次数*/
{printf("\nSuccess,the position is %d ",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失败，输出key与元素关键字的比较次数*/
{ printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContinue(y/n):\n");/*是否继续，y或Y继续查询，其它退出查询*/
ch=getch();
}
while (ch=='y' || ch=='Y') ;
}
else /*表ST建立失败，输出内存溢出的信息*/
printf("\noverflow");
}
【测试数据】
1.建立顺序表，根据运行提示输入表的长度和这些数据，建立一个顺序表,并可进行多次查找，注意观察运行结果。
Please input the length of table:10
Please input 10 data:2 1 9 8 10 21 90 43 11 32
Input the key you want to search: 90
Success,the position is 7
The time of compare is 4
Continue(y/n):y
Input the key you want to search: 7
Unsuccess
The time of compare is 11
continue(y/n):n
|