約瑟夫環(huán)-數(shù)據(jù)結構

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

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

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

4、在順時針方向的下一個人開始重新從1報數(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); /申請頭結點for

5、 (i = 1; i Index = i;printf(tt請輸入第%d號所帶密碼: ,i); /輸入當前結點所帶密碼scanf(%d,&pass);tail-Password=pass;tail-next = (JosephuNode *)malloc(sizeof(JosephuNode); /申請一個新結點tail = tail-next; /指針指向下一個結點 tail-Index = i;printf(tt請輸入第%d號所帶密碼: ,i);scanf(%d,&pass);tail-Password=pass;tail-next = head; /將尾結點指針指向表頭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個出局的人的編號是：%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個出局的人的編號是：%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輸出結果如下n);Josephu(head,Password);printf(tt-n);printf(tt是否繼續(xù)進行？是Y(y),否N(n)t);getchar();scanf(%c,&stop);getchar();printf(tt-n);while(stop=y|stop=Y); 3.運行結果程序開始的歡迎界面：輸入約瑟夫環(huán)的人數(shù)7 初始密碼20輸入密碼：3 1 7 2 4 7 4輸入y程序繼續(xù)運行，n 則退出4.心得體會此程序目前的缺點在于，結點密碼數(shù)據(jù)類型定義的存儲類型是int型，不能超過-21474836482147483648，一旦超過則程序輸出結果有誤，另一個缺點就是程序運行當中，一旦中途輸入出現(xiàn)錯誤，則無法返回，必須將當前操作結束等到下個主函數(shù)的循環(huán)開始，或者直接退出重新運行此程序。優(yōu)點則在于程序運行速度較快，不會出現(xiàn)輸出結果有誤的問題經(jīng)過這次集中上機的實驗，從開始選題到自己上手還是編寫程序的過程中