数据结构约瑟夫环实验报告.docx
伍）*#夕*大导世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;i<=n;i+) (q=(struct LNode*)malloc(sizeof(struct LNode);if(q=O) return(O);p->next=q;p=q;p->num=i;p->next=head;/使链表尾指向链表头，形成循环链表return head;)voidjoseph(NODE *p,intn5intm)约瑟夫函数，用于输出约瑟夫环intij;NODE *q;for(i=1 ;iv=n;i+) (for(j=1;j<m;j+) p=p->next;/计算出列者序号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=1)for(i=1 ;i<n;i+)head=head->next;elsefor(i=1 ;i<s-1 ;i+)head=head->next;输出约瑟夫环出列顺序出列的顺序如下joseph(head,n,m);一、实验目的1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际 的问题。2、在编程、上机调试的过程中，加深对线性链表这种数据结构的 基本概念理解。3、锻炼较强的思维和动手能力和更加了解编程思想和编程技 巧。二、实验内容1、采用单向环表实现约瑟夫环。请按以下要求编程实现：从键盘输入整数m,通过create函数生成一个具有m个结点的 单向环表。环表中的结点编号挨次为1, 2, ,ni。从键盘输入整数s (K=s<=m)和n,从环表的第s个结点开始 计数为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数据关系：R1=< a ,a >|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已存在，s>0, n>0, sv环表 结点数。操作结果：返回约瑟夫环的计算结果。ADT Joh(2)宏定义ttdefine NULL 0define OK 1ttdefine ERROR -1(3)主程序流程开始输入数据（m, s, n创建环表输出建立好的环计算处理输出结果结束（4） 模块调用关系程序分为下述模块：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; /n<0 错误J=(LinkList)malloc(sizeof(J);J->data=1;J->next=J;/建立第一个结点for(inti=n;i>1 ;-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;/寻觅起始结点while(p->next!=p)终止条件for(inti=0;i<n-1 ;i+)head=p;/保存前置节点p=p->next;)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 ()时，在终止条件的书写处 不是很清晰，导致我浪费了不少时间。2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了 遇到的问题时，一个很好的手段就是问询同学，寻求其匡助，就 比如我在想函数终止条件时，同学一句简单的话语就让我如梦初 醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时， 还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛 吧。五、用户使用说明1、本程序的运行环境为Windows操作系统下的Microsoft Visual C+ 6. 0o2、在VC环境下打开程序后，按要求键入要求的数字，以等号或者 空格断开，敲击“回车符”，即可以显示要求的结果。3、按下任意键以继续。六、程序运行结果程序测试1 ：程序测试2：j ,CKAH'QC SX j|F»S7 C1 tug卜*“*4*»»*«“打 理 H 1班 T£ ISC 1 18-刘沛 I 用续曲q的人故K?10j,y几人开邠现至几的人出列？一£列的顺序如下：1865? 10 4923Press ary key to contirwj憎£楙音输入法全：七、程序清单#include<stdio.h>引用函数库#include<stdlib.h>
