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

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

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

3、則返回TRUE，否則返回FALSE。ListLength(L)初始條件：有序表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)。GetElem(L,i)初始條件：有序表L已存在，并且1iListLength(L)。操作結(jié)果：返回L中第i個(gè)數(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已存在。操作結(jié)果：刪除L中第i個(gè)數(shù)據(jù)元素。

4、ListTraverse(L,visit()初始條件：有序表L已存在。操作結(jié)果：依次對L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。 ADT OrderedList2、本程序包含兩個(gè)模塊： （1）主程序模塊： void main() 初始化； 調(diào)用函數(shù)（接受命令，處理命令） （2）有序表單元模塊實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型。 （3）輸出函數(shù)模塊有序表的輸出。四、源程序代碼#include"stdio.h"#include"malloc.h"/1.元素類型，結(jié)點(diǎn)類型和指針類型 typedef struct LNode /定義結(jié)構(gòu)體

5、， int num,pwd; /num用來存儲人的序號，pwd用來存儲人的密碼 struct LNode *next;struct LNode *head,*p,*pt; /定義結(jié)點(diǎn)/2、創(chuàng)建循環(huán)鏈表函數(shù)int creatLinkList(int n) /參數(shù)n傳遞人數(shù)， int i; head=(struct LNode*)malloc(sizeof(struct LNode);/創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈表 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傳遞報(bào)數(shù)上限值和人數(shù) int i,a; for(i=1;i<=n;i+) /用一個(gè)for循環(huán)搜索循環(huán)鏈表 for(a=1;a<m;a+) /刪除結(jié)點(diǎn) pt=pt->next; p=pt->next; m=p->pwd; printf("%d ",p->num); /輸出人的序號 pt->next=p->next; free(p); /釋放動(dòng)態(tài)申請的結(jié)點(diǎn)空間 return 0; /主函數(shù)void main() int m,n; /m為報(bào)數(shù)上

8、限值，n為人數(shù)printf("n參數(shù)m、n傳遞報(bào)數(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出隊(duì)的人依次是:n"); outList( m,n); /調(diào)用輸出鏈表函數(shù)五、測試結(jié)果及功能說明 輸入報(bào)數(shù)上限值為m為6 ，人數(shù)n為7；7個(gè)人數(shù)密碼依次是1，2，3，4，5，6，7；出隊(duì)的人號碼依次是：6，5，4，3，2，1，7六、設(shè)計(jì)體會(huì)數(shù)據(jù)結(jié)構(gòu)是一門比較抽象的課程，但是也是一門最基礎(chǔ)的課程學(xué)的過程。在現(xiàn)實(shí)生活的應(yīng)用也非常廣泛通過設(shè)計(jì)該實(shí)驗(yàn)讓我更加深刻的掌握了掌握了，有關(guān)鏈表的知識，同時(shí)也認(rèn)識到了自己在平時(shí)學(xué)習(xí)當(dāng)中的盲點(diǎn)，通過這次實(shí)驗(yàn)發(fā)現(xiàn)了自己在數(shù)據(jù)結(jié)構(gòu)這門