1、數(shù)據(jù)結(jié)構(gòu)實驗報告題目：約瑟夫環(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é)構(gòu)模擬此過程，按照出列的順序打印各人的編號。實驗提示程序運行后首先要求用戶指定初始報數(shù)上限值。然后讀取各人的密碼。設n<=30。程序執(zhí)行后，要求用戶在計算機終端上顯示“提示信息”后，用

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

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

4、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.元素類型，結(jié)點類型和指針類型 typedef struct LNode /定義結(jié)構(gòu)體

5、， int 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)建不成功，返回0 p=head; for(i=1;i<n;i+) pt=(struct LNode*)malloc(sizeof(struc

6、t LNode); if(!pt) return 0; p->next=pt; p=pt; p->next=head;/構(gòu)成循環(huán)鏈表 pt=head;return 0; /3.創(chuàng)建輸入密碼函數(shù) int enterPwd(int n) /參數(shù)n傳遞人數(shù) 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->next; pt=p;return

7、 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;a<m;a+) /刪除結(jié)點 pt=pt->next; p=pt->next; m=p->pwd; printf("%d ",p->num); /輸出人的序號 pt->next=p->next; free(p); /釋放動態(tài)申請的結(jié)點空間 return 0; /主函數(shù)void main() int m,n; /m為報數(shù)上

8、限值，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ù)據(jù)結(jié)構(gòu)是一門比較抽象的課程，但是也是一門最基礎的課程學的過程。在現(xiàn)實生活的應用也非常廣泛通過設計該實驗讓我更加深刻的掌握了掌握了，有關鏈表的知識，同時也認識到了自己在平時學習當中的盲點，通過這次實驗發(fā)現(xiàn)了自己在數(shù)據(jù)結(jié)構(gòu)這門