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

北京電子科技學(xué)院（BESTI）實驗報告課程：數(shù)據(jù)結(jié)構(gòu)班級：學(xué)號：2009姓名：實驗日期：2011.4.20指導(dǎo)老師：實驗序號：實驗一實驗題目：約瑟夫環(huán)約瑟夫（Joeph）問題的一種描述是：編號為1,2,…,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序。實驗成績：實驗評語：需求分析本程序是用VC編寫，由于約瑟夫問題是n個人圍坐在一圈，所以采用循環(huán)鏈表實現(xiàn)，又由于報數(shù)時可能循環(huán)到開始，所以采用不帶頭結(jié)點的循環(huán)鏈表結(jié)構(gòu)。題目要求的約瑟夫環(huán)操作：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)計一個程序來求出出列順序。實驗要求：【測試數(shù)據(jù)】

m的初值為20；密碼：3，1，7，2，4，8，4（正確的結(jié)果應(yīng)為6，1，4，7，2，3，5）。

實驗過程：1.基本算法以及分析：本程序主要是以建立單循環(huán)鏈表的形式，建立起一個約瑟夫環(huán)，然后根據(jù)之前創(chuàng)立的結(jié)點，輸入結(jié)點里的一些數(shù)據(jù)，如下typedefstructNode{ intIndex;在當(dāng)前環(huán)中所處的位置，即編號 intPassword;在當(dāng)前環(huán)中的所帶的密碼 structNode*next;}JosephuNode;程序有主函數(shù)開始，首先，提示輸入創(chuàng)建約瑟夫環(huán)環(huán)數(shù)以及每個環(huán)上所帶的密碼。然后，開始調(diào)用JosephuNode*Creat_Node函數(shù)，利用單循環(huán)鏈表建立起約瑟夫環(huán)，tail->next=head;就是將最后一個結(jié)點的后繼指向頭結(jié)點，函數(shù)結(jié)尾returnhead;將約瑟夫環(huán)的頭指針返回，并將它賦值head，然后主函數(shù)繼續(xù)調(diào)用Josephu函數(shù)，通過講head和Password引入函數(shù)，以建立兩個嵌套循環(huán)輸出并實現(xiàn)如下功能：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。2.程序源代碼：約瑟夫環(huán)#include<stdio.h>#include<malloc.h>typedefstructNode{ intIndex; intPassword; structNode*next;}JosephuNode;///////////////////////////////////////////////使用單循環(huán)鏈表創(chuàng)建約瑟夫環(huán)JosephuNode*Creat_Node(intnumbers){ inti,pass; JosephuNode*head,*tail; head=tail=(JosephuNode*)malloc(sizeof(JosephuNode));//申請頭結(jié)點 for(i=1;i<numbers;++i) { tail->Index=i; printf("\t\t請輸入第%d號所帶密碼:",i);//輸入當(dāng)前結(jié)點所帶密碼 scanf("%d",&pass); tail->Password=pass; tail->next=(JosephuNode*)malloc(sizeof(JosephuNode));//申請一個新結(jié)點 tail=tail->next;//指針指向下一個結(jié)點 } tail->Index=i; printf("\t\t請輸入第%d號所帶密碼:",i); scanf("%d",&pass); tail->Password=pass; tail->next=head;//將尾結(jié)點指針指向表頭 returnhead;}//Creat_Node/////////////////////////////////////////////////約瑟夫環(huán)voidJosephu(JosephuNode*head,intPassword){ inti,j; JosephuNode*tail; for(i=1;tail!=head;++i) { for(j=1;j<Password;++j) { tail=head; head=head->next; } tail->next=head->next; printf("\n\t\t第%d個出局的人的編號是：%d\t密碼是：%d",i,head->Index,head->Password); Password=head->Password; free(head); head=tail->next; } i=head->Password; j=head->Index; printf("\n\t\t第7個出局的人的編號是：%d\t密碼是：%d\n",j,i); free(head);}//Josephu/////////////////////////////////////voidmain(){ intnumbers,Password; charstop; JosephuNode*head; printf("\t\t-----------------約瑟夫環(huán)問題-----------------\n"); printf("\t\t測試要求：輸入約瑟夫問題的人數(shù)和起始密碼：7,20\n"); printf("\t\t---------------------------------------------------\n"); do { printf("\t\t開始......\n\t\t輸入約瑟夫環(huán)問題的人數(shù)和起始密碼："); scanf("%d,%d",&numbers,&Password); head=Creat_Node(numbers); printf("\t\t---------------\n"); printf("\t\t輸出結(jié)果如下\n"); Josephu(head,Password); printf("\t\t-----------------------------------------------\n"); printf("\t\t是否繼續(xù)進(jìn)行？是Y(y),否N(n)\t"); getchar(); scanf("%c",&stop); getchar(); printf("\t\t-----------------------------------------------\n"); }while(stop=='y'||stop=='Y');}3.運行結(jié)果程序開始的歡迎界面：輸入約瑟夫環(huán)的人數(shù)7初始密碼20輸入密碼：31724784運行：輸入y程序繼續(xù)運行，n則退出4.心得體會經(jīng)過這次實驗，從開始選題到自己上手還是編寫程序的過程中，我學(xué)會了很多的東西，以前對C語言的知識和算法總是模棱兩可的，經(jīng)過這次練習(xí)，在某些方面上還是