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

1、數(shù)據(jù)結(jié)構(gòu)期末試驗(yàn)報(bào)告學(xué)院： 專業(yè)： 學(xué)號(hào)：班級(jí)：姓名： 2010.12.12Joseph約瑟夫環(huán)上機(jī)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：joseph約瑟夫環(huán)題目要求的約瑟夫環(huán)操作：編號(hào)是1，2，,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。實(shí)驗(yàn)要求：1）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。2）建立輸入處理輸入數(shù)據(jù)，輸入m的

2、初值，n ，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。3）建立一個(gè)輸出函數(shù)，將正確的輸出序列4）測試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？實(shí)驗(yàn)過程：1.基本算法以及分析：本程序主要是以建立單循環(huán)鏈表的形式，建立起一個(gè)約瑟夫環(huán)，然后根據(jù)之前創(chuàng)立的結(jié)點(diǎn)，輸入結(jié)點(diǎn)里的一些數(shù)據(jù)，如下typedef struct Node int Index; 在當(dāng)前環(huán)中所處的位置，即編號(hào)int Password; 在當(dāng)前環(huán)中的所帶的密碼struct Node *next; JosephuNode; 程序有主函數(shù)開始，首先，提示輸入創(chuàng)建約瑟夫環(huán)環(huán)數(shù)以及每個(gè)

3、環(huán)上所帶的密碼。然后，開始調(diào)用JosephuNode *Creat_Node函數(shù)，利用單循環(huán)鏈表建立起約瑟夫環(huán)，tail-next = head;就是將最后一個(gè)結(jié)點(diǎn)的后繼指向頭結(jié)點(diǎn)，函數(shù)結(jié)尾 return head; 將約瑟夫環(huán)的頭指針返回，并將它賦值head，然后主函數(shù)繼續(xù)調(diào)用Josephu函數(shù)，通過講head和Password引入函數(shù)，以建立兩個(gè)嵌套循環(huán)輸出并實(shí)現(xiàn)如下功能：編號(hào)是1，2，,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他

4、在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。2.程序源代碼： 約瑟夫環(huán)#include #include typedef struct Node int Index;int Password; struct Node *next; JosephuNode; / 使用單循環(huán)鏈表創(chuàng)建約瑟夫環(huán)JosephuNode *Creat_Node(int numbers) int i,pass; JosephuNode *head, *tail; head = tail = (JosephuNode *)malloc(sizeof(JosephuNode); /申請(qǐng)頭結(jié)點(diǎn)for

5、 (i = 1; i Index = i;printf(tt請(qǐng)輸入第%d號(hào)所帶密碼: ,i); /輸入當(dāng)前結(jié)點(diǎn)所帶密碼scanf(%d,&pass);tail-Password=pass;tail-next = (JosephuNode *)malloc(sizeof(JosephuNode); /申請(qǐng)一個(gè)新結(jié)點(diǎn)tail = tail-next; /指針指向下一個(gè)結(jié)點(diǎn) tail-Index = i;printf(tt請(qǐng)輸入第%d號(hào)所帶密碼: ,i);scanf(%d,&pass);tail-Password=pass;tail-next = head; /將尾結(jié)點(diǎn)指針指向表頭return he

6、ad;/Creat_Node/ 約瑟夫環(huán)void Josephu(JosephuNode *head,int Password) int i,j;JosephuNode *tail; for (i = 1; tail != head; +i) for (j = 1; j next; tail-next = head-next; printf(ntt第%d個(gè)出局的人的編號(hào)是：%dt密碼是：%d,i,head-Index,head-Password);Password=head-Password;free(head); head = tail-next; i =head-Password; j=h

7、ead-Index;printf(ntt第7個(gè)出局的人的編號(hào)是：%dt密碼是：%dn,j,i);free(head); /Josephu/void main() int numbers, Password;char stop;JosephuNode *head;printf(tt- 約瑟夫環(huán)問題 -n);printf(tt例如：輸入約瑟夫問題的人數(shù)和起始密碼：7,20n);printf(tt-n);doprintf(tt開始.ntt輸入約瑟夫環(huán)問題的人數(shù)和起始密碼：);scanf(%d,%d, &numbers, &Password);head=Creat_Node(numbers);prin

8、tf(tt-n);printf(tt輸出結(jié)果如下n);Josephu(head,Password);printf(tt-n);printf(tt是否繼續(xù)進(jìn)行？是Y(y),否N(n)t);getchar();scanf(%c,&stop);getchar();printf(tt-n);while(stop=y|stop=Y); 3.運(yùn)行結(jié)果程序開始的歡迎界面：輸入約瑟夫環(huán)的人數(shù)7 初始密碼20輸入密碼：3 1 7 2 4 7 4輸入y程序繼續(xù)運(yùn)行，n 則退出4.心得體會(huì)此程序目前的缺點(diǎn)在于，結(jié)點(diǎn)密碼數(shù)據(jù)類型定義的存儲(chǔ)類型是int型，不能超過-21474836482147483648，一旦超過則程序輸出結(jié)果有誤，另一個(gè)缺點(diǎn)就是程序運(yùn)行當(dāng)中，一旦中途輸入出現(xiàn)錯(cuò)誤，則無法返回，必須將當(dāng)前操作結(jié)束等到下個(gè)主函數(shù)的循環(huán)開始，或者直接退出重新運(yùn)行此程序。優(yōu)點(diǎn)則在于程序運(yùn)行速度較快，不會(huì)出現(xiàn)輸出結(jié)果有誤的問題經(jīng)過這次集中上機(jī)的實(shí)驗(yàn)，從開始選題到自己上手還是編寫程序的過程中