C语言实现约瑟夫环

1、约瑟夫环实验报告专业：网络工程班级学号姓名一、问题描述：约瑟夫问题的一种描述是：编号为1, 2,n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。一开始选一个正整数作为报数上限值m从第一个人开始从顺时针方向自1开始报数，报到m时停止。报到m的人出列，将他 的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从 1报数，如此 下去，直达所有人出列。基本要求： 利用单向循环链表存储结构模拟此过程， 按照出列的顺序输出各人的 编号。测试数据：m的初始值为20； n=7，7个人的密码依次是3，1, 7, 2, 4, 8, 4, 首先m的值为6 （正确的出列顺序为6, 1, 4, 7, 2, 3

2、, 5）二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表,格式为： struct Lnodeint number;int password; struct Lnode *next;Lnode,*p,*q,*head;其中 number 是人的排列序号, password 是各人所持有的密码值, next 是节点指针。 Lnode 是节点变量, p、q 是节点, head 是头指针。程序的代码：定义变量 n, i,m,j输入人的数量 nIf n<=0 或 n>30 重新输入 n 值当 0<i<n 时 建立单链表并且输入各人的密码值 p->passwor

3、d 尾指针指向头指针,形成循环链表 输入初始报数上限值 m当 1<=j<=n 时循环找出报 m 的节点 p输出报 m 节点的编号 p->number将 p->password 赋给 m 值 删除此节点结束/* 定义链表 */三、源程序及注释： #include<stdio.h> #include<stdlib.h> struct Lnode int number;int password; struct Lnode *next; Lnode,*p,*q,*head;int main(void)int n;/*n 个人 */int i;int m;

4、/* 初始报数上限值 */int j;printf("please enter the number of people n:");/* 输入测试人的数量 */scanf("%d",&n);loop:if(n<=0|n>30)/* 检验 n 是否满足要求，如不满足重新输入n 值 */printf("nn is erorr!nn");printf("please enter the number of people again n:");scanf("%d",&n);g

5、oto loop;for(i=1;i<=n;i+) /* 建立单链表 */if(i=1)head=p=(struct Lnode*)malloc(sizeof(struct Lnode);elseq=(struct Lnode*)malloc(sizeof(struct Lnode); p->next=q;p=q;printf("please enter the %d people's password:",i); /* 输入每个人所持有的密码值 */scanf("%d",&(p->password); p->nu

6、mber=i; p->next=head; p=head; printf("please enter the number m:"); scanf("%d",&m); printf("The password is:n"); for (j=1;j<=n;j+) for(i=1;i<m;i+,p=p->next);m=p->password;printf("%d ",p->number); p->number=p->next->number; p->

7、password=p->next->password; q=p->next;p->next=p->next->next;free(q);/* 形成循环链表 */* 输出各人的编号 */*删除报 m 的节点 */prin tf("nn");system("pause");/*等待按任意键退出*/四、运行输出结果：测试的数据：n为7, m的初值为20,密码：3、1、7、2、4、8、4,正确的 结果应为：6、1、4、7、2、3、5。A 1 2 3 4 5 6 ? 口第编： 入入1A1 AlAlAlAlA入>: 请请请请请请请壬23 S请按任盍犍继续7个人的密码：3 人人的童码" 人人的密码许 个人的密码唸 个人的密码泊 个人的密码汁 个人的密码 m：6五、调试分析本次实习作业难度较低，没有太大的困难。主要是练习使用单项循环链