數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---約瑟夫（joseph）環(huán)問題

1、<p>　　學(xué)生課程設(shè)計（論文）</p><p>　　題 目： 約瑟夫（Joseph）環(huán)問題 </p><p>　　2009年 12月 22日</p><p><b>　　攀枝花學(xué)院教務(wù)處制</b></p><p>　　本科學(xué)生課程設(shè)計任務(wù)書</p><p>　　注

2、：任務(wù)書由指導(dǎo)教師填寫。</p><p>　　課程設(shè)計（論文）指導(dǎo)教師成績評定表</p><p><b>　　摘 要</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)這門課程就是研究數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)元素及其關(guān)系在計算機中的存儲表示，以及對這些數(shù)據(jù)所施加的運算。</p><p>　　約瑟夫（Joseph）環(huán)問題處理所使用

3、的數(shù)據(jù)結(jié)構(gòu)為單循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)的模塊主要涉及鏈表的存儲結(jié)構(gòu)及各種操作的算法實現(xiàn)。</p><p>　　循環(huán)鏈表是一種首尾相接鏈表，其特點是無需增加存儲量，僅對表的鏈接方式稍作改變，即可使表處理更加方便靈活。有些實際問題更適合用循環(huán)鏈表處理，約瑟夫（Joseph）環(huán)問題就是一個實例。通過這個設(shè)計實例，了解單鏈表和單循環(huán)鏈表的相同與不同之處，進一步加深對鏈表結(jié)構(gòu)類型及鏈表操作等概念的理解。</p>

4、<p>　　約瑟夫（Joseph）環(huán)問題作為數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，應(yīng)充分考慮其實用性和合理性。將算法設(shè)計用VC++6.0軟件編程實現(xiàn)，最后調(diào)試成功。</p><p>　　關(guān)鍵詞 約瑟夫環(huán)，循環(huán)鏈表，數(shù)據(jù)域，指針域，結(jié)點</p><p><b>　　1 方案設(shè)計</b></p><p><b>　　1.1 問題描述：<

5、;/b></p><p>　　編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。</p><p>　　1.2

6、方案設(shè)計思想:</p><p>　　為了解決這一問題，可以用單循環(huán)鏈表來解決這一問題，實現(xiàn)的方法相對要簡單得多。首先定義鏈表結(jié)點如下：</p><p>　　typedef struct Node</p><p><b>　　{</b></p><p>　　int no;//結(jié)點的編號</p>&

7、lt;p>　　int password;//這個編號所擁有的密碼</p><p>　　struct Node *next;//這個結(jié)點的后繼，即指針域</p><p>　　}Node, *LinkList;</p><p>　　接下來從位置為1的結(jié)點開始報數(shù)，數(shù)到第m個結(jié)點，將當前結(jié)點的密碼賦給m，形成新的密碼，并且將當前結(jié)點從循環(huán)鏈表中刪除即可

8、。如此進行下去，直到輸出n個結(jié)點為止。</p><p>　　根據(jù)數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計的分模塊設(shè)計思想，將程序劃分成5個函數(shù)模塊，下面即分別就每個模塊進行設(shè)計。</p><p>　　1.2.1 根據(jù)給定參數(shù)建立單循環(huán)鏈表</p><p>　　根據(jù)給定總?cè)藬?shù)n建立單循環(huán)鏈表，新開辟結(jié)點，并利用在表尾插入新結(jié)點的方法（后插法）進行結(jié)點的插入，有n個結(jié)點后，將表尾和表頭利用指

9、針相連，即可構(gòu)成循環(huán)鏈表</p><p>　　1.2.2 根據(jù)給定參數(shù)輸出出列順序到屏幕上</p><p>　　可利用執(zhí)行n次的外層循環(huán)內(nèi)層嵌套m次循環(huán)的方法來構(gòu)成。外層設(shè)置循環(huán)n次，即只有n個結(jié)點，輸出n個結(jié)點的出列順序即可，而內(nèi)層中，要根據(jù)出列的結(jié)點的密碼更新m的值，因此在刪除結(jié)點時要注意，必須將密碼保存。</p><p>　　1.2.3 將出列順序?qū)懙街付ㄎ募?/p>

10、中</p><p>　　寫順序到文件函數(shù)和輸出順序到屏幕上的函數(shù)基本類似，需要添加一個文件指針，將相關(guān)信息寫到指定文件中即可。至于循環(huán)的設(shè)置和將順序輸出到屏幕上的函數(shù)的循環(huán)設(shè)置時一樣的，由兩層循環(huán)構(gòu)成，外層控制次數(shù)，內(nèi)層控制密碼的更新。</p><p>　　1.2.4 菜單選擇模塊</p><p>　　在此函數(shù)中，需要輸出函數(shù)能提供的相關(guān)功能，并利用能輸入的字符提示

11、，輸入有效的選項，進行功能選擇：1.在屏幕上輸出順序；2.將順序?qū)懙轿募校?.退出程序。</p><p>　　1.2.5 主函數(shù)模塊</p><p>　　在主函數(shù)中，要根據(jù)菜單函數(shù)的返回值來選擇不同的函數(shù)，進行功能執(zhí)行，調(diào)用相關(guān)的函數(shù)來完成指定的功能。當返回值是1或者2的時，程序還可以再次得到執(zhí)行，執(zhí)行相應(yīng)功能。而當返回值是3時，則退出程序，程序正常結(jié)束。</p><

12、p><b>　　2 算法設(shè)計</b></p><p>　　2.1 建立單循環(huán)鏈表函數(shù)流程圖</p><p>　　2.2 輸出出列順序到屏幕的函數(shù)流程圖</p><p>　　2.3 出列順序?qū)懙轿募暮瘮?shù)流程圖</p><p>　　2.4 菜單選擇函數(shù)流程圖</p><p>　　2.5 主函數(shù)

13、流程圖</p><p><b>　　3 詳細設(shè)計</b></p><p>　　3.1 鏈表建立函數(shù)代碼</p><p>　　void CreatLinkList(LinkList *L, int n)//鏈表建立函數(shù)</p><p><b>　　{</b></p><p&g

14、t;　　Node *p, *q;//定義結(jié)點指針</p><p>　　int i;//定義變量i</p><p>　　(*L) = (LinkList)malloc(sizeof(Node));</p><p>　　if ((*L) == NULL)</p><p><b>　　{</b

15、></p><p>　　printf("程序出錯，退出！");//輸出出錯信息</p><p>　　exit(1);//退出程序運行</p><p><b>　　}</b></p><p>　　p = (*L);//將p指針指向鏈表頭</p>

16、<p>　　printf("請輸入第1個元素的密碼:");</p><p>　　scanf("%d",&(p->password));//輸入第一個結(jié)點的密碼</p><p>　　p->no = 1;//將第一個結(jié)點編號為1</p><p>　　for (i = 2;

17、i <= n; i++)//從第二個到第n個結(jié)點執(zhí)行循環(huán)</p><p><b>　　{</b></p><p>　　q = (LinkList)malloc(sizeof(Node));//開辟新結(jié)點賦給q</p><p>　　if (q == NULL)</p><p><b>　　{<

18、;/b></p><p>　　printf("程序出錯，退出！");</p><p>　　exit(1);//遇到錯誤，退出程序</p><p><b>　　}</b></p><p>　　printf("\n請輸入第%d個元素的密碼:",i);//輸出提示信息

19、</p><p>　　scanf("%d",&(q->password));//輸入第i個結(jié)點的密碼</p><p>　　q->no = i;//將此結(jié)點編號為第i個</p><p>　　p->next = q;//q指向p的后繼結(jié)點</p><p>　　

20、p = q;//將q賦給p，即成功插入一個結(jié)點</p><p><b>　　}</b></p><p>　　p->next = (*L);//最后一個結(jié)點的后繼是表頭結(jié)點，即構(gòu)成循環(huán)鏈表</p><p><b>　　}</b></p><p>　　3.2 輸出函數(shù)

21、代碼</p><p>　　void Output(LinkList *L, int m, int n)//輸出出列順序到屏幕的函數(shù)</p><p><b>　　{</b></p><p>　　Node *p, *q;//定義結(jié)點指針</p><p>　　int i = 1;//給變量

22、i賦初值1</p><p>　　p = (*L);//p指向鏈表頭</p><p>　　printf("出列順序為:");</p><p>　　while (n)//當n非零時執(zhí)行循環(huán)</p><p><b>　　{</b></p><p>

23、　　while (i != m)//當i不等于密碼m時執(zhí)行循環(huán)</p><p><b>　　{</b></p><p><b>　　q = p;</b></p><p>　　p = p->next;//p指針向后移動一個</p><p>　　i++;//變量

24、i加一</p><p><b>　　}</b></p><p>　　printf("%-3d",p->no);//輸出結(jié)點編號到屏幕</p><p>　　m = p->password;//將當前結(jié)點的密碼賦給m,形成新的密碼</p><p>　　q->next = p-&

25、gt;next;//p、q指針同時向后移動一個結(jié)點</p><p>　　free(p);//釋放p結(jié)點</p><p>　　p = q->next;//將 q的后繼賦給p</p><p>　　i = 1;//將變量i置1</p><p>　　n--;//變量n減一</

26、p><p><b>　　}</b></p><p>　　printf("\n");//輸出換行符</p><p><b>　　}</b></p><p>　　3.3 寫到文件中函數(shù)代碼</p><p>　　void WriteToText(Li

27、nkList *L, int m, int n)//寫順序到文件函數(shù)</p><p><b>　　{ </b></p><p>　　Node *p, *q;//定義結(jié)點指針</p><p>　　int i = 1;//給變量i賦初值1</p><p>　　FILE *fp;

28、//定義文件指針fp</p><p>　　char filename[20]; </p><p>　　printf("\t\t\t寫出隊順序到指定文件中！\n"); </p><p>　　printf("\t\t\t輸入文件名:"); </p><p>　　scanf("

29、\t\t\t%s",filename); //輸入要寫入的文件名</p><p>　　if((fp=fopen(filename,"w"))==NULL) </p><p><b>　　{ </b></p><p>　　printf("\t\t\t打開文件失??！\n"); //輸出文件打

30、開失敗信息</p><p>　　system("pause"); </p><p><b>　　return; </b></p><p><b>　　} </b></p><p>　　p=(*L);// p指向鏈表頭</p><p>　　

31、fprintf(fp,"總?cè)藬?shù)為：%d\n",n); //向文件中寫入總?cè)藬?shù)n</p><p>　　fprintf(fp,"第一個報號的上限為：%d\n",m);//向文件中寫入第一個上限m</p><p>　　fprintf(fp,"出列順序為:\n");</p><p>　　while(n)

32、//當 n非零是執(zhí)行循環(huán)</p><p><b>　　{</b></p><p>　　while(i!=m)//當i不等于m時執(zhí)行循環(huán)</p><p><b>　　{</b></p><p><b>　　q = p;</b></p>&l

33、t;p>　　p = p->next;// p指針向后移動一個</p><p>　　i++;//變量i加一</p><p><b>　　}</b></p><p>　　fprintf(fp,"%-3d",p->no);//向文件中寫入此結(jié)點的編號</p><p&

34、gt;　　m = p->password;//將當前結(jié)點的密碼賦給m，形成新密碼</p><p>　　q->next = p->next;// p、q指針同時向后移動一個結(jié)點</p><p>　　free(p);//釋放p結(jié)點</p><p>　　p = q->next;//將 q的后繼賦給p</p&

35、gt;<p>　　i = 1;//將變量i置1</p><p>　　n--;//變量n減一</p><p><b>　　}</b></p><p>　　fclose(fp); //關(guān)閉文件</p><p>　　printf("寫文件成功!\n&quo

36、t;); </p><p><b>　　}</b></p><p>　　3.4 菜單選擇函數(shù)代碼</p><p>　　int menu_select() //選擇菜單函數(shù)</p><p><b>　　{ </b></p><p><b>　　char

37、 c; </b></p><p><b>　　do{ </b></p><p>　　system("cls"); //輸出相關(guān)信息，進行功能選擇</p><p>　　printf("\t\t*****約瑟夫環(huán)問題（數(shù)據(jù)結(jié)構(gòu)課程設(shè)計）*****\n"); </p><

38、;p>　　printf("\t\t* | 1. 在屏幕上輸出出列順序！ |\n"); </p><p>　　printf("\t\t* | 2. 將序列寫到文件中！ |\n"); </p><p>　　printf("\t\t* | 3. 退出！ |\n"); </p><p>　　printf(&q

39、uot;\t\t**************07計本 化寶峰**************\n"); </p><p>　　printf("\t\t\t請選擇(1-3):"); //輸出選擇提示信息</p><p>　　c=getchar(); //輸入字符</p><p>　　}while(c<'1'

40、||c>'3'); //當c 為無效字符時重新輸入</p><p>　　return(c-'0'); //返回一個功能編號的整數(shù)值</p><p><b>　　}</b></p><p><b>　　3.5 主函數(shù)代碼</b></p><p&g

41、t;　　void main() //主函數(shù)</p><p>　　{LinkList L;//定義鏈表L</p><p>　　int n, m;//定義整形變量n、m</p><p>　　for(;;) //執(zhí)行無限循環(huán)</p><p><b>　　{ <

42、/b></p><p>　　switch(menu_select()) //調(diào)用菜單函數(shù)，返回選項，進//入switch函數(shù)部分</p><p><b>　　{ </b></p><p>　　case 1: //當菜單返回1時，提示輸出相關(guān)信息</p><p>　　printf("\t\t\t輸入

43、相關(guān)數(shù)據(jù)！\n"); </p><p>　　printf("\t\t\t請輸入人數(shù):");</p><p>　　scanf("%d", &n);//輸入總?cè)藬?shù)n</p><p>　　getchar();</p><p>　　CreatLinkList(&L, n);<

44、;/p><p>　　//調(diào)用建立鏈表函數(shù)，建立鏈表</p><p>　　printf("\t\t\t請輸入第一個報號的上限:");</p><p>　　scanf("%d",&m);//輸入上限m</p><p>　　Output(&L, m, n);//調(diào)用輸出函數(shù)，進行輸出<

45、/p><p>　　system("pause");</p><p><b>　　break; </b></p><p>　　case 2: //當菜單返回2時，提示輸出相關(guān)信息</p><p>　　printf("\t\t\t將序列寫到文件中\(zhòng)n"); </p>&

46、lt;p>　　printf("\t\t\t輸入相關(guān)數(shù)據(jù)！\n");</p><p>　　printf("\t\t\t請輸入人數(shù):");</p><p>　　scanf("%d", &n);//輸入總?cè)藬?shù)n</p><p>　　getchar();</p><p>　

47、　CreatLinkList(&L, n);</p><p>　　//調(diào)用建立鏈表函數(shù)，建立鏈表</p><p>　　printf("\t\t\t請輸入第一個報號的上限:");</p><p>　　scanf("%d",&m);//輸入上限m</p><p>　　WriteT

48、oText(&L, m, n);</p><p>　　//調(diào)用寫順序到文件函數(shù)，進行寫</p><p>　　printf("\t\t\t"); </p><p>　　system("pause"); </p><p><b>　　break; </b></p>

49、<p>　　case 3: //當菜單返回3時2，準備結(jié)束程序</p><p>　　printf("\t\t\t工作結(jié)束，謝謝使用！\n"); </p><p>　　printf("\t\t\t"); </p><p>　　system("pause"); </p>&

50、lt;p>　　exit(0); //正常退出程序</p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　4 調(diào)試分析</b></p>

51、<p>　　本程序的測試軟件為VC++6.0軟件。</p><p><b>　　4.1程序運行界面</b></p><p>　　在程序調(diào)試階段，分三類進行測試。</p><p><b>　　測試數(shù)據(jù)為：</b></p><p><b>　　總?cè)藬?shù)n為8</b><

52、;/p><p>　　第一次報號上限m為4</p><p>　　各個元素的密碼均為4</p><p>　　將源程序進行編譯、連接、生成可執(zhí)行文件，運行可執(zhí)行文件，顯示結(jié)果如下圖所示：</p><p>　　圖4.1 運行程序初始化菜單</p><p>　　4.1.1功能1測試</p><p>　　圖4

53、.2 菜單選擇1的界面</p><p>　　輸入相關(guān)信息后，顯示結(jié)果如圖所示，出列順序為：4、8、5、2、1、3、7、6。結(jié)果是正確的，在此時為了輸入簡單，將所有元素的密碼均置1.</p><p>　　4.1.2功能2測試</p><p>　　圖4.3 菜單選擇2的界面</p><p>　　輸入相關(guān)信息后，指定文件名輸入為“123.txt

54、”則可將順序?qū)懙街付ㄎ募辛恕?lt;/p><p>　　圖4.4 文件中的內(nèi)容</p><p>　　查看文件“123.txt”中的內(nèi)容，即可看出文件中的內(nèi)容是所要求的，滿足程序要求。</p><p>　　圖4.5 DOC文檔中的內(nèi)容</p><p>　　將指定文件名改為“123.doc”，也可實現(xiàn)輸入功能。</p><p

55、>　　4.1.3功能3測試</p><p>　　圖4.6 菜單選擇3的界面</p><p>　　選擇3，即可退出程序。</p><p>　　4.2算法的改進思想</p><p>　　在算法的設(shè)計過程中，尤其是密碼的輸入過程中，沒有設(shè)計密碼的輸入范圍，即沒有限制m必須是大于0的整數(shù)。而在程序中，忽略了這一塊，在以后的程序設(shè)計中，必須注意

56、這些細節(jié)的問題，而在程序的設(shè)計過程中，還有一點是很重要的，就是模塊化的設(shè)計思想。</p><p><b>　　5、課程設(shè)計總結(jié)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)這門課是我們計算機科學(xué)與技術(shù)專業(yè)的一門專業(yè)基礎(chǔ)課，從開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)到現(xiàn)在，已經(jīng)整整一個學(xué)期了，這次的課程設(shè)計，給了我極大的鍛煉機會，并且讓我充分認識到數(shù)據(jù)結(jié)構(gòu)的重要性。</p><p&

57、gt;　　在課程設(shè)計的過程中，從開始拿到課題的一臉茫然，到后來的程序獨立完成，再到最后的成品出來，經(jīng)歷了好多。當開始拿到課題的時候，因苦于程序簡單，沒有更好的思路去擴展它，于是感覺無從下手，不知道如何去設(shè)計功能。在苦思冥想之后，設(shè)計出了現(xiàn)在這個具有兩個功能的程序。</p><p>　　通過這次課程設(shè)計，我感覺到要真正做出一個程序并不容易，但只要用心去做，總會有收獲，特別是當我遇到 一個問題，想辦法去解決，最后終于

58、找到方法時，心里的那份喜悅之情真是難以形容。編寫程序中遇到問題再所難免，應(yīng)耐心探究其中的原因，從出現(xiàn)問題的地方起，聯(lián)系前后程序，仔細推敲，逐個排查。直到最終搞清為止。而在這樣的設(shè)計過程中，耐心和毅力是很重要的。</p><p>　　經(jīng)過這次課程設(shè)計，我懂得，不僅是在寫程序還是平時的任何事情，無論做什么事情，都要認真對待，既然是該我做的事，肯定就是我應(yīng)該有這個能力，即使能力不夠，也是應(yīng)該借這個機會來培養(yǎng)。所以放心大

59、膽地做，對自己有信心，就有動力。只要用心去做了，即使結(jié)果不是很好，也是又收獲的，并且不管到什么時候，都要對自己充滿信心，只要相信自己能成功，就一定會成功的。</p><p>　　在此，還要感謝陳堯老師的指導(dǎo)，謝謝！同時要感謝幫助過我的同學(xué)，謝謝你們。經(jīng)過這次課程設(shè)計，我會更加努力學(xué)習(xí)我們專業(yè)的專業(yè)知識的。</p><p><b>　　參 考 文 獻</b></p

60、><p>　　蘇仕華．數(shù)據(jù)結(jié)構(gòu)課程設(shè)計．北京：機械工業(yè)出版社，2005．</p><p>　　王玲．數(shù)據(jù)結(jié)構(gòu)實驗教程．四川：四川大學(xué)出版社，2002．</p><p>　　嚴蔚敏，吳偉明．數(shù)據(jù)結(jié)構(gòu)（C語言版）．北京：清華大學(xué)出版社，2007．</p><p>　　劉懷亮．數(shù)據(jù)結(jié)構(gòu)（C語言描述）．北京：冶金工業(yè)出版社，2004．</p>