约瑟夫问题数据结构实验报告要点.docx

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

1、中南民族大学管理学院学生实验报告实验项目:约瑟夫问题课程名称：数据结构年级：专业：信息管理与信息系统指导教师：实验地点：管理学院综合实验室完成日期：小组成员：2012学年至2013学年度第1学期中南民族大学管理学院学生告一、实验目的（1）掌握性表表示和；（2）学会定抽象数据型；（3）学会分析，适当的解决方案；二、实验内容【描述】：号1,2,⋯,n的n个人按方向坐一圈，每人持有一个密（正整数）。一开始任一个正整数作数上限m，从第一个人开始按方向自1开始序数，到m停止数。报m的人出列，将他的密作新的m，从他在方向上的下一个人开始重新从1数，

2、如此下去，直至所有人全部出列止。一个程序求出出列序。【基本要求】：利用向循表存构模此程，按照出列的序印出各人的号。【数据】：m的初20；密：3，1，7，2，4，8，4（正确的果6，1，4，7，2，3，5）。三、实验步骤（一）需求分析于个程序来，首先要确定构造表所用的插入方法。当数到m一个人就出列，也即除个点，同建立个点的前点与后点的系。由于是循数，所以才采用循列表个性表方式。程序存构利用循表存构存瑟夫数据（即n个人的等），模瑟夫的示程，按照出列的序示个人的号。号1,2,⋯,n的n个人按方向坐一圈，每人持有一个密（正整数）。一开始任一个正

3、整数作数上限m，从第一个人开始按方向自1开始序数，到m停止数。报m的人出列，将他的密作新的m，从他在方向上的下一个人开始重新从1数，如此下去，直至所有人全部出列止。一个程序求出出列序。基本要求是利用向循表存构模此程，按照出列的序印出各人的号。程序行的命令（1）构造向循表。（2）按照出列的序引出各个人的号。数据m的初20；密：3，1，7，2，4，8，4（正确的果应为6，1，4，7，2，3，5）（1）、插入：在把元素插入到循表中，由于是采用的插法，所以我保留了front点。在每加入一个点，都会直接接在front后面，从而保一开始就的rear

4、尾点不用修改。代如下：中南民族大学管理学院学生实验报告1)、在堆中建立新节点：Node*s=newNode;2)、将a[i]写入到新节点的数据域：s->data=a[i];3)、修改新节点的指针域：s->next=front->next;4)、修改头结点的指针域，将新节点加入到链表中：front->next=s;时间复杂度为：1；(2)、删除：首先通过p指针查找到所要删除的节点的前一个节点，继而通过q=p->next简单地删除掉。假设所要查找的为第i个元素。伪代码阐释如下：1）、在堆中建立新节点p,通过循环查找到i-1，将此

5、节点的地址赋给p。2）、设q指向第i个节点：若p=rear，则q=front->next;否则，q=p->next;3)、摘链，即将q从链表中摘除：若q=rear，则p->next=front->next；否则，则p-next=q->next.4)、保存q元素的数据：x=q->data；5）、释放q元素：deleteq；时间复杂度为：1；（3）、约瑟夫问题的基本思想：在这个循环查找问题中，通过循环链表实现了循环查找到节点。一个关键部分就是删除节点后进行链表的链接，从而保证链表的循环性。在查找方面上，我利用了一个for循环来计数所查找过的

6、节点。其中查找的时间复杂度也为1；（二）概要设计测试主函数流程：流程图如下：开始输入m和n判断m、n是否符合要求否是创建Clinklist类的对象，首先建立循环链表，之后调用Josef函数。中南民族大学管理学院学生实验报告判断链表跳出函数是否为空否循环查找到所要删除节点的前一个节点。判断所要删除节点是否为最后一个是否删除该节点，并从该节点的直接后继结点重新计数。此时要判断P和q是否存在恰好为rear指针的情况输出m的位置结束（三）详细设计#includeusingnamespacestd;constintd=500

7、00;structNode{intdata;中南民族大学管理学院学生实验报告structNode*next;//声明next指针};classClinklist{public:Clinklist(inta[],intn);voidJosef(intm,intn);private:Node*rear;//声明rear和front指针Node*front;intn;};Clinklist::Clinklist(inta[],intn){rear=newNode;front=newNode;front->next=rear;//构造空单链表r

8、ear->next=front;rear->data=a[n-1];for(inti=n-2;i>=0;i--){Node*s=newNode;//循环插入元素来建立链表s->data=a[i];s->ne