《数据结构与算法设计》约瑟夫环实验报告——实验一专业：物联网工程班级：物联网1班学号：15180118姓名：刘沛航一、实验目的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={|,1,2,,,0}i i a a ElemSet i n n ∈=≥K数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈=K基本操作：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）主程序流程（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;}//createvoid 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("%d\n",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、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。
