數(shù)據(jù)結構_約瑟夫環(huán)_課程設計

1、<p>　　數(shù)據(jù)結構 課程設計報告</p><p>　　設計題目： </p><p>　　班 級： </p><p>　　組 長： 姓名（學號） </p><p>　　組 員：姓名（學號）… </p>

2、;<p>　　指導教師： </p><p>　　完成日期： </p><p><b>　　成績：</b></p><p><b>　　目 錄</b></p><p><b>　　1需求分析3

3、</b></p><p><b>　　1.1功能分析3</b></p><p><b>　　1.2設計平臺3</b></p><p><b>　　2概要設計3</b></p><p>　　2.1類LinkList3</p><p>　

4、　2.2類Joseph4</p><p>　　2.3類異常處理4</p><p>　　3詳細設計和實現(xiàn)4</p><p>　　3.1創(chuàng)建結點Node4</p><p>　　3.2創(chuàng)建雙向循環(huán)鏈表5</p><p>　　3.3從鏈表中刪除結點6</p><p>　　4調(diào)試與操作說明1

5、0</p><p>　　4.1調(diào)試情況10</p><p>　　4.2操作說明10</p><p><b>　　5設計總結11</b></p><p>　　參 考 文 獻12</p><p><b>　　附錄12</b></p><p>&l

6、t;b>　　1需求分析</b></p><p><b>　　1.1功能分析</b></p><p>　　本次選做的課程設計是改進約瑟夫(Joseph)環(huán)問題。約瑟夫環(huán)問題是一個古老的數(shù)學問題，本次課題要求用程序語言的方式解決數(shù)學問題。此問題僅使用單循環(huán)鏈表就可以解決此問題。而改進的約瑟夫問題通過運用雙向循環(huán)鏈表，同樣也能方便地解決。</p>

7、;<p>　　在建立雙向循環(huán)鏈表時，因為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結點的數(shù)據(jù)域的值定為生成結點時的順序號和每個人持有的密碼。進行操作時，用一個指針current指向當前的結點，指針front始終指向頭結點。然后建立雙向循環(huán)鏈表，因為每個人的密碼是通過rand()函數(shù)隨機生成的，所以指定第一個人的順序號，找到結點，不斷地從鏈表中刪除鏈結點，直到鏈表剩下最后一個結點，通過一系列的循環(huán)就可以解決改進約瑟夫環(huán)

8、問題。</p><p>　　1、本演示程序中，利用單向循環(huán)鏈表存儲結構模擬約瑟夫問題的進行。程序運行后，首先要求用戶指定初始報數(shù)上限值，然后讀取個人的密碼?？稍On≤30。此題所用的循環(huán)鏈表中不需要“頭結點”，因此在程序設計中應注意空表和非空表的界限。</p><p>　　2、演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運

9、算命令：相應的輸入數(shù)據(jù)和運算結果顯示在其后。</p><p>　　3、程序執(zhí)行的命令包括：</p><p>　　1）構造約瑟夫環(huán)；2）執(zhí)行約瑟夫環(huán)，并輸出出列人的序號以及相應的密碼；</p><p><b>　　3）結束。</b></p><p><b>　　4、測試數(shù)據(jù)</b></p&

10、gt;<p>　　1）m的初始值為20；</p><p>　　2）n=7，7個人的密碼依次為：3、1、7、2、4、8、4。</p><p>　　3）首先m值為6，正確的出列順序應為6、1、4、7、2、3、5。</p><p><b>　　1.2設計平臺</b></p><p>　　Windows2000以上

11、操作系統(tǒng)；Microsoft Visual C++ 6.0</p><p><b>　　2概要設計</b></p><p>　　已知n個人（以編號1，2，3...n分別表示）圍成一圈。從編號為1的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復下去，直到一圈的人全部出列。這個就是約瑟夫環(huán)問題的實際場景，有一種是要通過輸入n

12、,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結構，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head。解決問題的核心步驟：首先建立一個具有n個鏈結點，無頭結點的循環(huán)鏈表。然后確定第1個報數(shù)人的位置。最后不斷地從鏈表中刪除鏈結點，直到鏈表為空。</p><p>　　改進的約瑟夫環(huán)問題與原問題思路一致，只是不再采用單循環(huán)鏈表存儲結構，而采用雙向循環(huán)鏈表，而且用一個判斷

13、語句來決定報數(shù)的方向的順時針還是逆時針。本課程設計主要采用了類的數(shù)據(jù)結構，程序中包含了兩個類：Linklist , Joseph。</p><p>　　為實現(xiàn)上述程序功能，應以單向循環(huán)鏈表表示約瑟夫環(huán)。為此，需要兩個抽象數(shù)據(jù)類型：單向循環(huán)鏈表和約瑟夫環(huán)。</p><p>　　1）、單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：</p><p>　　ADT List{</

14、p><p>　　數(shù)據(jù)對象：D={ai｜ai∈Elemset,i=1,2,…,n,n≥0}</p><p>　　數(shù)據(jù)關系：R1={＜a(i-1),ai＞｜a(i-1),ai∈D,i=2,…n}</p><p><b>　　基本操作：</b></p><p>　　InitList(&L)</p><p

15、>　　操作結果：構造一個空的鏈表L。</p><p>　　DestroyList(&L)</p><p>　　初始條件：線性表L已存在。</p><p>　　操作結果：銷毀線性表L。</p><p>　　ListLength(L)</p><p>　　初始條件：線性表L已存在。</p>&l

16、t;p>　　操作結果：返回L中數(shù)據(jù)元素個數(shù)。</p><p>　　GetElem(L,i,&e)</p><p>　　初始條件：線性表L已存在，1≤i≤ListLength(L)。</p><p>　　操作結果：用e返回L中第i個數(shù)據(jù)元素的值。</p><p>　　ListInsert(&L,I,e)</p>

17、<p>　　初始條件：線性表L已存在，1≤i≤ListLength(L)+1。</p><p>　　操作結果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。</p><p>　　ListDelete(&L,i,&e)</p><p>　　初始條件：線性表L已存在且非空，1≤i≤ListLength(L)。</p>

18、<p>　　操作結果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。</p><p>　　ListTraverse(L,visit())</p><p>　　初始條件：線性表L已存在。</p><p>　　操作結果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。 </p><p>　　

19、}ADT List</p><p>　　2)約瑟夫環(huán)的抽象數(shù)據(jù)類型定義為：</p><p><b>　　ADT Set{</b></p><p>　　數(shù)據(jù)對象：D={ai｜ai為用戶輸入的數(shù)字密碼，i=1,2,…,n,1≤n≤7}</p><p><b>　　數(shù)據(jù)關系：{}</b></p&

20、gt;<p><b>　　基本操作：</b></p><p>　　CreatSet(&L，s)</p><p>　　初始條件：L為單向循環(huán)鏈表。</p><p>　　操作結果：對鏈表中的數(shù)據(jù)域進行賦值。</p><p>　　DeleteSet(&L,i,&e)</p>

21、<p>　　初始條件：線性表L已存在且非空，1≤i≤ListLength(L)。</p><p>　　操作結果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。</p><p>　　PrintSet(L)</p><p>　　初始條件：鏈表L已存在。</p><p>　　操作結果：按輸出次序顯示每個人的密碼。</p>

22、;<p><b>　　}ADT Set</b></p><p>　　3)本程序包含四個模塊：</p><p><b>　　1、主程序模塊：</b></p><p>　　Void main(){</p><p><b>　　初始化；</b></p>

23、<p><b>　　Do{</b></p><p><b>　　接受命令；</b></p><p><b>　　處理命令；</b></p><p>　　} while (“命令”=”退出”)；</p><p><b>　　}</b></p&

24、gt;<p>　　2、約瑟夫環(huán)單元模塊——實現(xiàn)約瑟夫環(huán)的抽象數(shù)據(jù)類型；</p><p>　　3、單向循環(huán)鏈表單元模塊——實現(xiàn)單向循環(huán)鏈表的抽象數(shù)據(jù)類型；</p><p>　　4、結點結構單元模塊——定義單向循環(huán)鏈表的結點結構。</p><p>　　各模塊之間的調(diào)用關系如下：</p><p><b>　　結點結構單元模塊

25、</b></p><p><b>　　↓</b></p><p>　　單向循環(huán)鏈表單元模塊</p><p><b>　　↓</b></p><p><b>　　約瑟夫環(huán)單元模塊</b></p><p><b>　　↓</b&g

26、t;</p><p><b>　　主程序模塊</b></p><p>　　2.1類LinkList</p><p>　　主要功能是創(chuàng)建結點，每個結點數(shù)值域包括data,password,還有指示前驅結點的指針llink,和指示后繼結點的指針rlink。</p><p>　　2.2類Joseph</p>&l

27、t;p>　　主要功能是實現(xiàn)創(chuàng)建雙向循環(huán)鏈表及一些相應的操作。</p><p><b>　　2.3類異常處理</b></p><p>　　在C++程序中，可以使用try-throw-catch結構處理程序異常。采用這一程序結構能夠將使用和實現(xiàn)分離：類和函數(shù)的實現(xiàn)者使用throw語句易地錯誤類別通知使用者。使用者根據(jù)獲悉的錯誤類別采取相應的措施，這就是異常處理。&l

28、t;/p><p><b>　　3詳細設計和實現(xiàn)</b></p><p>　　改進約瑟夫環(huán)問題的基本思路和原問題基本一致，只是一個采用單循環(huán)鏈表，另一個采用雙向循環(huán)鏈表來解決問題。第一步是定義結構變量結點linklist，并在該結點下定義結點的元素域:data,password，指針域:lLink和rLink。然后建立一個由n個鏈結點，無表頭結點的雙向循環(huán)鏈表。并由構造函數(shù)

29、對結點賦值，由隨機函數(shù)rand()產(chǎn)生每個結點的password。由于每個結點的password是由隨機函數(shù)產(chǎn)生的，也就是每個結點的password是后知的，所以在一開始人為地指定一個結點的順序，由此結點開始報數(shù)。報password個數(shù)后，報到的那個結點被刪除，它的password被記錄下，由它的下一個結點開始逆方向報數(shù)………如此循環(huán)，直到循環(huán)鏈表里只剩下一個結點，那就是問題所求的結果。具體到問題上，還需要創(chuàng)建一個Joseph類，由構造

30、函數(shù)來初始化，輸入所有的人數(shù)，也就是表長，然后指定由第幾個人開始報數(shù)。在Joseph類中定義一個GetWinner()函數(shù)，由它來實現(xiàn)獲得最后的勝利者。并在該類中設置一個判斷語句來確定先由順時針報數(shù)并淘汰了一個人之后，再按逆時針順序報數(shù)，如此交替進行。</p><p>　　主要功能實現(xiàn)的程序流程圖及核心代碼。</p><p><b>　　算法流程圖：</b></

31、p><p>　　3.1創(chuàng)建結點Node</p><p>　　鏈表都是由一個個結點組成，由于結點的不同，組成的鏈表也不同。因此需要創(chuàng)建雙向鏈表結點。由于每一個結點有一個密碼和一個序號，所以可以將結點結構體定義為：</p><p>　　struct Node{ </p><p><b>　　int data;</b></p

32、><p>　　int password;</p><p>　　DNode* llink;</p><p>　　DNode* rlink;} 圖3.1 結點Dnode</p><p>　　3.2創(chuàng)建雙向循環(huán)鏈表</p><p>　　創(chuàng)建一個空雙向循環(huán)鏈表，雙向循環(huán)鏈表和每個結點包括三個

33、域:Element，</p><p>　　lLink,rLink.其中element為元素域，rLink域為指向后繼結點的指針，新增的lLink域用以指向前驅結點。雙向鏈表也可以帶表頭結點，并且也可以構成雙向循環(huán)鏈表。此時，表頭結點的rLink，lLink分別指向雙向循環(huán)鏈表的頭結點(或表頭結點)和尾結點。</p><p>　　一個結點的lLink域的指針指向它左邊結點的后部，這并不意味著

34、該結點的lLink域保存的仍是該左邊結點存儲塊的起始地址。在此處，指針指向某個結點任何部分都是等價的，都是指該存儲塊的起始位置。</p><p>　　圖3.2 單表頭的雙向循環(huán)鏈表</p><p>　　每當結點計數(shù)到某一結點時，將他的前驅結點接到他的后繼結點，然后將他的密碼值password賦給計數(shù)變量，再將此結點刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。</p>

35、<p>　　由于當某個人退出圓圈后，報數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然是圍成一個圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對應著表中結點的刪除操作，對于這種刪除操作頻繁的情況，選用效率較高的鏈表結構，為了程序指針每一次都指向一個具體的代表一個人的結點而不需要判斷，鏈表不帶頭結點。所以，對于所有人圍成的圓圈所對應的數(shù)據(jù)結構采用一個不帶頭結點的循環(huán)鏈表來描述。設頭指針為front，front始終指向頭結點，并定義指針cu

36、rrent記錄當前的結點。并根據(jù)具體情況移動（順逆時針）。</p><p>　　為了記錄退出的人的先后順序，采用一個順序表進行存儲。程序結束后再輸出依次退出的人的編號順序。由于只記錄各個結點的data值就可以。最后通過函數(shù)調(diào)用來輸出順序。要解決約瑟夫環(huán)問題，首先一點就是必須有一個環(huán)，所以第一步我們必須建立一個雙向循環(huán)鏈表。而建立一個雙向循環(huán)鏈表必須有一個空的雙向循環(huán)鏈表，然后運用尾插法建立一個雙向循環(huán)鏈表，這樣約

37、瑟夫環(huán)就創(chuàng)建出來了，接下來就是處理約瑟夫環(huán)問題。</p><p>　　3.3從鏈表中刪除結點</p><p>　　在雙向循環(huán)鏈表中，一個結點的前驅結點地址保存在該結點的lLink域中，這樣可以方便地實現(xiàn)在一個指定結點之前插入一個新結點的操作，也可以方便地刪除某個指定結點。</p><p>　　函數(shù)通過代碼：q->llink->rlink=q->rl

38、ink;q->rlink->llink=q->llink;delete q;</p><p>　　來刪除當前的那個結點q，通過循環(huán)來一次次刪除當前的結點，直到鏈表中剩下最后一個結點。</p><p><b>　　具體程序如下：</b></p><p>　　#include<stdio.h></p>&

39、lt;p>　　#include<malloc.h></p><p>　　#include<stdlib.h></p><p>　　typedef struct node //定義單循環(huán)鏈表中節(jié)點的結構</p><p><b>　　{</b></p><p>　　int num;//序列號即個

40、人的編號</p><p>　　int cipher;//個人所持有的密碼</p><p>　　struct node *next;</p><p>　　}linklist;</p><p>　　class YSFH</p><p><b>　　{</b></p><p>&

41、lt;b>　　public:</b></p><p>　　linklist *Creat(int n);</p><p>　　linklist *Select1(int m);</p><p>　　linklist *head;//頭指針指示有n個結點的單循環(huán)鏈表creat</p><p>　　protected:</

42、p><p>　　linklist *Select(linklist *head,int m);</p><p><b>　　private:</b></p><p>　　linklist *p;//存放人員信息</p><p>　　linklist *r;//臨時存放</p><p>　　linkli

43、st *q;</p><p><b>　　int k;</b></p><p><b>　　};</b></p><p>　　/*建立單循環(huán)鏈表函數(shù)*/</p><p>　　linklist *YSFH::Creat(int n)</p><p><b>　　{&l

44、t;/b></p><p>　　linklist *head;</p><p>　　linklist *p;</p><p>　　p=(linklist *)malloc(sizeof(linklist));</p><p><b>　　head=p;</b></p><p><b&g

45、t;　　p->num=1;</b></p><p>　　printf("隨機產(chǎn)生第1個人的密碼: ");</p><p>　　p->cipher=rand()%10;</p><p>　　{if(p->cipher==0)</p><p>　　p->cipher=rand()%10;

46、</p><p><b>　　}</b></p><p>　　printf("%d\n",p->cipher);</p><p><b>　　r=p;</b></p><p>　　p->next=p;</p><p>　　for(int k=2

47、;k<=n;k++)</p><p><b>　　{</b></p><p>　　p=(linklist *)malloc(sizeof(linklist));</p><p>　　p->num=k;//給每人一個編號</p><p>　　printf("隨機產(chǎn)生第%d個人的密碼: ",

48、k);</p><p>　　p->cipher=rand()%10;</p><p>　　{if(p->cipher==0)</p><p>　　p->cipher=rand()%10;</p><p><b>　　}</b></p><p>　　printf("%d

49、\n",p->cipher);</p><p>　　r->next=p;</p><p><b>　　r=p;</b></p><p><b>　　}</b></p><p>　　p->next=head;</p><p>　　return(hea

50、d);</p><p><b>　　}</b></p><p>　　/*決定出列編號*/</p><p>　　linklist *YSFH::Select1(int m)</p><p><b>　　{</b></p><p>　　return Select(head,m);

51、</p><p><b>　　}</b></p><p>　　linklist *YSFH::Select(linklist *head,int m)</p><p><b>　　{</b></p><p><b>　　q=head;</b></p><p&

52、gt;<b>　　k=1;</b></p><p>　　p=q->next;//q為p的前驅指針,p指向當前報數(shù)的人</p><p>　　printf("出列的序號依次為:");</p><p>　　//在head中的第一個結點起循環(huán)記數(shù)找第m個結點</p><p>　　while(q!=p)&

53、lt;/p><p><b>　　{</b></p><p>　　k=k+1;//報一次數(shù)</p><p>　　if(k%m==0)//所報數(shù)等于報數(shù)上限值時</p><p><b>　　{</b></p><p>　　printf("%d ",p->n

54、um);//輸出該結點的num值</p><p>　　m=p->cipher;//把該結點的cipher(密碼)值賦給m</p><p>　　q->next=p->next;//對應的節(jié)點從鏈表中刪除</p><p><b>　　free(p);</b></p><p><b>　　k=0;&

55、lt;/b></p><p>　　p=q->next;</p><p><b>　　}</b></p><p><b>　　else{</b></p><p><b>　　q=p;</b></p><p>　　p=p->next;//p

56、指向當前報數(shù)的人</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　head=p;</b></p><p>　　return(head);</p><p><b>　　}</b&g

57、t;</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int n,m;</b></p><p><b>　　m!=0;</b></p><p><b>　　YSFH Y;</

58、b></p><p>　　printf("輸入總人數(shù)n: ");</p><p>　　scanf("%d",&n);</p><p>　　Y.head=Y.Creat(n);</p><p>　　printf("隨機產(chǎn)生第一次的報數(shù)上限值m: ");</p&g

59、t;<p>　　m=rand()%10;</p><p><b>　　{</b></p><p><b>　　if(m==0)</b></p><p>　　m=rand()%10;</p><p><b>　　}</b></p><p>　

60、　printf("%d\n",m);</p><p>　　Y.head=Y.Select1(m);</p><p>　　printf("%d\n",Y.head->num);</p><p><b>　　}</b></p><p><b>　　4調(diào)試與操作說明<

61、;/b></p><p><b>　　4.1調(diào)試情況</b></p><p>　　這次的課程設計的代碼很冗長，所以等有了解題思路后，把代碼都寫上后難免會有很多錯誤。當?shù)谝淮伟颜麄€程序寫好后運行，出現(xiàn)了很多錯誤。不過經(jīng)過一點點的改正，錯誤也慢慢地變少。這也說明做事要認真，尤其做計算機這方面工作的時候，因為計算機不容許不一點點的錯誤，有了一點小錯誤和有一個大錯誤在計

62、算機看來都是一樣的，都不會得不到結果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)溢出等都是些小錯誤，但也不能松懈。因為要注意的地方很多，經(jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應手。</p><p>　　在隨機設置每個結點的password時也曾是個問題，因為我做的隨機函數(shù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來通過老師的耐心講解才得

63、以解決。</p><p>　　在調(diào)試的過程中，類的優(yōu)勢很明顯，能很簡單的把問題解決，而不需要使用的其他的一些比較復雜的方法。</p><p><b>　　4.2操作說明</b></p><p>　　生成界面如圖4.1，4.2所示：</p><p><b>　　圖4.1 生成界面</b></p&

64、gt;<p><b>　　：</b></p><p><b>　　圖4.2生成界面</b></p><p>　　當程序運行的時候會出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總人數(shù)，使用者只需輸入自己所想的總人數(shù)，系統(tǒng)便會隨機產(chǎn)生每個人對應的密碼，同時隨機產(chǎn)生第一次的報數(shù)上限值。最后系統(tǒng)會給出出列的次序，最后產(chǎn)生的編號便是此

65、次游戲的獲勝者。使用者還可按下任意鍵，進行下一次的游戲。</p><p><b>　　5設計總結</b></p><p>　　心得、體會、收獲、下一步的改進等。</p><p><b>　　參 考 文 獻</b></p><p>　　1張乃孝,裘宗燕.數(shù)據(jù)結構C++與面向對象的途徑.北京：高等教育出

66、版社，1998</p><p>　　2 周云靜．數(shù)據(jù)結構習題解析與上機指導．北京：冶金工業(yè)出版社，2004</p><p>　　3 陳慧南．數(shù)據(jù)結構—C++語言描述．北京：人民郵電出版社，2005</p><p>　　4 嚴蔚敏，吳偉民．數(shù)據(jù)結構．北京：清華大學出版社，1997</p><p>　　5 Adam Drozdek．數(shù)據(jù)結構與算法