《 数 据 结 构 与 算 法 设 计 》 约 瑟 夫 环 实 验 报 告 ——实验一 专业：物联网工程 班级：物联网 1 班 学号：******** 姓名：*** 一、 实验目的 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}iiaaElemSet in n 数据关系：R1=11{,|,,1,2,, }iiiiaaaaD in 基本操作： 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）显示模块——输出建立好的环表 调用关系如下： 主函数模块 开始 输入数据（m，s，n） 创建环表 输出建立好的环计算处理 输出结果 结束 创建环表模块 显示模块 计算处理模块 2、详细设计 (1)数据类型设计 typedef int ElemType; //元素类型 typ...
