约瑟夫环问题实验报告

　 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); }

推荐访问： 约瑟夫 实验 报告