數(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í)間一、 問(wèn)題描述設(shè)有編號(hào)為 1,2, ,n 的 n ( n> 0)個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼m。從第一個(gè)人開(kāi)始報(bào)數(shù)， 報(bào)到 m 時(shí)停止報(bào)數(shù)， 報(bào) m 的人出圈，再?gòu)乃南乱粋€(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 Listint number; 始化，構(gòu)建循環(huán)鏈表，依次存儲(chǔ)序號(hào)1 至 n 的人 , 鏈表指針 L 指向序號(hào)為 1 的人。List *create_list_with_one_m(List *L, int n)List *pre; 了獲取被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) , m=1時(shí)重新賦值 m為 1+循環(huán)鏈表的長(zhǎng)度， 所以需要一個(gè)函數(shù)獲取循環(huán)鏈表的長(zhǎng)度。擬報(bào)數(shù)過(guò)程， L

3、 永遠(yuǎn)指向下一個(gè)第一個(gè)報(bào)數(shù)的人，刪除L 開(kāi)始后第 m個(gè)節(jié)點(diǎn)，用結(jié)點(diǎn)指針del 返回刪除結(jié)點(diǎn)。List *delete_node(List *L, int m, List *del)if(m = 1) 入構(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)果密碼 m 不同，則刪除節(jié)點(diǎn)后，以刪除節(jié)點(diǎn)的密碼m 作為新的 m。void joseph_with_diff_m(List *L, int n)int

4、i = 1;int m = L->m;while(i <= n)主函數(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ì) 程序需

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

6、pedef struct Listint 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_one_m(List *L, int n)List *pre;int i=1;for(; i <= n; i+)List *cur = (List*)malloc(sizeof(List); cur->number = i;cur->next = NULL;if(i = 1) 同密碼#inc

7、lude <>#include <> typedef struct Listint 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 <= n; i+)List *cur = (List*)malloc(sizeof(List); cur->number = i;pri

8、ntf(" 請(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 的長(zhǎng)度 int length_list(List *L)int i = 1;List *p = L->

9、next; while(p != L) i+; p = p->next; return i;/* 刪除 L 開(kāi)始后第 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)1+lengthif(m = 1) /為了獲取被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) , m=1 時(shí)重新賦值為int l = length_list(*L);m = 1+l;List *pri = *L;int j = 0;while(j < m-2) /移動(dòng) m-2

10、 次 , 獲取 pripri = pri->next; j+;del = pri->next; pri->next = del->next;*L = pri->next; return del;void joseph_with_diff_m(List *L, int n)int i = 1;int m = L->m;while(i <= n) /每次 del 一個(gè) nodeList *del = delete_node(&L, m, del); printf("第 %d個(gè)出圈的序號(hào)是 %dn", i, del->number);m = del->m;free(del); i+; int main()