存档:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define max 20
4 typedef int keytype;
5 #include "search.h"
6 int main()
7 {
8 sstable st;
9 keytype key;
10 int result,num;
11 init(st);
12 printf("***************************************\n");
13 printf("1.顺序查找\n");
14 printf("2.折半查找\n");
15 printf("3.输出表信息\n");
16 printf("4.退出\n");
17 printf("***************************************\n");
18 printf("请输入你的选择:\n");
19 scanf("%d",&num);
20 while(1)
21 {
22 switch(num)
23 {
24 case 1:
25 printf("请创建顺序查找表");
26 create(st);
27 printf("请输入顺序查找的关键字:");
28 scanf("%d",&key);
29 result=search_seq(st,key);
30 if(result!=0)
31 printf("在顺序表里第%d个位置查找到了!\n",result);
32 else
33 printf("在顺序表里没有找到!\n");
34 break;
35 case 2:
36 printf("请创建递增的折半查找表\n");
37 create(st);
38 printf("请输入折半查找的关键字:");
39 scanf("%d",&key);
40 result=search_bin(st,key);
41 if(result!=0)
42 printf("在顺序表里第%d个位置查找到了!\n",result);
43 else
44 printf("在顺序表里没有找到!\n");
45 break;
46 case 3:
47 print(st);
48 break;
49 case 4:
50 exit(0);
51 break;
52 default:printf("输入错误!\n");
53 }
54 printf("\n请重新输入您的选择:\n");
55 scanf("%d",&num);
56 }
57 return 0;
58 }
1 typedef char infotype;
2 typedef struct
3 {
4 keytype key;//keytype为关键字的数据类型
5 infotype other;//其他数据
6 }elemtype;//数据元素类型
7 typedef struct
8 {
9 elemtype *r;//基地址
10 int length;//元素个数
11 }sstable;//静态查找表
12 int init(sstable &l)//初始化静态查找表,分配资源
13 {
14 l.r=new elemtype[max];
15 if(!l.r)
16 {
17 printf("初始化错误!\n");
18 return 0;
19 }
20 l.length=0;
21 return 1;
22 }
23 void print(sstable l)//打印静态查找表的内容
24 {
25 for(int i=1;i<=l.length;i++)
26 printf("%d号关键字:%d\n",i,l.r[i].key);
27 printf("元素个数:%d\n",l.length);
28 }
29 int create(sstable &l)//创建表,对表中输入数据
30 {
31 l.length=0;
32 int k,i;
33 printf("请输入int型关键字,以-1结束:\n");
34 scanf("%d",&k);
35 while(k!=-1)
36 {
37 l.r[l.length+1].key=k;//0号位置留空
38 l.length++;
39 if(l.length>=max)
40 return 0;
41 scanf("%d",&k);
42 }
43 printf("下标:");
44 for(i=1;i<=l.length;i++)
45 printf("%4d",i);
46 printf("\n");
47 printf("key :");
48 for(i=1;i<=l.length;i++)
49 printf("%4d",l.r[i].key);
50 printf("\n");
51 return 1;
52 }
53 int search_seq(sstable st,keytype key)//在顺序表ST中顺序查找其关键字等于key的数据元素
54 {
55 //若找到,则函数值为该元素在表中的位置,否则为0
56 st.r[0].key=key;
57 for(int i=st.length;i>=1;i--)//从后往前找
58 {
59 if(st.r[i].key==key)
60 {
61 return i;
62 }
63 }
64 return 0;
65 }
66 int search_bin(sstable st,int key)//在有序表ST中折半查找其关键字等于key的数据元素
67 {
68 //若找到,则函数值为该元素在表中的位置,否则为0
69 int low=1;
70 int high=st.length;
71 int mid;
72 while(low<=high)
73 {
74 mid=(low+high)/2;
75 printf("折半查找的low值%d、high值%d、mid值%d\n",low,high,mid);
76 if(key==st.r[mid].key)
77 return mid;
78 else if(key<st.r[mid].key)
79 high=mid-1;
80 else
81 low=mid+1;
82 }
83 return 0;//表中不存在待查元素
84 }
运行结果如下: