约瑟夫环课程设计实验报告【约瑟夫环数据结构实验报告】

1、约瑟夫环课程设计实验报告【约瑟夫环数据结构实验报告】数据结构实验报告实习1 线性表及其应用题目：编制一个演示约瑟夫环的程序班级：1403011班 姓名：付尧 学号：1* 完成日期：x.10.25一需求分析1本程序中，人数n为任意整数，首先输入一个报数上限值整数m，程序应能自动将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。3程序执行的命令包括：（1）构造线性表；（2）输入数据；（3）执行报数，删除出列人的信息以

2、及把出列人的密码赋给m；（4）结束。4测试数据（1）m初值为20，n7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则正确的出列顺序为6，1，4，7，2，3，5。二概要设计为了实现程序上述功能，应以单向循环链表为存储结构。1. 基本操作：void createlist操作结果：构造单向循环链表，初始化每个人的密码并分配序号。void josephus初始条件：链表存在。操作结果：删除出列人的节点并重新报数。2 本程序包含三个模块：（1）主程序模块；（2）构造链表并输入信息模块；（3）执行约瑟夫环函数模块；三详细设计1.元素类型，结点类型和指针类型：struct nodeint

3、 num;int code;struct node *next;typedef struct node node;node *head,*tail;int m,n;2每个模块的分析：（1）主程序模块：int maincreatelist;josephus(head,m);return 0;（2）构造链表模块：void createlist申请头结点空间生成头结点printf(请输入m和nn);读取m，nprintf(请输入每个人的密码n);创建节点并写入密码分配相应序号。形成循环链表（3）约瑟夫环函数模块：void josephus(node *p,int m)node *q;int coun

4、t=0; 报数计数器q=tail; q为尾结点p=p-next; p为第一个数据while (p-next!=p)count+; 当循环链表所剩元素大于1时if (count=m)输出当前出列者的序号更新m为出列者的密码删除p节点令p指向下一个数据结点count=0;else 维护p和q到下一个结点打印最后剩下的人的序号四调试分析（1）设计过程中对函数结束的条件感到疑惑，经过考虑，采取 p=p-next来判断，非常简捷方便。（2）算法的时间复杂度为n2，空间复杂度为n，时间复杂度偏高，如果遇到数据过多可能会变得很慢。可以将m转化为m除以当前人数的余数，可以减少时间复杂度。（3）这道题第一眼看觉

5、得十分复杂，但编写中就会发现并不难。调试过程中我对链表的建立和插入删除操作更加熟练，也加深了对算法的认识。五用户使用说明（1）本程序的运行环境为vsx。（2）进入演示程序后即显示提示信息：请输入m和n：输入m和n请输入每个人的密码：输入密码输入完毕后就进行报数操作：六测试结果当输入m20，n7，每个人所持密码一次为：3，1，7，2，4，8，4时，则输出正确的出列顺序为：6，1，4，7，2，3，5。七附录#include#includestruct node建立链表数据类型int num;int code;struct node *next;typedef struct node node; 定

6、义node为链表数据类型node *head,*tail; 声明头指针，尾指针int m,n;void createlist建立链表函数node *p,*q;int i;p=new node; 申请头结点空间p-next=null;head=p; 生成头结点printf(请输入m和nn);scanf(%d %d,m,n);读取m，nprintf(请输入每个人的密码n);for (i=1;iq=new node; 申请结点空间q-num=i; 为节点排序scanf(%d,q-code); 记录该节点密码p-next=q; 插入节点pp=q;tail=p; 保存尾指针tail-next=head-next; 形成循环链表void josephus(node *p,int m)约瑟夫函数node *q;int count=0; 报数计数器q=tail; q为尾结点p=p-next; p为第一个数据while (p-next!=p)count+; 当循环链表所剩元素大于1时if (count=m)printf(%d ,p-num); 输出当前出列者的序号m=p-code; 更新m为出列者的密码q-next=p-next; 删除p节点delete(p);p=q-next; 令p指向下