资源描述：
《《数据结构与算法设计》实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构与算法设计》实验报告——实验一学院：班级：学号：姓名：一、实验目的1.熟悉VC++6.0环境，学习使用C++实现链表的存储结构；2.通过编程，上机调试，进一步理解线性表、链表、环表的基本概念，并利用单向环实现约瑟夫环。二、实验内容1、采用单向环表实现约瑟夫环。请按以下要求编程实现：①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对
2、应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。三、程序设计1、概要设计应用单向环寄存数字序列。（1）单向环表的抽象数据类型线性表定义如下：ADTList{数据对象：D={ai
3、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai∈D,i=2,…,n}基本操作：Creat(LinkLis
4、t&L,intm)操作结果：构造一个有m个节点的单向环表L。YSF(intm,ints,intn,LNode*L)初始条件：单向环表L已经存在。操作结果：找到单向环表L的第s个结点，并进行约瑟夫环的计算，并输出相应值。}ADTList（2）主程序流程主程序首先调用Creat(LinkList&L,intm)函数，创建含有m个结点的单向环表L；再调用YSF(intm,ints,intn,LNode*L)函数，找到第s个结点，并进行约瑟夫环的计算，在屏幕上显示计算结果。（3）模板调用关系由主函数模板调用创建模块和运
5、算模块。由运算模块将结果输出。（4）流程图开始输入数据（m，s，n）创建环表计算处理输出环表结束2、详细设计(1)数据类型设计typedefstructLNode//定义结构体{intdata;structLNode*next;}LNODE;(2)操作算法设计voidCreate(LNode*L,intm)//创建单向环表{inti;LNode*p;if(m>1){p=(LNode*)malloc(sizeof(LNode));p->data=m;p->next=L;L->next=p;m=m-1;}for(i
6、=m;i>1;i--)//插入到表头{p=(LNode*)malloc(sizeof(LNode));p->data=i;p->next=L->next;L->next=p;m=m-1}}voidYSF(intm,ints,intn,LNode*L)//找到第s个结点并进行约瑟夫计算{inta=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;h
7、ead=head->next;}for(b=m;b>0;b--){for(a=1;anext;head=head->next;}printf("%d",p->data);head->next=p->next;free(p);p=head->next;}}(3)主函数设计voidmain(){//主函数intm,s,n;LNode*L=NULL;scanf("%d%d%d",&m,&s,&n);L=(LNode*)malloc(sizeof(LNode));//建立第一个结点L->d
8、ata=1;L->next=NULL;Create(L,m);YSF(m,s,n,L);//计算并输出结果}四、程序调试分析（1）在第二步即环表建立的步骤时候，YSF函数的编写总是出error，在反复研究和调试之后依旧没有解决问题，最后在同学帮助下终于找到了的原因编写时未将结点退回原来结点处。所以说，调试一定要一步一步来，不能心急，仔细才能正确。（2）构造数据类型时，未写typedef，导致编译无法通过。这是概念上的疏忽，要重视。五、用户使用说明1、本程序的运行环境为Windows操作系统下的Microsoft
9、VisualC++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#includetype
