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

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

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

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

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

4、值比较函数输入需要比较的数据m,n是m>n否返回1返回0进行数据筛选生成大顶堆存在整型数组指针h，进行堆筛选的起始位置s,结束位置mrc记录数据的根节点初始位置j=2*s;直到j

5、1、存储类型，元素类型，结点类型：inth[]元素类型为整形数组。2、每个模块的分析：（1）主程序模块：voidmain(){intcount,h[20],i;printf("请输入排序数据的总数：");scanf("%d",&count);printf("请输入数据：");for(i=0;i

6、);}（2）比较函数模块intcompare(intn,intm){//进行数据m,n的比较if(n>m)return1;//如果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、;}h[s]=rc;//进行数据交换}堆排序函数模块voidheadsort(int*h,intcount){inti,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~i-1]重