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

2、機終端上顯示“提示信息”后，用鍵盤輸入“提示 信息”中規定的命令，以“回車符”為結束標志。相應的輸入數據和運算結果顯 示在其后。二、設計目的1. 達到熟練掌握 C+語言的基本知識和技能；2. 能夠利用所學的基本知識和技能，解決簡單的面向對象程序設計問題。3. 把課本上的知識應用到實際生活中，達到學以致用的目的。三、系統分析與設計(確定程序功能模塊)1、為實現上述程序的功能，應以有序鏈表表示集合。基本操作：InitList(&L) 操作結果：構造一個空的有序表 L。DestroyList(&L)初始條件：有序表 L 已存在。 操作結果：銷毀有序表 L。ListEmpty(L) 初

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

4、值和 e 相同的數據元素。DeleteElem(&L,i) 初始條件：有序表 L 已存在。 操作結果：刪除 L 中第 i 個數據元素。ListTraverse(L,visit() 初始條件：有序表 L 已存在。 操作結果：依次對 L 的每個數據元素調用函數 visit() 。一旦 visit() 失敗，則操作失敗。 ADT OrderedList 2、本程序包含兩個模塊：(1) 主程序模塊： void main()初始化； 調用函數(接受命令，處理命令) (2) 有序表單元模塊實現有序表的抽象數據類型。(3) 輸出函數模塊有序表的輸出。四、源程序代碼#include"stdi

5、o.h" #include"malloc.h"/1. 元素類型，結點類型和指針類型定義結構體，pwd用來存儲人的typedef struct LNode/int num,pwd; /num 密碼struct LNode *next;struct LNode *head,*p,*pt; /2 、 創建循環鏈表函數 int creatLinkList(int n) / 用來存儲人的序號定義結點參數 n 傳遞人數，int i;head=(struct LNode*)malloc(sizeof(struct LNode);/ 創建一個帶頭結點的鏈表if(!head) re

6、turn 0; / 創建不成功，返回 0 p=head;for(i=1;i<n;i+)pt=(struct LNode*)malloc(sizeof(struct LNode);if(!pt) return 0;p->next=pt;p=pt;p->next=head; / 構成循環鏈表 pt=head;return 0;/3. 創建輸入密碼函數int enterPwd(int n)/int i,j;printf("n 請輸入密碼 : n");for( i=1;i<=n;i+)scanf("%d",&j);pt->n

7、um=i; /num pt->pwd=j; /pwd pt=pt->next;pt=p;return j;/4 、創建輸出函數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;參數 n 傳遞人數存儲人的序號存儲人的密碼參數 m、 n 傳遞報數上限值和人數用一個 for 循環搜索循環鏈

8、表刪除結點輸出人的序號free(p); / 釋放動態申請的結點空間return 0;/ 主函數void main() int m,n; /m 為報數上限值， n 為人數printf("n 參數 m、 n 傳遞報數上限值和人數 ;n"); printf("n請輸入 m 和 n: n");scanf("%d %d",&m,&n);creatLinkList( n); /調用創建鏈表函數enterPwd( n); /調用輸入密碼函數printf("n 出隊的人依次是 :n");outList( m,n); /調用輸出鏈表函數五、測試結果及功能說明輸入報數上限值為 m 為 6 ，人數 n 為 7；7 個人數密碼依次是 1，2，3， 4，5，6，7； 出隊的人號碼依次是： 6，5，4，3，2，1，7六、設計體會數據結構是一門比較抽象的課程，但是也是一門最基礎的課程學的過程。 在現實生活的應用也非常廣泛通過設計該實驗讓我更加深刻的掌握了掌握了， 有 關鏈表的知識， 同時也認識到了自己在平時學習當中的盲點， 通過這次實驗發現 了自己在數據結構這門功課上