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

...wd......wd......wd...《数据构造与算法设计》约瑟夫环实验报告——实验一专业：物联网工程班级：物联网1班学号：15180118姓名：刘沛航实验目的1、熟悉VC环境，学习使用C语言利用链表的存储构造解决实际的问题。2、在编程、上机调试的过程中，加深对线性链表这种数据构造的根本概念理解。3、锻炼较强的思维和动手能力和更加了解编程思想和编程技巧。二、实验内容1、采用单向环表实现约瑟夫环。请按以下要求编程实现：从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。从键盘输入整数s〔1<=s<=m〕和n，从环表的第s个结点开场计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开场重新计数到n，这样，不断进展计数，不断进展输出，直到输出了这个环表的全部结点为止。例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。三、程序设计1、概要设计为了解决约瑟夫环的问题，我们可以建设单向环表来存储每个人的信息〔该人的编号以及其下一个人的编号〕，及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。抽象数据类型定义ADTJoh{ 数据对象：D= 数据关系：R1= 根本操作：create(&J,n) 操作结果：构造一个有n个结点的单向环表J。show(J) 初始条件：单向环表J已存在。 操作结果：按顺序在屏幕上输出J的数据元素。calculate(J,s,n)初始条件：单向环表J已存在，s>0，n>0，s<环表结点数。操作结果：返回约瑟夫环的计算结果。}ADTJoh〔2〕宏定义#defineNULL0#defineOK1#defineERROR-1〔3〕主程序流程开场开场输入数据输入数据〔m，s，n〕创立环表创立环表输出建设好的环表输出建设好的环表计算处理计算处理输出结果输出结果完毕完毕模块调用关系程序分为下述模块：1〕主函数模块——执行输入调用其他的功能函数2〕创立环表模块——创立单向环表3〕计算处理模块——计算出要出列的标号并输出4〕显示模块——输出建设好的环表调用关系如下：主函数模块创立环表模块显示模块计算处理模块2、详细设计(1)数据类型设计typedefintElemType;//元素类型typedefstruct{ ElemTypedata; structJoh*next;}Joh,*LinkList,*p;//结点类型，指针类型(2)操作算法Statuscreate(LinkList&J,intn){ //创立一个有n个结点的单向环表 if(n<=0) returnERROR; //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;//插入到表头 } returnOK;}//createvoidshow(LinkListJ){//主要的操作函数 //顺序输出环表J的结点 p=J; printf("%d",p->data); p=p->next; while(p!=J){//循环终止条件 printf("%d",p->data); p=p->next; }}//showvoidcalculate(LinkListJ,ints,intn){ 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; } printf("%d",p->data); head->next=p->next;//删除已输出结点 p=head->next; } if(n!=1) printf("%d\n",p->data); else printf("\n");}//calculate(3)主函数代码intmain(){//主函数 Joh*J;intm,s,n; printf("Thenumofnodeis:"); scanf("%d",&m); create(J,m);//创立单向环表J show(J);//输出J的数据 printf("\n"); printf("Thefirstnodewhichyouwantis:"); scanf("%d",&s); printf("Theinternalwhichyouwantis:"); scanf("%d",&n); calculate(J,s,n);//计算并输出结果 return0;}//main四、程序调试分析1、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要操作函数caculate〔〕时，在终止条件的书写处不是很清楚，导致我浪费了很多时间。2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了遇到的问题时，一个很好的手段就是询问同学，寻求其帮助，就比方我在想函数终止条件时，同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时，还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛吧。五、用户使用说明1、本程序的运行环境为Windows操作系统下的MicrosoftVisualC++6.0。2、在VC环境下翻开程序后，按要求键入要求的数字，以等号或空格断开，敲击“回车符〞，即可以显示要求的结果。3、按下任意键以继续。六、程序运行结果程序测试1：程序测试2：七、程序清单#include<stdio.h>#include<stdlib.h>//引用函数库structLNode{intnum;structLNode*next;};//定义链表typedefstructLNodeNODE;NODE*createlinklist(intn){ //初始化循环链表,并返回头指针NODE*head,*p,*q;inti=1;head=p=(structLNode*)malloc(sizeof(structLNode));p->num=i;for(i=2;i<=n;i++){q=(structLNode*)malloc(sizeof(structLNode));if(q==0)return(0);p->next=q;p=q;p->num=i;}p->next=head;//使链表尾指向链表头,形成循环链表 returnhead;}voidjoseph(NODE*p,intn,intm){ //约瑟夫函数，用于输出约瑟夫环inti,j;NODE*q;for(i=1;i<=n;i++) { for(j=1;j<m;j++) p=p->next;//计算出列者序号 q=p->next; p->next=q->next; printf("%d",q->num); free(q); }p->next=NULL;}voidmain(){ NODE*head;intn,s,m; inti; //确定计算系数 printf("**********************物理网1班-15180118-刘沛航****************************\n");printf("围绕圆桌的人数为?\n");scanf("%d",&n);printf("从第几人开场?\n");scanf("%d",&s);printf("数到几的人出列?\n");scanf("%d",&m); //确定头指针head=createlinkli