数据结c语言约瑟夫环实验报告 数据结构约瑟夫环实验报告.doc

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

数据结构与算法设计约瑟夫环实验报告实验一专业物联网工程班级物联网1班学号15180118姓名刘沛航一、 实验目的 1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际的问题。2、在编程、上机调试的过程中，加深对线性链表这种数据结构的基本概念理解。3、锻炼较强的思维和动手能力和更加了解编程思想和编程技巧。二、实验内容 1、 采用单向环表实现约瑟夫环。请按以下要求编程实现 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2m。 从键盘输入整数s(1sm)和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m10，s3，n4。则输出序列为6，10，4，9，5，2，1，3，8，7。三、程序设计 1、概要设计为了解决约瑟夫环的问题，我们可以建立单向环表来存储每个人的信息(该人的编号以及其下一个人的编号)，及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。(1) 抽象数据类型定义 ADT Joh数据对象D数据关系R1基本操作createJ, n操作结果构造一个有n个结点的单向环表J。showJ初始条件单向环表J已存在。操作结果按顺序在屏幕上输出J的数据元素。calculate J,s,n初始条件单向环表J已存在，s0，n0，s环表结点数。操作结果返回约瑟夫环的计算结果。ADT Joh(2)宏定义define NULL 0 define OK 1define ERROR -1 (3)主程序流程开始输入数据(m，s，n)创建环表输出建立好的环表计算处理输出结果结束(4) 模块调用关系程序分为下述模块1)主函数模块执行输入调用其他的功能函数 2)创建环表模块创建单向环表 3)计算处理模块计算出要出列的标号并输出 4)显示模块输出建立好的环表 调用关系如下 主函数模块 创建环表模块 显示模块 计算处理模块 2、详细设计1数据类型设计typedef int ElemType; 元素类型typedef struct ElemType data;struct Joh *next;Joh, *LinkList,*p; 结点类型，指针类型2操作算法Status createLinkList J,int n创建一个有n个结点的单向环表ifn0return ERROR;n0错误JLinkListmallocsizeofJ;J-data1;J-nextJ;建立第一个结点forint in;i1;ipLinkListmallocsizeofJ;p-datai;p-nextJ-next;J-nextp;插入到表头return OK;create void showLinkList J主要的操作函数顺序输出环表J的结点pJ;printfd ,p-data;pp-next;whilepJ 循环终止条件printfd ,p-data;pp-next;showvoid calculateLinkList J,int s,int npJ;Joh *headp; 声明结点whilep-dataspp-next;headp;寻找起始结点whilep-nextp 终止条件forint i0;in-1;iheadp; 保存前置节点pp-next;printfd ,p-data;head-nextp-next; 删除已输出结点phead-next;ifn1printfdn,p-data;elseprintfn;calculate3主函数代码int main主函数Joh *J;int m,s,n;printfThe num of node is;scanfd,m;createJ,m; 创建单向环表JshowJ; 输出J的数据printfn;printfThe first node which you want is;scanfd,s;printfThe internal which you want is;scanfd,n;calculateJ,s,n; 计算并输出结果return 0;main四、程序调试分析 1、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要操作函数caculate()时，在终止条件的书写处不是很清楚，导致我浪费了很多时间。 2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了遇到的问题时，一个很好的手段就是询问同学，寻求其帮助，就比如我在想函数终止条件时，同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时，还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛吧。五、用户使用说明 1、本程序的运行环境为Windows操作系统下的Microsoft Visual C 6.0。2、在VC环境下打开程序后，按要求键入要求的数字，以等号或空格断开，敲击“回车符”，即可以显示要求的结果。3、按下任意键以继续。六、程序运行结果程序测试1程序测试2 七、程序清单includestdio.hincludestdlib.h 引用函数库struct LNode int num; struct LNode *next 定义链表typedef struct LNode NODE;NODE *createlinklistint n初始化循环链表,并返回头指针 NODE *head,*p,*q; int i1; headpstruct LNode*mallocsizeofstruct LNode; p-numi; fori2;in;i qstruct LNode*mallocsizeofstruct LNode; ifq0 return0; p-nextq; pq; p-numi; p-nexthead; 使链表尾指向链表头,形成循环链表return head;void josephNODE *p,int n,int m约瑟夫函数，用于输出约瑟夫环int i,j; NODE *q; fori1;in;i forj1;jm;j pp-next; 计算出列者序号 qp-next; p-nextq-next; printfd ,q-num; freeq; p-nextNULL;void main NODE *head; int n,s,m; int i;确定计算系数printf物理网1班-15180118-刘沛航n; printf围绕圆桌的人数为n; scanfd,n; printf从第几人开始n; scanfd,s; printf数到几的人出列n; scanfd,m; 确定头指针 headcreatelinklistn; ifs1 fori1;in;i headhead-next; else fori1;is-1;i headhead-next;输出约瑟夫环出列顺序 printf出列的顺序如下n; josephhead,n,m; printfn;

如果觉得《数据结c语言约瑟夫环实验报告 数据结构约瑟夫环实验报告.doc》对你有帮助，请点赞、收藏，并留下你的观点哦！