数据结构实验报告一-约瑟夫环问题3300字.docx

    数据结构实验报告一-约瑟夫环问题3300字    实验1约瑟夫环问题1． 需求分析（1） 输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用逗号隔开若分别设为n,m，则输入格式为：“n,m”不对非法输入做处理，即假设输入都是合法的2） 输出的形式：输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中（3） 程序所能达到的功能：对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果正确：输入：10,3输出：3 6 9 2 7 1 8 5 10 4输入：41,3输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31错误：输入：10 3输出：6 8 7 1 3 4 2 9 5 102． 概要设计（1）抽象数据类型的定义：为实现上述程序的功能，可以用整数存储用户的输入并将用户输入的值存储于线性表中。

线性表ADT定义如下：ADT list数据对象：整形数据关系：线性关系，即(0≤a＜n)基本操作：bool remove(int &elem)//移除一个元素，被移除的元素赋给elem//如果操作成功，返回true,否则返回falsebool isEmpty()//判断数组的元素是否清空，空返回true,否则返回falsebool setPos(int place)//设置当前元素的位置，设置成功返回true,否则返回falseint getLength()//获取数组的实际长度－ 1 －（2）算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空3）主程序的流程：程序由三个模块组成：（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开2）处理模块：将元素储存于顺序表中在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值反复设置并删除直到表空3）输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置4）各程序模块之间的层次（调用）关系：主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序3． 详细设计（1） 实现概要设计中定义的所有数据类型（物理数据结构）：1、用整形存储用户输入的整数2、用顺序表实现线性表：class AList{private:int *listArray;//指向数组的指针int realSize;//数组中含有元素的实际长度int fence;//指向当前元素下标public:AList(int s)//构造函数，初始化数组{listArray=new int[s];for(int i=0;i=0&&place<=realSize){fence=place;return true;}return false;}int getLength()//获取数组长度{return realSize;}};－ 3 －（2） 算法的具体步骤：在主函数中调用上述模块的方法：ofstream fout;//文件流fout.open("C:\\Josephus.txt");//设置文件路径int n,m,elem,point=0;scanf("%d,%d",&n,&m);//获得用户输入AList alist(n);//创建顺序表对象while(!alist.isEmpty())//如果顺序表不为空，继续删除{m=m%alist.getLength();//调整计数的长度if(m==0)m=alist.getLength();if(point+m-1

2、处理部分，我为了提高效率没有采用循环寻找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为n的约瑟夫环，只做了n次定位，每次定位的复杂度为Θ(1)，所以时间复杂度为Θ(n)但是用顺序表实现时，每次其移除的方法是时间复杂度为Θ(k)的(k与实际长度有关)，(1?n)n所以处理部分总的结果是()的，化简后时间复杂度仍然为Θ(n2) 2综上，该算法的时间代价为Θ(n2)PS：如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是Θ(n*m)，然后再用顺序表的移除方法，总的复杂度应该是Θ(m*n2)的事实上要用线性表来完成这道题，其复杂度最好也是Θ(n2)的，毕竟对于n个数据，每个都要进行时间复杂度为Θ(n)的删除工作欲到达Θ(n)的效率除非不用线性表来实现－ 4 －（4） 画出函数的调用关系图：主程序（5） 输入和输出的格式：输入：10,3输出：3 6 9 2 7 1 8 5 10 4（文本中的输出）：3 6 9 2 7 1 8 5 10 44、测试结果－ 5 －第二篇：天大数据结构实验报告一_约瑟夫环 2900字题目：用单循环链表解决约瑟夫问题 数据结构上机实验报告学生姓名学生学号学院名称 计算机学院 专 业 计算机科学与技术 时 间2013.10.7目 录第一章、需求分析 ………………………………………… 11.1 原题表述 …………………………………………… 11.2 所选的要求及整体规划 …………………………… 1第二章、概要设计 ………………………………………… 22.1 抽象数据类型 ………………………………………… 22.2 算法 …………………………………………………… 2第三章、详细设计 ………………………………………… 33.1 程序代码 ……………………………………………… 3第四章、调试分析 ………………………………………… 74.1 调试工作 ……………………………………………… 74.2 时间复杂度 ………………………………………… 7第五章、测试结果 ………………………………………… 85.1 输入数据和输出数据样例 ………………………… 81计算机学院2012级数据结构上机实验报告第一章 需求分析1.1 原题表述设n个人围坐在一圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局者的下一人重新开始报数，数到第m个人，再让他出局······如此反复，直到所有的人全部出局为止。

1.2 所选的要求及整体规划对于任意给定的n、s和m，求出这个n个人的出局序列，数据结构采用单循环链表构造不带头结点的单循环链表1计算机学院2012级数据结构上机实验报告第二章 概要设计2.1 抽象数据类型不带头结点的单循环链表2.2 算法建立一个不带头结点的空循环链表，依次在链表中添加数据域为1~n的n个数据元素，此时指针head指向第一个元素，再用一个for循环让头指针head指向第s个元素，之后用while循环让head指向第m-1个元素，删除第m个元素，head指向第m+1个元素，直至链表中只剩一个元素依次输出被删除的元素及最后剩余的元素2计算机学院2012级数据结构上机实验报告第三章 详细设计3.1 程序代码#include#includetypedef struct node{int data; struct node *next;}node;//函数功能：构造不带头结点的循环链表并赋值1~n，头指针head指向第s个人node* create(int n,int s){node *head; node *p, *q, *r;int i,j;if(n<=0) return NULL; //若分配内存失败返回 //把长度为n的链表赋值1~n head=(node*)malloc(sizeof(node)); head->data=1; head->next=NULL; p=head; for(i=1; idata=i+1; p->next=q;3计算机学院2012级数据结构上机实验报告} p=q; } //构造循环链表 q=(node*)malloc(sizeof(node)); q->data=n; p->next=q; q->next=head;//不带头结点 for(j = 1; j < s; j++)//从第s个人开始数 { r = head -> next; head = r; } return head;int del(node *head)//删除 {node *p, *q; if(head==NULL) return -1; p=head; q=p->next; p->next=q->next; p=q->next; free(q); head=p;。