數(shù)據(jù)結(jié)構約瑟夫環(huán)問題

1、題目：約瑟夫環(huán)問題一設計內(nèi)容 問題描述 約瑟夫環(huán)問題的一種描述是：編號為 1，2，3，,， n 的 n 個人按順時針方向圍 坐一圈，每人手持一個密碼(正整數(shù)) 。一開始任選一個整數(shù)作為報數(shù)上限值， 從第一人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將 它的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從 1報數(shù)，如 此下去直到所有人全部出列為止。試設計程序?qū)崿F(xiàn)之。 基本要求 利用循環(huán)鏈表存儲結(jié)構模擬此過程，按照出列的順序打印各人的編號。 實驗提示 程序運行后首先要求用戶指定初始報數(shù)上限值。然后讀取各人的密碼。設 n<=30。 程序執(zhí)行后，要求用戶在計算機終端上顯

2、示“提示信息”后，用鍵盤輸入“提示 信息”中規(guī)定的命令，以“回車符”為結(jié)束標志。相應的輸入數(shù)據(jù)和運算結(jié)果顯 示在其后。二、設計目的1. 達到熟練掌握C+語言的基本知識和技能；2. 能夠利用所學的基本知識和技能，解決簡單的面向?qū)ο蟪绦蛟O計問題。3. 把課本上的知識應用到實際生活中，達到學以致用的目的。三、系統(tǒng)分析與設計(確定程序功能模塊)1、為實現(xiàn)上述程序的功能，應以有序鏈表表示集合?；静僮鳎篒nitList(&L)操作結(jié)果：構造一個空的有序表 L。DestroyList(&L)初始條件：有序表 L 已存在。操作結(jié)果：銷毀有序表 L。ListEmpty(L)初始條件：有序表 L

3、 已存在。操作結(jié)果：若L為空表，則返回TRUE否則返回FALSEListLength(L)初始條件：有序表 L 已存在。 操作結(jié)果：返回 L 中數(shù)據(jù)元素個數(shù)。GetElem(L,i)初始條件：有序表L已存在，并且 K i < ListLength(L)。 操作結(jié)果：返回 L 中第 i 個數(shù)據(jù)元素。LocatePos(L,e)初始條件：有序表L已存在，e和有序表中元素同類型的值。操作結(jié)果：若 L 中存在和 e 相同的元素，則返回位置；否則返回 0InsertElem(&L,e)初始條件：有序表 L 已存在操作結(jié)果：在L中，按有序關系插入值和e相同的數(shù)據(jù)元素。DeleteElem(&

4、amp;L,i)初始條件：有序表 L 已存在。操作結(jié)果：刪除L中第i個數(shù)據(jù)元素。ListTraverse(L,visit()初始條件：有序表 L 已存在。操作結(jié)果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit() 失敗，則操作失敗。 ADT OrderedList2、本程序包含兩個模塊：(1 )主程序模塊：void main()初始化；調(diào)用函數(shù)(接受命令，處理命令) (2) 有序表單元模塊實現(xiàn)有序表的抽象數(shù)據(jù)類型。(3) 輸出函數(shù)模塊有序表的輸出。四、源程序代碼#include"stdio.h" #include"malloc.h"/1.

5、 元素類型，結(jié)點類型和指針類型定義結(jié)構體，pwd用來存儲人的typedef struct LNode/int num,pwd; /num 密碼struct LNode *next;struct LNode *head,*p,*pt; /2 、 創(chuàng)建循環(huán)鏈表函數(shù) int creatLinkList(int n) / 用來存儲人的序號定義結(jié)點參數(shù) n 傳遞人數(shù)，int i;head=(struct LNode*)malloc(sizeof(struct LNode);/ 創(chuàng)建一個帶頭結(jié)點的鏈表if(!head) return 0; / 創(chuàng)建不成功，返回 0 p=head;for(i=1;i<

6、n;i+)pt=(struct LNode*)malloc(sizeof(struct LNode);if(!pt) return 0;p->next=pt;p=pt;p->next=head; / 構成循環(huán)鏈表 pt=head;return 0;/3. 創(chuàng)建輸入密碼函數(shù)int enterPwd(int n)/int i,j;printf("n 請輸入密碼 : n");for( i=1;i<=n;i+)scanf("%d",&j);pt->num=i; /num pt->pwd=j; /pwd pt=pt->n

7、ext;pt=p;return j;/4 、創(chuàng)建輸出函數(shù)int outList(int m,int n) /int i,a;for(i=1;i<=n;i+) /for(a=1;a<m;a+) /pt=pt->next;p=pt->next;m=p->pwd; printf("%d ",p->num); / pt->next=p->next;參數(shù) n 傳遞人數(shù)存儲人的序號存儲人的密碼參數(shù) m、 n 傳遞報數(shù)上限值和人數(shù)用一個 for 循環(huán)搜索循環(huán)鏈表刪除結(jié)點輸出人的序號free(p); II釋放動態(tài)申請的結(jié)點空間return 0

8、;II主函數(shù)void mai n() int m,n; I/m為報數(shù)上限值，n為人數(shù)printf("n 參數(shù)m n傳遞報數(shù)上限值和人數(shù);n");prin tf("n請輸入 m 和 n: n");scanf("%d %d",&m,&n);creatLi nkList( n); /調(diào)用創(chuàng)建鏈表函數(shù)en terPwd( n); II調(diào)用輸入密碼函數(shù)printf("n出隊的人依次是:n");outList( m,n); II調(diào)用輸出鏈表函數(shù)五、測試結(jié)果及功能說明下：'紳結(jié)構9訪陰儼據(jù)結(jié)罰啟疾-參數(shù)叭n傳遞報數(shù)上限值和人數(shù)：X青輸入m和亦F7青輸入密碼:1 2 3 4 5 6 7血隊的人依次是：6 5 4 3 2 1 7 Press any key to cont inue輸入報數(shù)上限值為 m 為 6 ，人數(shù) n 為 7；7 個人數(shù)密碼依次是 1，2，3， 4，5，6，7； 出隊的人號碼依次是： 6，5，4，3，2，1，7六、設計體會數(shù)據(jù)結(jié)構是一門比較抽象的課程，但是也是一門最基礎的課程學的過程。 在現(xiàn)實生活的應用也非常廣泛通過設計該實驗讓我更加深刻的掌握了掌握了， 有 關鏈表的知識， 同時也認識到了自己在平時學習當中的盲點， 通過這次實驗發(fā)現(xiàn) 了自己在數(shù)據(jù)結(jié)構這門