约瑟夫环实验报告(共11页).doc
精选优质文档-倾情为你奉上数据结构与算法设计实验报告实验一学院：自动化学院班级：学号：姓名：王冬一、 实验目的 1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际的问题。2、在编程、上机调试的过程中，加深对线性链表这种数据结构的基本概念理解。3、锻炼较强的思维和动手能力和更加了解编程思想和编程技巧。二、实验内容 1、 采用单向环表实现约瑟夫环。请按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，m。 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。三、程序设计 1、概要设计为了解决约瑟夫环的问题，我们可以建立单向环表来存储每个人的信息（该人的编号以及其下一个人的编号），及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。（1） 抽象数据类型定义 ADT Joh数据对象：D=数据关系：R1=基本操作：create(&J, n)操作结果：构造一个有n个结点的单向环表J。show(J)初始条件：单向环表J已存在。操作结果：按顺序在屏幕上输出J的数据元素。calculate( J,s,n)初始条件：单向环表J已存在，s>0，n>0，s<环表结点数。操作结果：返回约瑟夫环的计算结果。ADT Joh（2）宏定义#define NULL 0 #define OK 1#define ERROR -1 （3）主程序流程开始输入数据（m，s，n）创建环表输出建立好的环表计算处理输出结果结束（4） 模块调用关系程序分为下述模块：1）主函数模块执行输入调用其他的功能函数 2）创建环表模块创建单向环表 3）计算处理模块计算出要出列的标号并输出 4）显示模块输出建立好的环表 调用关系如下： 主函数模块 创建环表模块 显示模块 计算处理模块 2、详细设计(1)数据类型设计typedef int ElemType; /元素类型typedef struct ElemType data;struct Joh *next;Joh, *LinkList,*p; /结点类型，指针类型(2)操作算法Status create(LinkList &J,int n)/创建一个有n个结点的单向环表if(n<=0)return ERROR;/n<0错误J=(LinkList)malloc(sizeof(J);J->data=1;J->next=J;/建立第一个结点for(int i=n;i>1;-i)p=(LinkList)malloc(sizeof(J);p->data=i;p->next=J->next;J->next=p;/插入到表头return OK;/create void show(LinkList J)/主要的操作函数/顺序输出环表J的结点p=J;printf("%d ",p->data);p=p->next;while(p!=J) /循环终止条件printf("%d ",p->data);p=p->next;/showvoid calculate(LinkList J,int s,int n)p=J;Joh *head=p; /声明结点while(p->data!=s)p=p->next;head=p;/寻找起始结点while(p->next!=p) /终止条件for(int i=0;i<n-1;i+)head=p; /保存前置节点p=p->next;printf("%d ",p->data);head->next=p->next; /删除已输出结点p=head->next;if(n!=1)printf("%dn",p->data);elseprintf("n");/calculate(3)主函数代码int main()/主函数Joh *J;int m,s,n;printf("The num of node is:");scanf("%d",&m);create(J,m); /创建单向环表Jshow(J); /输出J的数据printf("n");printf("The first node which you want is:");scanf("%d",&s);printf("The internal which you want is:");scanf("%d",&n);calculate(J,s,n); /计算并输出结果return 0;/main四、程序调试分析 1、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要操作函数caculate（）时，在终止条件的书写处不是很清楚，导致我浪费了很多时间。 2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了遇到的问题时，一个很好的手段就是询问同学，寻求其帮助，就比如我在想函数终止条件时，同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时，还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛吧。五、用户使用说明 1、本程序的运行环境为Windows操作系统下的Microsoft Visual C+ 6.0。2、在VC环境下打开程序后，按要求键入要求的数字，以等号或空格断开，敲击“回车符”，即可以显示要求的结果。3、按下任意键以继续。 六、程序运行结果测试用例1：输入：m=10,s=3，n=4 输出：6，10，4，9，5，2，1，3，8，7测试用例2： 输入：m=13，s=4，n=3 输出：6，9，12，2 ，5，10 ，1， 7 ，13 ，8 ，4 ，11 ，3七、程序清单#define NULL 0 #define OK 1#define ERROR 0typedef int Status;typedef int ElemType; typedef struct /结点类型ElemType data;struct Joh *next;Joh,*LinkList;/定义约瑟夫结构Joh *p;#include"stdio.h"#include"stdlib.h"Status create(LinkList &J,int n)if(n<=0)return ERROR;J=(LinkList)malloc(sizeof(J);J->data=1;J->next=J;/建立第一个结点for(int i=n;i>1;-i)p=(LinkList)malloc(sizeof(J);/申请空间p->data=i;p->next=J->next;J->next=p;/插入到表头return OK;/构造函数void show(LinkList J)p=J;printf("%d ",p->data);p=p->next;while(p!=J) /循环结束条件printf("%d ",p->data);p=p->next;/显示函数void calculate(LinkList J,int s,int n)p=J;Joh *head=p;while(p->data!=s)p=p->next;head=p;/寻找起始结点while(p->next!=p)for(int i=0;i<n-1;i+)head=p; /保存前置结点p=p->next;printf("%d ",p->data);head->next=p->next; /删除已输出结点p=head->next;if(n!=1)printf("%dn",p->data);elseprintf("n");/主体计算函数int main()Joh *J;int m,s,n;printf("The num of node is（m=）:");scanf("%d",&m);create(J,m); /创建单向环表Jshow(J); /显示J的数据内容printf("The first node which you want is（s=0）:");scanf("%d",&s);printf("The internal which you want is(n=):");scanf("%d",&n);calculate(J,s,n); /计算并输出最后结果return 0;专心-专注-专业
