查找算法的实现(C/C++实现)详解编程语言

 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 }