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

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

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

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

4、 已存在。操作結(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ù)模塊有序表的輸出。四、源程序代碼#includestdio.h#includemalloc.h/1.元素類型，結(jié)點類型和指針類型typedef struct LNode/定義結(jié)構(gòu)體，i

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

6、輸入密碼函數(shù)int enterPwd(int n)/參數(shù)n 傳遞人數(shù)int i,j;printf(n請輸入密碼for( i=1;inum=i;pt-pwd=j;/num/pwd存儲人的序號存儲人的密碼pt=pt-next;pt=p;return j;/4、創(chuàng)建輸出函數(shù)int outList(int m,int n)/參數(shù)m、 n 傳遞報數(shù)上限值和人數(shù)int i,a;for(i=1;i=n;i+)/用一個for循環(huán)搜索循環(huán)鏈表for(a=1;anext;p=pt-next;m=p-pwd;printf(%d ,p-num);/輸出人的序號pt-next=p-next;free(p);/釋放動態(tài)申

7、請的結(jié)點空間return 0;/ 主函數(shù)void main() int m,n; /m為報數(shù)上限值， n 為人數(shù) printf(n 參數(shù) m、n 傳遞報數(shù)上限值和人數(shù) ;n);printf(n請輸入 m 和 n: n);scanf(%d %d,&m,&n);creatLinkList( n); /調(diào)用創(chuàng)建鏈表函數(shù)enterPwd( n);/調(diào)用輸入密碼函數(shù)printf(n出隊的人依次是 :n);outList( m,n);/調(diào)用輸出鏈表函數(shù)五、測試結(jié)果及功能說明輸入報數(shù)上限值為m 為 6 ，人數(shù) n 為 7；7 個人數(shù)密碼依次是 1，2，3，4，5，6，7；出隊的人號碼依次是： 6，5，4，3，2，1，7六、設(shè)計體會數(shù)據(jù)結(jié)構(gòu)是一門比較抽象的課程，但是也是一門最基礎(chǔ)的課程學(xué)的過程。在現(xiàn)實生活的應(yīng)用也非常廣泛通過設(shè)計該實驗讓我更加深刻的掌握了掌握了， 有關(guān)鏈表的知識， 同時也認(rèn)識到了自己在平時學(xué)習(xí)當(dāng)中的盲點， 通過這次實驗發(fā)現(xiàn)了自己在數(shù)據(jù)結(jié)構(gòu)這門功課上存在嚴(yán)重的不足。 鏈表中的指針理