(完整word版)实验十二实现顺序和二分查找算法(word文档良心出品).docx

(完整word版)实验十二实现顺序和二分查找算法(word文档良心出品).docx实验十二 实现顺序和二分查找算法
姓名：张就 班级： 09 计算机一班 学号： 2009111111
一、实验目的
掌握顺序和二分查找算法的基本思想及其实现方法 。
二、实验内容
对给定的任意数组 （设其长度为 n），分别用顺序和二分查找方法
在此数组中查找与给定值 k相等的元素 。
三、算法思想与算法描述
1、顺序查找，在顺序表 R[0..n-1] 中查找关键字为 k的记录，成功时
返回找到的记录位置，失败时返回 -1 ，具体的算法如下所示：
int SeqSearch(SeqList 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 -1;
else
{
printf( "%d",R[i].key);
return i;
}
}
2、二分查找，在有序表 R[0..n-1] 中进行二分查找，成功时返回记录
的位置，失败时返回 -1 ，具体的算法如下：
int BinSearch(SeqList 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;
if (R[mid].key>k)
high=mid-1;
else
low=mid+1;
}
return -1;
}
四、实验步骤与算法实现
#include
<>
#define
MAXL 100
typedef
int
KeyType;
typedef
char
InforType[10];
typedef
struct
{
KeyType key;
InforType data;
}NodeType;
typedef NodeType SeqList[MAXL];
int SeqSearch(SeqList 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 -1;
else
{
printf( "%d",R[i].key);
return i;
}
}
int BinSearch(