用无序循环单链表完成优先级队列抽象数据类型1405110002王一杰

1、武汉轻工大学数学与计算机学院数据结构课程设计设计题目：用无序循环单链表完成优先级队列抽象数据类型专业计算机大类班级计算机1404班学号1405110002姓名王一杰指导教师2022年12月31日1405110002王一杰数据结构实验报告第1页共11页数据结构实验报告成绩学号1405110002姓名王一杰授课教师专业计算机大类实验报告递交日期2022.1.5实验题目用无序循环单链表完成优先级队列抽象数据类型.一.需求分析1.程序的实现功能：根本操作：(1)Make构造空的优先级队列.(2)Size：返回优先队列中元素个数.(3)IsEmpty:如果优先级队列是否为空那么返回真,否那么返回假.(4

2、)Insert:插入一个数据兀素到优先级队列.(5)FindMax：查找、返回优先级取局的兀系(6)DeleteMax：删除、返回优先级取图的兀系.编写函数：(1)建立循环队列,返回尾指针函数linkqueue*create()(2)X入队,返回尾指针函数linkqueue*enqueue(linkqueue*rear,intx)(3)出队返回队头兀素函数linkqueue*outqueue(linkqueue*rear)(4)显小队列兀素函数voidlist(linkqueue*rear)(5)删除队列函数linkqueue*del(linkqueue*rear)(6)主函数完成功能：a)

3、.调用rear=creat();b) .调用list(rear);c) .输入x值；d) .调用enqueue(rear,x);e) .调用list(rear);f) .调用outqueue(rear)g)调用list(rear);h)调用del(rear)i)list(rear).2.从文件读入或随机产生作业的信息,作业的信息包括作业id(一个6字符字符串)、作业长度(一个表示秒数的int)、作业优先级.每一作业同样会被赋什个到达编号(作业号).该模拟程序应该输出作业id、作业优先级、作业长度以及完成时间(相对于从时间0开始的模拟程序而言的,可以设一个全局变量模拟).二.主要算法的算法思想.

4、1,构造空的优先级队列.2 .返回优先级队列中的兀素个数.3 .如果优先级队列为空那么返回真,否那么返回假.1405110002王一杰数据结构实验报告第2页共11页4.将队列重置为空.5.插入一个数据元素到优先级队列.6.查找、返回优先级最高的元素.7.删除、返回优先级最高的元素.三.设计：1.#include#include#include#includetypedefintStatus;typedefstructunsignedintnumber;unsignedintpriority;job;typedefstructlnodejob*data;structlnode*next;LNod

5、e,*LinkList;2 .参数表列出所有的符号常量与全局变量参数名数据传递方式数据内容传递所属函数NULL符号常量宏定义0所有函数3.列出每个函数的函数声明、函数作用、函数值、形参内容与形式、主要算法步骤等1) .构造空的优先级队列StatusMake(LinkList&L)if(L)return-1;L=(LNode*)malloc(sizeof(LNode);L-data=NULL;L-next=L;return0;2).返回优先级队列中的元素个数.StatusSize(LinkListL)inti;LNode*p;1405110002王一杰数据结构实验报告第3页共11页for

6、(i=0,p=L;p-next!=L;p=p-next,i+);returni;)3).如果优先级队列为空那么返回真,否那么返回假.StatusIsEmpty(LinkListL)(return(L-next=L);)4).将队列重置为空.voidClear(LinkListL)(LNode*p,*ptmp;for(p=L-next;p!=L;)(ptmp=p;p=p-next;free(ptmp-data);free(ptmp);)L-next=L;)5).插入一个数据元素到优先级队列.StatusInsert(LinkListL,job*data)(LNode*ptmp;ptmp=(LNo

7、de*)malloc(sizeof(LNode);if(!ptmp)return-2;ptmp-data=(job*)malloc(sizeof(job);if(!ptmp-data)free(ptmp);return-2;memcpy(ptmp-data,data,sizeof(job);ptmp-next=L-next;L-next=ptmp;return0;6).查找、返回优先级最高的元素.1405110002王一杰数据结构实验报告第4页共11页job*FindMax(LinkListL)(LNode*p;p=L-next;if(p=L)returnNULL;LNode*p0;for(p

8、0=p;p0!=L;p0=p0-next)if(p0-data-prioritydata-priority|p0-data-priority=p-data-priority&p0-data-numberdata-number)p=p0;returnp-data;7)./删除、返回优先级最高的元素.job*DeleteMax(LinkListL)(LNode*p;job*pD;p=L-next;if(p=L)returnNULL;LNode*p0;LNode*p1;for(p1=p0=L;p0-next!=L;p0=p0-next)if(p0-next-data-prioritydata

9、-priority|p0-next-data-priority=p-data-priority&p0-next-data-numberdata-number)p=p0-next;p1=p0;p1-next=p1-next-next;pD=p-data;free(p);returnpD;四.调试分析：1.调试中出现的问题,解决的方法1)没有把头结点表示出来,不知道把最高优先级怎么表示.2).写list函数时,没有注意到循环队列,陷入死循环.2.每个函数的时、空复杂性分析1) .linkqueue*create()建单链表函数T(n)=O(n),S(n)=O(n);2).linkqueue

10、*enqueue(linkqueue*rear,intx)输出队歹U函数1405110002王一杰数据结构实验报告第5页共11页T(n)=O(1),S(n)=O(1);3) .linkqueue*outqueue(linkqueue*rear)入队函数T(n)=O(1),S(n)=O(1);4) .voidlist(linkqueue*rear)出队函数T(n)=O(n),S(n)=O(1);5) .linkqueue*del(linkqueue*rear)删除队列T(n)=O(1),S(n)=O(1);6) .Intmain()主函数T(n)=O(n),S(n)=O(n).3.改良设想,经验

11、体会在优先级队列中无法找出最高优先级.五 .使用说明：如何使用你编制的程序、操作步骤.输入R-删除,取出优先级最高的作业并从队列中删除之输入A-添加新作业输入L-列举全部作业输入Q-退出六 .测试结果:输入输出数据内容：窗口显示如下：(下划线局部为输入局部,其余为输出局部)测试数据固定输出：用无序循环单链表完成优先级队列抽象数据类型姓名王一杰班级计算机大类1404班学号1405110002日期2022年12月30日输入R输入A:输入Q：输入L:七 .源代码:#include#include#include#includetypedefintStatus;typedefstructunsigne

12、dintnumber;unsignedintpriority;job;typedefstructlnodejob*data;structlnode*next;1405110002王一杰数据结构实验报告第6页共11页LNode,*LinkList;/构造空的优先级队列.StatusMake(LinkList&L)(if(L)return-1;L=(LNode*)malloc(sizeof(LNode);L-data=NULL;L-next=L;return0;/返回优先级队列中的元素个数.StatusSize(LinkListL)(inti;LNode*p;for(i=0,p=L;p-n

13、ext!=L;p=p-next,i+);returni;/如果优先级队列为空那么返回真,否那么返回假.StatusIsEmpty(LinkListL)(return(L-next=L);/将队列重置为空.voidClear(LinkListL)(LNode*p,*ptmp;for(p=L-next;p!=L;)(ptmp=p;p=p-next;free(ptmp-data);free(ptmp);L-next=L;1405110002王一杰数据结构实验报告第7页共11页/插入一个数据元素到优先级队列StatusInsert(LinkListL,job*data)(LNode*ptmp;ptmp

14、=(LNode*)malloc(sizeof(LNode);if(!ptmp)return-2;ptmp-data=(job*)malloc(sizeof(job);if(!ptmp-data)free(ptmp);return-2;memcpy(ptmp-data,data,sizeof(job);ptmp-next=L-next;L-next=ptmp;return0;/查找、返回优先级最高的元素.job*FindMax(LinkListL)LNode*p;p=L-next;if(p=L)returnNULL;LNode*p0;for(p0=p;p0!=L;p0=p0-next)if(p0

15、-data-prioritydata-priority|p0-data-priority=p-data-priority&p0-data-numberdata-number)p=p0;returnp-data;/删除、返回优先级最高的元素.job*DeleteMax(LinkListL)LNode*p;job*pD;p=L-next;if(p=L)returnNULL;LNode*p0;LNode*p1;for(p1=p0=L;p0-next!=L;p0=p0-next)if(p0-next-data-prioritydata-priority|p0-next-data-priorit

16、y=p-data-priority&p0-next-data-numberdata-number)1405110002王一杰数据结构实验报告第8页共11页p=p0-next;p1=p0;p1-next=p1-next-next;pD=p-data;free(p);returnpD;intmain()constchar*prtstr=;job*pfindData,*premoveData,tmpData;LNode*ptmp;intSerialNum=0;intc;LinkListpHead=NULL;pfindData=premoveData=NULL;Make(pHead);whil

17、e(1)system(cls);printf(用无序循环单链表完成优先级队列抽象数据类型n);printf(姓名王一杰n);printf(班级计算机大类1404班n);printf(学号1405110002n);printf(日期2022年12月31日n);printf(%s选择菜单%s,prtstr,prtstr);printf(ntR-删除,取出优先级最高的作业并从队列中删除之ntA-添加新作业ntL-列举全部作业ntQ-退出n);if(premoveData)printf(ntt最近取出的作业号：06d,premoveData-number);elseprintf(nnn);printf(请选择操作菜单:);fflush(stdin);c=getchar();if(c=a&cnext;ptmp!=pHead;ptmp=ptmp-next)printf(n作业号:%06d优先级:%d,ptmp-data-number,ptmp-data-priority);break;caseQ:Clear(pHead);free(pHea