約瑟夫環(huán)問題課程設計報告

1、數據結構 課程設計報告 設計課題： 約瑟夫問題 院 系： 計算機科學與技術學院 專業(yè)班級： 計算機網絡技術1102班 學生姓名： 張 利 學 號： 1 1 0 8 0 4 0 2 1 1 指導教師： 王 昱 哲 目 錄1.需求分析31.1問題描述3 1.2功能分析42.概要設計53.詳細設計64.調試與操作說明15總 結16一需求分析1.1問題描述約瑟夫環(huán)問題描述的是：設編號為1，2，n的n（n>0）個人按順時針方向圍坐一圈，每個人持有一正整數密碼。開始時選擇一個正整數作為報數上限m，從第一個人開始順時針方向自1起順序報數，報到m時停止報數，報m的人出圈，將他的密碼作為新的m值，從他在順

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

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

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

5、;/指向下一結點的指針LNode;2、本程序包含一下幾個模塊（1）構造結點模塊LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結點 p->num=m_num;/把實參賦給相應的數據域p->pwd=m_pwd;p->next=NULL;/指針域為空return p; （2）創(chuàng)建鏈表模塊void createList(LNode *ppHead,int n)（3）出隊處理模塊void jose(LNode *ppHead,int m_pwd)（4）約瑟夫環(huán)說明輸

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

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

8、 system("cls"); switch(x)case 1: printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n"); printf("碼(正整數).一開始任選一個正整數作為報數的上限值m,從第一個人開始n"); printf("按順時針方向自1開始順序報數,報到m時停止.報m的人出列，將他的密碼n"); printf("m作為新的m值,從他在順時針方向上的下一

9、人開始重新從1報數,如此下去,n"); printf("直到所有人全部出列為止.編程打印出列順序.n"); printf("*n"); main();break; case 2: printf("n請輸入總人數n："); scanf("%d",&n); printf("請輸入開始上限數m："); scanf("%d",&m); createList(&ppHead,n); printf("n");printf("

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

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

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

13、gt;pwd; j=ppHead->num;移動浮標指針m_pwd=ppHead->pwd;輸出密碼后，刪除相應的結點，并釋放所占的儲存空間free(ppHead); ppHead=p->next;執(zhí)行完后返回主函數jose()；出隊函數出隊處理的方法圖6 出隊函數的數據流程圖/*p指向要刪除節(jié)點的前一個節(jié)點，ppHead指向要刪除的節(jié)點，使p=ppHead，ppHead再指向要刪除節(jié)點的下一個節(jié)點，使p和ppHead鏈接，輸出p指向節(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/根據流程圖，出隊函數程序如下：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指向要刪除結點的前一個結點ppHead=ppHead->next;/ppHead指向下一個元素p->next = ppHead->next;/p結點與頭結點鏈接i=ppHead->pwd;/i賦值為ppHead->pwd j=ppHead->num;/j賦值為ppHead->num，j為要刪除的密碼值printf("

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

16、夫環(huán)說明模塊void instruction() printf("*n"); printf("約瑟夫環(huán):n"); printf(" 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n"); printf("碼(正整數).一開始任選一個正整數作為報數的上限值m,從第一個人開始n"); printf("按順時針方向自1開始順序報數,報到時停止.報m的人出列，將他的密碼n"); printf("m作為新的m值,從他在順時針方向上的下一人開始重新從1報數,如此下去,n&qu

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

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