C语言—实现优先队列的基本操作.doc

/ 二叉堆实现（最小）优先队列的基本操作/优先队列的基本操作包括创建一个空的优先队列、返回具有最小优先权的元素、将元素插入队列中和从队列中删除一个元素#include #include #define MINDATA -32767 / 构造二叉堆typedef struct HeapStruct int capacity; / 最大堆容量 int size; / 当前堆大小 int * elements; / 节点指针 * PriQueue; / 初始化PriQueue initPriQueue(int capacity) PriQueue h = (PriQueue)malloc(sizeof (struct HeapStruct); h-elements = (int *)malloc(capacity + 1) * sizeof (int); h-capacity = capacity; h-size = 0; / 将堆的顶端存入最小值 h-elements0 = MINDATA; return h; / 入队int inPriQueue(PriQueue h,int e) int i; /判断队列是否为空 if (h-size = h-capacity) printf(队满, 入队失败！n); return 0; for (i = +h-size; h-elementsi / 2 e; i = i / 2) h-elementsi = h-elementsi / 2; h-elementsi = e;return 1; / 出队int outPriQueue(PriQueue h) int i; / 索引 int child; / 子元素 int min; / 最小值 int last; / 队尾元素/判断队列是否为空 if (h-size = 0) printf(队空, 出队失败 n); return 0; min = h-elements1; / 要出队的元素 last = h-elementsh-size; h-size-;/删除一个元素后重新排序 for (i = 1; 2 * i size; i = child) / 让child指向左子树/ 对于任意一个结点i,若2i小于或等于结点总个数，则左孩子的编号为2i child = 2 * i; / 如果i的右子树小于左子树, 则使child指向右子树 if (child != h-size & h-elementschild + 1 elementschild) child+; / 如果队尾元素大于当前节点的最小子树, 则把子树赋给当前节点 / 否则退出循环 if (last h-elementschild) h-elementsi = h-elementschild; else break; / 将last存入当前节点 h-elementsi = last; return min;/返回最小优先权的元素int minPriority(PriQueue h) int min; if (h-size = 0) printf(队空, 出队失败 n); return 0; min=h-elements1;return min;/主函数void main(void)int count,element; / count用于存储输入到队列的元素个数，element用于存储输入的元素 int i,cycle=0; / i用作数组循环变量，cycle用于while中的循环变量int n,size; / n用于switch中表示case的值,size用于存储队列的元素的长度int funvalue; / funvalue用于存储函数的返回值 PriQueue h = initPriQueue(30);printf(请输入入队的个数：);scanf(%d,&count);printf(请输入入队的元素：);for(i=0;isize;/ 遍历所有元素for (i = 0; i size; i+) printf(%dt, outPriQueue(h);printf(nn请按任意键继续下一步操作!n);getchar();while(getchar()!=n);bre