数据结构约瑟夫环实验报告.docx

《数据结构约瑟夫环实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构约瑟夫环实验报告.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、伍）*#夕*大导世E岸花CMwnrCM*.fM tBlMMnwoati数据结构与算法设计约瑟夫环实验报告一实验一专业：物联网工程班级：物联网1班学号：姓名：struct LNodeint num;struct LNode *next;；定义链表typedef struct LNode NODE;NODE *createlinklist(intn) (初始化循环链表,并返回头指针NODE *head,*p,*q;inti=1;head=p=(struct LNode*)malloc(sizeof(struct LNode);p-num=i;for(i=2;inext=q;p=q;p-num=i;

2、p-next=head;/使链表尾指向链表头，形成循环链表return head;)voidjoseph(NODE *p,intn5intm)约瑟夫函数，用于输出约瑟夫环intij;NODE *q;for(i=1 ;iv=n;i+) (for(j=1;jnext;/计算出列者序号q=p-next;p-next=q-next;free(q);)p-next=NULL;void main()(NODE *head;int n,s,m;inti;确定计算系数物理网 1 班15180118刘沛航环绕圆桌的人数为从第儿人开始数到几的人出列确定头指针head=createlinklist(n);if(s=

3、1)for(i=1 ;inext;elsefor(i=1 ;inext;输出约瑟夫环出列顺序出列的顺序如下joseph(head,n,m);一、实验目的1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际 的问题。2、在编程、上机调试的过程中，加深对线性链表这种数据结构的 基本概念理解。3、锻炼较强的思维和动手能力和更加了解编程思想和编程技 巧。二、实验内容1、采用单向环表实现约瑟夫环。请按以下要求编程实现：从键盘输入整数m,通过create函数生成一个具有m个结点的 单向环表。环表中的结点编号挨次为1, 2, ,ni。从键盘输入整数s (K=s=m)和n,从环表的第s个结点开始 计数为

4、1,当计数到第n个结点时，输出该第n结点对应的编 号，将该结点从环表中消除，从输出结点的下一个结点开始重 新计数到n,这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。例如，m=10, s=3, n=4o 则输出序列为：6, 10, 4, 9, 5, 2,1, 3, 8, 7o三、程序设计1、概要设计为了解决约瑟夫环的问题，我们可以建立单向环表来存储每个人的信息(该人的编号以及其下一个人的编号)，及结点，人 后通过查找每一个结点，完成相应的操作来解决约瑟夫问题。(1)抽象数据类型定义ADT Joh数据对象：D=a |a eElemSet,i = 1,2,.,n,nN0数据关

5、系：R1=|a ,a eD,i = 1,2,.,n)i-1 i i-1 i基本操作：create(&J, n)操作结果：构造一个有n个结点的单向环表J。show(J)初始条件：单向环表J已存在。操作结果：按顺序在屏幕上输出J的数据元素。calculate( J,s,n)初始条件：单向环表J已存在，s0, n0, sv环表 结点数。操作结果：返回约瑟夫环的计算结果。ADT Joh(2)宏定义ttdefine NULL 0define OK 1ttdefine ERROR -1(3)主程序流程开始输入数据（m, s, n创建环表输出建立好的环计算处理输出结果结束（4） 模块调用关系程序分为下述模块

6、：1）主函数模块一一执行输入调用其他的功能函数2）创建环表模块一一创建单向环表3）计算处理模块一一计算出要出列的标号并输出4）显示模块一一输出建立好的环表调用关系如下：主函数模块。创建环表模块显示%块计算处%模块2、详细设计(1)数据类型设计typedef intElemType;元素类型typedef struct ElemType data;struct Joh *next;Joh, *LinkList,*p;结点类型，指针类型操作算法Status create(LinkList &J,intn)创建一个有n个结点的单向环表if(n=0)return ERROR; /ndata=1;J-n

7、ext=J;/建立第一个结点for(inti=n;i1 ;-i)p=(LinkList)malloc(sizeof(J);p-data=i;p-next=J-next;J-next=p; 插入至 ij 表头)return OK;/createvoid show(LinkList J)主要的操作函数顺序输出环表J的结点P=J；p=p-next;while(p!=J) 循环终止条件p=p-next;)/showvoid calculate(LinkList JJnt s3intn)P=J;Joh *head=p;声明结点while(p-data!=s)p=p-next;head=p;/寻觅起始结点

8、while(p-next!=p)终止条件for(inti=0;inext;)head-next=p-next; /删除已输出结点 p=head-next;)if(n!=1)else/calculate(3)主函数代码int main。主函数Joh *J;int m3s5n;create(J5m);show(J);/创建单向环表j/输出J的数据calculate(J5s5n);计算并输出结果return 0;/main四、程序调试分析1、细节决定成败，编程最需要的是严谨，如何的严谨都无非 分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数 据类型上。在写主要操作函数caculate (

9、)时，在终止条件的书写处 不是很清晰，导致我浪费了不少时间。2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了 遇到的问题时，一个很好的手段就是问询同学，寻求其匡助，就 比如我在想函数终止条件时，同学一句简单的话语就让我如梦初 醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时， 还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛 吧。五、用户使用说明1、本程序的运行环境为Windows操作系统下的Microsoft Visual C+ 6. 0o2、在VC环境下打开程序后，按要求键入要求的数字，以等号或者 空格断开，敲击“回车符”，即可以显示要求的结果。3、按下任意键以继续。六、程序运行结果程序测试1 ：程序测试2：j ,CKAHQC SX j|FS7 C1 tug卜*“*4*“打 理 H 1班 T ISC 1 18-刘沛 I 用续曲q的人故K?10j,y几人开邠现至几的人出列？一列的顺序如下：1865? 10 4923Press ary key to contirwj憎楙音输入法全：七、程序清单#include引用函数库#include