兰州大学数据实验堆排序实验报告

《兰州大学数据实验堆排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、兰州大学信息科学与工程学院数据结构实验报告课程名称实验名称专业班级姓名学号实验日期周—佳期日，三四节实验地点贺兰堂2012—2013学年度第一学期一、实验目的1、熟悉堆排序方法二、实验内容1、假设有一个数据类型为整型的一维数组A,A中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。三、实验环境1、硬件配置：Pentium(R)Dual-Core9CUPE6500@2.93GHz,1.96的内存2、软件环境：MicrosoftWindowsXPProfessionalServicePack3,MicrosoftVisualC++6.0四、需求分析1、输入的形式

2、和输入值的范围：根据题H要求与提示输入排序的数据总数，和参与比较的数据。2、输出的形式：输出从大到小的排序结果。3、程序所能达到的功能：输出排序后的结果。4、测试数据：输入数据总数，回车。输入具体数据，数据以空格隔开。如：数据总数：5比较的数据：56812396输出的数据为：96561283.五、概要设计为了实现上述操作，应以数组为存储结构。1、基本操作：(1)intcompare(intn,intm)初始条件：存在参与比较的整型数据叫m操作结果：如果m>n返回1,否则返回0。(2)voidheadadjust(int*h,ints,intm)初始条件：存在整型的数组的指针h,数据起始位置s,

3、结束位置m；操作结果：对编号s到m的数组中的数据进行筛选，成为根节点较大数据的堆。(3)voidheadsort(int*h,intcount)初始条件：存在整型数组指针h,数组内数据的总数count；操作结果：使整型数组内的数据进行堆排序。2、本程序包含二个模块：（1）主程序模块；（2）数值比较函数，筛选堆函数，堆排序函数模块（3）模块调用图:主程序模块堆排序函数模块筛选堆函数模块数值比较函数模块3、流程图主函数模块屏幕上输出“请输入排序数据的总数”将总数赋值给count将需要排序的数据存在整型数组h调用堆排序函数输出堆排序后的结果数值比较函数输入需要比较的数据m,n是m>n否返回1返回0进

4、行数据筛选生成大顶堆存在整型数组指针h,进行堆筛选的起始位置s,结束位置mrc记录数据的根节点初始位置j=2*s;直到j〈m,每次循环j二2*j是j且两个叶节点左节点是否大于右节点否j++否根节点是否小于叶节点是h[s]=h[j]跳出循环交换初始位置和数值较大的叶节点的值堆排序函数i的初始值从中间编号循环到等于0,每次循环i数值减一调用筛选堆函数(h,i,count)i的值从数组长度循环到0,每次循环i的值减一将堆顶记录和当前未经排序子序列[0〜i]中最后一个记录相互交换将[0〜i一1]重新调整为大顶堆六、详细设计1、存储类型，元素类型，结点类型:inth[]元素类型为整形数组。2、每个模块的

5、分析：(1)主程序模块：voidmain(){intcount,h[20],i;printfC请输入排序数据的总数：〃)；scanf("%d〃，&count);printfC请输入数据：〃)；for(i=0;im)r

6、eturn1;//如果m大于n,返回1elsereturn0;//否则返回0筛选堆函数模块voidheadadjust(int*h,ints,intm){//进行筛选堆intrc,j;rc=h[s];//记录根节点的初始位置for(j=2*s;j<=m;j*=2){if((j

7、,n;for(i=count/2;i>=0;i--)headadjust(h,i,count);//将堆中全部数据建成一个大堆for(i=count;i>0;i--){n二h[0];//将堆顶记录和当前未经排序子序列[0~i]中最后一个记录进行交换h[0]=h[i];h[i]二n;headadjust(h,0,i-1);//[0~iT]重新调整为大顶堆3）函数调用关系图main()intcompa