數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告約瑟夫環(huán)

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)課程編號(hào)0906550實(shí)驗(yàn)項(xiàng)目名稱約瑟夫環(huán)學(xué)號(hào)年級(jí)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)班級(jí) 學(xué)號(hào) 姓名 時(shí)間 2016.04.05一、 問題描述設(shè)有編號(hào)為 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)存儲(chǔ)序號(hào)number和m，存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct list int number; /序號(hào) int m; /密碼m struct list *next; /指向下一個(gè)人的指針list;為了方便查詢及刪除的定位，表按序號(hào)有序存儲(chǔ)。三、 算法設(shè)計(jì)1.初始化，構(gòu)建循環(huán)鏈表，依次存儲(chǔ)序號(hào)1至n的人,鏈表指針 l指向序號(hào)為1的人。list *create_list_with_one_m(list *l, int n) list *p

3、re; / previous node int i=1; for(; i number = i; cur-next = null; if(i = 1) /只在第一次進(jìn)入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動(dòng)pre pre-next = cur; pre = cur; pre-next = 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; lis

4、t *p = l-next; while(p != l) i+; p = p-next; 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; j+; del = pri-

5、next; /delete node pri-next = del-next; *l = pri-next; 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 number); free(del); i+; 5.如果密碼m不同，則刪除節(jié)點(diǎn)后，以刪除節(jié)點(diǎn)的密碼m作為新的m。void joseph_with_diff_m(list *l, int n) int i = 1; int m = l-m; wh

6、ile(i number); m = del-m; free(del); i+; 6.在主函數(shù)中獲取人數(shù)和密碼m，構(gòu)建鏈表，調(diào)用joseph函數(shù)。int main() int n, m; printf(請(qǐng)輸入人數(shù)n: ); scanf(%d, &n); printf(請(qǐng)輸入所有人的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和不同的密碼m），輸出出圈順序。所以以提示的形式獲取n和m。五、

7、運(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語言對(duì)數(shù)據(jù)結(jié)構(gòu)的描述，發(fā)現(xiàn)了過去的薄弱之處，重新進(jìn)行學(xué)習(xí)。3. 體會(huì)到了正確的數(shù)據(jù)結(jié)構(gòu)對(duì)程序的重要性。七、附錄1.相同密碼#include #include typedef struct list int number; int m; struct list *next;list;/* * 構(gòu)建循環(huán)鏈表，依次存儲(chǔ)

8、1-n, 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 number = i; cur-next = null; if(i = 1) /只在第一次進(jìn)入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動(dòng)pre pre-next = cur; pre = cur; pre-next = l;return l;/ 返回循環(huán)鏈表l的長度int leng

9、th_list(list *l) int i = 1; list *p = l-next; 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)的前一個(gè)節(jié)點(diǎn), m=1時(shí)重新賦值為1+length int l = length_list(*l); m = 1+l; list *pri =

10、*l; int j = 0; while(j next; j+; del = pri-next; pri-next = del-next; *l = pri-next; return del;void joseph_with_one_m(list *l, int n, int m) int i = 1; while(i number); free(del); i+; int main() int n, m; printf(請(qǐng)輸入人數(shù)n: ); scanf(%d, &n); printf(請(qǐng)輸入所有人的m: ); scanf(%d, &m); list *l; l = create_list_w

11、ith_one_m(l, n); joseph_with_one_m(l, n, m); return 0;2.不同密碼#include #include typedef struct list int number; int m; struct list *next;list;/* * 構(gòu)建循環(huán)鏈表，依次存儲(chǔ)1-n, l指向1 * pre:previous node * cur:current node */ list *create_list_with_diff_m(list *l, int n) list *pre; int i=1; for(; i number = i; printf

12、(請(qǐng)輸入第%d人的m: , i); scanf(%d, &(cur-m); cur-next = null; if(i = 1) /只在第一次進(jìn)入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動(dòng)pre pre-next = cur; pre = cur; pre-next = l;return l;/ 返回循環(huán)鏈表l的長度int length_list(list *l) int i = 1; list *p = l-next; while(p != l) i+; p = p-next; return i;/* * 刪除l開始后第m個(gè)

13、節(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)的前一個(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 next; j+; del = pri-next; pri-next = del-next; *l = pri-next; return del;void joseph_with_diff_m(list *l, int n) int