北京理工大学数据结构实验报告实验一..doc

《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 通过实验实践、巩固线性表的相关操作； VC环境，编程、调试的； C语言编写函数，实现循环链表的建立插入删除数据等基本操作； 与实际相结合，上述基本操作实现约瑟夫环。 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 从键盘输入整数s（1=s=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用环表寄存，需要建立一个抽象数据类型：。 ）单向环表的抽象数据类型定义为： ADT Joseph{ D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ ai-1,ai|ai∈D,i=1,2,……,n} 基本操作： create(L,n) 操作结果：构造一个有n个结点的单向环表L。 show(L) 初始条件：单向环表L已存在。 操作结果：按顺序在屏幕上输出L的数据元素。 Josephf( L,m,s,n) 初始条件：单向环表L已存在， s0,n0，sm。 操作结果：返回约瑟夫环的计算结果。 }ADT Joseph （2）主程序流程 首先调用create(L,n)，创建含有节点的单向环表L然后调用show(L)输出链表中的数据最后调用Josephf( L,m,s,n)依次输出报的数。 ）函数调用关系图 2、详细设计 (1)、数据类型设计 typedef int ElemType; //定义元素类型typedef struct Lnode{ ElemType data; struct Lnode *next; }Lnode,*Linklist; //定义节点类型类型）操作程序实现：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(The numbers of the list are: \n); //提示用户 Linklist h; h=L; for(int i=1;i=m;i++) { printf(%d ,h-data); h = h-next; } printf(\n); } 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;j=m;j++) { int i=1; while(in) { q=q-next; i++; } printf(%d ,q-next-data); //依次输出报号为n的节点 q-next = q-next-next; //删除已输出节点 } printf(\n); } （3）主程序代码实现：int main() { int s,m,n; Linklist L; printf(请输入节点数m：\n); scanf(%d,m); create(L,m);