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

数据结构与算法设计实验报告实验一学院： 班级：学号：姓名： 1、 实验目的 1. 熟悉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、概要设计应用单向环寄存数字序列。（1） 单向环表的抽象数据类型线性表定义如下：ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=ai-1,aiD,i=2,n 基本操作： Creat(LinkList&L,int m) 操作结果：构造一个有m个节点的单向环表L。 YSF(int m,int s,int n,LNode *L) 初始条件：单向环表L已经存在。 操作结果： 找到单向环表L的第s个结点，并进行约瑟夫环的计算，并输出相应值。ADT List（2） 主程序流程 主程序首先调用Creat(LinkList&L,int m)函数，创建含有m个结点的单向环表L；再调用YSF(int m,int s,int n,LNode *L)函数，找到第s个结点，并进行约瑟夫环的计算，在屏幕上显示计算结果。（3） 模板调用关系由主函数模板调用创建模块和运算模块。由运算模块将结果输出。 （4） 流程图开始输入数据（m，s，n）创建环表计算处理 输出环表结束 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;anext;head=head-next;printf(%dn,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); /计算并输出结果四、程序调试分析 （1）在第二步即环表建立的步骤时候，YSF函数的编写总是出error，在反复研究和调试之后依旧没有解决问题，最后在同学帮助下终于找到了的原因编写时未将结点退回原来结点处。所以说，调试一定要一步一步来，不能心急，仔细才能正确。 （2）构造数据类型时，未写typedef，导致编译无法通过。这是概念上的疏忽，要重视。五、用户使用说明 1、本程序的运行环境为Windows操作系统下的Microsoft Visual C+ 6.0。2、在VC环境下打开程序后，按要求键入m,s,n的值，敲击“回车符”，即可以显示要求的结果。六、程序运行结果测试用例1：输入：m=10，s=3，n=4 输出：6，10，4，9，5，2，1，3，8，7测试用例2： 输入：m=8，s=2，n=5 输出：6，3，1，8 ，2，5 ，7， 4 七、程序清单#include #include typedef struct LNode /定义结构体int data;struct LNode *next;LNODE;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=m;p-next=L-next;L-next=p;m-;void YSF(int m,int s,int n,LNode *L) /主要的操作函数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;anext;head=head-next;printf(%dn,p-data);head-next=p-next;free(p);p=head-next;void main() /主函数int m,s,n;