《约瑟夫环问题实验报告完整版.pdf》由会员分享，可在线阅读，更多相关《约瑟夫环问题实验报告完整版.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 班级 000 学号 000 姓名 神刀公子 时间 1.问题描述 约瑟夫环问题（1）问题描述 设有编号为 1,2,n 的 n（n0）个人围成一个圈，每个人持有一个密码 m。从第一个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，如此下去，直到所有人全部出圈为止。当任意给定 n 和 m 后，设计算法求 n 个人出圈的次序。（2）基本要求 建立模型，确定存储结构。对任意 n 个人，密码为 m，实现约瑟夫环问题。出圈的顺序可以依次输出，也可以用一个数组存储。（3）思
2、考：采用顺序存储结构如何实现约瑟夫环问题？如果每个人持有的密码不同，应如何实现约瑟夫环问题？2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node int data;/数据域 Node*next;/next 指针指向下一个结点;3.算法设计 问题要求建立模型，确定存储结构，之后对任意 n 个人，密码为 m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。2 设计流程图如图 1.1 所示。图 1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方
3、便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list 函数将后续结点一次插入链接，构造为循环链表。NODE*link(int number)NODE*head=NULL,*p=NULL,*q=NULL;int i=1;head=(struct node*)malloc(sizeof(struct node);head-value=i;p=head;for(i=2;inext=q;p=q;p-value=i;p-next=head;return head;（2）约瑟夫环报数的算法在运行为循环方式，报数者除非本身已经出去，否则继续顺序报数，其报数循环的
4、代码为 void Joseph(NODE*p,int number,int n)int i,j;NODE*q=NULL;for(i=1;i=number;i+)for(j=1;jnext;q=p-next;p-next=q-next;p=p-next;printf(第%3d 个出圈的人是：%3dn,i,q-value);free(q);scanf(n);p-next=NULL;（3）主程序执行 主程序运行，调用函数，程序接受数据后，输出出圈列数。printf(请输入总人数 n 和密码 m:n);scanf(%d,&number);scanf(%d,&n);NODE*head=NULL;head
5、=link(number);Joseph(head,number,n);system(PAUSE);return 0;4 4界面设计 程序无需复杂的界面设计，包含输入提示功能和输出提示功能。5.运行测试与分析（1）输出提示，如图 1.2 所示。（2）根据提示，输入圈内人数n 和每个人持有的密码 m 如图 1.3 所示。（3）输出结果如图 1.4 所示 分析 6.实验收获及思考 5 通过该实验，我进一步增强了对于链表的理解，也对链表的操作和实现更为熟悉，熟练掌握了如何实现置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立不带头结点的单链表（头插入法建表）、建立带头结点的单链表（尾插入法建表），输出带头结点的单链表等操作。同时，锻炼了实际操作时的动手能力。教师评分：教师签字：