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

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告 設(shè)計(jì)課題： 約瑟夫問題 院 系： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專業(yè)班級： 計(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問題描述3 1.2功能分析42.概要設(shè)計(jì)53.詳細(xì)設(shè)計(jì)64.調(diào)試與操作說明15總 結(jié)16一需求分析1.1問題描述約瑟夫環(huán)問題描述的是：設(shè)編號(hào)為1，2，n的n（n0）個(gè)人按順時(shí)針方向圍坐一圈，每個(gè)人持有一正整數(shù)密碼。開始時(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í)針方向

2、上的下一個(gè)人起重新從1報(bào)數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計(jì)一個(gè)程序模擬此過程，求出出圈的編號(hào)序列。如下圖分析：1234567890這是第一個(gè)人，他的密碼是“1”，個(gè)他輸一個(gè)m值，如果m=3,則從他開始向下走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約瑟夫環(huán)問圖

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

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è)人的密碼是通過rand()函數(shù)隨機(jī)生成的，所以指定第一個(gè)人的順序號(hào)，找到結(jié)點(diǎn)，不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表剩下最后一個(gè)結(jié)點(diǎn)，通過一系列的循環(huán)就可以解決改進(jìn)約瑟夫環(huán)問題。2、 概要設(shè)計(jì)1、循環(huán)鏈表抽象數(shù)據(jù)類型定義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)說明輸出模塊void instruct

6、ion()（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è)簡單的輸出函數(shù)，用于說明約瑟夫環(huán)；void instruction()case 0:default : 輸入0，退出 exit(0)；三、詳細(xì)設(shè)計(jì)1. 主函數(shù)main()開始men

7、u()功能菜單功能1：約瑟夫環(huán)說明功能2：按要求求解約瑟夫環(huán)功能3：退出系統(tǒng)輸入總?cè)藬?shù)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請選擇要執(zhí)行的操作：); scanf(%d,&x); system(cls); switch(x)case 1: printf(*n); print

8、f(約瑟夫環(huán):n); printf( 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針方向圍坐一圈,每人持有一個(gè)密n); printf(碼(正整數(shù)).一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開始n); printf(按順時(shí)針方向自1開始順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼n); printf(m作為新的m值,從他在順時(shí)針方向上的下一人開始重新從1報(bào)數(shù),如此下去,n); printf(直到所有人全部出列為止.編程打印出列順序.n); printf(*n); main();break; case 2: printf(n請輸入總?cè)藬?shù)n：); scanf(%d,&n); printf(請

9、輸入開始上限數(shù)m：); scanf(%d,&m); createlist(&pphead,n); printf(n);printf(出隊(duì)順序：n); jose(pphead,m); printf(n約瑟夫環(huán)游戲結(jié)束!n); main();break; case 0: exit(0); default: system(cls); printf(n您選擇的操作有誤，請重新選擇.nnn); main(); return 0; 2. 鏈表的創(chuàng)建否是createlist（）;從主函數(shù)中獲取玩家信息n如果n0創(chuàng)建循環(huán)單鏈表，儲(chǔ)存各個(gè)玩家密碼退出創(chuàng)建鏈表完成返回主函數(shù)main()創(chuàng)建儲(chǔ)存玩家密碼的循環(huán)單鏈表

10、的方法main()函數(shù)圖5 創(chuàng)建鏈表函數(shù)的數(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;inext=*pphead;/cur的指針域指向自身 else/如果不為空，則插入結(jié)點(diǎn) p-next = cur-next;cur-next =

11、 p;cur= p;/cur指向新插入結(jié)點(diǎn) printf(完成創(chuàng)建！n); /提示鏈表創(chuàng)建完成 3. 出隊(duì)處理main()函數(shù)從循環(huán)鏈表中按初始密碼依次掃描，找出對應(yīng)的玩家序列輸出其持有的密碼i=pphead-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)

12、，使p和pphead鏈接，輸出p指向節(jié)點(diǎn)的編號(hào)和密碼值，釋放pphead，如此循環(huán)，直至把所有節(jié)點(diǎn)都打印和刪除為止！*/根據(jù)流程圖，出隊(duì)函數(shù)程序如下：void jose(lnode *pphead,int m_pwd)int i,j;lnode *p,*p_del;/定義指針變量for(i=1;p!=pphead;i+)for(j=1;jnext;/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(第%d個(gè)人出

13、列，密碼：%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. 約瑟夫環(huán)說明模塊void instruction() printf(*n); printf(約瑟夫環(huán):n); printf(

14、 編號(hào)為1,2,3,4,n的n個(gè)人按順時(shí)針方向圍坐一圈,每人持有一個(gè)密n); printf(碼(正整數(shù)).一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開始n); printf(按順時(shí)針方向自1開始順序報(bào)數(shù),報(bào)到時(shí)停止.報(bào)m的人出列，將他的密碼n); printf(m作為新的m值,從他在順時(shí)針方向上的下一人開始重新從1報(bào)數(shù),如此下去,n); printf(直到所有人全部出列為止.編程打印出列順序.n); printf(*n); return 0;5. 菜單模塊void menu()printf(*約瑟夫環(huán) *n);printf( n);printf( 1約瑟夫環(huán)問題的闡述 n);print

15、f( 2按要求求解約瑟夫環(huán) n);printf( 0退出 n);printf(* 歡迎使用！ *n); 四、程序調(diào)試與測試1. 調(diào)用模塊時(shí)，結(jié)點(diǎn)結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩次錯(cuò)誤，加入子函數(shù)的聲明后錯(cuò)誤消失。2 . 剛開始時(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)過本次實(shí)驗(yàn)，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了進(jìn)一步的了解，每一個(gè)程序經(jīng)過需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)之后，思路即清

16、晰呈現(xiàn)，程序也很快就出來了，最后經(jīng)過調(diào)試、運(yùn)行又有新的體驗(yàn)。這是一個(gè)使用循環(huán)鏈表的經(jīng)典問題。本程序開始運(yùn)行界面如下：圖7 約瑟夫環(huán)開始運(yùn)行界面選擇1進(jìn)入約瑟夫環(huán)問題闡述。圖8 約瑟夫環(huán)問題闡述選擇2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：7請輸入開始上限數(shù)m：20；請依次輸入每個(gè)人的密碼：3 1 7 2 4 8 4出隊(duì)順序：6 1 4 7 2 3 5圖9 約瑟夫環(huán)測試1繼續(xù)選擇2，輸入下列數(shù)據(jù)測試：請輸入總?cè)藬?shù)n：5請輸入開始上限數(shù)m：30請依次輸入每個(gè)人的密碼：3 4 5 6 7 出隊(duì)順序：5 3 1 2 4圖11 約瑟夫環(huán)測試3測試完成，選擇0退出。 設(shè)計(jì)總結(jié) 我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是:約瑟夫環(huán),通過對該題目的設(shè)計(jì),我加深了對數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解,進(jìn)一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對單循環(huán)鏈表上基本運(yùn)算的實(shí)現(xiàn),學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問題,鍛煉了自己動(dòng)手的能力。通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫出來，所以這次課程設(shè)計(jì)最大的收獲就在于對循環(huán)鏈表有了一定的理