北京工业大学计算机软件基础(折半查找).docx

折半查找实验报告样板程序:#include stdio.h#include conio.h#define N 80struct record{ int key;};typedefstruct record RECORD;intbinsearch(RECORD A[],int k);voidbubblesort(RECORD R[],int n);int n;int main(void){ RECORD A[N+1];inti,k,mid;printf(请输入待排序数据个数n:);scanf(%d,n);printf(请输入待排序的%d个数据\n,n); //输入待排序数据for(i=0;iN;i++) A[i].key=0;for(i=1;i=n;i++)scanf(%d,A[i].key);bubblesort(A,n); //调用排序函数printf(排好序的结果为); for(i=1;i=n;i++)printf(%d ,A[i].key);printf(请输入要查找的数据关键字key:\n); //调用查找函数scanf(%d,k);mid=binsearch(A,k);if(mid!=-1)printf(找到的数据所在位置为:%d\n,mid); else printf(该数据不存在！\n);return 0;}void bubblesort(RECORD R[],int n) //冒泡排序{inti,j,flag; RECORD temp; i=1;do{flag=0;for(j=1;j=n-i;j++)if(R[j].keyR[j+1].key) {temp=R[j]; R[j]=R[j+1];R[j+1]=temp;flag=1; }i++; } while((in)flag);}intbinsearch(RECORD A[],int k) //折半查找{intlow,mid,high;low=0;high=n;while(low=high) {mid=(low+high)/2;if(k==A[mid].key)return mid;else if(kA[mid].key)low=mid+1;elsehigh=mid-1;}return -1;}原理分析：首先利用冒泡排序，对用户输入的数据的关键字进行排序，形成有序顺序表；然后利用折半查找，找出用户输入的关键字，返回该数据的位置。运行结果：输入1 4 6 8 3排序输出1 3 4 6 8并返回查找到的数据的位置输入 1 3 5 7 4 2输出排好序的结果 1 2 3 4 5 7若关键字不存在，返回查找失败信息。总结：该程序比较简单，基本实现了查找排序功能，达到实验基本目的。但不足之处在于每次查找只能查找一次,只能一次性输入n个数据而不能添加。