查找

查找

一、目的：

掌握顺序查找、折半查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。

二、要求：

实现各种查找的算法程序

1、顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

2、折半查找（二分查找）的基本思想：在有序的线性表中，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前查找区间就缩小一半。重复这一过程直到找到关键字为K 的结点，或者直至当前查找区间为空（即查找失败）时为止。

三、实验内容

1、 设计程序，输入顺序表，编写顺序查找和折半查找两种算法，输入查找的关键字，输出顺序表，输出查找到的关键字的位序，如果查找失败返回0。

2、 调试程序。运行时注意：若选择折半查找，必须输入有序序列。

//======顺序查找及二分查找的示例========
#include"stdio.h"
#include"stdlib.h"
#define Max 100 //假设文件长度
typedef int KeyType; //自定义数据类型
typedef struct{ //定义记录类型
KeyType key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
int n; //实际顺序表的长度

//====在顺序表R[1..n]中顺序查找关键字为K的结点，成功返回找到结点的位置，===
//=====失败时返回0=======
int SeqSearch(SeqList R,KeyType K)
{
int i;
R[0].key=K; //设置哨兵
for(i=n;R[i].key!=K;i--); //从表后往前找
return i; //若i为0，表示查找失败；否则R[i]是要找的结点
}
//====在有序表R[1..n]中进行二分查找，成功返回找到结点的位置，失败时返回0====
int BinSearch(SeqList R,KeyType K)
{
int low=1,high=n,mid; //置当前查找区间上、下界的初值
while(low<=high){ //当前查找区间R[low..high]不空
mid=(low+high)/2;
if(R[mid].key==K) return mid; //查找成功返回
if(R[mid].key>K)
high=mid-1; //继续在R[low..mid-1]中查找
else
low=mid+1; //继续在R[mid+1..high]中查找
}
return 0; //当low>high时表示查找区间为空。查找失败
}
//==========输入顺序表========
void input_int(SeqList R)
{
int i;
printf("Please input num(int):");
scanf("%d",&n); //读入顺序表的长度
printf("Plase input %d integer:",n);
for(i=1;i<=n;i++)
scanf("%d",&R[i].key);
}
//==========输出顺序表========
void output_int(SeqList R)
{
int i;
for(i=1;i<=n;i++)
printf("%4d",R[i].key);
}
//==========主函数=======
void main()
{
SeqList R;
int K,i,j=0;
input_int(R); //输入顺序表
printf("Please Input Serach number:");
scanf("%d",&K); //输入查找关键字
printf("========Input 1 to SeqSearch; 2 to BinSearch:====");
scanf("%d",&i); //输入1采用顺序查找；输入2采用折半查找
if(i==1)
j=SeqSearch(R,K);
if(i==2)
j=BinSearch(R,K);
output_int(R); //输出顺序表
printf("\nSearch %d is %d seat\n",K,j); //输出查找到的结点位置
}