數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(約瑟夫環(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.存儲(chǔ)結(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>　　三、實(shí)現(xiàn)9</b></p><p>　　四、實(shí)驗(yàn)結(jié)果13</p><p>　　1.實(shí)驗(yàn)數(shù)據(jù)13<

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

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

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

7、2）使學(xué)生熟練掌握數(shù)據(jù)類型的定義和實(shí)現(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é)在以下題目中任選一題（在方框中打勾），獨(dú)立完成課程設(shè)計(jì)：</p><p>　　約瑟夫環(huán)：參見《數(shù)據(jù)結(jié)構(gòu)題集》P179。</p><p>　　□ 赫夫曼編/譯碼器：參見《數(shù)據(jù)結(jié)構(gòu)題集》P149。</p><p>　　□ 教學(xué)計(jì)劃編制問題：參見《數(shù)據(jù)結(jié)構(gòu)題集》P150。</p><p>　　3．課程設(shè)計(jì)論文編寫要求</p&g

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

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

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

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è)計(jì)中用到的數(shù)據(jù)結(jié)構(gòu)ADT定義如下：</p><p><b>　　ADT Node{</b></p><p>　　數(shù)據(jù)對(duì)象：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為出列者所在編號(hào)</p><p>　　操作結(jié)果：刪除出隊(duì)編號(hào)所在結(jié)點(diǎn)，并將該結(jié)點(diǎn)的key作為新的key，從該結(jié)點(diǎn)的下一結(jié)點(diǎn)移動(dòng)</p><p>　　} ADT Node</p><p&

16、gt;<b>　　存儲(chǔ)結(jié)構(gòu)定義</b></p><p>　　數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的C語言定義如下：</p><p>　　typedef struct Node{//帶頭結(jié)點(diǎn)的單循環(huán)鏈表 </p><p>　　int id;//編號(hào) </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)的基本操作實(shí)現(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("請(qǐng)輸入第%d個(gè)人所持有的密碼：",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)已建成，可以開始進(jìn)入報(bào)數(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個(gè)人所持有的密碼是：%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é)點(diǎn)并輸出結(jié)點(diǎn)信息函數(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é)點(diǎn)，為刪除做好準(zhǔn)備</p><p>　　while(iFlag){</p><p&

26、gt;　　for(iCount=1;iCount<=ikey;iCount++){//移動(dòng)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é)點(diǎn)</p><p>　　pDel=pCur;//刪除pCur指向的結(jié)點(diǎn) </p><p>　　pPrv->next=pCur->next;</p><p>　　pCur=pCur->next;</p><p>　　printf("第%d個(gè)人出列，所持密碼為:%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)實(shí)現(xiàn)以下功能：建立約瑟夫環(huán)并解約瑟夫環(huán)，直到所有玩家出列，并順序輸出出列編號(hào)。它主要解決約瑟夫環(huán)問題。</p><p><b>　　模塊結(jié)構(gòu)</b></

30、p><p>　　系統(tǒng)主要由 5個(gè)模塊組成，分別是：</p><p>　?。?）、構(gòu)造鏈表模塊</p><p>　　void CreatList(CircularList *ppHead,const int k)</p><p>　?。?）、輸出鏈表模塊</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>　　各模塊的實(shí)現(xiàn)步驟為</b></p>&

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

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

35、然，又可以供操作者自主選擇。</p><p>　　（5）主函數(shù)模塊：設(shè)置標(biāo)簽iflag，供用戶選擇輸入數(shù)字操作。若為1則開始或繼續(xù)約瑟夫環(huán)游戲；若為0，退出游戲。游戲開始后，首先得設(shè)置參與者人數(shù)n以及初始報(bào)數(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>　　實(shí)現(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é)點(diǎn)的單循環(huán)鏈表 </p><p>　　int id;//編號(hào) </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("請(qǐng)輸入第%d個(gè)人所持有的密碼：",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)已建成，可以開始進(jìn)入報(bào)數(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個(gè)人所持有的密碼是：%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é)點(diǎn)并輸出結(jié)點(diǎn)信息 </p><p>　　int iCount,iFlag=1;</p><p>　　Node *pPrv,*pCur,*pDel;</p><p>　　pPrv=pCur=*ppHead;//將pPrv初始為指向尾結(jié)點(diǎn)，為刪除做好準(zhǔn)備</p><p>　　while(iFlag){</p&

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

47、=pCur) iFlag=0;//最后一結(jié)點(diǎn)</p><p>　　pDel=pCur;//刪除pCur指向的結(jié)點(diǎn) </p><p>　　pPrv->next=pCur->next;</p><p>　　pCur=pCur->next;</p><p>　　printf("第%d個(gè)人出列，所持密碼為:%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)報(bào)數(shù)游戲(繼續(xù)游戲)\n");</p><p>　　printf(" 0、退出游戲\n");</p><p>　　printf("\n*****************************請(qǐng)輸入數(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("請(qǐng)輸入總?cè)藬?shù)n:");</p><p>　　

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

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

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

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

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

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

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

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

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

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

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

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

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