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

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

2、)Insert:插入一個數(shù)據(jù)兀素到優(yōu)先級隊列.(5)FindMax：查找、返回優(yōu)先級取局的兀系(6)DeleteMax：刪除、返回優(yōu)先級取圖的兀系.編寫函數(shù)：(1)建立循環(huán)隊列,返回尾指針函數(shù)linkqueue*create()(2)X入隊,返回尾指針函數(shù)linkqueue*enqueue(linkqueue*rear,intx)(3)出隊返回隊頭兀素函數(shù)linkqueue*outqueue(linkqueue*rear)(4)顯小隊列兀素函數(shù)voidlist(linkqueue*rear)(5)刪除隊列函數(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.從文件讀入或隨機產(chǎn)生作業(yè)的信息,作業(yè)的信息包括作業(yè)id(一個6字符字符串)、作業(yè)長度(一個表示秒數(shù)的int)、作業(yè)優(yōu)先級.每一作業(yè)同樣會被賦什個到達編號(作業(yè)號).該模擬程序應該輸出作業(yè)id、作業(yè)優(yōu)先級、作業(yè)長度以及完成時間(相對于從時間0開始的模擬程序而言的,可以設(shè)一個全局變量模擬).二.主要算法的算法思想.

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

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

6、(i=0,p=L;p-next!=L;p=p-next,i+);returni;)3).如果優(yōu)先級隊列為空那么返回真,否那么返回假.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).插入一個數(shù)據(jù)元素到優(yōu)先級隊列.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)先級最高的元素.1405110002王一杰數(shù)據(jù)結(jié)構(gòu)實驗報告第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)./刪除、返回優(yōu)先級最高的元素.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)的問題,解決的方法1)沒有把頭結(jié)點表示出來,不知道把最高優(yōu)先級怎么表示.2).寫list函數(shù)時,沒有注意到循環(huán)隊列,陷入死循環(huán).2.每個函數(shù)的時、空復雜性分析1) .linkqueue*create()建單鏈表函數(shù)T(n)=O(n),S(n)=O(n);2).linkqueue

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

11、體會在優(yōu)先級隊列中無法找出最高優(yōu)先級.五 .使用說明：如何使用你編制的程序、操作步驟.輸入R-刪除,取出優(yōu)先級最高的作業(yè)并從隊列中刪除之輸入A-添加新作業(yè)輸入L-列舉全部作業(yè)輸入Q-退出六 .測試結(jié)果:輸入輸出數(shù)據(jù)內(nèi)容：窗口顯示如下：(下劃線局部為輸入局部,其余為輸出局部)測試數(shù)據(jù)固定輸出：用無序循環(huán)單鏈表完成優(yōu)先級隊列抽象數(shù)據(jù)類型姓名王一杰班級計算機大類1404班學號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)實驗報告第6頁共11頁LNode,*LinkList;/構(gòu)造空的優(yōu)先級隊列.StatusMake(LinkList&L)(if(L)return-1;L=(LNode*)malloc(sizeof(LNode);L-data=NULL;L-next=L;return0;/返回優(yōu)先級隊列中的元素個數(shù).StatusSize(LinkListL)(inti;LNode*p;for(i=0,p=L;p-n

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