用無(wú)序循環(huán)單鏈表完成優(yōu)先級(jí)隊(duì)列抽象數(shù)據(jù)類(lèi)型1405110002王一杰

1、武漢輕工大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：用無(wú)序循環(huán)單鏈表完成優(yōu)先級(jí)隊(duì)列抽象數(shù)據(jù)類(lèi)型專(zhuān)業(yè)計(jì)算機(jī)大類(lèi)班級(jí)計(jì)算機(jī)1404班學(xué)號(hào)1405110002姓名王一杰指導(dǎo)教師2022年12月31日1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第1頁(yè)共11頁(yè)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告成績(jī)學(xué)號(hào)1405110002姓名王一杰授課教師專(zhuān)業(yè)計(jì)算機(jī)大類(lèi)實(shí)驗(yàn)報(bào)告遞交日期2022.1.5實(shí)驗(yàn)題目用無(wú)序循環(huán)單鏈表完成優(yōu)先級(jí)隊(duì)列抽象數(shù)據(jù)類(lèi)型.一.需求分析1.程序的實(shí)現(xiàn)功能：根本操作：(1)Make構(gòu)造空的優(yōu)先級(jí)隊(duì)列.(2)Size：返回優(yōu)先隊(duì)列中元素個(gè)數(shù).(3)IsEmpty:如果優(yōu)先級(jí)隊(duì)列是否為空那么返回真,否那么返回假.(4

2、)Insert:插入一個(gè)數(shù)據(jù)兀素到優(yōu)先級(jí)隊(duì)列.(5)FindMax：查找、返回優(yōu)先級(jí)取局的兀系(6)DeleteMax：刪除、返回優(yōu)先級(jí)取圖的兀系.編寫(xiě)函數(shù)：(1)建立循環(huán)隊(duì)列,返回尾指針函數(shù)linkqueue*create()(2)X入隊(duì),返回尾指針函數(shù)linkqueue*enqueue(linkqueue*rear,intx)(3)出隊(duì)返回隊(duì)頭兀素函數(shù)linkqueue*outqueue(linkqueue*rear)(4)顯小隊(duì)列兀素函數(shù)voidlist(linkqueue*rear)(5)刪除隊(duì)列函數(shù)linkqueue*del(linkqueue*rear)(6)主函數(shù)完成功能：a)

3、.調(diào)用rear=creat();b) .調(diào)用list(rear);c) .輸入x值；d) .調(diào)用enqueue(rear,x);e) .調(diào)用list(rear);f) .調(diào)用outqueue(rear)g)調(diào)用list(rear);h)調(diào)用del(rear)i)list(rear).2.從文件讀入或隨機(jī)產(chǎn)生作業(yè)的信息,作業(yè)的信息包括作業(yè)id(一個(gè)6字符字符串)、作業(yè)長(zhǎng)度(一個(gè)表示秒數(shù)的int)、作業(yè)優(yōu)先級(jí).每一作業(yè)同樣會(huì)被賦什個(gè)到達(dá)編號(hào)(作業(yè)號(hào)).該模擬程序應(yīng)該輸出作業(yè)id、作業(yè)優(yōu)先級(jí)、作業(yè)長(zhǎng)度以及完成時(shí)間(相對(duì)于從時(shí)間0開(kāi)始的模擬程序而言的,可以設(shè)一個(gè)全局變量模擬).二.主要算法的算法思想.

4、1,構(gòu)造空的優(yōu)先級(jí)隊(duì)列.2 .返回優(yōu)先級(jí)隊(duì)列中的兀素個(gè)數(shù).3 .如果優(yōu)先級(jí)隊(duì)列為空那么返回真,否那么返回假.1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第2頁(yè)共11頁(yè)4.將隊(duì)列重置為空.5.插入一個(gè)數(shù)據(jù)元素到優(yōu)先級(jí)隊(duì)列.6.查找、返回優(yōu)先級(jí)最高的元素.7.刪除、返回優(yōu)先級(jí)最高的元素.三.設(shè)計(jì)：1.#include#include#include#includetypedefintStatus;typedefstructunsignedintnumber;unsignedintpriority;job;typedefstructlnodejob*data;structlnode*next;LNod

5、e,*LinkList;2 .參數(shù)表列出所有的符號(hào)常量與全局變量參數(shù)名數(shù)據(jù)傳遞方式數(shù)據(jù)內(nèi)容傳遞所屬函數(shù)NULL符號(hào)常量宏定義0所有函數(shù)3.列出每個(gè)函數(shù)的函數(shù)聲明、函數(shù)作用、函數(shù)值、形參內(nèi)容與形式、主要算法步驟等1) .構(gòu)造空的優(yōu)先級(jí)隊(duì)列StatusMake(LinkList&L)if(L)return-1;L=(LNode*)malloc(sizeof(LNode);L-data=NULL;L-next=L;return0;2).返回優(yōu)先級(jí)隊(duì)列中的元素個(gè)數(shù).StatusSize(LinkListL)inti;LNode*p;1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第3頁(yè)共11頁(yè)for

6、(i=0,p=L;p-next!=L;p=p-next,i+);returni;)3).如果優(yōu)先級(jí)隊(duì)列為空那么返回真,否那么返回假.StatusIsEmpty(LinkListL)(return(L-next=L);)4).將隊(duì)列重置為空.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).插入一個(gè)數(shù)據(jù)元素到優(yōu)先級(jí)隊(duì)列.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).查找、返回優(yōu)先級(jí)最高的元素.1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第4頁(yè)共11頁(yè)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)./刪除、返回優(yōu)先級(jí)最高的元素.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;四.調(diào)試分析：1.調(diào)試中出現(xiàn)的問(wèn)題,解決的方法1)沒(méi)有把頭結(jié)點(diǎn)表示出來(lái),不知道把最高優(yōu)先級(jí)怎么表示.2).寫(xiě)list函數(shù)時(shí),沒(méi)有注意到循環(huán)隊(duì)列,陷入死循環(huán).2.每個(gè)函數(shù)的時(shí)、空復(fù)雜性分析1) .linkqueue*create()建單鏈表函數(shù)T(n)=O(n),S(n)=O(n);2).linkqueue

10、*enqueue(linkqueue*rear,intx)輸出隊(duì)歹U函數(shù)1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第5頁(yè)共11頁(yè)T(n)=O(1),S(n)=O(1);3) .linkqueue*outqueue(linkqueue*rear)入隊(duì)函數(shù)T(n)=O(1),S(n)=O(1);4) .voidlist(linkqueue*rear)出隊(duì)函數(shù)T(n)=O(n),S(n)=O(1);5) .linkqueue*del(linkqueue*rear)刪除隊(duì)列T(n)=O(1),S(n)=O(1);6) .Intmain()主函數(shù)T(n)=O(n),S(n)=O(n).3.改良設(shè)想,經(jīng)驗(yàn)

11、體會(huì)在優(yōu)先級(jí)隊(duì)列中無(wú)法找出最高優(yōu)先級(jí).五 .使用說(shuō)明：如何使用你編制的程序、操作步驟.輸入R-刪除,取出優(yōu)先級(jí)最高的作業(yè)并從隊(duì)列中刪除之輸入A-添加新作業(yè)輸入L-列舉全部作業(yè)輸入Q-退出六 .測(cè)試結(jié)果:輸入輸出數(shù)據(jù)內(nèi)容：窗口顯示如下：(下劃線(xiàn)局部為輸入局部,其余為輸出局部)測(cè)試數(shù)據(jù)固定輸出：用無(wú)序循環(huán)單鏈表完成優(yōu)先級(jí)隊(duì)列抽象數(shù)據(jù)類(lèi)型姓名王一杰班級(jí)計(jì)算機(jī)大類(lèi)1404班學(xué)號(hào)1405110002日期2022年12月30日輸入R輸入A:輸入Q：輸入L:七 .源代碼:#include#include#include#includetypedefintStatus;typedefstructunsigne

12、dintnumber;unsignedintpriority;job;typedefstructlnodejob*data;structlnode*next;1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第6頁(yè)共11頁(yè)LNode,*LinkList;/構(gòu)造空的優(yōu)先級(jí)隊(duì)列.StatusMake(LinkList&L)(if(L)return-1;L=(LNode*)malloc(sizeof(LNode);L-data=NULL;L-next=L;return0;/返回優(yōu)先級(jí)隊(duì)列中的元素個(gè)數(shù).StatusSize(LinkListL)(inti;LNode*p;for(i=0,p=L;p-n

13、ext!=L;p=p-next,i+);returni;/如果優(yōu)先級(jí)隊(duì)列為空那么返回真,否那么返回假.StatusIsEmpty(LinkListL)(return(L-next=L);/將隊(duì)列重置為空.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王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第7頁(yè)共11頁(yè)/插入一個(gè)數(shù)據(jù)元素到優(yōu)先級(jí)隊(duì)列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;/查找、返回優(yōu)先級(jí)最高的元素.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;/刪除、返回優(yōu)先級(jí)最高的元素.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王一杰數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第8頁(yè)共11頁(yè)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(用無(wú)序循環(huán)單鏈表完成優(yōu)先級(jí)隊(duì)列抽象數(shù)據(jù)類(lèi)型n);printf(姓名王一杰n);printf(班級(jí)計(jì)算機(jī)大類(lèi)1404班n);printf(學(xué)號(hào)1405110002n);printf(日期2022年12月31日n);printf(%s選擇菜單%s,prtstr,prtstr);printf(ntR-刪除,取出優(yōu)先級(jí)最高的作業(yè)并從隊(duì)列中刪除之ntA-添加新作業(yè)ntL-列舉全部作業(yè)ntQ-退出n);if(premoveData)printf(ntt最近取出的作業(yè)號(hào)：06d,premoveData-number);elseprintf(nnn);printf(請(qǐng)選擇操作菜單:);fflush(stdin);c=getchar();if(c=a&cnext;ptmp!=pHead;ptmp=ptmp-next)printf(n作業(yè)號(hào):%06d優(yōu)先級(jí):%d,ptmp-data-number,ptmp-data-priority);break;caseQ:Clear(pHead);free(pHea