用雙向循環(huán)鏈表求解約瑟夫環(huán)

上傳人：奔*** IP屬地：河北更新時間：2024-03-03 格式：doc 頁數(shù)：9 大?。?2.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩8頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　用雙向循環(huán)鏈表求解約瑟夫環(huán)　　學(xué)校：東北大學(xué)　　專業(yè)：計算機(jī)科學(xué)與技術(shù)　　1.問題描述　　Josephus排列問題定義如下：假設(shè)n個競賽者排成一個環(huán)形。給定一個正整數(shù)m≤n，

2、從第1人開始，沿環(huán)計數(shù)，第m人出列。這個過程一直進(jìn)行到所有人都出列為止。最后出列者為優(yōu)勝者。全部出列次序定義了1，2，…n的一個排列。稱為（n，m）Josephus排列。例如，（7，3）Josephus排列為3,6,2,7,5,1,4。　　【實(shí)驗(yàn)要求】　　設(shè)計求解Josephus排列問題程序。

3、　?。?）采用順序表、單鏈表或雙向循環(huán)鏈表等數(shù)據(jù)結(jié)構(gòu)。　?。?）采用雙向循環(huán)鏈表實(shí)現(xiàn)Josephus排列問題，且奇數(shù)次順時針輪轉(zhuǎn)，偶數(shù)次逆時針輪轉(zhuǎn)。　?。?）推薦采用靜態(tài)鏈表實(shí)現(xiàn)Josephus排列問題。　　2.需求分析<p&g

4、t;　　本程序要求根據(jù)輸入的人數(shù)n和給定的正整數(shù)m，求得約瑟夫排列，且奇數(shù)次順時針輪轉(zhuǎn)，偶數(shù)次逆時針輪轉(zhuǎn)。故可利用雙向循環(huán)鏈表建立存儲結(jié)構(gòu)，利用雙向循環(huán)鏈表的遍歷與刪除操作實(shí)現(xiàn)功能要求。　　3.概要設(shè)計　　1.抽象數(shù)據(jù)類型定義：　　typedef struct DuLNode

5、　　{　　int data;　　struct DuLNode *prior;　　struct DuLNode *next;　　}DuLNode,*DuLi

6、nkList; //定義雙向循環(huán)鏈表 　　基本操作　　int InitList_Dul(DuLinkList &L) //建立一個只含頭結(jié)點(diǎn)的空雙向循環(huán)鏈表　　int CreateList_DuL(DuLinkList &L,int n)

7、 //建立一個帶頭結(jié)點(diǎn)的含n個元素的雙向循環(huán)鏈表L　　int ListDelete_DuL(DuLinkList &L,DuLinkList x) //刪除指針x指向的結(jié)點(diǎn)　　3.設(shè)計思路　　首先建立一個雙向循環(huán)鏈表作為存儲結(jié)構(gòu)，每個結(jié)點(diǎn)的數(shù)據(jù)域存儲每個人的編號，

8、然后根據(jù)給定的m值對整個鏈表進(jìn)行遍歷，找到所要找的結(jié)點(diǎn)后，輸出該結(jié)點(diǎn)的數(shù)據(jù)域的值，并在雙向循環(huán)鏈表中刪除該結(jié)點(diǎn)，重復(fù)這樣的操作，一直到所有的人都出列，依次輸出的數(shù)列即為所求的Josephus排列。　　4.詳細(xì)設(shè)計　　typedef struct DuLNode

9、;　　{　　int data;　　struct DuLNode *prior;　　struct DuLNode *next;　　}DuLNode,*DuLinkList; //定義

10、雙向循環(huán)鏈表　　int InitList_Dul(DuLinkList &L) //建立一個只含頭結(jié)點(diǎn)的空雙向循環(huán)鏈表　　{　　L=(DuLinkList) malloc(sizeof(DuLNode));　　if

11、(!L) return ERROR;　　L->data=0;　　L->next=L;　　L->prior=L;　　return OK;　　}<

12、;p>　　int CreateList_DuL(DuLinkList &L,int n) //建立一個帶頭結(jié)點(diǎn)的含n個元素的雙向循環(huán)鏈表L　　{　　DuLinkList p,q;　　int i;</p&g

13、t;　　q=L;　　for(i=0;i<n;i++)　　{　　p=(DuLinkList)malloc(sizeof(DuLNode));　　p->data=i+

14、1; //m值的自動獲取　　p->next=q->next;　　q->next=p;　　p->prior=q;　　L->prior=p;　　q

15、=p;　　}　　return OK;　　}　　int ListDelete_DuL(DuLinkList &L,DuLinkList x) //刪除指針x指向的

16、結(jié)點(diǎn)　　{　　x->prior->next=x->next;　　x->next->prior=x->prior;　　free(x);&l

17、t;p>　　return 0;　　}　　int main()　　{　　int n,m;&l

18、t;p>　　int i=1;　　cin>>n;　　DuLinkList S;　　InitList_Dul(S);　　CreateList_DuL(S,n);

19、　　cin>>m;　　DuLinkList a=S->next;//a指向第一個結(jié)點(diǎn)（不是頭結(jié)點(diǎn)）　　if(m%2==1) //奇數(shù)次順時針轉(zhuǎn)　　{

20、while(!(S->next==S->prior)) //當(dāng)剩下最后一個人時（此時還有頭結(jié)點(diǎn)）時退出循環(huán)　　{　　if(i==m)　　{

21、DuLinkList p;　　if(a->data==0)　　a=a->next;//跳過頭結(jié)點(diǎn)　　p=a;　　a=a->next;　　cout<<p->d

22、ata<<" ";　　ListDelete_DuL(S,p); //刪除節(jié)點(diǎn)p　　i=1;　　}　　else

23、;　　{　　if(a->data==0)　　a=a->next;//跳過頭結(jié)點(diǎn)　　a=a->next;　　i++;

24、　　}　　}　　cout<<S->next->data<<endl; //輸出最后一個出列人的的編號　　free(S->next);　　free(S);

25、 //釋放除頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn)　　}　　else //偶數(shù)次逆時針轉(zhuǎn)　　{　　while(!(S->next==S->prior)) //當(dāng)剩下最后一個人時（此時還有頭結(jié)

26、點(diǎn)）時退出循環(huán)　　{　　if(i==m)　　{　　DuLinkList p;　　if(a->data==0)&

27、lt;/p>　　a=a->prior; //跳過頭結(jié)點(diǎn)　　p=a;　　a=a->prior;　　cout<<p->data<<" ";　　L

28、istDelete_DuL(S,p); //刪除節(jié)點(diǎn)p　　i=1;　　}　　else　　{

29、　　if(a->data==0)　　a=a->prior; //跳過頭結(jié)點(diǎn)　　a=a->prior;　　i++;　　}<p&g

30、t;　　}　　cout<<S->next->data<<endl; //輸出最后一個出列人的的編號　　free(S->next);　　free(S); //釋放除頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn)&

31、lt;b>　　}　　return 0;　　}　　5.調(diào)試分析　　1. 遇到的問題：</p

32、>　　（1）開始對雙向循環(huán)鏈表的刪除操作的指針改變順序出現(xiàn)了問題，導(dǎo)致刪除結(jié)點(diǎn)時出現(xiàn)了錯誤；　?。?）雙向循環(huán)鏈表中帶有頭結(jié)點(diǎn)，而頭結(jié)點(diǎn)的數(shù)據(jù)域是空的（該程序中設(shè)為0），因此在對雙向循環(huán)鏈表進(jìn)行遍歷和刪除操作時，必須判斷該結(jié)點(diǎn)是否是頭結(jié)點(diǎn)，如果是，必須跳過該結(jié)點(diǎn)；　　2.收獲：</p

33、>　?。?）通過對雙向循環(huán)鏈表的建立、遍歷、刪除等操作的實(shí)現(xiàn)，對指針和鏈表了解得更加透徹，掌握得更加牢固；　?。?）對頭結(jié)點(diǎn)問題的特殊處理，使自己解決問題的能力有了提升。　　6.測試結(jié)果　　說明：若m是奇數(shù)，順時針遍歷雙向循環(huán)鏈表；若m是偶數(shù)，逆時

34、針遍歷雙向循環(huán)鏈表。　　附錄：程序源代碼　　/*****************************************************************************　　約瑟夫環(huán)問題求解

35、　東北大學(xué) 計算機(jī)科學(xué)與技術(shù)　　*****************************************************************************/　　#include<iostream>　　#include<conio.h>

36、　　#include<cstdlib>　　using namespace std;　　# define OK 1　　# define ERROR 0　　typedef struct DuLNode&

37、lt;b>　　{　　int data;　　struct DuLNode *prior;　　struct DuLNode *next;　　}DuLNode,*DuLinkList;

38、 //定義雙向循環(huán)鏈表　　int InitList_Dul(DuLinkList &L) //建立一個只含頭結(jié)點(diǎn)的空雙向循環(huán)鏈表　　{　　L=(DuLinkList) malloc(sizeof(DuLNode));<p&

39、gt;　　if(!L) return ERROR;　　L->data=0;　　L->next=L;　　L->prior=L;　　return OK;　　}</p&g

40、t;　　int CreateList_DuL(DuLinkList &L,int n) //建立一個帶頭結(jié)點(diǎn)的含n個元素的雙向循環(huán)鏈表L　　{　　DuLinkList p,q;　　int i;<

41、/p>　　q=L;　　for(i=0;i<n;i++)　　{　　p=(DuLinkList)malloc(sizeof(DuLNode));　　p->dat

42、a=i+1; //m值的自動獲取　　p->next=q->next;　　q->next=p;　　p->prior=q;　　L->prior=p;

43、;　　q=p;　　}　　return OK;　　}　　int ListDelete_DuL(DuLinkList &L,DuLinkList x) //刪除指針x指

44、向的結(jié)點(diǎn)　　{　　x->prior->next=x->next;　　x->next->prior=x->prior;　　free(x);

45、　　return 0;　　}　　int main()　　{　　while(1){ //主程序循環(huán)執(zhí)行<p&

46、gt;　　int n,m;　　int i=1;　　cout<<"請輸入競賽者人數(shù)n:"<<endl;　　cin>>n;&

47、lt;p>　　DuLinkList S;　　InitList_Dul(S);　　CreateList_DuL(S,n);　　cout<<"請輸入正整數(shù)m:"<<endl;　　cin>>m;&l

48、t;/b>　　cout<<"("<<n<<","<<m<<")"<<"Josephus排列(奇數(shù)次順時針輪轉(zhuǎn)，偶數(shù)次逆時針輪轉(zhuǎn)）為："<<endl;　　DuLinkList a=S-&g

49、t;next;//a指向第一個結(jié)點(diǎn)（不是頭結(jié)點(diǎn)）　　if(m%2==1) //奇數(shù)次順時針轉(zhuǎn)　　{　　while(!(S->next==S->prior)) //當(dāng)剩下最后一個人時（此時還有頭結(jié)點(diǎn)）時退出循環(huán)&l

50、t;b>　　{　　if(i==m)　　{　　DuLinkList p;　　if(a->data==0)　　a=a->

51、next;//跳過頭結(jié)點(diǎn)　　p=a;　　a=a->next;　　cout<<p->data<<" ";　　ListDelete_DuL(S,p); //刪除節(jié)點(diǎn)p</p&g

52、t;　　i=1;　　}　　else　　{　　if(a->data==0)

53、　　a=a->next;//跳過頭結(jié)點(diǎn)　　a=a->next;　　i++;　　}　　}<p&g

54、t;　　cout<<S->next->data<<endl;//輸出最后一個出列人的的編號　　free(S->next);　　free(S);//釋放除頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn)　　}　　else

55、 //偶數(shù)次逆時針轉(zhuǎn)　　{　　while(!(S->next==S->prior))//當(dāng)剩下最后一個人時（此時還有頭結(jié)點(diǎn)）時退出循環(huán)　　{　　if(i==m)&

56、lt;/b>　　{　　DuLinkList p;　　if(a->data==0)　　a=a->prior;//跳過頭結(jié)點(diǎn)　　p=a;&l

57、t;/p>　　a=a->prior;　　cout<<p->data<<" ";　　ListDelete_DuL(S,p); //刪除節(jié)點(diǎn)p　　i=1;

58、　　}　　else　　{　　if(a->data==0)　　a=a->prior;//跳過頭結(jié)點(diǎn)　　a=

59、a->prior;　　i++;　　}　　}　　cout<<S->next->data<<endl;//輸出最后一個出

60、列人的的編號　　free(S->next);　　free(S);//釋放除頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn)　　}　　} //while(1)　　return 0;

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

用雙向循環(huán)鏈表求解約瑟夫環(huán)

文檔簡介

溫馨提示

最新文檔

評論

用雙向循環(huán)鏈表求解約瑟夫環(huán)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載