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

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

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

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

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

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

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

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

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

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個(gè)結(jié)點(diǎn)，輸出n個(gè)結(jié)點(diǎn)的出列順序即可，而內(nèi)層中，要根據(jù)出列的結(jié)點(diǎn)的密碼更新m的值，因此在刪除結(jié)點(diǎn)時(shí)要注意，必須將密碼保存。</p><p>　　1.2.3 將出列順序?qū)懙街付ㄎ募?/p>

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

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

12、p><b>　　2 算法設(shè)計(jì)</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 詳細(xì)設(shè)計(jì)</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é)點(diǎn)指針</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("程序出錯(cuò)，退出！");//輸出出錯(cuò)信息</p><p>　　exit(1);//退出程序運(yùn)行</p><p><b>　　}</b></p><p>　　p = (*L);//將p指針指向鏈表頭</p>

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

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

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

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

20、p = q;//將q賦給p，即成功插入一個(gè)結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　p->next = (*L);//最后一個(gè)結(jié)點(diǎn)的后繼是表頭結(jié)點(diǎn)，即構(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é)點(diǎn)指針</p><p>　　int i = 1;//給變量

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

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

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

25、gt;next;//p、q指針同時(shí)向后移動(dòng)一個(gè)結(jié)點(diǎn)</p><p>　　free(p);//釋放p結(jié)點(diǎn)</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é)點(diǎn)指針</p><p>　　int i = 1;//給變量i賦初值1</p><p>　　FILE *fp;

28、//定義文件指針fp</p><p>　　char filename[20]; </p><p>　　printf("\t\t\t寫出隊(duì)順序到指定文件中！\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,"第一個(gè)報(bào)號(hào)的上限為：%d\n",m);//向文件中寫入第一個(gè)上限m</p><p>　　fprintf(fp,"出列順序?yàn)?\n");</p><p>　　while(n)

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

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

34、gt;　　m = p->password;//將當(dāng)前結(jié)點(diǎn)的密碼賦給m，形成新密碼</p><p>　　q->next = p->next;// p、q指針同時(shí)向后移動(dòng)一個(gè)結(jié)點(diǎn)</p><p>　　free(p);//釋放p結(jié)點(diǎn)</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)信息，進(jìn)行功能選擇</p><p>　　printf("\t\t*****約瑟夫環(huán)問題（數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)）*****\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計(jì)本 化寶峰**************\n"); </p><p>　　printf("\t\t\t請(qǐng)選擇(1-3):"); //輸出選擇提示信息</p><p>　　c=getchar(); //輸入字符</p><p>　　}while(c<'1'

40、||c>'3'); //當(dāng)c 為無效字符時(shí)重新輸入</p><p>　　return(c-'0'); //返回一個(gè)功能編號(hào)的整數(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ù)，返回選項(xiàng)，進(jìn)//入switch函數(shù)部分</p><p><b>　　{ </b></p><p>　　case 1: //當(dāng)菜單返回1時(shí)，提示輸出相關(guān)信息</p><p>　　printf("\t\t\t輸入

43、相關(guān)數(shù)據(jù)！\n"); </p><p>　　printf("\t\t\t請(qǐng)輸入人數(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請(qǐng)輸入第一個(gè)報(bào)號(hào)的上限:");</p><p>　　scanf("%d",&m);//輸入上限m</p><p>　　Output(&L, m, n);//調(diào)用輸出函數(shù)，進(jìn)行輸出<

45、/p><p>　　system("pause");</p><p><b>　　break; </b></p><p>　　case 2: //當(dāng)菜單返回2時(shí)，提示輸出相關(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請(qǐng)輸入人數(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請(qǐng)輸入第一個(gè)報(bào)號(hào)的上限:");</p><p>　　scanf("%d",&m);//輸入上限m</p><p>　　WriteT

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

49、<p>　　case 3: //當(dāng)菜單返回3時(shí)2，準(zhǔn)備結(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>　　本程序的測(cè)試軟件為VC++6.0軟件。</p><p><b>　　4.1程序運(yùn)行界面</b></p><p>　　在程序調(diào)試階段，分三類進(jìn)行測(cè)試。</p><p><b>　　測(cè)試數(shù)據(jù)為：</b></p><p><b>　　總?cè)藬?shù)n為8</b><

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

53、.2 菜單選擇1的界面</p><p>　　輸入相關(guān)信息后，顯示結(jié)果如圖所示，出列順序?yàn)椋?、8、5、2、1、3、7、6。結(jié)果是正確的，在此時(shí)為了輸入簡(jiǎn)單，將所有元素的密碼均置1.</p><p>　　4.1.2功能2測(cè)試</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”，也可實(shí)現(xiàn)輸入功能。</p><p

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

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

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

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

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

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