约瑟夫环问题 实验报告

1、实验报告实验名称：约瑟夫环问题 班级： 信管131 姓名： 学号： 同实验者： 实验时间： 11.7 成绩： 指导老师： 一、实验目的：（1）进一步掌握线性表的各种链式存储结构，包括单链表与循环链表，熟悉各种操作。（2）认真分析实际项目的内容，将其中的算法付诸实现，目的是练习利用线性表的链表结构来解决实际应用问题的能力，掌握线性表的实际应用。二、实验设备及主要内容一 一 实验题目：编号是1,2,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从

2、他在顺时针方向的下一个人开始重新从1报数，如果要求围坐一圈的人并不全出列，要余下k（自己确定）个人不出列又该怎样改进此算法。设计一个程序来求出出列顺序，并输出结果。需求分析：本演示程序在VC环境下编写二 需求分析输入的形式和输入值的范围：输入元素的个数；每个人的密码；在所有输入中，元素的值都是整数输出的形式：剩余人数的出列序号测试程序：输入总人数为5 剩余人数为3 从第一个人开始出列 每个人的密码分别为：2 3 4 5 6 则输出的为：2 5 三 概要设计从参考程序分析typedef struct int num; int cipher; struct node *next; linklist

3、;#includeh1.h /* 建立单循环链表函数 */ linklist *creat(int n) int k; linklist *head, *r, *p; p=(linklist *)malloc(sizeof(linklist); head=p; p-num=1;printfprintf(输入第一个人的密码:n); scanf(%d,&p-cipher); r=p; p-next=p; for(k=2;knum=k; printf(输入密码:n); scanf(%d,&p-cipher); r-next=p; r=p; p-next=head;return(head); /* 选

4、择出列编号 */linklist *select(linklist *head, int m) linklist *p,*q; int k;q=head;k=1;p=q-next; /q为p的前趋指针,p指向当前报数的人while(q!=p) k=k+1; /报一次数 if(k%m=0) printf(出列的序号为：%dn,p-num); m=p-cipher; q-next=p-next; /对应的结点从链表中删除 free(p); k=0; p=q-next; elseq=p; p=p-next; / p指向当前报数的人 head=p;return(head);void main()voi

5、d main() int n,m;linklist *head;printf(Input n:n);scanf(%d,&n);printf(Input the number to call:n);scanf(%d,&m);head=creat(n);head=select(head,m);printf(The last one is:%dn,head-num);若要控制剩余人数必须再定义一个变量N作为判断依据！本程序包含三个函数：主函数：main()建立单循环链表函数 linklist *creat(int n)选择出列函数：linklist *select(linklist *head, i

6、nt m,int N,int n)详细设计：#include#includetypedef struct node int num; int cipher; struct node *next; linklist; /* 建立单循环链表函数 */ linklist *creat(int n) int k; linklist *head, *r, *p; p=(linklist *)malloc(sizeof(linklist); head=p; p-num=1; printf(输入第1个人的密码:n); scanf(%d,&p-cipher); r=p; p-next=p; for(k=2;k

7、num=k; printf(输入第%d个人的密码:n,k); scanf(%d,&p-cipher);r-next=p;r-next=p; r=p; p-next=head;return(head); /* 选择出列编号 */linklist *select(linklist *head, int m,int N,int n) linklist *p,*q; int k,j=0;q=head;k=1;p=q-next; /q为p的前趋指针,p指向当前报数的人while(q!=p&jnum);j+; m=p-cipher; q-next=p-next; /对应的结点从链表中删除 free(p);

8、 k=0; p=q-next; elseq=p; p=p-next; / p指向当前报数的人 head=p;return(head); void main() int n,m,N;linklist *head;printf(请输入总人数:n);scanf(%d,&n);printf(请输入剩余的人数:n);scanf(%d,&N);printf(请输入从第一次从第几个人开始出列:n)；scanfscanf(%d,&m);head=creat(n);head=select(head,m,N,n);/printf(The last one is:%dn,head-num);调试分析：程序是否编写错误使用