約瑟夫環(huán)問(wèn)題課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告 設(shè)計(jì)課題： 約瑟夫問(wèn)題 院 系： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專(zhuān)業(yè)班級(jí)： 計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)1102班 學(xué)生姓名： 張 利 學(xué) 號(hào)： 1 1 0 8 0 4 0 2 1 1 指導(dǎo)教師： 王 昱 哲 目 錄1.需求分析31.1問(wèn)題描述3 1.2功能分析42.概要設(shè)計(jì)53.詳細(xì)設(shè)計(jì)64.調(diào)試與操作說(shuō)明15總 結(jié)16一需求分析1.1問(wèn)題描述約瑟夫環(huán)問(wèn)題描述的是：設(shè)編號(hào)為1，2，n的n（n>0）個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一正整數(shù)密碼。開(kāi)始時(shí)選擇一個(gè)正整數(shù)作為報(bào)數(shù)上限m，從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?起順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，將他的密碼作為新的m值，從他在順

2、時(shí)針?lè)较蛏系南乱粋€(gè)人起重新從1報(bào)數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計(jì)一個(gè)程序模擬此過(guò)程，求出出圈的編號(hào)序列。如下圖分析：1234567890這是第一個(gè)人，他的密碼是“1”，個(gè)他輸一個(gè)m值，如果m=3,則從他開(kāi)始向下走3個(gè)這就是第二步的位置，這時(shí)他的密碼作為新的m值，即m=4,同時(shí)得到的第一個(gè)密碼為4；4號(hào)出去向下走4，到9這兒；（這這一步完了剩余的為：1,2,3,5,6，7,8,9,0，）這就是第三步的位置，這時(shí)他的密碼作為新的m值，即m=9，同時(shí)得到的第二個(gè)密碼為9；9號(hào)出去向下走9，到0這兒；繼續(xù)走就行了（這兒剩余的就是：1，2，3，5，6,7,8,0）圖1約瑟

3、夫環(huán)問(wèn)圖解3271484約瑟夫環(huán)原理演示圖1234567第二部：第一次停下的位置，此時(shí)6號(hào)出列，并將他的值作為新的m值，即：新的m=8；從7好開(kāi)始繼續(xù)向下走8次，到1號(hào)的位置最后排序后的密碼序列：（本圖只演示前兩步）8第三步：第二次，1號(hào)出列第四步：第三次，4號(hào)出列3第一步：給第一個(gè)人賦初始密碼為：20則從它開(kāi)始向下走20次，到6號(hào)位置241746147235圖2 約瑟夫環(huán)原理演示圖1.2功能分析約瑟夫環(huán)問(wèn)題是一個(gè)古老的數(shù)學(xué)問(wèn)題，本次課題要求用程序語(yǔ)言的方式解決數(shù)學(xué)問(wèn)題。此問(wèn)題僅使用單循環(huán)鏈表就可以解決此問(wèn)題。而改進(jìn)的約瑟夫問(wèn)題通過(guò)運(yùn)用雙向循環(huán)鏈表，同樣也能方便地解決。在建立雙向循環(huán)鏈表時(shí)，因

4、為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值定為生成結(jié)點(diǎn)時(shí)的順序號(hào)和每個(gè)人持有的密碼。進(jìn)行操作時(shí)，用一個(gè)指針current指向當(dāng)前的結(jié)點(diǎn)，指針front始終指向頭結(jié)點(diǎn)。然后建立雙向循環(huán)鏈表，因?yàn)槊總€(gè)人的密碼是通過(guò)rand()函數(shù)隨機(jī)生成的，所以指定第一個(gè)人的順序號(hào)，找到結(jié)點(diǎn)，不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表剩下最后一個(gè)結(jié)點(diǎn)，通過(guò)一系列的循環(huán)就可以解決改進(jìn)約瑟夫環(huán)問(wèn)題。2、 概要設(shè)計(jì)1、循環(huán)鏈表抽象數(shù)據(jù)類(lèi)型定義typedef struct LNode/定義單循環(huán)鏈表中節(jié)點(diǎn)的結(jié)構(gòu) int num;/編號(hào) int pwd;/passwordstruct LNode *next

5、;/指向下一結(jié)點(diǎn)的指針LNode;2、本程序包含一下幾個(gè)模塊（1）構(gòu)造結(jié)點(diǎn)模塊LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個(gè)結(jié)點(diǎn) p->num=m_num;/把實(shí)參賦給相應(yīng)的數(shù)據(jù)域p->pwd=m_pwd;p->next=NULL;/指針域?yàn)榭誶eturn p; （2）創(chuàng)建鏈表模塊void createList(LNode *ppHead,int n)（3）出隊(duì)處理模塊void jose(LNode *ppHead,int m_pwd)（4）約瑟夫環(huán)說(shuō)明輸

6、出模塊void instruction()（5）菜單模塊void menu()（6）主函數(shù)模塊int main（）函數(shù)的調(diào)用關(guān)系圖如下：Case 2:建立的約瑟夫環(huán),并輸出已建立的約瑟夫環(huán)：createList(LNode *ppHead,int n)輸出該約瑟夫環(huán)的每個(gè)人的出列順序: jose(LNode *ppHead,int m_pwd)圖3 約瑟夫環(huán)函數(shù)調(diào)用關(guān)系圖菜單函數(shù)；void menu()主函數(shù)調(diào)用函數(shù)；main()Case 1：一個(gè)簡(jiǎn)單的輸出函數(shù)，用于說(shuō)明約瑟夫環(huán)；void instruction()Case 0:default : 輸入0，退出 exit(0)；三、詳細(xì)設(shè)計(jì)1

7、. 主函數(shù)Main()開(kāi)始Menu()功能菜單功能1：約瑟夫環(huán)說(shuō)明功能2：按要求求解約瑟夫環(huán)功能3：退出系統(tǒng)輸入總?cè)藬?shù)n輸入開(kāi)始上線(xiàn)數(shù)：m輸入每個(gè)玩家的密碼調(diào)用：createList(&ppHead,n);jose(ppHead,m);函數(shù)求解所需的密碼序列選擇要執(zhí)行的操作程序運(yùn)行完，自動(dòng)返回到功能菜單圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)流程圖，主函數(shù)程序如下：int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf("n請(qǐng)選擇要執(zhí)行的操作："); scanf("%d",&x);

8、 system("cls"); switch(x)case 1: printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密n"); printf("碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始n"); printf("按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼n"); printf("m作為新的m值,從他在順時(shí)針?lè)较蛏系南乱?/p>

9、人開(kāi)始重新從1報(bào)數(shù),如此下去,n"); printf("直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); main();break; case 2: printf("n請(qǐng)輸入總?cè)藬?shù)n："); scanf("%d",&n); printf("請(qǐng)輸入開(kāi)始上限數(shù)m："); scanf("%d",&m); createList(&ppHead,n); printf("n");printf("

10、出隊(duì)順序：n"); jose(ppHead,m); printf("n約瑟夫環(huán)游戲結(jié)束!n"); main();break; case 0: exit(0); default: system("cls"); printf("n您選擇的操作有誤，請(qǐng)重新選擇.nnn"); main(); return 0; 2. 鏈表的創(chuàng)建否是createList（）;從主函數(shù)中獲取玩家信息n如果n>0創(chuàng)建循環(huán)單鏈表，儲(chǔ)存各個(gè)玩家密碼退出創(chuàng)建鏈表完成返回主函數(shù)main()創(chuàng)建儲(chǔ)存玩家密碼的循環(huán)單鏈表的方法Main()函數(shù)圖5 創(chuàng)建鏈表函數(shù)

11、的數(shù)據(jù)流程圖/*創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個(gè)數(shù)為n，并輸入每個(gè)人的密碼值，若建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，若建立成功則插入結(jié)點(diǎn)P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的節(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/根據(jù)流程圖，創(chuàng)建鏈表函數(shù)程序如下：void createList(LNode *ppHead,int n)int i,m_pwd;LNode *p,*cur;/cur:浮標(biāo)指針for(i=1;i<=n;i+)printf("輸入第%d個(gè)人的密碼：",i);scanf("%d",&m_pwd);/輸

12、入持有密碼 p=createNode(i,m_pwd);/調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù)if(*ppHead=NULL)/如果頭結(jié)點(diǎn)為空 *ppHead=cur=p;/生成頭結(jié)點(diǎn)，讓cur指向他 cur->next=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p->next = cur->next;cur->next = p;cur= p;/cur指向新插入結(jié)點(diǎn) printf("完成創(chuàng)建！n"); /提示鏈表創(chuàng)建完成 3. 出隊(duì)處理Main()函數(shù)從循環(huán)鏈表中按初始密碼依次掃描，找出對(duì)應(yīng)的玩家序列輸出其持有的密碼i=ppHead-&

13、gt;pwd; j=ppHead->num;移動(dòng)浮標(biāo)指針m_pwd=ppHead->pwd;輸出密碼后，刪除相應(yīng)的結(jié)點(diǎn)，并釋放所占的儲(chǔ)存空間free(ppHead); ppHead=p->next;執(zhí)行完后返回主函數(shù)jose()；出隊(duì)函數(shù)出隊(duì)處理的方法圖6 出隊(duì)函數(shù)的數(shù)據(jù)流程圖/*p指向要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，ppHead指向要?jiǎng)h除的節(jié)點(diǎn)，使p=ppHead，ppHead再指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，使p和ppHead鏈接，輸出p指向節(jié)點(diǎn)的編號(hào)和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點(diǎn)都打印和刪除為止！*/根據(jù)流程圖，出隊(duì)函數(shù)程序如下：void jose(LNode

14、 *ppHead,int m_pwd)int i,j;LNode *p,*p_del;/定義指針變量for(i=1;p!=ppHead;i+)for(j=1;j<m_pwd;+j)p=ppHead;/p賦值為ppHead，p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)ppHead=ppHead->next;/ppHead指向下一個(gè)元素p->next = ppHead->next;/p結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為ppHead->num，j為要?jiǎng)h除的密碼值printf("

15、第%d個(gè)人出列，密碼：%dn",j,i); m_pwd=ppHead->pwd;/m_pwd賦值為ppHead->pwdfree(ppHead);/釋放頭結(jié)點(diǎn)ppHead=p->next;/ppHead重新賦值給p->next,即釋放前的ppHead->pwd指針/刪除報(bào)數(shù)結(jié)點(diǎn) i=ppHead->pwd;/i賦值為ppHead->pwdj=ppHead->num;/j賦值為ppHead->numprintf("最后一個(gè)出列是%d號(hào)，密碼是:%dn",j,i); free(ppHead);/釋放頭結(jié)點(diǎn)4. 約瑟

16、夫環(huán)說(shuō)明模塊void instruction() printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密n"); printf("碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始n"); printf("按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù),報(bào)到時(shí)停止.報(bào)m的人出列，將他的密碼n"); printf("m作為新的m值,從他在順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去,n&qu

17、ot;); printf("直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); return 0;5. 菜單模塊void menu()printf("*約瑟夫環(huán) *n");printf(" n");printf(" 1約瑟夫環(huán)問(wèn)題的闡述 n");printf(" 2按要求求解約瑟夫環(huán) n");printf(" 0退出 n");printf("* 歡迎使用！ *n"); 四、程序調(diào)試與測(cè)試1. 調(diào)用模塊時(shí)，結(jié)點(diǎn)

18、結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩次錯(cuò)誤，加入子函數(shù)的聲明后錯(cuò)誤消失。2 . 剛開(kāi)始時(shí)曾忽略了一些變量參數(shù)的標(biāo)識(shí)"&"和“*”，使調(diào)試程序時(shí)費(fèi)時(shí)不少。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識(shí)。3. 本次課程設(shè)計(jì)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序劃分為三個(gè)層次結(jié)構(gòu)：元素節(jié)點(diǎn)、單向循環(huán)鏈表，主控制模塊。思路較為清晰，實(shí)現(xiàn)調(diào)用順利。 經(jīng)過(guò)本次實(shí)驗(yàn)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程有了進(jìn)一步的了解，每一個(gè)程序經(jīng)過(guò)需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)之后，思路即清晰呈現(xiàn)，程序也很快就出來(lái)了，最后經(jīng)過(guò)調(diào)試、運(yùn)行又有新的體驗(yàn)。<測(cè)試用例>這是一個(gè)使用循環(huán)鏈表的經(jīng)典問(wèn)題。本程序開(kāi)始運(yùn)行界面如下：圖7 約瑟夫環(huán)開(kāi)始運(yùn)行界面選擇1進(jìn)入約瑟夫環(huán)問(wèn)題闡述。圖8 約瑟夫環(huán)問(wèn)題闡述選擇2，輸入下列數(shù)據(jù)測(cè)試：請(qǐng)輸入總?cè)藬?shù)n：7請(qǐng)輸入開(kāi)始上限數(shù)m：20；請(qǐng)依次輸入每個(gè)人的密碼：3 1 7 2 4 8 4出隊(duì)順序：6 1 4 7 2