查找算法的数据结构及实现

一、目的

掌握顺序查找算法的实现过程熟悉折半查找算法的原理及实现

二、内容

实现顺序查找的算法 编写一个程序exp9-1.cpp，输出在顺序表（3，6，2，10，1，8，5，7，4，9）中采用顺序查找方法查找关键字5的过程。实现折半查找的算法 编写一个程序exp9-2.cpp，输出在顺序表（1，2，3，4，5，6，7，8，9，10）中采用折半查找方法查找关键字9的过程。

三、源代码

实现顺序查找的算法 #include<stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType; typedef struct { KeyType key; InfoType data; }RecType; void CreateList(RecType R[],KeyType keys[],int n) { for(int i=0;i<n;i++) R[i].key=keys[i]; } void DispList(RecType R[],int n) { for(int i=0;i<n;i++) printf("%d",R[i].key); printf("\n"); } int SeqSearch(RecType R[],int n,KeyType k) { int i=0; while(i<n&&R[i].key!=k) { printf("%d",R[i].key); i++; } if(i>=n) return 0; else { printf("%d",R[i].key); return i+1; } } int main() { RecType R[MAXL]; int n=10,i; KeyType k=5; int a[]={3,6,2,10,1,8,5,7,4,9}; CreateList(R,a,n); printf("关键字序列：");DispList(R,n); printf("查找%d所比较的关键字：\n\t",k); if((i=SeqSearch(R,n,k))!=0) printf("\n元素%d的位置是%d\n",k,i); else printf("\n元素%d不在表中\n",k); return 1; } 实现折半查找的算法 #include<stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType; typedef struct { KeyType key; InfoType data; }RecType; void CreateList(RecType R[],KeyType keys[],int n) { for(int i=0;i<n;i++) R[i].key=keys[i]; } void DispList(RecType R[],int n) { for(int i=0;i<n;i++) printf("%d",R[i].key); printf("\n"); } int BinSearch(RecType R[],int n,KeyType k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次比较：在[%d,%d]中比较元素R[%d]:%d\n",++count,low,high,mid,R[mid].key); if(R[mid].key==k) return mid+1; if(R[mid].key>k) high=mid-1; else low=mid+1; } return 0; } int main() { RecType R[MAXL]; KeyType k=9; int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10; CreateList(R,a,n); printf("关键字序列：");DispList(R,n); printf("查找%d的比较过程如下：\n",k); if((i=BinSearch(R,n,k))!=-1) printf("元素%d的位置是%d\n",k,i); else printf("元素%d不在表中\n",k); return 0; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！