约瑟夫环实验报告

实验报告中山大学数学学院课程设计题目：约瑟夫环问题一．问题描述设有编号为1,2，…，n的n个（n0）个人围城一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的人出圈，……，知道所有人全部出圈为止。当任意给定n和m后，求n个人出圈的次序。二．基本要求1.建立数据模型，确定储存结构；2.对任意n个人，密码为m，实现约瑟夫环问题；3.出圈的顺序可以依次输出，也可以用一个数组存储。三．概要设计1.数据结构的设计1.由于约瑟夫环问题本身具有循环性质，考虑采用循环链表；2.为了统一对表中任意结点的操作，循环链表不带头结点；3.为了方便的进行计数，选用尾指针；2.算法的设计由于约瑟夫环所需的数据结构为不带头指针的循环链表，所以在单链表的基础上，需要对构造函数进行改造；约瑟夫环的实现过程中已经把链表所占用的空间释放掉，因此，析构函数只需采用默认析构函数，输出单链表时采用要改变终止条件。综合来看，需要构造的函数只有三个，一个是构造函数，一个是PrintList函数，一个是实现约瑟夫环算法的函数。1.构造函数；1.工作指针r，s初始化；控制循环变量i初始化；2.为rear申请空间；将a[n-1]的值赋给rear的指针域；r指向rear的指针域；3.重复执行下述操作，直到i等于n-23.1为s申请空间；3.2将a[i]的值赋给s的数据域；3.3将s插入到r；3.4r指针后移；4.将rear插入到r之后；2.voidPrintList（）；1.工作指针p初始化；2.重复以下操作，直到p-等于rear；2.1输出结点p的数据域；2.2工作指针p后移3.输出rear的数据域3.voidYueSeFuHuan（intm，intn）；1.工作指针p，pre初始化；计数器count初始化；2.重复以下操作，直到pre等于p；2.1如果count=m，输出p的数据域；删除p结点；计数器count初始化；2.2否则工作指针pre，p后移；count++；3.删除p结点；3.抽象数据类型的设计ADTCircleLinkListData循环链表中的元素具有相同类型，相邻元素通过指针域具有前驱和后继的关系，第一个结点是最后一个结点的后继OperationInitCircleLinkList前置条件：循环链表不存在输入：数组的头指针，数组的长度功能：循环链表的初始化和赋值输出：无后置条件：一个具有数据的循环链表DestroyCircleLinkList前置条件：循环链表已存在输入：无功能：销毁循环链表输出：无后置条件：释放循环链表所占用的存储空间PrintList前置条件：循环链表已存在输入：无功能：遍历操作，按序号依次输出循环链表中的元素输出：循环列表的各个数据元素后置条件：线性表不变YueSeFuHuan前置条件：循环链表已存在输入：循环列表长度n，各个对象拥有的密码m功能：依照一定的次序删除各个对象，输出每次删除的对象序号输出：每次删除的对象的序号后置条件：线性表置空四．详细设计1．设计抽象数据类型对应的C++类定义。1.InitCircleLinkList:templateclassDataTypeCircleLinkListDataType::CircleLinkList(DataTypea[],intn){NodeDataType*r,*s;rear=newNodeDataType;r=rear;rear-data=a[n-1];//尾指针的数据的赋值for(inti=0;in-1;i++){s=newNodeDataType;s-data=a[i];r-next=s;r=s;}r-next=rear;}2.DestroyCircleLinkList:CircleLinkListDataType::~CircleLinkList(){NodeDataType*q=NULL;while((rear-next)!=rear){//这里由于不能直接判定是否循环终止，所以需要看后继是否为rear本身q=rear;rear=rear-next;deleteq;}deleterear;//还剩下头指针没有被释放}3.PrintList:templateclassDataTypevoidCircleLinkListDataType::PrintList(){NodeDataType*p=rear-next;while(p!=rear){coutp-data;p=p-next;}coutrear-dataendl;}4.YueSeFuHuan:templateclassDataTypevoidCircleLinkListDataType::YueSeFuHuan(intn,intm){NodeDataType*p,*pre;pre=rear;//这里不应该加*p=rear-next;intcount=1;while(pre!=p){if(count==m){cout这轮删除的是：p-dataendl;pre-next=p-next;if(p==rear)rear=pre;//删除到对位结点要进行判断；deletep;p=pre-next;count=1;}else{pre=p;p=p-next;count++;}}deletep;}2．设计每个数据成员。NodeDataType*rear;/*structNode{DataTypedata;NodeDataType*next;};*/3．设计主函数。#includeiostreamusingnamespacestd;#includeCircleLinkList.cppintmain(){constintn=10;constintm=3;intr[10]={1,2,3,4,5,6,7,8,9,10};CircleLinkListintL(r,10);cout执行约瑟夫环操作前数据为：endl;L.PrintList();cout执行约瑟夫环:endl;L.YueSeFuHuan(n,m);}五．运行与测试1.在调试程序的过程中遇到什么问题，是如何解决的？算法上：1.1由于一开始的时候没有参考实验辅导里的算法，所以一开始用的是利用Delete函数再加上计数来做，然后又因为采用了带有头结点的循环列表，所以有一些需要特殊处理的问题；1.2再用Delete函数的时候，发生了错误，是因为在这题的应用之中，指向头结点和最后一个结点的时候不能简单的报错，而是要给与相应的解决方式；1.3不再使用Delete函数之后，直接在需要删除的点进行删除，但是除了头结点和最后一个结点的删除之外还发生了其他的错误：输出不再列表之内的数。经过调试检查，最后发现要在每次循环的时候进行判断，如果是头指针，count不能自加；1.4课本上采用了带头指针的循环列表，但是如果是带头指针的循环列表的话，m最小只能为2，因此，我选择采用带尾指针的循环列表，这使我能够让m=1成为可能；编程过程中：1.5尾指针指向最后一个结点，最后一个结点要在赋值的循环之外单独进行赋值，否则会输出“奇怪”的数字；1.6循环列表的遍历过程，由于初始位置与终止位置相同，因此，判断循环终止的条件要改为指向尾指针的前一个，同时尾指针徐要单独处理；1.7删除时要注意尾指针的特殊处理；1.8运行的时候出现了一直输出“奇怪的数”的情况。经过排查发现，出现这种情况是因为PrintList一直在运行，而这个的原因是没有指向NULL，然后回去看YueSeFuHuan的函数，发现有个地方的操作让“指针”断掉了；1.9new一个新的数据只能用来插入，用于存储的话不能用那一个结点的指针，只能用他的指针域进行存储；2.设计了那些测试数据？测试结果是什么？1.constintn=10;constintm=3;intr[10]={1,2,3,4,5,6,7,8,9,10};（图1）2.constintn=10;constintm=1;intr[10]={1,2,3,4,5,6,7,8,9,10};（图2）3.constintn=3；constintm=5;intr[10]={1,2,3};图（3）图1图2图3六．总结与心得写约瑟夫环这个程序，我改了很多次，有几次还是整个算法的改变，最大的想法是：当你选用一个数据结构的时候，你要充分考虑为什么你要选择它不选择其他的数据结构，从而让这个数据结构的优势充分发挥，而不是出现你选了它，却不利用这种算法的优势，失去了选择这种算法的意义。七．思考与拓展采用顺序存储结构实现约瑟夫环问题。关于这一个问题，在我第一次编程的时候利用Delete函数的算法类似（不再给出），由于顺序存储结构能够实现随机存取，所以采用这种算法能够省去查找的时间，但同时会增加移动元素的时间；并且，元素的遍历不需要通过指针，只需要通过下标即可，在循环链表中，我采用了Listcount来记录次序，并且会自己判断是否到达终点，在顺序存储结构中，只需让ListcountLength即可。采用带尾指针rear指示的不带头结点的循环列表。我设计的程序中采用的就是这一种方法。每个人持有的密码不同，实现约瑟夫环问题。NodeDataType*rear;/*structNode{DataTypedata;NodeDataType*next;intCode；};*/结构体中增加一个Code，在YueSeFuHuan中的循环外再嵌套一个循环存储Code，原循环在找到被删结点后，读取Code，删除结点，跳出原循环即可。