数据结构约瑟夫实验报告.doc

12级 计科软件班 _2013___年__11_月__8_日
姓名 袁振荣__ 学号__2012550301__ 电话_15575904712
1．设计题目
线性表
实验目的：本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。
实验内容：
1. [问题描述]
约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
2.[基本要求]
　利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3.[测试数据]
　　m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
4.[实现提示]
　　程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。
5.[选作内容]
向上述程序中添加在顺序结构上实现的部分。
实验设备及器材配置：微型计算机、Windows操作系统、vc++6.0
实验类型及基本要求：设计型实验，使用已学的数据结构，编程知识，实现线性表的基本操作，以及线性表的综合应用

2．需求分析
1． 本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
3． 程序执行的命令包括：
（1）构造链表；
（2）输入数据；
（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；
（4）结束。
4． 测试数据
（1）n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。

3．概要设计

　为了实现上述操作，应以单向循环链表为存储结构。
5． 基本操作：
操作结果：构造空链表，若成功就初始化每个人的相关信息
初始条件：线性链表存在
操作结果：释放指向出列的人的结点，并重新报数
2． 本程序包含三个模块：
（1） 主程序模块；
（2） 构造链表并输入每个人信息模块；
（3） 释放结点模块；

4．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
(1)元素类型，结点类型和指针类型：

typedef struct Lnode
{ int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;

(2)每个模块的分析：
1.主程序模块：
int main(void)

{
int n; /*n个人*/
int i;
int m; /*初始报数上限值*/
int j;

printf("\n\n\t\t************约瑟夫环问题************\n");
printf("\t\t\t请输入参与人的数量(n):"); /*输入测试人的数量*/
scanf("%d",&n);
printf("\n");

loop:if(n<=0||n>30) /*检验n是否满足要求，如不满足重新输入n值*/
{printf("\n n是错误的！！\n\n");
printf("\n\t\t\t请再次输入参与人的数量(n):");
scanf("%d",&n);
goto loop;
}

2.构造链表并输入每个人信息模块:
for(i=1;i<=n;i++) /* 建立单链表*/
{if(i==1)
{head=p=(struct Lnode*)malloc(sizeof(struct Lnode));
}
else
{q=(struct Lnode*)malloc(sizeof(struct Lnode));
p->next=q;
p=q;
}
printf("\t\t\t请输入第 %d个人所持有的密码:",i); /*输入每个人所持有的密码值*/
scanf("%d",&(p->password)); /*将输入的密码放进链表P中去*/
p->number=i;
}
p->next=head;
p=head;

3.释放结点模块
printf("请输入一个密码(m):");
scanf("%d",&m);

for (j=1;j<=n;j++) /*输出各人的编号*/
{for(i=1;i<m;i++,p=p->next);
m=p->password;
printf("\t\t\t第%d个出列的人是：%d \n",j,p->number);
p->number=p->next->number; /*删除报m的节点*/
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");
}

(3)完整的程序：
#include<stdio.h>
#include<stdlib.h>
typedef struct Lnode /*定义链表*/
{int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;

int main(void)

{
int n; /*n个人*/
int i;
int m; /*初始报数上限值*/
int j;

printf("\n\n\t\t************约瑟夫环问题************\n");
printf("\t\t\t请输入参与人的数量(n):"); /*输入测试人的数量*/
scanf("%d",&n);
printf("\n");

loop:if(n<=0||n>30) /*检验n是否满足要求，如不满足重新输入n值*/
{printf("\n n是错误的！！\n\n");
printf("\n\t\t\t请再次输入参与人的数量(n):");
scanf("%d",&n);
goto loop;
}

for(i=1;i<=n;i++) /* 建立单链表*/
{if(i==1)
{head=p=(struct Lnode*)malloc(sizeof(struct Lnode));
}
else
{q=(struct Lnode*)malloc(sizeof(struct Lnode));
p->next=q;
p=q;
}
printf("\t\t\t请输入第 %d个人所持有的密码:",i); /*输入每个人所持有的密码值*/
scanf("%d",&(p->password)); /*将输入的密码放进链表P中去*/
p->number=i;
}
p->next=head; /*形成循环链表*/
p=head;
printf("请输入一个密码(m):");
scanf("%d",&m);

for (j=1;j<=n;j++) /*输出各人的编号*/
{for(i=1;i<m;i++,p=p->next);
m=p->password;
printf("\t\t\t第%d个出列的人是：%d \n",j,p->number);

p->number=p->next->number; /*删除报m的节点*/
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");

}

5．调试分析
调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果。

6．使用说明
6． 　　说明
（1）程序名为LinkList.exe，运行环境为DOS。
程序执行后显示

（2）在输入（n）的值后，会提示输入n个人的密码；
3）随后将提示输入n以内的任意一个数m；

（4）当输入的这个密码m，并且按enter后会自动弹出所出列人的顺序:

7． 测试结果
依次输入的密码为：3，1,7,2,4,8,4
密码值m：6
输出的出列顺序为：6,14,7,2,3,5