北京理工大学《数据结构与算法设计》实验报告

1、整版实验一学院：班级： 学号： 姓名： 一、实验目的1. 2. 3. 4.VC 程、调试的练习；用C 等基本操作； 理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。二、实验内容1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： create 函数生成一个具有m 环表。环表中的结点编号依次为 1，2，m。 和n，从环表的第s个结点开始1，当计数到n n 计数，不断进行输出，直到输出了这个环表的全部结点为止。三、程序设计 1、概要设计个抽象数据类型：单向环表。（1、单向环表的抽象数据类型定义为：T数据对象： D=ai|aiElemSet,i=1,2,3,n,n0 数据关系：R1= |a

2、iD,i=1,2,n 基本操作： create(L,n)操作结果：构造一个有n 个结点的单向环表L。 show(L)初始条件：单向环表L 已存在。L的数据元素。Josephf( L,m,s,n)初始条件：单向环表Lth （2、主程序流程create(L,n)m个节点的单向环表L，然后调用 show(L) 函数，顺序输出链表中的数据，最后调用Josephf( L,m,s,n)函数，依次输出报的数。（3、函数调用关系图creat Josephf 2、详细设计(1)、数据类型设计typedefintElemType;/ 定义元素类型 typedefLnode ElemTypedata;struct

3、Lnode *next; （实现：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;ii+) p = (Linklist)malloc(sizeof(Lnode);p-data = i; /生成新节点，数据为节点编号 h-next = p; h = p; /插入链表 h-next = L; /形成循环链表 void show(Linklist L,int m) /从第一个节点开始依次输出节点编号printf(提示用户

4、 Linklist h; h=L;for(int i=1;ii+) printf( h = h-next; printf(void Josephf(Linklist L,int m,int s,int n) /实现约瑟夫环 Linklist h,q; h = L; q = L; while(h-data != s) / h = h-next;while(q-next!=h) / q = q-next; for(int j=1;jj+) int i=1; while(in) q=q-next; i+; printf( q-next = q-next-next; / （3、主程序的代码实现： t ) int s,m,n; Linklist L;printf(请输入节点数 m：n scanf(; / ; / 请输入起始位置 printf(n：n scanf(Josephf(L,m,s,n); /定位开始的节点 定位在开始位置的上一个节n return 0; 四、程序调试分析1. 2. 3. 4.引用标识符不符合C 语言语法，应使用 C+;编号数据；“”（空格）”（换行使输出易于辨识。五、 用户使用说明1本程序的运行环境为DOS2. m,Enter“请输入起始位置用户输入起始位置r“请输入报的数”，Enter键，即可得到依次报号的结果。测试一：测试二：七、程序清单#i