c语言—实现优先队列的基本操作

《c语言—实现优先队列的基本操作》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、//二叉堆实现（最小）优先队列的基本操作//优先队列的基本操作包括创建一个空的优先队列、返回具有最小优先权的元素、将元素插入队列中和从队列中删除一个元素#include#include#defineMINDATA-32767//构造二叉堆typedefstructHeapStruct{intcapacity;//最大堆容量intsize;//当前堆大小int*elements;//节点指针}*PriQueue;//初始化PriQueueinitPriQueue(

2、intcapacity){PriQueueh=(PriQueue)malloc(sizeof(structHeapStruct));h->elements=(int*)malloc((capacity+1)*sizeof(int));h->capacity=capacity;h->size=0;//将堆的顶端存入最小值h->elements[0]=MINDATA;returnh;}//入队intinPriQueue(PriQueueh,inte){inti;//判断队列是否为空if(h->size=

3、=h->capacity){printf("队满,入队失败！");return0;}for(i=++h->size;h->elements[i/2]>e;i=i/2)h->elements[i]=h->elements[i/2];h->elements[i]=e;return1;}//出队intoutPriQueue(PriQueueh){inti;//索引intchild;//子元素intmin;//最小值intlast;//队尾元素//判断队列是否为空if(h->size==0){print

4、f("队空,出队失败");return0;}min=h->elements[1];//要出队的元素last=h->elements[h->size];h->size--;//删除一个元素后重新排序for(i=1;2*i<=h->size;i=child){//让child指向左子树//对于任意一个结点i,若2i小于或等于结点总个数，则左孩子的编号为2ichild=2*i;//如果i的右子树小于左子树,则使child指向右子树if(child!=h->size&&h->elements[child

5、+1]elements[child]){child++;}//如果队尾元素大于当前节点的最小子树,则把子树赋给当前节点//否则退出循环if(last>h->elements[child])h->elements[i]=h->elements[child];elsebreak;}//将last存入当前节点h->elements[i]=last;returnmin;}//返回最小优先权的元素intminPriority(PriQueueh){intmin;if(h->size==0){print

6、f("队空,出队失败");return0;}min=h->elements[1];returnmin;}//主函数voidmain(void){intcount,element;//count用于存储输入到队列的元素个数，element用于存储输入的元素inti,cycle=0;//i用作数组循环变量，cycle用于while中的循环变量intn,size;//n用于switch中表示case的值,size用于存储队列的元素的长度intfunvalue;//funvalue用于存储函数的返回值P

7、riQueueh=initPriQueue(30);printf("请输入入队的个数：");scanf("%d",&count);printf("请输入入队的元素：");for(i=0;i

8、1");printf("☆从队列中删除一个元素....请按：2");printf("☆查看优先权最小的元素....请按：3");printf("☆遍历队列中所有元素......请按：4");printf("☆退出....................请按：5");printf("********************************************");printf("请输入要执行的操作：");scanf("%d",&n);