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

// 二叉堆实现（最小）优先队列的基本操作 //优先队列的基本操作包括创建一个空的优先队列、返回具有最小优先权的元素、将元素插入队列中和从队列中删除一个元素 #include stdio.h #include malloc.h #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-elements[0] = 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-elements[i / 2] e; i = i / 2) h-elements[i] = h-elements[i / 2]; h-elements[i] = 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-elements[1]; // 要出队的元素 last = h-elements[h-size]; h-size--; //删除一个元素后重新排序 for (i = 1; 2 * i = h-size; i = child){ // 让child指向左子树 // 对于任意一个结点i,若2i小于或等于结点总个数，则左孩子的编号为2i child = 2 * i; // 如果i的右子树小于左子树, 则使child指向右子树 if (child != h-size h-elements[child + 1] h-elements[child]){ child++; } // 如果队尾元素大于当前节点的最小子树, 则把子树赋给当前节点 // 否则退出循环 if (last h-elements[child]) h-elements[i] = h-elements[child]; else break; } // 将last存入当前节点 h-elements[i] = last; return min; } //返回最小优先权的元素 int minPriority(PriQueue h){ int min; if (h-size == 0){ printf(队空, 出队失败 \n); return 0; } min=h-elements[1]; return min; } //主函数 void main(void){ int count,element; // count用于存储输入到队列的元素个数，element用于存储输入的元素 int i,cycle=0; // i用作数组循环变量，cycle用