资源描述：
《北理工自动化数据结构实验报告1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《数据结构与算法设计》实验报告——实验一一、实验目的利用单向环表实现约瑟夫环二、实验内容采用单向坏表实现约瑟夫环。请按以下要求编程实现：①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。环表屮的结点编号依次为1,2,……，肌②从键盘输入整数s(l<=s<=m)和n,从环表的第s个结点开始计数为1,当计数到第n个结点时，输出该第n结点对应的编号，将该结点从坏表中消除，从输出结点的下一个结点开始重新计数到n,这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10,s=3,n=4c则输出序列为:6,10,4,9,5,2,1,3,8,7。三、
2、程序设计1、概要设计为了实现程序功能，应当建立单向环表來寄存信息及结点，通过查找结点来完成相应的操作。(1)、单项环表的抽象数据类型定义为：ADTJoseph{数据对彖：D二{
3、,1,2,,,0}iiaaElemSetinn数据关系：Rl=ll{,
4、,,1,2,,JiiiiaaaaDin基本操作：create(&J,n)操作结果：构造一个有n个结点的单向环表J。show(J)初始条件：单向环表J已存在。操作结果：按顺序在屏幕上输出J的数据元素。calculate(J,s,n)初始条件：单向环表J己存在，s>0,n>0,s<环表结点数。操作结果：返回约瑟夫环的计算结果。}ADTJose
5、ph(1)、宏定义#defineOK1#defineERROR0(2)、主程序流程主程序首先调用create(J,m)函数创建含有m个结点的单向环表J,随后调用show(J)函数显示创建的环表内容，最后调用calculated,s,n)函数计算结果并在屏幕上打卬。(1)、模块调用关系：由主两数模块调川创建模块，显示模块与计算模块。由计算模块将结果输出。(2)、流程图2、详细设计(1)〃定义结构体typedefstructLNode{intdata;structLNode*next;}LNODE;(2)〃创建单向循环链表voidcreate(LNode*L,intm){inti;LNo
6、de*p;if(m>l){p=(LNode*)malloc(sizeof(LNode));p->data=m;p->ncxt二L;I厂〉next二p;m=m-l;}for(i=m;i>l;i--){//插入到表头p=(LNode*)malloc(sizeof(LNode));p->data二i;p-〉next二L->next;L->next=p;m=m-1；}}voiddel(intm,ints,intn,LNode*L){//主要的操作函数inta=l,b=0;LNode*p,*head;P=L；head二p->next;while(head->next!=p)head=head-
7、>ncxt;while(p->data!=s){//寻找起始结点p=p->next;head=head->next;}for(b=m;b>0;b一){for(a二1;a〈n;a++){p=p->next;head=head->next;}printf(z/%d，z,p->clata);head->next=p->next;free(p);p二head->next;}}(1)//主函数voidmainOintm,s,n;LNode*L=NULL;scanf("%d%d%d",&m,&s,&n);〃建立第一个结点L=(LNode*)malloc(sizeof(LNode));L->d
8、ata=l;L->next=NULL;created,m);//计算并输出结果del(m,s,n,L);}四、程序调试分析首先，在完成编写第一次编译的吋候，出现了许多个erroro仔细检查Z后发现有5个都是由粗心造成的错误，比如在语句结束时漏写了“；”，“；”、“，”打串了等等，或者类似程序前后同一变量大小写使用不同之类错误。这说明以后编程的时候一定要细心，注意细节才能节约吋间、提高效率。在第二步即环表建立的步骤时候，dol函数的编写总是!llerror,在反复研究和调试Z后依【口没有解决问题，最后还是同学指出了一个很隐蔽的错谋才解决的，可见当程序运行出现问题的时候，一定要仔细一步步
9、去调试，很有可能一•个很小的漏洞就导致整个程序的错误。在计算函数屮，未定义当前结点的前直结点，导致输出结果有误，后经检查分析，应定义指针指向当前结点的前置结点，修改之后简化了程序，也提高了效率。五、用户使用说明1.本程序的运行环境为Windows操作系统下的MicrosoftVisualC++6.0。2.在VC环境下打开程序后，点击运行。3.按要求键入m,s,n的值，敲击“回车符”，即可以使全部节点按照题目所要求的顺序输出。六、程序运行结果测试用例1:输入
