《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-約瑟夫環(huán).doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-約瑟夫環(huán).doc（10頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí) 驗(yàn) 報(bào) 告課程名稱數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)課程編號0906550實(shí)驗(yàn)項(xiàng)目名稱約瑟夫環(huán)學(xué)號年級2014姓名專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生所在學(xué)院計(jì)算機(jī)學(xué)院指導(dǎo)教師楊靜實(shí)驗(yàn)室名稱地點(diǎn)21B276哈爾濱工程大學(xué)實(shí)驗(yàn)報(bào)告一實(shí)驗(yàn)課名稱：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)名稱:約瑟夫環(huán)班級 學(xué)號 姓名 時(shí)間 2016.04.05一、 問題描述設(shè)有編號為 1，2,n 的 n(n0)個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼 m.從第一個(gè)人開始報(bào)數(shù),報(bào)到 m 時(shí)停止報(bào)數(shù),報(bào) m 的人出圈，再從他的下一個(gè)人起重新報(bào)數(shù),報(bào)到 m 時(shí)停止報(bào)數(shù),報(bào) m 的出圈，如此下去，直到所有人全部出圈為止。當(dāng)任意給定 n 和

2、m 后，設(shè)計(jì)算法求 n 個(gè)人出圈的次序.二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)每個(gè)人按報(bào)數(shù)順序有唯一的前驅(qū)與后繼關(guān)系,并且報(bào)數(shù)順序循環(huán)，所以采用單向循環(huán)鏈表模擬，鏈表節(jié)點(diǎn)存儲序號number和m，存儲結(jié)構(gòu)定義如下:typedef struct List int number; /序號 int m; /密碼m struct List next; /指向下一個(gè)人的指針List;為了方便查詢及刪除的定位，表按序號有序存儲。三、 算法設(shè)計(jì)1.初始化，構(gòu)建循環(huán)鏈表，依次存儲序號1至n的人,鏈表指針 L指向序號為1的人.List create_list_with_one_m（List *L, int n） List *pre

3、； / previous node int i=1； for（； i next = NULL； if（i = 1） /只在第一次進(jìn)入， init L, pre L = cur; pre = cur； else /鏈接pre與cur，并向后移動pre prenext = cur； pre = cur； prenext = L；return L;2.為了獲取被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)， m=1時(shí)重新賦值m為1+循環(huán)鏈表的長度，所以需要一個(gè)函數(shù)獲取循環(huán)鏈表的長度./ 返回循環(huán)鏈表L的長度int length_list（List L) int i = 1; List *p = Lnext; while(p

4、 ！= L） i+； p = pnext； return i；3。模擬報(bào)數(shù)過程, L永遠(yuǎn)指向下一個(gè)第一個(gè)報(bào)數(shù)的人,刪除L開始后第m個(gè)節(jié)點(diǎn)，用結(jié)點(diǎn)指針del返回刪除結(jié)點(diǎn).List delete_node(List *L， int m, List *del） if(m = 1） /為了獲取被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn), m=1時(shí)重新賦值為1+length int l = length_list（*L); m = 1+l； List *pri = *L; / prior node int j = 0； while（j next; /delete node pri-next = delnext； *L =

5、prinext; return del;4.輸入構(gòu)建好的鏈表L，人數(shù)n,密碼m,每次調(diào)用delete_node函數(shù)刪除一人，進(jìn)行n次.void joseph_with_one_m(List L， int n， int m) int i = 1； while(i = n) / 每次del一個(gè)node List del； del = delete_node(L， m， del）； printf（第%d個(gè)出圈的序號是%dn”, i， del-number）； free（del); i+； 5.如果密碼m不同，則刪除節(jié)點(diǎn)后，以刪除節(jié)點(diǎn)的密碼m作為新的m。void joseph_with_diff_m（

6、List *L, int n) int i = 1； int m = L-m； while(i m； free（del)； i+； 6.在主函數(shù)中獲取人數(shù)和密碼m，構(gòu)建鏈表，調(diào)用joseph函數(shù)。int main（） int n， m； printf（”請輸入人數(shù)n： ”）； scanf（%d, n）； printf（請輸入所有人的m： ”）; scanf(”%d， &m)； List *L; L = create_list_with_one_m（L, n); joseph_with_one_m（L， n， m）; return 0；四、界面設(shè)計(jì)程序需要獲取人數(shù)n,密碼m(相同的密碼m和不同的

7、密碼m），輸出出圈順序.所以以提示的形式獲取n和m。五、運(yùn)行測試與分析（1）運(yùn)行程序，顯示輸入提示,如圖所示。（2）根據(jù)提示，輸入人數(shù)，并輸入密碼，即可輸出結(jié)果。（3）需要不同密碼的程序可根據(jù)提示輸入不同密碼，即可輸出結(jié)果.六、實(shí)驗(yàn)收獲與思考1. 掌握了循環(huán)鏈表的初始化，刪除,求長等常用方法的使用，鞏固了相關(guān)數(shù)據(jù)結(jié)構(gòu)。2. 在實(shí)驗(yàn)中熟悉了C語言對數(shù)據(jù)結(jié)構(gòu)的描述，發(fā)現(xiàn)了過去的薄弱之處,重新進(jìn)行學(xué)習(xí).3. 體會到了正確的數(shù)據(jù)結(jié)構(gòu)對程序的重要性。七、附錄1。相同密碼include #include stdlib.htypedef struct List int number; int m; stru

8、ct List next;List；/ 構(gòu)建循環(huán)鏈表，依次存儲1n， L指向1 * pre:previous node * cur：current node */ List create_list_with_one_m（List L, int n） List *pre; int i=1; for（; i = n； i+） List *cur = (List*)malloc(sizeof（List)； cur-number = i； curnext = NULL; if（i = 1） /只在第一次進(jìn)入, init L, pre L = cur; pre = cur； else /鏈接pre與cu

9、r,并向后移動pre pre-next = cur； pre = cur; prenext = L;return L;/ 返回循環(huán)鏈表L的長度int length_list(List *L) int i = 1; List p = Lnext; while（p != L) i+; p = p-next; return i；/ 刪除L開始后第m個(gè)節(jié)點(diǎn),用del返回 * L永遠(yuǎn)指向第一個(gè)報(bào)數(shù)的人 * pri： prior node * del： delete node/ List delete_node（List *L, int m， List *del） if（m = 1） /為了獲取被刪除節(jié)點(diǎn)

10、的前一個(gè)節(jié)點(diǎn), m=1時(shí)重新賦值為1+length int l = length_list(L)； m = 1+l； List pri = *L; int j = 0; while（j m2） /移動m-2次，獲取pri pri = pri-next; j+； del = pri-next; pri-next = delnext; *L = pri-next; return del；void joseph_with_one_m(List *L， int n， int m) int i = 1； while(i = n) / 每次del一個(gè)node List del; del = delete_

11、node（&L， m， del）; printf(第d個(gè)出圈的序號是%dn， i,delnumber); free（del); i+； int main（） int n, m; printf（請輸入人數(shù)n： ”）； scanf（”d, &n）; printf（請輸入所有人的m: ”）; scanf(d”, &m）; List L; L = create_list_with_one_m（L， n)； joseph_with_one_m(L， n, m）； return 0;2.不同密碼include stdio.hinclude stdlib.htypedef struct List int number； int m; struct List *next;List；/* 構(gòu)建循環(huán)鏈表，依次存儲1n, L指向1 pre:previous no