资源描述：
《数据结构堆排序问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、《数据结构与算法设计》堆排序问题实验报告一一实验五专业：物联网工程班级：物联网1班学号:15180118姓名：刘沛航一、实验目的本程序是利用堆排序算法进行排序按照字典序列由小到大排列出某个集体中的n个人名(汉语拼音)。二、实验内容用户可以根据自己的需求输入一个顺序表，并通过利用堆排序按非递减排序已存的顺序表。大概操作如下：1、首先创建一个空列表，用于保存已排序的有序数列(我们称之为"有序列表")。2、找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。3重复2号步骤，直至原数列为空。三、程序设计1、概要设计(1)为实现上述算法，需要
2、顺序表的抽象数据类型：ADTsqlist{数据对象D:D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数裾元素的关键字。数据关系R:数据元素同属一个集合。基本操作P:Creatsqlist(&1)操作结果：构造一个具有n个数据元素的顺序表1。ListLcngth(L)初始条件：线性表L已经存在操作结果：返回1屮数据元素的个数。destroy1ist(&1)初始条件：顺序表1存在。操作结果：销毁顺序表1。display1ist(1)初始条件：顺序表1存在。操作结果：显示顺序表1。quicksort(&1)初始条件：顺序表1存在。操作
3、结果：通过快速排序得到一个有序的顺序表1。heapsort(&1)初始条件：顺序表1存在。操作结果：通过堆排序得到一个有序的顺序表1。heapadjust(&1,s,m)初始条件：顺序表1存在。操作结果：调整h-〉r[s]的关键字，使h->r[s]成为一个大顶堆partion(&1,&low,high)初始条件：顺序表1存在。操作结果：交挽顺序表屮子表r[low...high]的记录，使枢轴记录到位，并返回其所在的位置。}ADTsqlist(1).本程序有三个模块：(1)主程序模块main(){初始化；{接受命令；显示结果；}}(2)创建顺序表的模块：
4、主要建立一个顺序表；⑶快速排序模块：得到一个有序的顺序表；G1)输出顺序表模块：显示己创建顺序表；(5)堆排序模块：得到一个有序的顺序表。voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}b、桟模块——实现栈的抽象数据类型c、迷宫模块——实现迷宫的抽象数据类型2、详细设计(1)元素类型，结点类型typedefstructintkey;}keytype;typedefstruct{keytyper[100];intlength;Jsqlist;(2)对抽象数据类型中的部分基本操作的伪码算法如下：/*创建顺序表*/voidcreat(sqlis
5、t*1){inti,key;printf(〃pleaseintputit’slength,);scanf(/z%dz/，&l->length);printf(/zpleaseintput%ddata1->length);for(i=l;i<=l-〉length;i++){scanf(〃％d〃，&key);1-〉r[i].key=key;}}/*交换顺序表屮子表r[low...high]的记录，使枢轴记录到位，并返回其•所在的位賈*/intpartion(sqlist*1,intlow,inthigh){intpivotkey;l-〉r[0
6、]=l->r[low];pivotkey=l-〉r[low],key;whilc(lowr[high].key>=pivotkoy)—high;1-〉r[low]=l-〉r[high];whi1e(1owr[1ow].key〈=pivotkey)++lo'v;l->r[high]=l->r[low];}l-〉r[low]=l-〉r[0];returnlow;}/*快速排序*/voidQsort(sqlist*1,intlow,inthigh){intpivotloc;if(low<
7、high){pivotloc=partion(l,low,high);Qsort(1,low,pivotloc-1):Qsort(1,pivotloc+1,high);}}/*快速排序*/voidquicksort(sqlist氺1){Qsort(1,1,l-〉length);}/*显示顺序表*/voiddisplay(sqlist氺1){inti;for(i=l;i<=l->1ength;i++)printf2cT,i);printfCAn");for(i=l;i<=2*l->length;i++)printf("");for(i=l;i<=l-
8、>length;i++)printf(〃%-4.2d〃，l-〉r[i].key);}A调整h-
