2022年實驗1鏈表及其應(yīng)用

1、精選學(xué)習(xí)資料 - - - 歡迎下載試驗 1鏈表及其應(yīng)用一.試驗?zāi)康?. 加深對線性表鏈?zhǔn)絻浣Y(jié)構(gòu)的懂得；2. 嫻熟把握單鏈表類的描述方法及操作的c+實現(xiàn)；3. 把握鏈表結(jié)構(gòu)的應(yīng)用；4. 加強(qiáng)對算法設(shè)計才能和程序調(diào)試才能的培育；二.試驗學(xué)時 ：建議 24 學(xué)時三.基本學(xué)問（略）四.試驗內(nèi)容試驗內(nèi)容 1單鏈表的基本操作1 問題描述設(shè)計一個帶表頭結(jié)點(diǎn)的單鏈表類,實現(xiàn)單鏈表的創(chuàng)建.輸出.插入.刪除.查找.銷毀等操作；2 數(shù)據(jù)結(jié)構(gòu)設(shè)計依據(jù)問題要求,采納單鏈表儲備結(jié)構(gòu)儲備線性表；在頭文件 linklist.h中定義；（1） ） 結(jié)點(diǎn)結(jié)構(gòu)template<class t>struct node/

2、結(jié)點(diǎn)結(jié)構(gòu)t data;/結(jié)點(diǎn)數(shù)據(jù)node*link;nodelink=null; nodet e、node*next=nulldata=e; link=next;（2） ） 單鏈表類單鏈表類的數(shù)據(jù)成員主要有單鏈表的頭指針,依據(jù)要求其成員函數(shù)有構(gòu)造.輸出.插入.刪除.查找.銷毀等操作；template<class t>class linklist/帶表頭結(jié)點(diǎn)的單鏈表類private:node<t> *head;/鏈表指針public:精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載linklist;/構(gòu)造帶表頭結(jié)點(diǎn)的空單鏈表linklistt data、int msize;

3、/構(gòu)造有 msize 個元素的單鏈表linklistclear;/析構(gòu)函數(shù)bool insertint pos、const t&x;/在單鏈表第pos 個元素前插入元素x bool removeint pos、 t&x;/刪除單鏈表第pos 個元素bool replaceint pos、const t&x; /將修改單鏈表第pos 個元素為x int lengthconst;/求表長bool isempty const ; /判空操作 void clear ;/清空操作 void output const ;/輸出鏈表bool searchconst t&x c

4、onst;/查找元素x 在表中為否存在; / class linklist3 算法設(shè)計與實現(xiàn)（1） ） 構(gòu)造函數(shù)#include"linklist.h" template<class t>linklist<t>:linklist/構(gòu)造函數(shù)1 /創(chuàng)建帶表頭結(jié)點(diǎn)的空單鏈表head=new node<t>/創(chuàng)建表頭結(jié)點(diǎn)template<class t>linklist<t>:linklistt data、int msize/構(gòu)造函數(shù)2 /創(chuàng)建具有msize 個元素的帶表頭結(jié)點(diǎn)單鏈表/ 用尾插法創(chuàng)建單鏈表node<t

5、> *p、*r;head= p=new node<t>/創(chuàng)建表頭結(jié)點(diǎn),p 指針指向當(dāng)前單鏈表的最終一個結(jié)點(diǎn) forint i=0;i<msize;i+r=new node<t>datai;p->link=r;/鏈接到 p 指針?biāo)附Y(jié)點(diǎn)之后p=p->link;/p指針后移（2） ） 插入操作a) 插入原理：（在 p 所指結(jié)點(diǎn)之后插入s 所指結(jié)點(diǎn)；）ppabcabc精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載xs圖 1.1 插入前xs圖 1.2 插入后精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載在進(jìn)行插入操作時,要先確定待插入結(jié)點(diǎn)（ s 所指結(jié)點(diǎn)

6、） 的 link指針（ s->link）指向,精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載再修改鏈表指針（p->link）指向,如圖1.1 和圖 1.2 所示 、 即s->link= p->link; p->link=s;b) 算法描述：（在單鏈表的第pos 個元素之前插入元素x ）如 pos<1,就插入失敗,終止；掃描單鏈表,查找單鏈表中第pos-1 個元素結(jié)點(diǎn)的指針p；如 p 存在（ p 非空）就在其后插入,操作勝利,否就不能插入；c) 算法實現(xiàn)template<class t>bool linklist<t>:insertin

7、t pos、const t&x /在單鏈表的第pos 個元素之前插入元素x,插入勝利返回true、否就返回false；ifpos<1 /插入位置不合法return false; node<t> *s、*p=head;int i=0; / i為計數(shù)器whilep && i<pos-1/找第 pos-1個元素結(jié)點(diǎn)的指針frontp=p->link; i+;if.p /插入位置不合法return false;s=new node<t>x、p->link; s->data=x;s->link= p->link;/

8、確定待插入結(jié)點(diǎn)（s 所指結(jié)點(diǎn)）的link指針（ s->link）指向p->link=s; /修改鏈表中的指針（p->link）指向return true;（3） ） 刪除操作a) 刪除原理：（刪除 p 所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)s,如下圖所示； ）ppabcabc精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載s刪除前s刪除后精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載在進(jìn)行刪除操作時,直接修改鏈表指針（p->link）指向,即p->next =s->next;b) 算法步驟：（刪除單鏈表中的第pos 個元素）如 pos<1,就刪除失敗,終止；在單鏈表中找第p

9、os -1個元素結(jié)點(diǎn)的指針p；如 p 和 p->link均非空,就刪除p->link所指結(jié)點(diǎn),否就刪除失?。籧) 實現(xiàn)精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載template<class t>bool linklist<t>:removeint pos、t&x /刪除單鏈表的第pos 個元素,并置入xifpos<1/刪除位置不合法return false;node<t> *current、*p=head; int i=0;/ i為計數(shù)器whilep->link && i<pos-1/找第 pos-1

10、 個元素結(jié)點(diǎn)的指針p=p->link; i+;if.p->link /刪除位置不合法、pos 大于表長return false;current=p->link; / current指向被刪除結(jié)點(diǎn)p->link=current->link; /修改鏈表指針x= current->data; delete current; return true;（4） ） 輸出鏈表template<class t>void linklist<t>:output const/輸出鏈表node<t> *current=head->link

11、;/ current指向首元結(jié)點(diǎn)whilecurrent/依次掃描鏈表結(jié)點(diǎn)cout<<current->data<<" " current=current->link;cout<<endl;（5） ） 單鏈表清空操作template<class t>void linklist<t>:clear/清空操作,將各元素結(jié)點(diǎn)空間釋放,單鏈表為空表node<t> *current=head->link; / current指向首元結(jié)點(diǎn)whilecurrent.=null /依次掃描鏈表結(jié)點(diǎn),并逐

12、個釋放空間node<t> *r=current; current=current->link; delete r;head->link =null; /單鏈表為空精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載（6） ） 單鏈表查找template<class t>bool linklist<t>:searchconst t&x/查找元素x 在表中為否存在node<t> *current=head->link;whilecurrent&&/查找ifcurrent->data=x break;elsec

13、urrent=current->link; /指針后移return current.=null;4 測試（1）測試代碼#include<iostream.h>#include<time.h>#include<stdlib.h>#include"linklist.h"void menu/模擬菜單項項cout<<"-"<<endl;cout<<"|1 輸出鏈表|"<<endl;cout<<"|2 插入元素|"<&

14、lt;endl;cout<<"|3 刪除元素|"<<endl;cout<<"|4 銷毀鏈表|"<<endl;cout<<"|5 查找|"<<endl;cout<<"|0 退出系統(tǒng)|"<<endl;cout<<"-"<<endl;const int n=10; void mainsrandtimenull;/以系統(tǒng)當(dāng)前時間初始化隨機(jī)數(shù)發(fā)生器int datan;forint i=0

15、;i<n;i+datai=rand%100;/用隨機(jī)數(shù)發(fā)生器產(chǎn)生100 以內(nèi)的整數(shù)linklist<int> ldata、n;/創(chuàng)建 n 個元素的單鏈表 menu;while1 /模擬菜單工作方式intselect;cout<<" 請輸入您的挑選："cin>>select;精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載switchselectcase 1:/輸出單鏈表l.output; break;case 2:/插入int pos、elem;cout<<" 請輸入插入位置："cin>>

16、pos;cout<<" 插入元素： "cin>>elem;ifl.insertpos、elem/插入勝利cout<<" 在第 "<< pos <<"個元素前勝利插入"<<elem<<endl; else/插入失敗cout<<" 插入位置不合法！"<<endl; break;case 3:/刪除cout<<" 請輸入刪除位置："cin>>pos; int x;ifl.

17、removepos、x/刪除單鏈表的第pos 個元素cout<<" 單鏈表的第 "<< pos <<"個元素 "<<x<<" 已被刪除； "<<endl;elsecout<<" 刪除位置不合法！"<<endl;break;case 4:/銷毀鏈表char ok;cout<<" 確定要銷毀鏈表嗎？（y/n ） "<<endl;cin>>ok; ifok='y&

18、#39;|ok='y'l.clear;break;case 5:/查找cout<<" 請輸入查找元素："<<endl;cin>>elem; ifl.searchelemcout<<" 查找勝利！ "<<endl;elsecout<<" 查找失?。?"<<endl;break;case 0:/退出return; default:cout<<" 您輸入的選項有誤,請重新輸入："（2）測試用例精品學(xué)習(xí)資料精選學(xué)

19、習(xí)資料 - - - 歡迎下載5 擴(kuò)展提高（1）刪除鏈表中全部值為x 的元素結(jié)點(diǎn)；（2）單鏈表類的拷貝構(gòu)造函數(shù)設(shè)計；（3）隨機(jī)數(shù)使用方法；（4）單鏈表的銷毀操作；內(nèi)容2約瑟夫（ joseph ）環(huán)問題1 問題描述約瑟夫問題的一種描述為：編號為1, 2, n 的 n 個人按順時針方向圍坐一圈、 從某人開頭,從1 起,報到k 就出圈,下一個人再從1 報起,如此下去直到圈中只有一人為止, 最終一人稱為優(yōu)勝者；求優(yōu)勝者的編號；2 數(shù)據(jù)結(jié)構(gòu)設(shè)計對于 n 個人的編號（ 1, 2, n）可用線性表進(jìn)行組織,因為n 個人按順時針方向圍坐一圈,故可用循環(huán)鏈表儲備方式儲備,要設(shè)計循環(huán)鏈表類和約瑟夫環(huán)類；第一要解決好

20、約瑟夫環(huán)類和循環(huán)鏈表類的關(guān)系問題,二者關(guān)系可以有三種處理方式：一為循環(huán)鏈表類作為約瑟夫環(huán)類的基類；二為約瑟夫環(huán)類中含有循環(huán)鏈表類的一個對象作為其成員；三為循環(huán)鏈表僅作為約瑟夫環(huán)類求優(yōu)勝者操作的過程中所借助的手段,即作為為約瑟夫環(huán)類求優(yōu)勝者編號成員函數(shù)intgetwinner的局部變量來處理；這里僅以第三種方式為 例給出設(shè)計過程；（1） ） 循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載template<class t>struct node/結(jié)點(diǎn)結(jié)構(gòu)t data;/結(jié)點(diǎn)數(shù)據(jù)node*link;nodelink=null; nodet e、node*next=null

21、data=e; link=next;（2） ） 循環(huán)鏈表類循環(huán)鏈表類主要供應(yīng)構(gòu)造.輸出.插入.刪除.查找.后移.銷毀等操作,其數(shù)據(jù)成員主要有循環(huán)鏈表的頭指針（其實指向循環(huán)鏈表中任一結(jié)點(diǎn)的指針均可,故設(shè)置current）； template<class t>class circlelinklist/不帶表頭結(jié)點(diǎn)的循環(huán)鏈表類private:node<t> *current、*front;/current指向某結(jié)點(diǎn), front指向 current前驅(qū)public:circlelinklist :currentnull、frontnull /構(gòu)建空循環(huán)鏈表circlelink

22、list t *d、int msize; /利用 d 數(shù)組元素構(gòu)建循環(huán)鏈表 circlelinklist ;/析構(gòu)函數(shù)bool insertafterconst t&x;/在 current所指結(jié)點(diǎn)之后插入x bool removecurrentt&x;/刪除 current所指結(jié)點(diǎn)void movenextint n=1;/current后移 n 次t getcurrentdatareturn current->data;bool tolocatioint &t;/讓 current指向 t 結(jié)點(diǎn),如沒有就current不移動void output const

23、;/輸出循環(huán)鏈表; / class circlelinklist（3） ） 約瑟夫環(huán)類約瑟夫環(huán)類供應(yīng)構(gòu)造和設(shè)置圈中人數(shù)numofboy（編號為1numofboy）.報數(shù)起始點(diǎn)startposition.報數(shù)間隔interval,并能由此求得最終優(yōu)勝者；class joseph /約瑟夫環(huán)類private:int numofboy; /圈中人數(shù)int startposition; /報數(shù)起始點(diǎn)int interval;/報數(shù)間隔public:josephint boys、int start、int m:精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載numofboyboys、startpositi

24、onstart、intervalm/構(gòu)造函數(shù)void setnumofboyint numnumofboy=num;/重置圈中人數(shù)void setstartpositionint startstartposition=start;/重置起始點(diǎn)void setintervalint interinterval=inter;/重置報數(shù)間隔int getwinner;/求得最終優(yōu)勝者編號void print;/輸出約瑟夫環(huán);3 算法設(shè)計與實現(xiàn)（1） ） 求約瑟夫環(huán)優(yōu)勝者a) 原理：currentfront12345依據(jù)總?cè)藬?shù) numofboy建立編號分別為 1numofboy的循環(huán)鏈表, 如上圖所示

25、, 設(shè)立一個報數(shù)器,先找到報數(shù)起始點(diǎn),然后從起始點(diǎn)開頭,從 1 開頭報數(shù),報到間隔 interval 就出圈（即刪除該結(jié)點(diǎn)） ,如此下去,直到循環(huán)鏈表中只有一個元素為止,最終一個元素即為優(yōu)勝者；b) 算法步驟： 給定圈中人數(shù)numofboy.報數(shù)起始點(diǎn)startposition.報數(shù)間隔interval； 以編號 1numofboy創(chuàng)建循環(huán)鏈表； 找到報數(shù)起始結(jié)點(diǎn)startposition； 當(dāng)圈中人數(shù)大于1 時,重復(fù)做：從當(dāng)前結(jié)點(diǎn)依次從1 報到 interval,就刪除當(dāng)前結(jié)點(diǎn),并將當(dāng)前指針指向下一結(jié)點(diǎn)； 返回圈中最終剩下的人的編號；c) 實現(xiàn)int joseph:getwinner/獲得最

26、終優(yōu)勝者circlelinklist<int>boys;forint i=0;i<numofboy;i+/創(chuàng)建循環(huán)鏈表 、 編號依次為1numofboyint temp=i+1; boys.insertaftertemp;boys.tolocatioinstartposition;/找到報數(shù)起點(diǎn)cout<<endl<<"依次出列的小孩為："<<endl; fori=1;i<numofboy;i+/numofboy-1個小孩出圈int x;boys.movenextinterval-1; /報數(shù)boys.remove

27、currentx; /出圈精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載cout<<x<<" " /輸出出圈編號return boys.getcurrentdata; /返回優(yōu)勝者編號（2） ） 輸出約瑟夫環(huán)void joseph:print/輸出約瑟夫環(huán)cout<<" 圈中人數(shù) :"<< numofboy<<endl;cout<<" 報數(shù)起始點(diǎn) :"<< startposition <<endl;cout<<" 報數(shù)

28、間隔 :"<< interval <<endl;（3） ） 構(gòu)造循環(huán)鏈表template<class t> circlelinklist<t>:circlelinklistt *d、int msize/ 構(gòu)造函數(shù) 、 將 d 數(shù)組中的 msize 個元素創(chuàng)建循環(huán)鏈表/ 采納前插法創(chuàng)建；int i;node<t> *p;current=new node<t> current->data=dmsize-1; front=current;fori=msize-2;i>=0;i-p=new node<t

29、>di、current; current=p;front->link=current;（4） ） 析構(gòu)循環(huán)函數(shù)template<class t>circlelinklist<t>:circlelinklist/析構(gòu)函數(shù)whilecurrent.=front/銷毀循環(huán)鏈表node<t> *r=current; current=current->link; delete r;delete current;（5） ） 循環(huán)鏈表插入操作template<class t>bool circlelinklist<t>:inser

30、tafterconst t&x/在 current所指結(jié)點(diǎn)之后插入x、current指向 x 結(jié)點(diǎn)精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載node<t> *s=new node<t>x; if.sreturn false;if.current /原循環(huán)鏈表為空current=front=s->link=s; else /原循環(huán)鏈表非空s->link=current->link; current->link=s; front=current; current=s;return true;（6） ） 循環(huán)鏈表刪除操作template&l

31、t;class t>bool circlelinklist<t>:removecurrentt&x /刪除 current所指結(jié)點(diǎn)if.current/循環(huán)鏈表為空return false; x=current->data;ifcurrent=front/鏈表中只有一個元素精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載elsedelete current; current=front=null;front->link=current->link;/修改鏈表指針delete current; current=front->link;精品學(xué)習(xí)資料精

32、選學(xué)習(xí)資料 - - - 歡迎下載return true;（7） ） 循環(huán)鏈表輸出template<class t>void circlelinklist<t>:output const/輸出循環(huán)鏈表if.current/循環(huán)鏈表為空return ; node<t> *p=current; docout<<p->data<<" "精品學(xué)習(xí)資料精選學(xué)習(xí)資料 - - - 歡迎下載p=p->link;whilep.=current; cout<<endl;（8） ） 循環(huán)鏈表后移操作template<class t>void circlelinklist<t>: movenextint k/current后 移 k 次forint i=1;i<=k;i+front=current; / front