《数据结构与算法设计》
实验报告
——实验一
学院：
班级： 学号： 姓名：
一、实验目的
1. 2. 3. 4.
通过实验实践、巩固线性表的相关操作； 熟悉VC环境，加强编程、调试的练习；
用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。
二、实验内容
1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ① 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的
结点编号依次为1，2，……，m。
② 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到
第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。
三、程序设计 1、概要设计
为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。
（1）、单向环表的抽象数据类型定义为： ADT Joseph{
数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={
操作结果：构造一个有n个结点的单向环表L。 show(L)
初始条件：单向环表L已存在。
操作结果：按顺序在屏幕上输出L的数据元素。 Josephf( L,m,s,n)
初始条件：单向环表L已存在， s>0,n>0，s 主程序首先调用create(&L,n)函数，创建含有m个节点的单向环表L，然后调用show(L)函数，顺序输出链表中的数据，最后调用Josephf( L,m,s,n)函数，依次输出报的数。 （3）、函数调用关系图 creat Josephf 2、详细设计 (1)、数据类型设计 typedef int ElemType; //定义元素类型 typedef struct Lnode{ ElemType data; struct Lnode *next; }Lnode,*Linklist; //定义节点类型，指针类型 （2）、操作算法程序实现： void create(Linklist &L,int m) { //生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，……，m Linklist h,p; L=(Linklist)malloc(sizeof(Lnode)); L->data = 1; h=L; for(int i=2;i<=m;i++) { p = (Linklist)malloc(sizeof(Lnode)); p->data = i; //生成新节点，数据为节点编号 h->next = p; h = p; //插入链表 } h->next = L; //形成循环链表 } void show(Linklist L,int m) { //从第一个节点开始依次输出节点编号 printf(\提示用户 Linklist h; h=L;