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

《数据结构》课程实验 实 验 报 告 题目： Joseph问题求解算法的设计与实现 专业： 计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 流程图 四、源程序代码 //Joseph问题求解算法的设计与实现 #includestdio.h #includestdlib.h 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)); //为头结点分配空间. p=head; printf(输入人的总个数:); scanf(%d,n); for(i=1;i=n;i++) { key=rand() % 100; printf(第%d个人的密码:%d\n,i,key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s-next=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(\n\n输入第一个报的数:\n); scanf(%d,key); printf(\n出列顺序为:\n); do { j=1; p=head; while(jkey) { s=p; p=p-next; 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:第2号成员出列 3:第3号成员出列 4:第5号成员出列 5:第4号成员出列 Press any key to continue 输入总人数n 创建并初始化 n个结点 输入第一个报的数key n==0 报数过程 输出出列者的编号及密码 结束