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

..數(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í)行后,要求用戶在計算機終端上顯示"提示信息"后,用鍵盤輸入"提示信息"中規(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)以有序鏈表表示集合。基本操作：InitList<&L>操作結(jié)果：構(gòu)造一個空的有序表L。DestroyList<&L>初始條件：有序表L已存在。操作結(jié)果：銷毀有序表L。ListEmpty<L>初始條件：有序表L已存在。操作結(jié)果：若L為空表,則返回TRUE,否則返回FALSE。ListLength<L>初始條件：有序表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。GetElem<L,i>初始條件：有序表L已存在,并且1≤i≤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已存在。操作結(jié)果：刪除L中第i個數(shù)據(jù)元素。ListTraverse<L,visit<>>初始條件：有序表L已存在。操作結(jié)果：依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit<>。一旦visit<>失敗,則操作失敗。}ADTOrderedList2、本程序包含兩個模塊：〔1主程序模塊：voidmain<>{初始化；調(diào)用函數(shù)〔接受命令,處理命令}〔2有序表單元模塊——實現(xiàn)有序表的抽象數(shù)據(jù)類型。 〔3輸出函數(shù)模塊——有序表的輸出。四、源程序代碼#include"stdio.h"#include"malloc.h"http://1.元素類型,結(jié)點類型和指針類型typedefstructLNode//定義結(jié)構(gòu)體,{intnum,pwd;//num用來存儲人的序號,pwd用來存儲人的密碼structLNode*next;};structLNode*head,*p,*pt;//定義結(jié)點//2、 創(chuàng)建循環(huán)鏈表函數(shù)intcreatLinkList<intn>//參數(shù)n傳遞人數(shù),{inti;head=<structLNode*>malloc<sizeof<structLNode>>; //創(chuàng)建一個帶頭結(jié)點的鏈表if<!head>{return0;}//創(chuàng)建不成功,返回0p=head;for<i=1;i<n;i++>{pt=<structLNode*>malloc<sizeof<structLNode>>;if<!pt>{return0;}p->next=pt;p=pt;}p->next=head; //構(gòu)成循環(huán)鏈表pt=head; return0;}//3.創(chuàng)建輸入密碼函數(shù)intenterPwd<intn>//參數(shù)n傳遞人數(shù){inti,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; returnj;}//4、創(chuàng)建輸出函數(shù)intoutList<intm,intn>//參數(shù)m、n傳遞報數(shù)上限值和人數(shù){inti,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é)點空間}return0;}//主函數(shù)voidmain<>{intm,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)中的盲點,通過這次實驗