數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(約瑟夫環(huán)）

1、<p><b>　　目錄</b></p><p><b>　　目錄1</b></p><p>　　任務(wù)書…………………………………………………………………………………….2</p><p><b>　　正 文4</b></p><p>　　一、數(shù)據(jù)結(jié)構(gòu)定義4&

2、lt;/p><p>　　1.抽象數(shù)據(jù)類型4</p><p>　　2.存儲結(jié)構(gòu)定義4</p><p><b>　　3.基本操作5</b></p><p><b>　　二、解題過程7</b></p><p><b>　　1.問題分解7</b>

3、</p><p><b>　　2.模塊結(jié)構(gòu)7</b></p><p><b>　　3.解題思路8</b></p><p><b>　　三、實現(xiàn)9</b></p><p>　　四、實驗結(jié)果13</p><p>　　1.實驗數(shù)據(jù)13<

4、;/p><p>　　2.實驗結(jié)果13</p><p>　　五、實驗小結(jié)16</p><p>　　1.數(shù)據(jù)結(jié)構(gòu)使用小結(jié)16</p><p>　　2.需完善之處17</p><p><b>　　課程設(shè)計體會19</b></p><p><b>　　參考文

5、獻20</b></p><p>　　課程設(shè)計(論文)任務(wù)書</p><p>　　軟件 　學(xué)院　　軟件工程　專業(yè)　2012 - 3　班 </p><p>　　一、課程設(shè)計(論文)題目　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　</p><p>　　二、課程設(shè)計(論文)工作自 2013 年 12月 24日起至 2013 年 12月 26 日止。&l

6、t;/p><p>　　三、課程設(shè)計(論文) 地點: 軟件工程實訓(xùn)中心 308 </p><p>　　四、課程設(shè)計(論文)內(nèi)容要求：</p><p>　　1．本課程設(shè)計的目的</p><p>　?。?）使學(xué)生熟練掌握抽象數(shù)據(jù)類型的組織和定義； </p><p>　　（

7、2）使學(xué)生熟練掌握數(shù)據(jù)類型的定義和實現(xiàn)； </p><p>　?。?）培養(yǎng)學(xué)生組織和分析數(shù)據(jù)的能力；</p><p>　?。?）培養(yǎng)學(xué)生分析和應(yīng)用基于不同數(shù)據(jù)結(jié)構(gòu)的算法的能力；</p><p>　?。?）提高學(xué)生的科技論文寫作能力。</p><p><b>　　2．基本要求：</b></p><p&g

8、t;　　每位同學(xué)在以下題目中任選一題（在方框中打勾），獨立完成課程設(shè)計：</p><p>　　約瑟夫環(huán)：參見《數(shù)據(jù)結(jié)構(gòu)題集》P179。</p><p>　　□ 赫夫曼編/譯碼器：參見《數(shù)據(jù)結(jié)構(gòu)題集》P149。</p><p>　　□ 教學(xué)計劃編制問題：參見《數(shù)據(jù)結(jié)構(gòu)題集》P150。</p><p>　　3．課程設(shè)計論文編寫要求</p&g

9、t;<p>　?。?）要按照書稿的規(guī)格打印謄寫課設(shè)報告；</p><p>　?。?）報告分為封面、任務(wù)書（本文檔）、正文、</p><p>　　課程設(shè)計體會和參考文獻四部分；</p><p>　　學(xué)生簽名： </p><p><b>　　年 月 日</b></p>

10、<p>　　課程設(shè)計(論文)評審意見</p><p>　　（1）題目分析（20分）：優(yōu)（?。?、良（?。?、中（?。?、一般（?。?、差（　）； </p><p>　?。?）流程分析?。?0分）：優(yōu)（?。?、良（?。?、中（?。⒁话悖ā。?、差（?。?； </p><p>　?。?）數(shù)據(jù)定義?。?0分）：優(yōu)（　）、良（　）、中（?。?、一般（　）、差（　）；&l

11、t;/p><p>　　（4）代碼編寫?。?0分）：優(yōu)（　）、良（?。?、中（?。⒁话悖ā。⒉睿ā。?；</p><p>　?。?）創(chuàng)新能力　（10分）：優(yōu)（?。⒘迹ā。?、中（?。⒁话悖ā。?、差（　）；</p><p>　　（6）格式規(guī)范性、設(shè)計態(tài)度及考勤是否降等級：是（?。⒎瘢ā。?lt;/p><p>　　評閱人： 　　　 職稱：

12、講 師 </p><p><b>　　2014年1月6日</b></p><p><b>　　正 文</b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)定義</b></p><p><b>　　抽象數(shù)據(jù)類型</b></p><p>　　本

13、設(shè)計中用到的數(shù)據(jù)結(jié)構(gòu)ADT定義如下：</p><p><b>　　ADT Node{</b></p><p>　　數(shù)據(jù)對象：D={id,key|id∈Node,key∈Node,id>=0;key>=0}</p><p>　　數(shù)據(jù)關(guān)系：R={<id,key>|id,key∈D, id>=0;key>=0}&l

14、t;/p><p><b>　　基本操作：</b></p><p>　　CreatList(&pHead,k)</p><p>　　操作結(jié)果：構(gòu)造單循環(huán)鏈表</p><p>　　PrintList(pHead)</p><p>　　初始條件：鏈表已存在</p><p>　

15、　操作結(jié)果：打印輸出鏈表數(shù)據(jù)元素</p><p>　　Joesph(&pHead,m)</p><p>　　初始條件：鏈表已存在，m為出列者所在編號</p><p>　　操作結(jié)果：刪除出隊編號所在結(jié)點，并將該結(jié)點的key作為新的key，從該結(jié)點的下一結(jié)點移動</p><p>　　} ADT Node</p><p&

16、gt;<b>　　存儲結(jié)構(gòu)定義</b></p><p>　　數(shù)據(jù)存儲結(jié)構(gòu)的C語言定義如下：</p><p>　　typedef struct Node{//帶頭結(jié)點的單循環(huán)鏈表 </p><p>　　int id;//編號 </p><p>　　int key;//密碼 </p><p>　

17、　struct Node *next;</p><p>　　}Node,*CircularList;</p><p><b>　　基本操作</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)的基本操作實現(xiàn)如下：</p><p>　　構(gòu)造單循環(huán)鏈表函數(shù)：</p><p>　　void CreatList(Circ

18、ularList *ppHead,const int k){</p><p>　　int i,ikey;</p><p>　　Node *pNew,*pCur;</p><p>　　for(i=1;i<=k;i++){</p><p>　　printf("請輸入第%d個人所持有的密碼：",i);</p>

19、<p>　　scanf("%d",&ikey);</p><p>　　pNew=(Node *)malloc(sizeof(Node));</p><p>　　pNew->id=i;</p><p>　　pNew->key=ikey;</p><p>　　pNew->next=NUL

20、L;</p><p>　　if(*ppHead==NULL){</p><p>　　*ppHead=pCur=pNew;</p><p>　　pCur->next=*ppHead;</p><p><b>　　}</b></p><p><b>　　else{</b>&

21、lt;/p><p>　　pNew->next=pCur->next;</p><p>　　pCur->next=pNew;</p><p>　　pCur=pNew;</p><p><b>　　}</b></p><p><b>　　}</b></p>

22、;<p>　　printf("約瑟夫環(huán)已建成，可以開始進入報數(shù)游戲！\n");</p><p><b>　　}</b></p><p>　　輸出單循環(huán)鏈表函數(shù)：</p><p>　　void PrintList(const Node *pHead){</p><p>　　const N

23、ode *pCur=pHead;</p><p>　　if(!pHead) printf("單循環(huán)鏈表是空的！\n");</p><p><b>　　do{</b></p><p>　　printf("第%d個人所持有的密碼是：%d\n",pCur->id,pCur->key);</p&

24、gt;<p>　　pCur=pCur->next;</p><p>　　}while(pCur!=pHead);</p><p><b>　　}</b></p><p>　　3、約瑟夫環(huán)規(guī)則刪除結(jié)點并輸出結(jié)點信息函數(shù)： </p><p>　　void Joesph(CircularList *ppHe

25、ad,int ikey){</p><p>　　int iCount,iFlag=1;</p><p>　　Node *pPrv,*pCur,*pDel;</p><p>　　pPrv=pCur=*ppHead;//將pPrv初始為指向尾結(jié)點，為刪除做好準(zhǔn)備</p><p>　　while(iFlag){</p><p&

26、gt;　　for(iCount=1;iCount<=ikey;iCount++){//移動iCount-1趟指針 </p><p>　　pPrv=pCur;</p><p>　　pCur=pCur->next;</p><p><b>　　}</b></p><p>　　if(pPrv==pCur) iFla

27、g=0;//最后一結(jié)點</p><p>　　pDel=pCur;//刪除pCur指向的結(jié)點 </p><p>　　pPrv->next=pCur->next;</p><p>　　pCur=pCur->next;</p><p>　　printf("第%d個人出列，所持密碼為:%d\n",pDel-&g

28、t;id,pDel->key);</p><p>　　ikey=pDel->key-1;</p><p>　　free(pDel);</p><p><b>　　}</b></p><p>　　ppHead=NULL;</p><p><b>　　}</b><

29、;/p><p><b>　　解題過程</b></p><p><b>　　問題分解</b></p><p>　　該問題主要應(yīng)實現(xiàn)以下功能：建立約瑟夫環(huán)并解約瑟夫環(huán)，直到所有玩家出列，并順序輸出出列編號。它主要解決約瑟夫環(huán)問題。</p><p><b>　　模塊結(jié)構(gòu)</b></

30、p><p>　　系統(tǒng)主要由 5個模塊組成，分別是：</p><p>　　（1）、構(gòu)造鏈表模塊</p><p>　　void CreatList(CircularList *ppHead,const int k)</p><p>　　（2）、輸出鏈表模塊</p><p>　　void PrintList(const Node

31、 *pHead)</p><p>　?。?）、約瑟夫環(huán)函數(shù)模塊</p><p>　　void Joesph(CircularList *ppHead,int ikey)</p><p><b>　?。?）、菜單模塊</b></p><p>　　void menu()</p><p><b&g

32、t;　?。?）、主函數(shù)模塊</b></p><p>　　int main(int argc,char *argv[])</p><p>　　模塊之間的結(jié)構(gòu)如下：</p><p><b>　　解題思路</b></p><p><b>　　各模塊的實現(xiàn)步驟為</b></p>&

33、lt;p>　?。?）、創(chuàng)建單循環(huán)鏈表函數(shù)模塊：用一個for循環(huán)來給鏈表的每一個結(jié)點分配空間，輸入每個人所持有的密碼key，并創(chuàng)建結(jié)點。然后用頭插法建立一個帶結(jié)點的單循環(huán)鏈表。</p><p>　?。?）、輸出單循環(huán)鏈表模塊：先判斷表是否為空，若不空則輸出結(jié)點信息，同時指針向后移，指向下一結(jié)點，繼續(xù)輸出直到指針再次指向頭結(jié)點為止，輸出完畢。</p><p>　?。?）、約瑟夫環(huán)函數(shù)模塊

34、：建立一個iFlag標(biāo)簽，值為1執(zhí)行循環(huán)語句，值為0跳出循環(huán)。While循環(huán)語句里的for循環(huán)實現(xiàn)報數(shù)功能，設(shè)指針pPrv和指針pCur，移動結(jié)點到ikey,再刪除第ikey個結(jié)點并把該結(jié)點的key值賦給ikey，再從該結(jié)點的下一個結(jié)點開始移動，重復(fù)上述過程，直到結(jié)點全部出列。結(jié)束while循環(huán)。</p><p>　?。?）、菜單模塊：用簡單的printf設(shè)計出具有一定美觀的菜單界面，使得程序所要實現(xiàn)的功能一目了

35、然，又可以供操作者自主選擇。</p><p>　?。?）主函數(shù)模塊：設(shè)置標(biāo)簽iflag，供用戶選擇輸入數(shù)字操作。若為1則開始或繼續(xù)約瑟夫環(huán)游戲；若為0，退出游戲。游戲開始后，首先得設(shè)置參與者人數(shù)n以及初始報數(shù)上限m，調(diào)用CreatList()創(chuàng)建約瑟夫環(huán)，然后調(diào)用PrintList()輸出當(dāng)前已輸入的信息以確認(rèn)信息無誤，再調(diào)用Joesph()函數(shù)解決約瑟夫環(huán)問題。結(jié)束后再用iflag標(biāo)志位判斷是否繼續(xù)。</

36、p><p><b>　　實現(xiàn)</b></p><p><b>　　代碼及注釋：</b></p><p>　　//#include"consts.h"</p><p>　　#include<stdio.h></p><p>　　#include<

37、;stdlib.h></p><p>　　typedef struct Node{//帶頭結(jié)點的單循環(huán)鏈表 </p><p>　　int id;//編號 </p><p>　　int key;//密碼 </p><p>　　struct Node *next;</p><p>　　}Node,*Circul

38、arList;</p><p>　　void CreatList(CircularList *ppHead,const int k){//構(gòu)建單循環(huán)鏈表 </p><p>　　int i,ikey;</p><p>　　Node *pNew,*pCur;</p><p>　　for(i=1;i<=k;i++){</p>

39、<p>　　printf("請輸入第%d個人所持有的密碼：",i);</p><p>　　scanf("%d",&ikey);</p><p>　　pNew=(Node *)malloc(sizeof(Node));</p><p>　　pNew->id=i;</p><p>

40、　　pNew->key=ikey;</p><p>　　pNew->next=NULL;</p><p>　　if(*ppHead==NULL){</p><p>　　*ppHead=pCur=pNew;</p><p>　　pCur->next=*ppHead;</p><p><b>　

41、　}</b></p><p><b>　　else{</b></p><p>　　pNew->next=pCur->next;</p><p>　　pCur->next=pNew;</p><p>　　pCur=pNew;</p><p><b>　　}&l

42、t;/b></p><p><b>　　}</b></p><p>　　printf("約瑟夫環(huán)已建成，可以開始進入報數(shù)游戲！\n");</p><p><b>　　}</b></p><p>　　void PrintList(const Node *pHead){//輸

43、出單循環(huán)鏈表 </p><p>　　const Node *pCur=pHead;</p><p>　　if(!pHead) printf("單循環(huán)鏈表是空的！\n");</p><p><b>　　do{</b></p><p>　　printf("第%d個人所持有的密碼是：%d\n&qu

44、ot;,pCur->id,pCur->key);</p><p>　　pCur=pCur->next;</p><p>　　}while(pCur!=pHead);</p><p><b>　　}</b></p><p>　　void Joesph(CircularList *ppHead,int ik

45、ey){//約瑟夫環(huán)規(guī)則刪除結(jié)點并輸出結(jié)點信息 </p><p>　　int iCount,iFlag=1;</p><p>　　Node *pPrv,*pCur,*pDel;</p><p>　　pPrv=pCur=*ppHead;//將pPrv初始為指向尾結(jié)點，為刪除做好準(zhǔn)備</p><p>　　while(iFlag){</p&

46、gt;<p>　　for(iCount=1;iCount<=ikey;iCount++){//移動iCount-1趟指針 </p><p>　　pPrv=pCur;</p><p>　　pCur=pCur->next;</p><p><b>　　}</b></p><p>　　if(pPrv=

47、=pCur) iFlag=0;//最后一結(jié)點</p><p>　　pDel=pCur;//刪除pCur指向的結(jié)點 </p><p>　　pPrv->next=pCur->next;</p><p>　　pCur=pCur->next;</p><p>　　printf("第%d個人出列，所持密碼為:%d\n&qu

48、ot;,pDel->id,pDel->key);</p><p>　　ikey=pDel->key-1;</p><p>　　free(pDel);</p><p><b>　　}</b></p><p>　　ppHead=NULL;</p><p><b>　　}&l

49、t;/b></p><p>　　void menu(){</p><p>　　printf("******************************約瑟夫環(huán)問題*************************************\n\n");</p><p>　　printf(" 1、

50、約瑟夫環(huán)報數(shù)游戲(繼續(xù)游戲)\n");</p><p>　　printf(" 0、退出游戲\n");</p><p>　　printf("\n*****************************請輸入數(shù)字選擇************************************\n");</p

51、><p><b>　　}</b></p><p>　　int main(int argc,char *argv[]){</p><p><b>　　int n,m;</b></p><p>　　int iflag=1;</p><p><b>　　menu();<

52、/b></p><p>　　scanf("%d",&iflag);</p><p>　　while(iflag){</p><p>　　CircularList pHead=NULL;</p><p>　　printf("請輸入總?cè)藬?shù)n:");</p><p>　　

53、scanf("%d",&n);</p><p>　　printf("請輸入初始報數(shù)上限m:");</p><p>　　scanf("%d",&m);</p><p>　　CreatList(&pHead,n);</p><p>　　printf("\

54、n----------------參與游戲者的個人信息如下:\n");</p><p>　　PrintList(pHead);</p><p>　　printf("\n----------------按照出列順序輸出游戲者的編號:\n");</p><p>　　Joesph(&pHead,m-1);</p><

55、;p>　　printf("\n本回游戲結(jié)束！\n");</p><p>　　printf("\n\n是否繼續(xù)游戲?(請輸入數(shù)字選擇)\n");</p><p>　　scanf("%d",&iflag);</p><p><b>　　}</b></p><

56、;p><b>　　}</b></p><p><b>　　實驗結(jié)果</b></p><p><b>　　實驗數(shù)據(jù)</b></p><p>　　輸入數(shù)字1，輸入下列數(shù)據(jù)測試：</p><p><b>　　請輸入總?cè)藬?shù)n:7</b></p>

57、<p>　　請輸入初始報數(shù)上限m:20</p><p>　　然后依次輸入每個人的密碼：3 1 7 2 4 8 4</p><p>　　繼續(xù)輸入數(shù)字1繼續(xù)游戲，輸入下列數(shù)據(jù)測試：</p><p><b>　　請輸入總?cè)藬?shù)n:5</b></p><p>　　請輸入初始報數(shù)上限m:30</p><

58、;p>　　然后依次輸入每個人的密碼：3 4 5 6 7</p><p>　　輸入數(shù)字0，結(jié)束程序。</p><p><b>　　實驗結(jié)果</b></p><p><b>　　圖1為主界面</b></p><p><b>　　圖2</b></p><p&

59、gt;　　輸入數(shù)字1，輸入下列數(shù)據(jù)測試：</p><p><b>　　請輸入總?cè)藬?shù)n:7</b></p><p>　　請輸入初始報數(shù)上限m:20</p><p>　　然后依次輸入每個人的密碼：3 1 7 2 4 8 4</p><p>　　出列順序為：6 1 4 7 2 

60、3 5 </p><p><b>　　圖3</b></p><p>　　繼續(xù)輸入數(shù)字1繼續(xù)游戲，輸入下列數(shù)據(jù)測試：</p><p><b>　　請輸入總?cè)藬?shù)n:5</b></p><p>　　請輸入初始報數(shù)上限m:30</p><p>　　然后依次輸入每個

61、人的密碼：3 4 5 6 7</p><p>　　出列順序為：5 3 1 2 4</p><p><b>　　圖4</b></p><p><b>　　輸入0，選擇退出。</b></p><p><b>　　實驗小結(jié)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)

62、使用小結(jié) </p><p>　　本次課程設(shè)計的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問題，循環(huán)鏈表是一種首尾相接鏈表，其特點是無須增加存儲容量，僅對表的鏈接方式稍作改變，使表處理更加靈活，約瑟夫環(huán)問題就是用單循環(huán)鏈表處理的一個實際應(yīng)用。通過這個設(shè)計實例，了解單鏈表和單循環(huán)鏈表的相同與不同之處，進一步加深對鏈表結(jié)構(gòu)類型及鏈表操作的理解。 通過該課程設(shè)計，能運用所學(xué)知識，能上機解決一些實際問題，了解并初步掌握設(shè)計

63、、實現(xiàn)較大程序的完整過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計、實現(xiàn)以及操作方法，為進一步的應(yīng)用開發(fā)打好基礎(chǔ)。</p><p><b>　　需完善之處</b></p><p>　　由于本程序主要解決的事約瑟夫環(huán)問題，并且程序的功能設(shè)計的比較單一，代碼本身也并不復(fù)雜。</p><p><b>　　

64、課程設(shè)計體會</b></p><p>　　通過此次課程設(shè)計，讓我對單循環(huán)鏈表的使用加深了印象，了解到單循環(huán)鏈表的構(gòu)造，刪除操作，以及指針的移動等。此次約瑟夫環(huán)問題用的是單循環(huán)鏈表存儲結(jié)構(gòu)解決的。雖然約瑟夫環(huán)問題的原理不難理解，甚至剛看到這個問題時，讓我想起了以前學(xué)習(xí)C語言時的隊列問題，不過那個只是按某一個數(shù)字為周期,然后在一個循環(huán)隊列中進行游戲，按一定的次序報數(shù)，誰報到該數(shù)則出列，最后輸出所有出列編號

65、的次序。而約瑟夫環(huán)又感覺到在這種簡單問題上深化了點，畢竟它選的key會變化，出列后，從下一元素開始報數(shù)。所以解決這個問題時使用單循環(huán)鏈表存儲結(jié)構(gòu)具有一定的簡化性，利用此存儲結(jié)構(gòu)的優(yōu)點，使用指針進行結(jié)點移動，在實現(xiàn)刪除這一功能時單鏈表具有很大的化簡性。也讓我覺得要對數(shù)據(jù)進行操作，必須選擇好一種比較合適的存儲結(jié)構(gòu)，了解該存儲結(jié)構(gòu)才能對具體的操作有更好的了解，也可以快速又準(zhǔn)確寫出它的代碼。很多東西都是很重要的，而今后也要對軟件方面的代碼算法有