约瑟夫环数据结构实验

《约瑟夫环数据结构实验》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验1约瑟夫环问题背景约瑟夫问题（JosephusProblem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 原题： 用户输入M,N值，N个人围

2、成一个环，从0号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？问题描述设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。基本要求需要基于线性表的基本操作来实现约瑟夫问题需要利用顺序表来实现线性表输入输出格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中测试用例（举例）输入：10，3输出

3、：36927185104课后选做内容（1）使用单链表来实现之（2）使用循环链表来实现之课后习题请以O（n）的时间复杂度来实现约瑟夫问题。HUNANUNIVERSITY实验报告题目：约瑟夫环问题学生姓名**学生学号***********专业班级*******指导老师****完成日期****/**/**一、需求分析（1）编号为1-n的n个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。程序依次输出出列人的编号到文件。（2

4、）输入格式:n,mn为约瑟夫环的大小，m为退出游戏人编号的报数。n和m都为大于0的整数。（3）输出格式1、在文件中输出这n个数的输出序列2、将这n个数的输出序列写入到文件中（4）测试数据：输入：10，3输出：36927185104二、概要设计抽象数据类型游戏中人的编号为正整数，所以用整数来存储编号。约瑟夫环中人的编号为连续的正整数，可以看做是一个数列，用线性表来存储这个数列。基本操作包括线性表的初始化，和删除环中元素，以及判断表是否为空等。ADTList{数据对象：D={a[i]

5、a[i]∈整数,i=1,2,……,n,n>=0}数据关系：R1={

6、],a[i]>

7、[ai-1],a[i]∈D,i=2,……,n}基本操作：InitList(&L)操作结果：构造一个空的线性表ListLength(L)初始条件：线性表L已经存在操作结果：返回L中元素个数ListEmpty(L)初始条件：线性表L已经存在操作结果：若L为空表，返回TRUE，否则返回FALSEListAppend(&L,e)初始条件：线性表L已经存在操作结果：将元素e插入到L的表尾ListDelete(&L,i,&e)初始条件：线性表L已经存在操作结果：删除L的第i个数据元素，返回e}ADTList算法的基本思想将约瑟夫环中人的编号依次放进线性表

8、中，当前位置从线性表中的第一个元素开始，移动m-1次（每次移动，当前位置向后移动一次。如果某一次移动前，当前位置为线性表中最后位置时，将当前位置移动到线性表第一个元素位置）。输出当前位置元素值然后删除该元素，线性表大小相应减小长度1。当前位置继续按前述方法移动m-1次并删除移动后当前位置元素。循环进行上述步骤直到线性表为空。程序的流程程序由三个模块组成：（1）输入模块：完成两个正整数的输入，存入变量n和m中。（2）计算模块：通过循环剔除环中的元素，减小约瑟夫环的大小直到元素个数为零。（3）输出模块：依次输出被剔除元素的值到屏幕上三、详细设计物理数据类型按照题

9、目基本要求，该现行表用顺序表来实现。元素用整型存储，用C语言中int类型。TypederintElemtypetypedefstruct{Elemtype*elem;intlength;intlistsize;}SqList;基本操作伪代码：StatusInitList(SqList&L){//构造一个空的线性表L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;retu

10、rnOK;}//InitList_SqintList