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

2、結構設計并且報數順序循環，所以采用單向循環鏈每個人按報數順序有唯一的前驅與后繼關系,number和m ,存儲結構定義如下:序號密碼m/指向下一個人的指針表模擬，鏈表節點存儲序號 typedef struct Listint number;int m;struct List *next;List;為了方便查詢及刪除的定位，表按序號有序存儲。算法設計1.初始化，構建循環鏈表，依次存儲序號1至n的人，鏈表指針L指向序號為1的人。List *create_list_with_one_m(List *L, int n)List *pre; / previous nodeint i=1;for(; i n

3、umber = i;cur-next = NULL;if(i = 1)/ 只在第一次進入，init L, preL = cur;pre = cur;else/鏈接pre與cur,并向后移動 prepre-next = cur; pre = cur;pre-next = L;return L;2 .為了獲取被刪除節點的前一個節點，m=1時重新賦值 m為1+循環鏈表的長度，所以需要個函數獲取循環鏈表的長度。/返回循環鏈表L的長度int length_list(List *L兒int i = 1;List *p = L-next;while(p != L) i+；p = p-next; return

4、 i;3 .模擬報數過程，L永遠指向下一個第一個報數的人，刪除L開始后第m個節點，用結點指針del返回刪除結點。List *delete_node(List *L, int m, List *del)if(m = 1) 為了獲取被刪除節點的前一個節點，m=1時重新賦值為1+lengthint l = length_list(*L);m = 1+l;List *pri = *L; / prior nodeint j = 0;while(j next;j+; del = pri-next; /delete node pri-next = del-next;*L = pri-next;return

5、del; 4 .輸入構建好的鏈表L,人數n,密碼m,每次調用delete_node函數刪除一人，進行 n次。void joseph_with_one_m(List *L, int n, int m)int i = 1;while(i number);free(del);i+;5 .如果密碼m不同，則刪除節點后，以刪除節點的密碼 m作為新的m。void joseph_with_diff_m(List *L, int n)int i = 1;int m = L-m;while(i number);m = del-m;free(del); i+；6 .在主函數中獲取人數和密碼m,構建鏈表，調用jos

6、eph函數。int main()int n, m;printf(請輸入人數 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;四、界面設計程序需要獲取人數 n,密碼m (相同的密碼 m和不同的密碼 m),輸出出圈順序。所以以提 示的形式獲取n和m。五、運行測試與分析(1)運行程序，顯示輸入提示，如圖所示。醐命令提示符-joseph.exe XE：NCabstractarexlinear_li

7、stjoseph_with_diFf_njoseph.exe 請輸入人數n：(2)根據提示，輸入人數，并輸入密碼，即可輸出結果。_listjaseph_with_one_R7joseph.exe224683751 :口香看雷雷香7E 8皿號號號號號 口 JTTSrT-rTrl Jtt Jrrt人一5人圈圈圈圈圈圈 M出出出出出出出翦-NR主 QE till12345678片存第第第第Cdaita_s tract Lire 1 in e ar_1 is t Xj o s e pli_w it h_o nie jn (3)需要不同密碼的程序可根據提示輸入不同密碼，即可輸出結果。命令亙示符r 1 2

8、 4 6 fl 7 3 5tu12 3 2 3 2 3ucfDr):r):r):r):r):m:m:r):號號號號 號號 tr.一的的的的的的7s工人人人人人人人的的的的 事費1 2 3 4 S 圈圈圈圈圈圈圈圈 S入人人人人入at，至DE主里DE生:Cd六、實驗收獲與思考1 .掌握了循環鏈表的初始化，刪除，求長等常用方法的使用，鞏固了相關數據結構。2 .在實驗中熟悉了 C語言對數據結構的描述，發現了過去的薄弱之處，重新進行學習。3 .體會到了正確的數據結構對程序的重要性。七、附錄1 .相同密碼#include #include typedef struct Listint number;in

9、t m;struct List *next;List;/* 構建循環鏈表，依次存儲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, preL = cur;pre = cur;else鏈接pre與cur,并向后移動prepre-next = cur; pre = cur;pre-next = L;retur

10、n L;/返回循環鏈表L的長度int length_list(List *L)int i = 1;List *p = L-next;while(p != L)i+;p = p-next;return i;/* 刪除L開始后第m個節點，用del返回* L永遠指向第一個報數的人* pri: prior node* del: delete node*/List *delete_node(List *L, int m, List *del)if(m = 1) /為了獲取被刪除節點的前一個節點，m=1時重新賦值為1+lengthint l = length_list(*L);m = 1+l;List *

11、pri = *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(請輸入人數n:);scanf(%d, &n);printf(請輸入所有人的 m:);scanf(%d, &m);List *L;L = create_list_with_one_m(L, n

12、);joseph_with_one_m(L, n, m);return 0;2.不同密碼#include #include typedef struct Listint number;int m;struct List *next;List;/* 構建循環鏈表，依次存儲 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(請輸入第d人的m: , i);scanf(%d, &(

13、cur-m);cur-next = NULL;if(i = 1)/ 只在第一次進入，init L, preL = cur;pre = cur;else鏈接pre與cur,并向后移動prepre-next = cur; pre = cur;pre-next = L;return L;/返回循環鏈表L的長度int length_list(List *L)int i = 1;List *p = L-next;while(p != L)i+；p = p-next;return i;/* 刪除L開始后第m個節點，用del返回* L永遠指向第一個報數的人* pri: prior node* del: delete node*/List *delete_node(List *L, int m, List *del)1+lengthif(m = 1) /為了獲取被刪除節點的前一個節點，m=1時重新賦值為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_di