《数据结构与算法设计》实验报告.docVIP

《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 实验目的 熟悉VC++6.0环境，学习使用C++实现链表的存储结构； 2. 通过编程，上机调试，进一步理解线性表、链表、环表的基本概念，并利用单向环实现约瑟夫环。 二、实验内容 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、概要设计 应用单向环寄存数字序列。 单向环表的抽象数据类型线性表定义如下： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ai-1,aiai-1,ai∈D,i=2,…,n} 基本操作： Creat(LinkListL,int m) 操作结果：构造一个有m个节点的单向环表L。 YSF(int m,int s,int n,LNode *L) 初始条件：单向环表L已经存在。 操作结果： 找到单向环表L的第s个结点，并进行约瑟夫环的计算，并输出相应值。 }ADT List 主程序流程 主程序首先调用Creat(LinkListL,int m)函数，创建含有m个结点的单向环表L；再调用YSF(int m,int s,int n,LNode *L)函数，找到第s个结点，并进行约瑟夫环的计算，在屏幕上显示计算结果。 模板调用关系 由主函数模板调用创建模块和运算模块。 由运算模块将结果输出。 （4） 流程图 2、详细设计 (1)数据类型设计 typedef struct LNode //定义结构体 { int data; struct LNode *next; }LNODE; (2)操作算法设计 void Create(LNode *L,int m) //创建单向环表 { int i; LNode *p; if(m1) { p=(LNode*)malloc(sizeof(LNode)); p-data=m; p-next=L; L-next=p; m=m-1; } for(i=m;i1;i--) //插入到表头 { p=(LNode*)malloc(sizeof(LNode)); p-data=i; p-next=L-next; L-next=p; m=m-1 } } void YSF(int m,int s,int n,LNode *L) //找到第s个结点并进行约瑟夫计算 { int a=1,b=0; LNode *p,*head; p=L; head=p-next; while(head-next!=p) head=head-next; while(p-data!=s) //寻找起始结点 { p=p-next; head=head-next; } for(b=m;b0;b--) { for(a=1;an;a++) { p=p-next; head=head-next; } printf(%d\n,p-data); head-next=p-next; free(p); p=head-next; } } (3) 主函数设计 void main() { //主函数 int m,s,n; LNode *L=NULL; scanf(%d %d %d,m,s,n); L=(LNode*)malloc(sizeof(LNode)); //建立第一个结点 L-data=1; L-next=NULL; Create(L,m); YSF(m,s,n,L); //计算并输出结果 } 四、程序调试分