數(shù)據(jù)結構實驗約瑟夫環(huán)

1、數(shù)據(jù)結構課程設計題目1. 目的數(shù)據(jù)結構是研究數(shù)據(jù)元素之間的邏輯關系的一門課程，以及數(shù)據(jù)元素及其關系在計算機中的存儲表示和對這些數(shù)據(jù)所施加的運算。該課程設計的目的是通過課程設計的綜合訓練，培養(yǎng)分析和編程等實際動手能力，系統(tǒng)掌握數(shù)據(jù)結構這門課程的主要內(nèi)容。2. 內(nèi)容本次課程設計的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問題，循環(huán)鏈表是一種首尾相接鏈表，其特點是無須增加存儲容量，僅對表的鏈接方式稍作改變，使表處理更加靈活，約瑟夫環(huán)問題就是用單循環(huán)鏈表處理的一個實際應用。通過這個設計實例，了解單鏈表和單循環(huán)鏈表的相同與不同之處，進一步加深對鏈表結構類型及鏈表操作的理解。 約瑟夫環(huán)問題的描述是：設編號為1，2，n

2、的n個人按順時針方向圍坐一圈，每個人持有一正整數(shù)密碼。開始時選擇一個正整數(shù)作為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，報m的人出圈，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新從1報數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設計一個程序模擬此過程，求出出圈的編號序列。3. 設計： 1）對設計內(nèi)容進行分析1234567890這是第一個人，他的密碼是“1”，當他輸一個m值，如果m=3,則從他開始向下走3個這就是第二步的位置，這時他的密碼作為新的m值，即m=4,同時得到的第一個密碼為4；4號出去向下走4，到9這兒；（這這一步完了剩余的為：

3、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約瑟夫環(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)原理演

4、示圖2）邏輯設計1、循環(huán)鏈表抽象數(shù)據(jù)類型定義typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結構 int num;/編號 int pwd;/passwordstruct LNode *next;/指向下一結點的指針LNode;2、本程序包含一下幾個模塊（1）構造結點模塊LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結點 p-num=m_num;/把實參賦給相應的數(shù)據(jù)域p-pwd=m_pwd;p-next=NULL;/指針域為空return p; （2）創(chuàng)建鏈

5、表模塊void createList(LNode *ppHead,int n)（3）出隊處理模塊void jose(LNode *ppHead,int m_pwd)（4）約瑟夫環(huán)說明輸出模塊void instruction()（5）菜單模塊void menu()（6）主函數(shù)模塊int main（）函數(shù)的調(diào)用關系圖如下：Case 2:建立的約瑟夫環(huán),并輸出已建立的約瑟夫環(huán)：createList(LNode *ppHead,int n)輸出該約瑟夫環(huán)的每個人的出列順序: jose(LNode *ppHead,int m_pwd)圖3 約瑟夫環(huán)函數(shù)調(diào)用關系圖菜單函數(shù)；void menu()主函數(shù)調(diào)用

6、函數(shù)；main()Case 1：一個簡單的輸出函數(shù)，用于說明約瑟夫環(huán)；void instruction()Case 0:default : 輸入0，退出 exit(0)；3）具體設計流程：1. 主函數(shù)Main()開始Menu()功能菜單功能1：約瑟夫環(huán)說明功能2：按要求求解約瑟夫環(huán)功能3：退出系統(tǒng)輸入總?cè)藬?shù)n輸入開始上線數(shù)：m輸入每個玩家的密碼調(diào)用：createList(&ppHead,n);jose(ppHead,m);函數(shù)求解所需的密碼序列選擇要執(zhí)行的操作程序運行完，自動返回到功能菜單圖4 主函數(shù)數(shù)據(jù)流程圖根據(jù)流程圖，主函數(shù)程序如下：int main() int n,m,x; LNode

7、*ppHead=NULL; menu(); for(;) printf(n請選擇要執(zhí)行的操作：); scanf(%d,&x); system(cls); switch(x)case 1: printf(*n); printf(約瑟夫環(huán):n); printf( 編號為1,2,3,4,n的n個人按順時針方向圍坐一圈,每人持有一個密n); printf(碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始n); printf(按順時針方向自1開始順序報數(shù),報到m時停止.報m的人出列，將他的密碼n); printf(m作為新的m值,從他在順時針方向上的下一人開始重新從1報數(shù),如此下去,

8、n); printf(直到所有人全部出列為止.編程打印出列順序.n); printf(*n); main();break; case 2: printf(n請輸入總?cè)藬?shù)n：); scanf(%d,&n); printf(請輸入開始上限數(shù)m：); scanf(%d,&m); createList(&ppHead,n); printf(n);printf(出隊順序：n); jose(ppHead,m); printf(n約瑟夫環(huán)游戲結束!n); main();break; case 0: exit(0); default: system(cls); printf(n您選擇的操作有誤，請重新選擇.n

9、nn); main(); return 0; 2. 鏈表的創(chuàng)建否是createList（）;從主函數(shù)中獲取玩家信息n如果n0創(chuàng)建循環(huán)單鏈表，儲存各個玩家密碼退出創(chuàng)建鏈表完成返回主函數(shù)main()創(chuàng)建儲存玩家密碼的循環(huán)單鏈表的方法Main()函數(shù)圖5 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流程圖/*創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個數(shù)為n，并輸入每個人的密碼值，若建立失敗則生成頭結點，讓cur指向他，若建立成功則插入結點P，cur指向的數(shù)據(jù)元素為p,后續(xù)為空的節(jié)點，再把P插入循環(huán)鏈表ppHead中*/根據(jù)流程圖，創(chuàng)建鏈表函數(shù)程序如下：void createList(LNode *ppHead,int n)int

10、i,m_pwd;LNode *p,*cur;/cur:浮標指針for(i=1;inext=*ppHead;/cur的指針域指向自身 else/如果不為空，則插入結點 p-next = cur-next;cur-next = p;cur= p;/cur指向新插入結點 printf(完成創(chuàng)建！n); /提示鏈表創(chuàng)建完成 3. 出隊處理Main()函數(shù)從循環(huán)鏈表中按初始密碼依次掃描，找出對應的玩家序列輸出其持有的密碼i=ppHead-pwd; j=ppHead-num;移動浮標指針m_pwd=ppHead-pwd;輸出密碼后，刪除相應的結點，并釋放所占的儲存空間free(ppHead); ppHea

11、d=p-next;執(zhí)行完后返回主函數(shù)jose()；出隊函數(shù)出隊處理的方法圖6 出隊函數(shù)的數(shù)據(jù)流程圖/*p指向要刪除節(jié)點的前一個節(jié)點，ppHead指向要刪除的節(jié)點，使p=ppHead，ppHead再指向要刪除節(jié)點的下一個節(jié)點，使p和ppHead鏈接，輸出p指向節(jié)點的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/根據(jù)流程圖，出隊函數(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指向下一個元素

12、p-next = ppHead-next;/p結點與頭結點鏈接i=ppHead-pwd;/i賦值為ppHead-pwd j=ppHead-num;/j賦值為ppHead-num，j為要刪除的密碼值printf(第%d個人出列，密碼：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd賦值為ppHead-pwdfree(ppHead);/釋放頭結點ppHead=p-next;/ppHead重新賦值給p-next,即釋放前的ppHead-pwd指針/刪除報數(shù)結點 i=ppHead-pwd;/i賦值為ppHead-pwdj=ppHead-num;/j賦值為ppHead-numprint

13、f(最后一個出列是%d號，密碼是:%dn,j,i); free(ppHead);/釋放頭結點4. 約瑟夫環(huán)說明模塊void instruction() printf(*n); printf(* 約瑟夫(Joseph)環(huán): *n); printf(* 編號為1，2，,n的n個人按順時針方向圍坐一圈，每人持有一個密碼 *n); printf(* (正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順 *n); printf(* 時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼 *n); printf(* m作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)

14、，如此下 *n); printf(* 去，直至所有人全部出列為止。試設計一個程序求出出列順序。 *n); printf(*n); 5. 菜單模塊void menu()printf(*約瑟夫環(huán) *n);printf( n);printf( 1約瑟夫環(huán)問題的闡述 n);printf( 2按要求求解約瑟夫環(huán) n);printf( 0退出 n);printf(* 歡迎使用！ *n); 4. 實現(xiàn)： 程序語言：#include /輸入輸出函數(shù)頭文件#include /字符串轉(zhuǎn)短整形函數(shù)的頭文件/typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結構 int num;/編號int pwd;/

15、密碼struct LNode *next;/指向下一結點的指針LNode;/*構造結點*/LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一個結點 p-num=m_num;/把實參賦給相應的數(shù)據(jù)域p-pwd=m_pwd;p-next=NULL;/指針域為空return p; /*創(chuàng)建循環(huán)鏈表*/void createList(LNode *ppHead,int n)int i,m_pwd;LNode *p,*cur;/cur:浮標指針for(i=1;inext=*ppHead;/

16、cur的指針域指向自身 else/如果不為空，則插入結點 p-next = cur-next;cur-next = p;cur = p;/cur指向新插入結點 printf(完成創(chuàng)建！n); /提示鏈表創(chuàng)建完成 /*出隊處理*/void jose(LNode *ppHead,int m_pwd)/*p指向要刪除節(jié)點的前一個節(jié)點，ppHead指向要刪除的節(jié)點，使p=ppHead， ppHead再指向要刪除節(jié)點的下一個節(jié)點，使p和ppHead鏈接，輸出p指向節(jié)點 的編號和密碼值，釋放ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/int i,j;LNode *p,*p_del;/定義指

17、針變量for(i=1;p!=ppHead;i+)for(j=1;jnext;/ppHead指向下一個元素p-next = ppHead-next;/p結點與頭結點鏈接i=ppHead-pwd;/i賦值為ppHead-pwd j=ppHead-num;/j賦值為ppHead-num，j為要刪除的密碼值printf(第%d個人出列，密碼：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd賦值為ppHead-pwdfree(ppHead);/釋放頭結點ppHead=p-next;/ppHead重新賦值給p-next,即釋放前的ppHead-pwd指針/刪除報數(shù)結點 i=ppHead-

18、pwd;/i賦值為ppHead-pwdj=ppHead-num;/j賦值為ppHead-numprintf(最后一個出列是%d號，密碼是:%dn,j,i); free(ppHead);/釋放頭結點void instruction() printf(*n); printf(* 約瑟夫(Joseph)環(huán): *n); printf(* 編號為1，2，,n的n個人按順時針方向圍坐一圈，每人持有一個密碼 *n); printf(* (正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順 *n); printf(* 時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼 *n)

19、; printf(* m作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下 *n); printf(* 去，直至所有人全部出列為止。試設計一個程序求出出列順序。 *n); printf(*n); void menu()printf(*約瑟夫環(huán)*n);printf(* 制作人：志斌、基岳、偉明 *n);printf(* *n);printf(* 1約瑟夫環(huán)問題的闡述 *n);printf(* 2按要求求解約瑟夫環(huán) *n);printf(* 0退出 *n);printf(* *n);printf(*歡迎使用！*n); /*主函數(shù)模塊*/int main() int n,m,x; L

20、Node *ppHead=NULL; menu(); for(;) printf(n請選擇要執(zhí)行的操作：); scanf(%d,&x); system(cls); switch(x) case 1: printf(*n); printf(* 約瑟夫(Joseph)環(huán): *n); printf(* 編號為1，2，,n的n個人按順時針方向圍坐一圈，每人持有一個密碼 *n); printf(* (正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順 *n); printf(* 時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼 *n); printf(* m作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下 *n); printf(* 去，直至所有人全部出列為止。試設計一個程序求出出