约瑟夫环问题实验报告
1
《专业实训 II》 实训报告
实训项目名称：
约瑟夫环问题
班级：
学号：
姓名：
指导教师：
2 目录
目录 .................................................................................................................................................. 2 一、摘要........................................................................................................................................... 3 二、专业实训项目描述 ................................................................................................................... 3 三、程序设计 ................................................................................................................................... 3 3.1 菜单系统设计（系统功能结构设计）
............................................................................. 3 3.2 基础数据结构设计 ............................................................................................................ 4 3.3
函数封装（功能模块设计）
.......................................................................................... 4 四、关键算法分析 ........................................................................................................................... 6 五、总结........................................................................................................................................... 6 附录：程序源代码 ........................................................................................................................... 7
湖北第二师范学院计算机学院
83030177
专业实训 I
3
一、摘要
报告描述了《约瑟夫环系统》的 C 语言实现方案，程序代码用 C语言给出，包含所有的数据结构及函数定义、功能模块，以及专业实训过程中的心得体会。
二、专业实训项目描述 本专业实训项目以《约瑟夫环系统》为主题，包含初始化链表、创建链表、约瑟夫环输出等模块，主要采用了循环单链表数据结构，及相关的递归算法等。
三、程序设 计
3.1 菜单系统设计（系统功能结构设计）
void main()
{
int n,m; Node *p,*head; LinkList CL;
printf("\t\t************欢迎来到约瑟夫环*************\n\n\n");
printf("请输入一个初始密码作为一个报数上限值，再输入每个人的密码，并求出出列顺序\n\n\n");
printf("请输入人数 N：\n");
scanf("%d",&n);
printf("请输入初始密码 m:\n");
scanf("%d",&m);
InitCLinkList(&CL);
head=CreateCLinkList(CL,n);
PrintLinkList(head,n);
p=head;
printf("出列的顺序为：\n");
joseph(p,n,m); }
湖北第二师范学院计算机学院
83030177
专业实训 I
4 3.2 基础数据结构设计
************************** typedef struct Node {
int num;
int data;
struct Node *next; } Node,*LinkList;//结点类型，指针类型
int InitCLinkList(LinkList *CL)//创建一个无头结点的单向循环链表 {
int key;
printf("请依次输入密码：");
scanf("%d",&key);
*CL=(Node *)malloc(sizeof(Node));//申请一个结点
(*CL)->data=key;
(*CL)->num=1;
(*CL)->next=*CL;
return OK; }
3.3
函数封装（功能模块设计）
1.主函数模块——执行输入调用其他的功能函数 2.创建环表模块——创建单向循环链表 Node *CreateCLinkList(LinkList CL,int n) {
Node *rear; Node *s,*head;
int i=1,key;
rear=CL;
for(i=2;i<=n;i++)
{
scanf("%d",&key);
head=s=(Node*)malloc(sizeof(Node));//创建一个结点
s->data=key;
s->num=i;
rear->next=s;
湖北第二师范学院计算机学院
83030177
专业实训 I
5
rear=s;
}
head=rear->next=CL;//尾指针指向头指针
return head;
} 3.计算处理模块——计算出要出列的标号并输出 4.宣示模块——输出建立好的环表
int PrintLinkList(LinkList CL,int n)
{
int i;
Node *p;
p=CL;
printf("每个人的序号及对应的密码为：\n");
for(i=1;i<=n;i++)
{
printf("%d,%d\n",p->num,p->data);
p=p->next;
}
if(p=NULL)
{
printf("此链表为空");
exit(OVERFLOW);
}
printf("\n");
return OK;
}
湖北第二师范学院计算机学院
83030177
专业实训 I
6
四、关键算法分析 int joseph(LinkList CL,int n,int m)
{
int i,j;
Node *p;
Node *q;
p=CL;
for(j=1;j<m-1;j++)//循环到第 m-1 个结点
{
p=p->next;
}
q=p->next;
//q 指向第 m 个结点
p->next=q->next;
p=p->next;
printf("%d\t",q->num);//输出第 m 个结点的序号
n--;
if(n>1)
joseph(p,n,q->data);//用第 m 个结点的密码进行递归调用
else
printf("%d",p->num);//输出最后一个结点的序号
free(q);
p->next=NULL;
return OK;
} 五、 总结 答：细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要函数 joseph()时，在查找目标结
湖北第二师范学院计算机学院
83030177
专业实训 I
7 点的书写处不是很清楚，导致我浪费了很多时间。
附录：程序源代码 #include <stdio.h> #include <stdlib.h> #include <conio.h> #define OK 1 #define OVERFLOW 0 typedef struct Node {
int num;
int data;
struct Node *next;
} Node,*LinkList;
int InitCLinkList(LinkList *CL) {
int key;
printf("请依次输入密码：");
scanf("%d",&key);
*CL=(Node *)malloc(sizeof(Node));
(*CL)->data=key;
(*CL)->num=1;
(*CL)->next=*CL;
return OK; }
Node *CreateCLinkList(LinkList CL,int n) {
Node *rear; Node *s,*head;
int i=1,key;
rear=CL;
for(i=2;i<=n;i++)
{
scanf("%d",&key);
head=s=(Node*)malloc(sizeof(Node));
s->data=key;
s->num=i;
rear->next=s;
湖北第二师范学院计算机学院
83030177
专业实训 I
8
rear=s;
}
head=rear->next=CL;
return head;
}
int joseph(LinkList CL,int n,int m)
{
int i,j;
Node *p;
Node *q;
p=CL;
for(j=1;j<m-1;j++)
{
p=p->next;
}
q=p->next;
p->next=q->next;
p=p->next;
printf("%d\t",q->num);
n--;
if(n>1)
joseph(p,n,q->data);
else
printf("%d",p->num);
free(q);
p->next=NULL;
return OK;
}
int PrintLinkList(LinkList CL,int n)
{
int i;
Node *p;
p=CL;
printf("每个人的序号及对应的密码为：\n");
for(i=1;i<=n;i++)
{
printf("%d,%d\n",p->num,p->data);
p=p->next;
湖北第二师范学院计算机学院
83030177
专业实训 I
9
}
if(p=NULL)
{
printf("此链表为空");
exit(OVERFLOW);
}
printf("\n");
return OK;
}
void main()
{
int n,m; Node *p,*head; LinkList CL;
printf("\t\t************欢迎来到约瑟夫环*************\n\n\n");
printf("请输入一个初始密码作为一个报数上限值，再输入每个人的密码，并求出出列顺序\n\n\n");
printf("请输入人数 N：\n");
scanf("%d",&n);
printf("请输入初始密码 m:\n");
scanf("%d",&m);
InitCLinkList(&CL);
head=CreateCLinkList(CL,n);
PrintLinkList(head,n);
p=head;
printf("出列的顺序为：\n");
joseph(p,n,m); }
上一篇：扩频通信实验报告
下一篇：java课程设计实验报告