实验报告1-约瑟夫环

PAGEPAGE1华北水利水电学院约瑟夫环实验报告2010～2011学年第一学期09级计算机科学与技术专业班级：2009119学号：200911902姓名：万婷婷实验目的要求设计一个程序模拟约瑟夫环问题过程，求出出列编号序列。二、实验要求1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。2）建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。3）建立一个输出函数，将正确的输出序列测试数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4三、实验内容基本算法以及分析：本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下typedefstructNode{ intIndex;在当前环中所处的位置，即编号 intPassword;在当前环中的所带的密码 structNode*next;}JosephuNode;程序有主函数开始，首先，提示输入创建约瑟夫环环数以及每个环上所带的密码。然后,利用单循环链表建立起约瑟夫环，p->next=head->next;就是将最后一个结点的后继指向头结点的下一个结点，然后主函数调用Josephu函数，并实现如下功能：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。四、程序源代码1．约瑟夫环问题#include<iostream.h>#include<malloc.h>#include<stdio.h>typedefstructLNode{ intM;//当前出局人的编号 intPassword;//当前出局人所带密码 structLNode*next;}JosephuNode;voidJosephu(intn,intm){ inti,j,password; JosephuNode*head,*p,*q,*L; head=p=(JosephuNode*)malloc(sizeof(JosephuNode)); for(i=1;i<=n;i++) {q=(JosephuNode*)malloc(sizeof(JosephuNode));p->next=q; q->M=i; printf("请输入第%d号所带密码:", i); scanf("%d",&password); q->Password=password; p=q; } p->next=head->next; free(head); L=q->next; printf("出列者的编号顺序是：");while(p!=L) { for(j=1;j<m;j++) { p=L; L=L->next; } p->next=L->next; printf("%d,",L->M); m=L->Password; free(L); L=p->next; } printf("%d\n",p->M); free(L); }voidmain(){ intn,m; printf("约瑟夫环问题\n"); printf("输入的n和m值不小于1：\n"); printf("请输入参加的人数n:"); scanf("%d",&n); printf("请输入起始报数上限值m:"); scanf("%d",&m); Josephu(n,m);}五、运行结果六、小结（不少于100字）通过这次实验，使我更加知道自己的不足和需要加强的地方，指针仍然是自己需要去加强巩固的地方。每次看到自己写的程序和网上的比较发现自己需要