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

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

2、m 后，設(shè)計算法求 n 個人出圈的次序。二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計每個人按報數(shù)順序有唯一的前驅(qū)與后繼關(guān)系，并且報數(shù)順序循環(huán)，所以采用單向循環(huán)鏈表模擬，鏈表節(jié)點存儲序號number和m，存儲結(jié)構(gòu)定義如下：typedef struct list int number; /序號 int m; /密碼m struct list *next; /指向下一個人的指針list;為了方便查詢及刪除的定位，表按序號有序存儲。三、 算法設(shè)計1.初始化，構(gòu)建循環(huán)鏈表，依次存儲序號1至n的人,鏈表指針 l指向序號為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) /只在第一次進入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動pre pre-next = cur; pre = cur; pre-next = l;return l;2.為了獲取被刪除節(jié)點的前一個節(jié)點, m=1時重新賦值m為1+循環(huán)鏈表的長度，所以需要一個函數(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.模擬報數(shù)過程， l永遠指向下一個第一個報數(shù)的人，刪除l開始后第m個節(jié)點，用結(jié)點指針del返回刪除結(jié)點。list *delete_node(list *l, int m, list *del) if(m = 1) /為了獲取被刪除節(jié)點的前一個節(jié)點, m=1時重新賦值為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ù)刪除一人，進行n次。void joseph_with_one_m(list *l, int n, int m) int i = 1; while(i number); free(del); i+; 5.如果密碼m不同，則刪除節(jié)點后，以刪除節(jié)點的密碼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(請輸入人數(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è)計程序需要獲取人數(shù)n，密碼m（相同的密碼m和不同的密碼m），輸出出圈順序。所以以提示的形式獲取n和m。五、

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

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) /只在第一次進入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動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個節(jié)點，用del返回 * l永遠指向第一個報數(shù)的人 * pri: prior node * del: delete node*/ list *delete_node(list *l, int m, list *del) if(m = 1) /為了獲取被刪除節(jié)點的前一個節(jié)點, m=1時重新賦值為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(請輸入人數(shù)n: ); scanf(%d, &n); printf(請輸入所有人的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)鏈表，依次存儲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、(請輸入第%d人的m: , i); scanf(%d, &(cur-m); cur-next = null; if(i = 1) /只在第一次進入, init l, pre l = cur; pre = cur; else /鏈接pre與cur,并向后移動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個

13、節(jié)點，用del返回 * l永遠指向第一個報數(shù)的人 * pri: prior node * del: delete node*/ list *delete_node(list *l, int m, list *del) if(m = 1) /為了獲取被刪除節(jié)點的前一個節(jié)點, m=1時重新賦值為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