资源描述
1.题目采用顺序存储结构实现堆的筛选，建造，插入，删除，排序等操作。ADT Heap基本操作： voiMdakeHeap(Heap &H, RcdType *E, int n, int size, int tag) 操作结果：构造一个堆；Destro&yH() 初始条件：堆已存在。 操作结果：销毁堆H。 GetLength(H) 初始条件：堆 H 已存在。 操作结果：返回堆H中元素个数。 Get(L, i&,e) 初始条件：堆H已存在，1iLengthList(L)。 操作结果：用e返回堆H中第i个元素的值。 RemoveFirstHeap(H,e);初始条件：堆 H 已存在 操作结果：删除第一个节点 insertHeap(H,e); 初始条件：堆H已存在，1iLengthList(L)+1o 操作结果：在H的第n个元素之后插入新的元素e, L的长度加1 showRcd(H.rcd,H.n);初始条件：堆 H 已存在。 操作结果：依次输出H的每个元素。 ADT Heap2.存储结构定义 /引入系统头文件 #include #include #include /定义一些常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/定义一些状态类型typedef int Status;/用作函数类型，用作函数结果状态 typedef int ElemType;typedef int KeyType;/定义一个记录类型typedef structKeyType key;/关键字 RcdType;/定义一个记录类型的顺序表 typedef structRcdType *rcd;/rcd 的 0 号单元闲置； int length;int size;int tag;/排序类型，1为升序，0为降序 int increament; RcdSqList;/定义堆的结构体类型typedef structRcdType *rcd;/堆的基址，0号单元不使用int n; /堆长度int size; /堆容量int tag; /大根对与小根堆的标志int (*prior)(KeyType,KeyType,int);/函数变量，用于关键字优先级比较 Heap;堆类型3.算法设计/* 这是一个比较关键字优先级的函数参数说明：a 和 b 为需要比较的两个关键字tag 为排序的标识，1 为升序，2 为降序 */Status prior(KeyType a,KeyType b,int tag) if(tag = 1)return (a b) ? 1 : 0;else if(tag = 0)return (b = a) ? 1 : 0;elsereturn 0;*初始化一个顺序表的函数参数说明：L 为需要初始化的函数size 为顺序表的长度tag 为顺序表的排序类型*/Status initSqList(RcdSqList &L, int size,int tag) /将当前时间设置成随机函数的种子，所以每次产生的数都不一样 srand( (unsigned)time( NULL ) );L.length = 0;L.tag = tag;L.size = size+11;L.rcd = (RcdType*)malloc(size+11)*sizeof(RcdType); if(L.rcd = NULL)return 0;elsefor(int i = 1; i = size; i+)L.rcdi.key = rand()%100;L.length+;return 1;*打印记录参数说明：rcd 为需要打印的记录序列length 为序列的长度 */ void showRcd(RcdType *rcd,int length) int i;for(i = 1; i = length; i+) printf(%d ,rcdi.key); printf(n);*交换节点、参数说明：H 为需要交换节点的堆i 和 j 为需要交换的两个节点位置 */Status swapHeapElem(Heap &H,int i,int j)RcdType t;if(i 0 | j H.n | j H.n) return ERROR;elset = H.rcdi;H.rcdi = H.rcdj;H.rcdj = t;return OK;*堆的筛选操作参数说明：H 为需要筛选的堆pos 为筛选的其实位置*/void shiftDown(Heap &H,int pos)int c,rc; /c是左孩子的位置，rc是右孩子的位置while(pos n/2 时是叶子节点，则循环结束 c = pos*2;rc = pos*2+1;/ 判断条件解释：/rc = H.n , 判断右孩子是否大于总长度。左孩子不用判断，因为 它必然小于右子树/H.prior(H.rcdrc.key,H.rcdc,H.tag 用于比较谁更优秀 if(rc= H.size-1)return ERROR;elsecurr = +H.n;H.rcdcurr = e;while(1 != curr & H.prior(H.rcdcurr.key, H.rcdcurr/2.key, H.tag)swapHeapElem(H,curr,curr/2);/ / 向上调整 curr /= 2;return OK;*删除堆顶点的操作参数说明：H 为需要删除节点的堆e 得到删除那个节点*/Status RemoveFirstHeap(Heap &H,RcdType &e)if(H.n 1)shiftDown(H,1);/ 向下筛选;return OK;*建堆函数参数说明：H 为需要建立的堆E 为记录n 为堆的长度size 为堆的容量tag 为堆的类型，1 为大顶堆，2 为小顶堆 * void MakeHeap(Heap &H)int i;for(i = H.n/2; i 0; i-)shiftDown(H,i);*堆初始化函数参数说明：H 为需要初始化的堆L 为一个已经初始化了的顺序表* void initHeap(Heap &H,RcdSqList &L)H.rcd = L.rcd;/堆的n个节点，0号单元闲置;H.n = L.length;H.size = L.size;H.tag = L.tag;H.prior = prior;MakeHeap(H);showRcd(H.rcd,H.n);*堆排序函数参数说明：L 是要一个待排序初始序列，为记录顺序表类型tag 是排序类型：1 为升序，0 为降序*void heapSort(Heap H)MakeHeap(H);int i;RcdType e;for(i = H.n; i 0; i-)RemoveFirstHeap(H,e); printf(%d ,e);/销毁堆void destroyHeap(Heap &H)/H.rcd = NULL;/堆的n个节点，0号单元闲置;H.n = 0;showRcd(H.rcd,H.n);/获取堆的长度int getLength(Heap &H)return H.n;/获取第i个位置的元素void getEle(Heap H, int pos)if(pos H.n)printf(”对不起，你的输入不合法！请重新选择菜单”)； return ;elseprintf (”堆的第d个节点的值为：，pos); printf(%dn,H.rcdpos.key);4测试/ 引进基础库和函数库#include basic/basic.h#include basic/func.hint main()int length;/该变量通过用户输入的数字来决定表长int type;/该变量通过用户输入的数字决定堆的类型，1为大顶堆，0 为小顶堆int menu;/菜单选项int pos;/第i个位置RcdType e;/ 记录类型printf(RcdSqList L; /定义一个待排序的顺序表序列 Heap H;kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk*n);printf(|欢迎使用宇哥顶堆管理系统printf(|n);kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk*n);printf (”请输入堆的长度：n);scanf(%d,&length);printf(您输入的长度是%dn,length);printf (”请输入构建堆的类型(1表示大顶堆，0表示小顶堆)：n); while(1)scanf(%d,&type);if(type = 1)printf(”您选择的是大顶堆n);break;else if(type = 0)printf(”您选择的是小顶堆n);break;elseprintf （”您的输入不合法，请再次输入，1为大顶堆，0为小顶堆:n）;/初始化顺序表if（ !initSqList（L,length,type） ）/如果顺序表初始化失败，则 结束程序return 0;printf（系统随机产生的序列如下：n）;showRcd（L.rcd,L.length）;printf（生成堆后的序列为：n）;initHeap（H,L）;printf（n）;printf（插入节点请输入1n）;printf（删除堆顶节点请输入2n）;printf（销毁堆请输入3n）;printf（利用堆排序请输入4n）;printf（获取堆长度请输入5n）;printf（获取某个节点的值请输入6n）;printf（退出请输入0n）;int end = 1;while(end)scanf(%d,&menu);switch(menu)case 1 :printf(”请输入待插的节点的值：”)；scanf(%d,&e.key);insertHeap(H,e);printf(插入新节点后的序列为：n);showRcd(H.rcd,H.n);break;case 2 ：RemoveFirstHeap(H,e);printf(删除堆顶节点后的序列为：n);showRcd(H.rcd,H.n);break;case 3 ：destroyHeap(H);printf(销毁成功！ n);break;case 4 ：printf(利用堆排序后的序列为：n);heapSort(H);printf(n);MakeHeap(H);/排序后堆被打乱，因此要重新建堆 break;case 5 :printf(堆的长度为dn,getLength(H);break;case 6 :printf(请输入要相应位置的索引：n);scanf(%d,&pos);getEle(H,pos);break;case 0:end = 0;break;default:printf(您的输入有误，请重新输入);break;printf(本次使用结束，欢迎再次使用n);/HeapSort(L,1);return 0;5思考与小结(1) 直接用rand函数生成的不是随机数，因此需要将当前时间设置成随机函数的种子,srand( (unsigned)time( NULL ) );(2) 在取值获取增加节点时要判断参数的合法性，比如长度，容量等。(3) 堆排序之后堆的结构会被打乱，因此需要重新调用makeHeap函数来重建堆。
展开阅读全文