数据结构实习报告
题目:约瑟夫环
班级:xx 姓名:xx 学号:xx
一.需求分析
1. 以单项循环链表存储结构模拟约瑟夫环问题。即编号为 1、2、3…、n 的 n 个人按顺时
针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m,
从第一个人开始按顺时针方向自 1 开始报数,报到 m 时停止报数。报 m 的人出列,将他的
密码作为新的 m 值,从他在顺时针方向下一个人开始重新从 1 报数,如此下去,直至所有
的人全部出列为止。按出列顺序印出各人编号。
2. 演示程序以用户与计算机的对话方式执行,用户输入相应的数据,输出结果显示在其后。
3. 测试数据:m 初始值 20,n=7,7 个人密码依次为:3,1,7,2,4,6,4。正确出列
顺序为 6,1,4,7,2,3,5。
二.概要设计
1.为实现程序功能,应以循环链表表示约瑟夫环。先定义结构体表示约瑟夫环中的元素。
2.建立链表的算法:
三.详细设计
程序代码:
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int num;
int psw;
struct Node *next;
}*Joseph;
int n;
int m;
void Delete(Joseph *h,int m)
{
Joseph p,q;
int i;
p=(*h);
q=(*h);
while(p->next!=p)
{
for(i=1;i<=m-1;i++)
{
q=p;