欢迎来到天天文库
浏览记录
ID:8797153
大小:26.00 KB
页数:5页
时间:2018-04-08
《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;i8、1");printf("☆从队列中删除一个元素....请按:2");printf("☆查看优先权最小的元素....请按:3");printf("☆遍历队列中所有元素......请按:4");printf("☆退出....................请按:5");printf("********************************************");printf("请输入要执行的操作:");scanf("%d",&n);
8、1");printf("☆从队列中删除一个元素....请按:2");printf("☆查看优先权最小的元素....请按:3");printf("☆遍历队列中所有元素......请按:4");printf("☆退出....................请按:5");printf("********************************************");printf("请输入要执行的操作:");scanf("%d",&n);
此文档下载收益归作者所有