约瑟夫环-数据结构-2

北京电子科技学院（BESTI）实验报告课程：数据结构班级：学号：2009姓名：实验日期：2011.4.20指导老师：实验序号：实验一实验题目：约瑟夫环约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。实验成绩：实验评语：需求分析本程序是用VC编写，由于约瑟夫问题是n个人围坐在一圈，所以采用循环链表实现，又由于报数时可能循环到开始，所以采用不带头结点的循环链表结构。题目要求的约瑟夫环操作：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。实验要求：【测试数据】

m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

实验过程：1.基本算法以及分析：本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下typedefstructNode{ intIndex;在当前环中所处的位置，即编号 intPassword;在当前环中的所带的密码 structNode*next;}JosephuNode;程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后，开始调用JosephuNode*Creat_Node函数，利用单循环链表建立起约瑟夫环，tail->next=head;就是将最后一个结点的后继指向头结点，函数结尾returnhead;将约瑟夫环的头指针返回，并将它赋值head，然后主函数继续调用Josephu函数，通过讲head和Password引入函数，以建立两个嵌套循环输出并实现如下功能：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。2.程序源代码：约瑟夫环#include<stdio.h>#include<malloc.h>typedefstructNode{ intIndex; intPassword; structNode*next;}JosephuNode;///////////////////////////////////////////////使用单循环链表创建约瑟夫环JosephuNode*Creat_Node(intnumbers){ inti,pass; JosephuNode*head,*tail; head=tail=(JosephuNode*)malloc(sizeof(JosephuNode));//申请头结点 for(i=1;i<numbers;++i) { tail->Index=i; printf("\t\t请输入第%d号所带密码:",i);//输入当前结点所带密码 scanf("%d",&pass); tail->Password=pass; tail->next=(JosephuNode*)malloc(sizeof(JosephuNode));//申请一个新结点 tail=tail->next;//指针指向下一个结点 } tail->Index=i; printf("\t\t请输入第%d号所带密码:",i); scanf("%d",&pass); tail->Password=pass; tail->next=head;//将尾结点指针指向表头 returnhead;}//Creat_Node/////////////////////////////////////////////////约瑟夫环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-----------------约瑟夫环问题-----------------\n"); printf("\t\t测试要求：输入约瑟夫问题的人数和起始密码：7,20\n"); printf("\t\t---------------------------------------------------\n"); do { printf("\t\t开始......\n\t\t输入约瑟夫环问题的人数和起始密码："); scanf("%d,%d",&numbers,&Password); head=Creat_Node(numbers); printf("\t\t---------------\n"); printf("\t\t输出结果如下\n"); Josephu(head,Password); printf("\t\t-----------------------------------------------\n"); printf("\t\t是否继续进行？是Y(y),否N(n)\t"); getchar(); scanf("%c",&stop); getchar(); printf("\t\t-----------------------------------------------\n"); }while(stop=='y'||stop=='Y');}3.运行结果程序开始的欢迎界面：输入约瑟夫环的人数7初始密码20输入密码：31724784运行：输入y程序继续运行，n则退出4.心得体会经过这次实验，从开始选题到自己上手还是编写程序的过程中，我学会了很多的东西，以前对C语言的知识和算法总是模棱两可的，经过这次练习，在某些方面上还是