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

1405110002王一杰数据结构实验报告第1页共11页武汉轻工大学数学与计算机学院数据结构课程设计设计题目：用无序循环单链表完成优先级队列抽象数据类型专业计算机大类班级计算机1404班学号1405110002姓名王一杰指导教师2015年12月31日1405110002王一杰数据结构实验报告第2页共11页数据结构实验报告成绩_____学号1405110002姓名王一杰授课教师专业计算机大类实验报告递交日期2015.1.5实验题目用无序循环单链表完成优先级队列抽象数据类型。一．需求分析1.程序的实现功能：基本操作：（1）Make：构造空的优先级队列。（2）Size：返回优先队列中元素个数。（3）IsEmpty：如果优先级队列是否为空则返回真，否则返回假。（4）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).调用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开始的模拟程序而言的，可以设一个全局变量模拟）。二.主要算法的算法思想.1．构造空的优先级队列.2.返回优先级队列中的元素个数.3.如果优先级队列为空则返回真，否则返回假。1405110002王一杰数据结构实验报告第3页共11页4.将队列重置为空.5.插入一个数据元素到优先级队列.6.查找、返回优先级最高的元素.7.删除、返回优先级最高的元素.三.设计：1．#includestdio.h#includestdlib.h#includemalloc.h#includestring.htypedefintStatus;typedefstruct{unsignedintnumber;unsignedintpriority;}job;typedefstructlnode{job*data;structlnode*next;}LNode,*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王一杰数据结构实验报告第4页共11页for(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=(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;}6）.查找、返回优先级最高的元素。1405110002王一杰数据结构实验报告第5页共11页job*FindMax(LinkListL){LNode*p;p=L-next;if(p==L)returnNULL;LNode*p0;for(p0=p;p0!=L;p0=p0-next)if(p0-data-priorityp-data-priority||p0-data-priority==p-data-priority&&p0-data-numberp-data-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-priorityp-data-priority||p0-next-data-priority==p-data-priority&&p0-next-data-numberp-data-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*enqueue(linkqueue*rear,intx)输出队列函数1405110002王一杰数据结构实验报告第6页共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．改进设想，经验体会在优先级队列中无法找出最高优先级。五.使用说明：如何使用你编制的程序、操作步骤.输入R---删除，取出优先级最高的作业并从队列中删除之输入A---添加新作业输入L---列举全部作业输入Q---退出六.测试结果：输入输出数据内容：窗口显示如下：(下划线部分为输入部分，其余为输出部分)测试数据固定输出：用无序循环单链表完成优先级队列抽象数据类型姓名王一杰班级计算机大类1404班学号1405110002日期2015年12月30日输入R:输入A：输入Q:输入L:七．源代码：#includestdio.h#includestdlib.h#includemalloc.h#includestring.htypedefintStatus;typedefstruct{unsignedintnumber;unsignedintpriority;}job;typedefstructlnode{job*data;structlnode*next;1405110002王一杰数据结构实验报告第7页共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-next!=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王一杰数据结构实验报告第8页共11页//插入一个数据元素到优先级队列。StatusInsert(LinkListL,job*data){LNode*ptmp;ptmp=(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-data-priorityp-data-priority||p0-data-priority==p-data-priority&&p0-data-numberp-data-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-priorityp-data-priority||p0-next-data-priority==p-data-priority&&p0-next-data-numberp-data-number)1405110002王一杰数据结构实验报告第9页共11页{p=p0-next;p1=p0;}p1-next=p1-next-next;pD=p-data;free(p);returnpD;}intmain(){constchar*prtstr=----------------------;job*pfindData,*premoveData,tmp