《编写优先队列数据(priority-queue)》由会员分享，可在线阅读，更多相关《编写优先队列数据(priority-queue)（13页珍藏版）》请在金锄头文库上搜索。
1、#includeiostream#include stdlib.htypedef int T;#define ERROR 0#define OK 1#define MAX 50typedef struct T *array;int length;int MaxSize;Array;/定义一个数组，用来存放第一次录入的数据。对应有两个函数操作using namespace std;template/定义一种格式，当T改变时，class类型改变,采用class才完成，用最大堆来存取class MaxHeap public :MaxHeap(int MaxSize);int Size() retur
2、n CurrentSize;/求当前堆的元素大小T Max() if (CurrentSize = 0) throw OutOfBounds();return heap1;/求最大的元素void LoadHeap()/遍历整个堆元素cout输出数据为endl;for(int i=1;i=CurrentSize;i+)coutheapiendl;MaxHeap& Insert( T x);/插入MaxHeap& DeleteMax(T& x);/删除void Initialize(T a, int size);/初始化void heapAdjust();/调整private:int Curren
3、tSize, MaxSize;/当前长度和最大长度T *heap; / 元素数组，用堆来存取 ;templateMaxHeap:MaxHeap(int MaxHeapSize)/ 构造函数MaxSize = MaxHeapSize;heap = new TMaxSize+1;CurrentSize = 0;templatevoid MaxHeap:Initialize(T a, int size)/初始化/ 把最大堆初始化为数组a .heap = a;CurrentSize = size;void MaxHeap:heapAdjust()/调整for (int i = CurrentSize/
4、2; i = 1; i-) T y = heapi; / 子树的根/ 寻找放置y的位置int c = 2*i; / c的父节点是y的目标位置while (c = CurrentSize) / heapc 应是较大的同胞节点if (c CurrentSize &heapc = heapc) break; / 能/ 不能heapc/2 = heapc; / 将孩子上移c *= 2; / 下移一层heapc/2 = y;templateMaxHeap& MaxHeap:Insert(T x)/插入/ 把x 插入到最大堆中if (CurrentSize = MaxSize)throw NoMem();
5、 / 没有足够空间/为x寻找应插入位置/ i 从新的叶节点开始，并沿着树上升int i = +CurrentSize;while (i != 1 & x heapi/2) / 不能够把x 放入h e a p i heapi = heapi/2; / 将元素下移i /= 2; / 移向父节点heapi = x;return *this;templateMaxHeap& MaxHeap:DeleteMax(T& x)/删除/ 将最大元素放入x ，并从堆中删除最大元素/ 检查堆是否为空if (CurrentSize = 0)throw OutOfBounds(); / 队列空x = heap1; /
6、 最大元素/ 重构堆T y = heapCurrentSize-; / 最后一个元素/ 从根开始，为y 寻找合适的位置int i = 1, / 堆的当前节点ci = 2; / i的孩子while (ci = CurrentSize) / heapci 应是i的较大的孩子if (ci CurrentSize &heapci = heapci) break; / 能/ 不能heapi = heapci; /i = ci; /下移一层ci *= 2;heapi = y;return *this;void InitArray(Array &A)/初始化元素数组A.array=(T *)malloc(M
7、AX*sizeof(T);A.length=0;A.MaxSize=MAX;void GetArrayKey(Array &A)/输入元素数组的值cout请输入您数组集合的大小个数n;int key;cout请输入数据endl;for(int i=1;ikey;if(A.length=A.MaxSize)A.array=(T*)realloc(A.array,(A.length+MAX)*sizeof(T);A.array+A.length=key;class OutOfBounds /异常抛出，太麻烦不写public:OutOfBounds()OutOfBounds();class NoMe
8、m public:NoMem()virtual NoMem();/异常抛出，太麻烦不写int main()MaxHeap H(MAX);T x;Array A;InitArray(A); H.LoadHeap();int choose;/控制选择while(choose)/菜单选择cout1.初始化输入数据endl;cout2.插入数据endl;cout3.查找数据endl;cout4.删除数据endl;cout5.遍历数据endl;cout0.退出choose;switch(choose)case 1:GetArrayKey(A);/初始化数据 H.Initialize(A.array,A.
9、length);H.heapAdjust();break;case 2:/插入元素cout请输入您想要插入的元素的值x;H.Insert(x);cout插入成功endl;break;case 3:x=H.Max();/求最大元素cout当前查找最大的元素为：xendl; break;case 4:H.DeleteMax(x);/删除最大元素cout删除的最大元素为: xendl;break;case 5: H.LoadHeap();break;/遍历整个数组元素case 0:return 0;return 0;数据结构选择：定义T为INT类型，权值为INT类型，定义一个class，里面一个pr
10、ivate T *heap，采用大顶堆的方法实现函数功能，函数实现都是在class里面的public 函数;算法实现: 在class里面实现全部函数，函数定义为public一个初始化initialize(T a, int size),把一个数组直接覆盖掉原来的T *heap，并执行相应的长度变化操作.一个插入Insert( T x)：在数组的最尾部插入，插入之后进行大顶堆调整，保证第一个数组元素为最大权值一个删除DeleteMax(T& x)：返回第一个数组元素，然后进行大顶堆调整，重新建堆一个查找最大元素T Max()：返回第一个数组元素一个遍历void LoadHeap()：采用从头到尾遍
11、历整个数组元素一个求元素数组的长度int Size()：返回当前长度总结：由于编写优先队列数据（priority_queue）类型可以用很多种方法实现，而且难度不大，所以在数据结构和C语音的基础上自学了C+,代码才用C+语言描写，函数在class内完成，大顶堆代码在数据结构中稍微调整了一下，整个元素集合封装只可以调用函数访问.测试数据：第一组： 第二组： 电视墙也就是电视背景装饰墙，是居室装饰特别是大户型居室的重点之一，在装修中占据相当重要的地位，电视墙通常是为了弥补客厅中电视机背景墙面的空旷，同时起到修饰客厅的作用。因为电视墙是家人目光注视最多的地方，长年累月地看也会让人厌烦，所以其装修就尤为讲究
