实验目的
使用C语言实现静态查找表中的顺序查找和折半查找，并分析时间长短。
Search.h文件
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#define OK 1 #define ERROR -1 #include <stdio.h> #include<stdlib.h> #include<time.h> #define MAXSIZE 100 typedef int KeyType; typedef int ElemType; typedef struct{ ElemType data[10]; KeyType key; }Node; typedef struct{ Node elem[MAXSIZE]; int length; }SSTable; int CreateTable(SSTable &ST,int n); void OutputTable(SSTable ST); int Search_Seq(SSTable ST,KeyType key); int Search_Bin(SSTable ST,KeyType key); |
主要函数：
① 顺序表的创建
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int CreateTable(SSTable &ST,int n) { int i; ST.length=n; for(i=1;i<=n;i++) { printf("输入关键字："); scanf("%d",&ST.elem[i].key); printf("输入值："); scanf("%s",&ST.elem[i].data); } return OK; } |
②.顺序表的输出
|
1 2 3 4 5 6 7 8 9 10 |
void OutputTable(SSTable ST) { int i; printf("关键字: "); for(i=1;i<=ST.length;i++) printf("%6d",ST.elem[i].key); printf("\n值 : "); for(i=1;i<=ST.length;i++) printf(" %s ",ST.elem[i].data); } |
③顺序查找
|
1 2 3 4 5 6 7 |
int Search_Seq(SSTable ST,KeyType key) { ST.elem[0].key=key; int i=ST.length; while(ST.elem[i].key!=key)i--; return i; } |
④折半查找
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int Search_Bin(SSTable ST,KeyType key) { int low=1,high=ST.length; while(low<=high) { int mid=(low+high)/2; if(key==ST.elem[mid].key)return mid; else if(key<ST.elem[mid].key)high=mid-1; else low=mid+1; } return 0; } |
Main函数
Main函数中增加了时间函数用来测试查找时间的大小，当然，在试验中，无法输入大量数据，故两者查找时间相差不大。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
int main(int argc, char* argv[]) { clock_t start,finish; printf("输入构造的顺序表的长度："); SSTable ST;int n; scanf("%d",&n); CreateTable(ST,n); printf("检查顺序表\n"); OutputTable(ST); printf("\n--------------顺序查找--------------------\n"); printf("输入要查找的值的序号："); int key; scanf("%d",&key); int t; start=clock(); t=Search_Seq(ST,key); finish=clock(); if(t==0) printf("查找失败，无匹配\n"); else { printf("关键字为%d的数据是%s。\n",t,ST.elem[Search_Seq(ST,key)].data); printf("查找时间为: %lf\n",(double)(finish-start)); } printf("\n--------------折半查找--------------------\n"); printf("输入要查找的值的序号："); scanf("%d",&key); start=clock(); t=Search_Bin(ST,key); finish=clock(); if(t==0) printf("查找失败，无匹配\n"); else { printf("关键字为%d的数据是%s。\n",t,ST.elem[Search_Bin(ST,key)].data); printf("查找时间为: %lf\n",(double)(finish-start)); } return 0; } |
数据：
查找：
三.实验小结
1. Main函数中增加了时间函数用来测试查找时间的大小，当然，在试验中，无法输入大量数据，故两者查找时间相差不大。
2.定义结构体的时候要注意
每个数据有两个元素，一个是关键字，一个是保存数据
|
1 2 3 4 5 6 7 8 9 |
typedef struct{ ElemType data[10]; KeyType key; }Node; typedef struct{ Node elem[MAXSIZE]; int length; }SSTable; |
膜