二分法查找实验报告

数 据 结 构

二分法查找实验

班级：计算机应用技术10-1班 学号：10602101018 姓名：石美远

一、实验目的及要求：

掌握有关二分法函数对数据的统计的基本操作和存储结构，并编写相应的基本操作算法。 二、实验内容：

1、完成插入排序函数的程序 2、用循环完成二分法查找函数 3、用递归完成二分法查找函数

4、在二分法函数中统计出查找次数与被查找关键字在有序表中的位置 5、最好能与顺序查找对比查找效率

三、实验准备： 1) 计算机设备；

2) 程序调试环境的准备，如VC6、C++或WIN-TC环境； 3) 实验内容的算法分析与代码设计准备。 四、函数实现 1、二分法函数

#include #define MAXSIZE 10

int BinSearch(int s[],int low,int high,int key) { int mid,count=0; while(low<=high)

{ mid=(low+high)/2; count++; if(key==s[mid])

{ printf(\,count); return (mid+1); } else

if(key>s[mid]) low=mid+1; else high=mid-1; } return -1; }

int BinSearch2(int s[],int low,int high,int key) { int mid;

static int count=0; while(low<=high) { mid=(low+high)/2; count++; if(key==s[mid])

{ printf(\,count); return (mid+1); } else

if(key>s[mid]) return BinSearch2(s,mid+1,high,key); else return BinSearch2(s,low,mid-1,key); } return -1; } int main()

{ int m[MAXSIZE]={4,7,-1,0,8,12,20,3,2,15},i,length,key,location; for(length=1;length<10;length++) { key=m[length]; i=length-1; while(i>=0)

{ if(key

printf(\); for(i=0;i<10;i++) printf(\,m[i]); printf(\);

location=BinSearch(m,0,9,7);

printf(\,location); location=BinSearch2(m,0,9,12);

printf(\,location); return 0; }

2、二分法函数统计数据

#include #define MAXSIZE 10

int BinSearch(int s[],int low,int high,int key) { int mid,count=0; while(low<=high) { mid=(low+high)/2; count++; if(key==s[mid])

{ printf(\,count); return (mid+1); } else

if(key>s[mid]) low=mid+1; else high=mid-1; }

printf(\); return -1; }

int BinSearch2(int s[],int low,int high,int key) { int mid;

static int count=0; while(low<=high) { mid=(low+high)/2; count++; if(key==s[mid])

{ printf(\,count); return (mid+1); } else

if(key>s[mid]) return BinSearch2(s,mid+1,high,key); else return BinSearch2(s,low,mid-1,key); }

printf(\); return -1;

}

void InserSort(int m[],int length) { int key,i,k;

for(k=1;k=0)

{ if(key

int main()

{ int m[MAXSIZE]={4,7,-1,0,8,12,20,3,2,15},location,len=10,x,i;

InserSort(m,len); printf(\); for(i=0;i<10;i++)

printf(\,m[i]);

printf(\); scanf(\,&x);

location=BinSearch(m,0,len-1,x); printf(\,location); location=BinSearch2(m,0,len-1,x);

printf(\,location); return 0; }

五、测试（在主函数中调用函数测试功能）

#include #include #define MAXSIZE 80 int main(void)

{ char p1[]=\

printf(\