计算机软件技术基础实验报告封面模板.doc

《计算机软件技术基础实验报告封面模板.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、中国矿业大学矿业工程学院实验报告课程名称计算机软件技术基础姓名jdsljf班级班学号日期2013年10月成绩教师jgkhkl一．实验名称对半查找与排序二．实验目的（1）了解查找的基本概念，重点掌握线性查找、对分查找、分块查找、二叉排序树查找、哈希表查找的基本方法与原理； （2）掌握对分查找对半排序使用C++编程的基本实现方法； （3）了解对半查找与对半排序的优缺点； （4）了解计算机的各种排序方法，重点掌握对半排序；三．实验流程图开始输入所需查找的数据查找的数据=第N/2个数据Y输出该数所在位置N结束查找的数据<第

2、N/2个数据N要寻找的数据在第0个与第N/2-1个之间CHONGXINCHONGXINY要寻找的数据在第N/2个与第N-1个之间对半查找法的核心算法描述如下：若从一组由小到大排序的N个数据中寻找某一特定的数据，首先将这一特定的数据与这组数据中第N/2个数据相比较。若该数据不等于要寻找的数据，则判断该数据与要寻找数据的大小，假如第N/2个数据大于要寻找的数据，则要寻找的数据范围在第0个与第N/2-1个数据之间，否则要寻找的数据范围在第N/2+1和第N-1个数据之间，这样就可以将寻找数据的范围缩小一半，然后循环将要寻找

3、的数据与新的数据范围的中间的那个数据比较，则又可以将寻找范围缩小一半，……，依此类推，所以最多的循环次数为log2^N.1.打开C++编程软件，自选所需控件和设计最终界面。界面如下：2.输入下列算法#includeintbinary(intarray[],intn,intnumber)//从数组array中寻找数值为number的数，数组有n个元素{intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(number

4、mid])high=mid-1;elseif(number>array[mid])low=mid+1;elsereturnmid;}return-1;}voidmain(){inta[]={2,4,6,8,10,12,14,16,18,20,22,24};intnum;cout<<"请输入要寻找的数：";cin>>num;intindex=binary(a,sizeof(a)/sizeof(a[0]),num);if(index!=-1)cout<<"该数在数组中的序号为："<

5、ut<<"数组中没有该元素";3.调试运行对分插入排序的核心算法描述如下：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功

6、，或直到子表不存在为止，此时查找不成功。二分查找算法初始状态：假设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点，key为给定值，初始时，令low=0,high=n-1,mid=(low+high)/2让key与mid指向的记录比较。若key==r[mid].key，查找成功,算法结束，若keyr[mid].key，则low=mid+1。重复上述操作，直至low>high时，查找失败。二分插入排序的基本操作是在一个有序表中进行查

7、找和插入，这个“查找”操作可利用“折半查找来实现，由此进行的插入排序称之为折半插入排序。1.打开C++编程软件，自选所需控件和设计最终界面。界面如下：2.输入下列算法#include#includeusingnamespacestd;voidbsort(char*arr,intcount){inti,j,low,mid,high;chart;for(i=1;i

8、//low为插入的正确位置{mid=(low+high)/2;if(t=low;j--)arr[j+1]=arr[j];arr[low]=t;}}intmain(intargc,char*argv[]){chara[]={'k','k','x','a','w','