数据结构实验报告(约瑟夫环)

1、数据结构课程实验实 验 报 告题目：joseph 问题求解算法的设计与实现专业：计算机科学与技术班级：姓名：学号：完成日期：一、试验内容约瑟夫（joseph）问题的一种描述是：编号为1，2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值 m ， 从第一个人开始按顺时针方向自1 开始顺序报数， 报到 m时停止报数。报 m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去， 直至所有人全部出列为止。 试设计一个程序求出出列顺序。二、试验目的掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数

2、据结构。三、流程图创建并初始化n 个结点输入第一个报的数 key n=0 输入总人数n 报数过程输出出列者的编号及密码n- 结束四、源程序代码/joseph问题求解算法的设计与实现#include #include struct list int num,code; struct list *next; ; void main() printf(joseph问题求解算法的设计与实现n n); int i,j,m=1; int key; / 密码 . int n; /人数 . list *p,*s,*head; head=(list *)malloc(sizeof(list); /为头结点分配空

3、间. p=head; printf(输入人的总个数:); scanf(%d,&n); for(i=1;inext=p; p-num=i; p-code=key; p-next=head-next; p=head; head=head-next; free(p); /释放头结点 . p=head; do printf(n第%d号成员的密码为:%d,p-num,p-code); /输出链表 . p=p-next; while(p!=head); printf(nn输入第一个报的数:n); scanf(%d,&key); printf(n出列顺序为 :n); do j=1; p=he

4、ad; while(jnext; j+; /报数过程 . i=p-num; key=p-code; printf(%d:第%d号成员出列 n,m,i); m+; s-next=p-next; head=p-next; /重新定义head, 下次循环的开始结点. free(p);/ 释放已出列的结点. n-; /人数减一 . while(n0); 五、调试过程调试过程中 , 曾出现过缺少分号、括号之类的错误 , 还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教, 终于得出了正确结果 . 六、结果分析joseph 问题求解算法的设计与实现输入人的总个数 :5 第 1 个人的密码 :41 第 2 个人的密码 :67 第 3 个人的密码 :34 第 4 个人的密码 :0 第 5 个人的密码 :69 第 1 号成员的密码为 :41 第 2 号成员的密码为 :67 第 3 号成员的密码为 :34 第 4 号成员的密码为 :0 第 5 号成员的密码为 :69 输入第一个报的数 : 6 出列顺序为 : 1: 第 1 号成员出列2: