实验目的：深入理解静态查找表的建立过程，以及顺序排序和折半排序算法的基本思想
实验内容：
1．建立静态查找表
2．实现顺序排序函数并完成功能测试
3．实现折半排序函数并完成功能测试
步骤1：包含必要的函数库，对结构体LNode中的常量和数据类型进行具体定义
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 //将关键字的类型实例化为整型
5 typedef int KeyType;
6 //设置静态表的最大长度
7 #define MAXSIZE 20步骤2：定义结构体SSElement
1 /*利用结构体SSElement实现静态表中的每个元素*/
2 typedef struct{
3 KeyType key;
4 //可进一步地增加定义其他的域
5 }SSElement;步骤3：定义结构体SSTable
1 /*利用结构体SSTable实现静态查找表*/
2
3 typedef struct{
4
5 SSElement *elem;
6
7 int length;//静态查找表的长度
8
9 int tablesize;//静态查找表的最大长度
10
11 }SSTable;提示：结构体SSTable的定义方式与实验1中的结构体SqList类似
步骤4：定义函数InitSSTable()，用于对静态查找表进行初始化。
提示1：该函数利用malloc()函数为结构体的elem数组分配内存空间。
提示2：elem数组的0号单元用于保存哨兵元素，1至MAXSIZE号单元用于保存静态查找表中的数据元素。
1 /*函数InitSSTable()用于初始化静态表*/
2
3 int InitSSTable(SSTable *ST)
4
5 {
6
7 (*ST).elem=(SSElement *)malloc((MAXSIZE+1)*sizeof(SSElement));
8
9 if (!(*ST).elem) exit(-1);
10
11 (*ST).length=0;
12
13 (*ST).tablesize=MAXSIZE;
14
15 /*创建哨兵元素，并将其保存在数组单元(*ST).elem[0]中，将该元素的关键字初值设置为0*/
16
17 SSElement se;
18
19 se.key=0;
20
21 (*ST).elem[0]=se;
22
23 return 1;
24
25 }步骤5：定义函数SSTableInsert()，用于向静态查找表中添加数据元素
提示：与实验1中的函数ListInsert_Sq()类似，最大的区别是第i个元素保存在elem数组的i号单元而非i-1单元。
1 /*函数SSTableInsert()用于向静态表中添加元素*/
2 int SSTableInsert(SSTable *ST,int i,
3 SSElement se)
4 {
5 SSElement *p,*q;
6 if (i<1||i>(*ST).tablesize)
7 return 0;
8 if((*ST).length>=(*ST).tablesize)
9 {
10 printf("静态查找表已满！");
11 return 0;
12 }
13 else
14 {
15 q=&((*ST).elem[i]);
16 for(p=&((*ST).elem[(*ST).length]);p>=q;--p)
17 *(p+1)=*p;
18 *q=se;
19 ++(*ST).length;
20 return 1;
21 }
22 }步骤6：定义函数GetSSElem()，该函数的作用是对前两个函数InitSSTable()、SSTableInsert()的功能进行测试。
提示：与实验1中的函数GetElem_Sq()类似，最大的区别是第i个元素保存在elem数组的i号单元而非i-1单元。
1 /*函数GetSSElem()用于返回静态查找表指定位置上的元素*/
2 int GetSSElem(SSTable ST,int i,SSElement *se)
3 {
4 if(i<1||i>ST.length)
5 return -1;
6 *se=ST.elem[i];
7 return 1;
8 }步骤7：在主函数main()中对前两个函数InitSSTable()、SSTableInsert()的功能进行测试。
测试代码：
1 int flag;//该标志表示函数执行是否成功
2
3 int i;//控制for循环的变量
4
5 SSElement se;
6
7 SSTable A;
8
9 InitSSTable(&A);//初始化静态查找表
10
11 /*向静态查找表中插入元素10,20,30,40,56,60,70,80*/
12 se.key=10;
13 SSTableInsert(&A,1,se);
14
15 …
16
17 se.key=80;
18 SSTableInsert(&A,8,se);
19
20 //测试插入的元素是否正确
21 printf("静态查找表中的元素为：\n");
22 for(i=1;i<=A.length;i++)
23 {
24 flag=GetSSElem(A,i,&se);
25 if(flag==1)
26 printf("%4d",se.key);
27 }
28 printf("\n");步骤8：定义函数SSTableSearch_Seq()，实现顺序查找功能
提示：可以直接对课本216页的算法9.1进行改造，但是需要在for循环执行空操作，否则会在for循环过程中不断向外层返回位置i。
1 /*函数SSTableSearch_Seq()用于实现静态查找*/
2 int SSTableSearch_Seq(SSTable ST,KeyType key);步骤9：对函数SSTableSearch_Seq()进行测试
测试代码：
1 //在主函数中追加定义如下变量
2 int pos;//保存匹配元素在静态查找表中的位置
3 int key;//保存待查找的关键字
4 //测试顺序查找函数SSTableSearch_Seq()
5 printf("函数SSTableSearch_Seq > 输入待查找的关键字:");
6 scanf("%d",&key);
7 pos=SSTableSearch_Seq(A,key);
8 if (pos==0) printf("函数SSTableSearch_Seq > 查找失败!\n");
9 else printf("函数SSTableSearch_Seq > 匹配元素在静态查找表中的位置为：%4d\n",pos);步骤10：定义函数SSTableSearch_Bin()，实现顺序查找功能
提示：可以直接对课本220页的算法9.2进行改造
1 /*函数SSTableSearch_Bin()用于实现折半查找*/
2 int SSTableSearch_Bin(SSTable ST,KeyType key);步骤11：对函数SSTableSearch_Bin()进行测试
1 //测试折半查找函数SSTableSearch_Bin()
2 printf("函数SSTableSearch_Bin > 输入待查找的关键字:");
3 scanf("%d",&key);
4 pos=SSTableSearch_Bin(A,key);
5 if (pos==0) printf("函数SSTableSearch_Bin > 查找失败!");
6 else printf("函数SSTableSearch_Bin > 匹配元素在静态查找表中的位置为：%4d\n",pos);思考题
1．如何编程实现9.1.4节的索引顺序查找。
1 /*函数SSTableSearch_Seq()用于实现静态查找*/
2 int SSTableSearch_Seq(SSTable ST,KeyType key)
3 {
4 int i;
5 ST.elem[0].key=key;
6 for(i=ST.length;ST.elem[i].key!=key;--i)
7 {}//此处需要执行空操作，否则会在for循环过程中不断向外层返回位置i
8 /*
9 也可以采用书上的方式在for语句之后加分号，即
10 for(i=ST.length;ST.elem[i].key!=key;--i);
11 */
12 return i; //查找失败时返回0
13 }
14 /*函数SSTableSearch_Bin()用于实现折半查找*/
15 int SSTableSearch_Bin(SSTable ST,KeyType key)
16 {
17 int low,high,mid;
18 low=1;
19 high=ST.length;
20 while(low<=high)
21 {
22 mid=(low+high)/2;
23 if (key==ST.elem[mid].key) return mid;
24 else if(key<ST.elem[mid].key) high=mid-1;
25 else low=mid+1;
26 }
27 return 0; //查找失败时返回0
28 }