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

中国矿业大学矿业工程学院

实验报告

课程名称计算机软件技术基础

姓名 班级 #班

学号日期 20##年10月

成绩教师

一．实验名称

对半查找与排序

二．实验目的

（1）了解查找的基本概念，重点掌握线性查找、对分查找、分块查找、二叉排序树查找、哈希表查找的基本方法与原理；

（2）掌握对分查找对半排序使用C++编程的基本实现方法；

（3）了解对半查找与对半排序的优缺点；

（4）了解计算机的各种排序方法，重点掌握对半排序；

三．实验流程图

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

对半查找法的核心算法描述如下：

若从一组由小到大排序的N个数据中寻找某一特定的数据，首先将这一特定的数据与这组数据中第N/2个数据相比较。若该数据不等于要寻找的数据，则判断该数据与要寻找数据的大小，假如第N/2个数据大于要寻找的数据，则要寻找的数据范围在第0个与第N/2-1个数据之间，否则要寻找的数据范围在第N/2+1和第N-1个数据之间，这样就可以将寻找数据的范围缩小一半，然后循环将要寻找的数据与新的数据范围的中间的那个数据比较，则又可以将寻找范围缩小一半，……，依此类推，所以最多的循环次数为log2^N.

1.打开C++编程软件，自选所需控件和设计最终界面。界面如下：

2.输入下列算法

#include

int binary(int array[],int n,int number)

//从数组array中寻找数值为number的数，数组有n个元素

{int low=0,high=n-1,mid;

while(low＜=high)

{ mid=(low+high)/2;

if(number

high=mid-1;

else if(number＞array[mid])

low=mid+1;

else

return mid;

}

return -1;

}

void main()

{int a[]={2,4,6,8,10,12,14,16,18,20,22,24};

int num;

cout＜＜"请输入要寻找的数：";

cin＞＞num;

int index=binary(a,sizeof(a)/sizeof(a[0]),num);

if(index!=-1)

cout＜＜"该数在数组中的序号为："＜

else

cout＜＜"数组中没有该元素\n";

3.调试运行

对分插入排序的核心算法描述如下：

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。二分查找算法初始状态：假设表长为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时，查找失败。二分插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用“折半查找来实现，由此进行的插入排序称之为折半插入排序。

1.打开C++编程软件，自选所需控件和设计最终界面。界面如下：

2.输入下列算法

#include

using namespace std;

void bsort(char *arr,int count)

{

int i,j,low,mid,high;

char t;

for(i=1;i

{

t=arr[i];

low=0;

high=i-1;

while(low＜=high) // low 为插入的正确位置

{

mid=(low+high)/2;

if(t

high=mid-1;

else

low=mid+1;

}

for(j=i-1;j＞=low;j--)

arr[j+1]=arr[j];

arr[low]=t;

}

int main(int argc, char *argv[])

{

char a[]={'k','k','x','a','w','f'};

int x=6;

bsort(a,x);

for(int i=0;i＜6;i++)

putchar(a[i]);

system("PAUSE");

return EXIT_SUCCESS;

}

在C++中输入上面的代码，进行编程。

3.调试运行

四．试验小结

结果分析：

所编程序在一定程度上存在有缺陷，例如在查找时时只能在有序数列中进行查找，所以需要对所给数列先进行排序，之后在进行查找工作，所编程序的优点是简洁明了，运算速度快，方便理解。

收获：

通过本次实验，我对C++这门语言重新进行了学习同时又对计算机程序的语言有了崭新的认识，这次上机实验，增加了我学习软件技术的兴趣，虽然还不明确软件技术包含的具体内容，但从计算机软件技术基础这门课程开始，已发现程序设计的乐趣，在温习C++语言的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个大体的了解。

在实际操作过程中犯的一些错误还会有意外的收获，感觉上机很有意思。在具体操作中对这学期所学的软件技术的理论知识得到巩固，达到了上机的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C++语言具有的语句简洁，使用灵活，执行效率高等特点。同时发现上机操作的重要作用，特别是对数组和循环有了更加深刻的理解。

总之，通过实际操作，回顾了C++语言程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。