2023年数据结构约瑟夫环实验报告新编.docx

《2023年数据结构约瑟夫环实验报告新编.docx》由会员分享，可在线阅读，更多相关《2023年数据结构约瑟夫环实验报告新编.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、他仅冲洗石n数据结构课程实验报告书姓名：徐鑫学号：专业:物联网工程班级:16042023年 10 月15 日一、实验目的.掌握线性表特性1 .纯熟掌握线性表的基本操作.运用线性表设计算法并实现二、实验内容.解决约瑟夫环问题：已知n个人（以编号1,2, 3. . n分别表达）围坐在一 张圆桌周边。从编号为k的人开始报效，数到m的那个人出列；他的下一个人又 从1开始报数，数到m的那个人又出列；依此规律反复下去，直到圆桌周边的人 所有出列。1 .基本规定：1）根据题目规定设计解决约瑟夫环应用问题的数据结构。2）规定采用C+ +编程语言实现设计的算法。三、设计思绪.数据逻辑关系的分析。令将人的顺序简朴

2、编号，从1到n;。o中构造一个循环链表，可以解决首位相连的问题；他 将人的编号插入到结构体的Dat a域中；电遍历人的编号，输出参与的人的编号；中 开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点。 直到人数只有一个人时，退出循环，输出获胜的人。1 .存储结构设计 p re p, c o unt=2（建立约瑟夫环）preP（循环结束条件）2 .算法的核心思想说明口拟定需要删除的位置；口。设立并删除该位置。已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，假如 获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际 长度来修正修正（即模拟环状计数）。然后把顺序表

3、中的当前指向位置设立 为该位置，继而删掉该位置。反复进行上述拟定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1 .类的声明和定义（规定给出完整的类声明和核心成员函数的定义）3 0 #if n def Joseph_H# d e fin e J o seph_H#include using namespac e std;st r uct Node/结点(&int data;存储数据ao&Nod e *nex t ； 下一个节点的地址I；Circul a rL i nkL i s t / /单向循环链表类clas s publCircular L in k L i s t ()构造函数。

4、 f irs t = n ew N ode;o first-da t a = NULL;ofi r st- next = f i rst;ga Cir c u 1 a rL i n k L ist () d cl e t e finavoid C r eateLi n kLi st (in t a, i nt n)；，3Voi d P r int L ink L ist();遍历链表a void Joseph(int k,i n( n); 约瑟夫环实现p riva t c:a aN o de * f irst;)；#end i f2.算法实现#includc Jo Sep h.hi n c l

5、u d e # i n c 1 u de void Ci r cula r Li n kList:： C reate L i(g Nod e *s, *r = 尾指针初始化。 for (int i = 0 ； i data = a i ；) 析构函数/创建单向循环链表n kList(int a , in t n)r-next=S；r-next = first-n e xl;/循环)void C i r c u 1 a rLinkList: P r i ntL i nkList()(。in t c ount = 0;计数器Node *r = firs t-next：gd o 。 cout set

6、w (3) r data;维 o u n t +；。 r = r-next;。i f (co u n t % 10 = 0)o co u t endln ext);/ /当链表循环到第一节点时跳出循环 wcout end 1 ；)void CircularLinkList:Jose p h (int k,i n t n)(int m；。cout 请输入约瑟夫密码：；gein 输入约瑟夫密码Node *pre, * p ;。pre = first;/工作指针初始化。 p prc-nc x t ;ofor (in t i = 0; i next;gp pre-ne x t;0 Ioint coun

7、t = 1;/计数器初始化，约瑟夫问题至少有两个成员00 COU t * * * * * * * 丈 火* 大* * * *w h i Ie (pr e != p)00 。 -if (cou nt = m)/假如计数器等于密码皿。 Sleep(l * 1000)，执行挂起一段时间(1秒)。cout data vv号死亡!vv endl;显示结果。 Node * Q = p ;g pre next = p- next;。de 1 ete q;/删除死亡结点 g p = pre-next;。coun t = 1 J/计数器重新计数00)空Ise。(gopre = pre-nex t ;工作指针后移

8、3g 叩=p- next;8g c o u nt+;/ 计数器加一0 o Jcout * * * * * * * * * * 大* n ；， cou t s etw( 2 6)da t a vv 号存活！ 请输入参与人数：6对所有人进行编号！编号如下：1 2 3 4 5 6一请输入从第几人开始：2六、实验调试SB C:Windowssystem32cmd.exe约瑟夫环游戏请输入参与人数：6对所有人进行编号！ 编号如下：1 2 3 4 5 6一请输入从第几人开始：2 一分请输入约瑟夫密码：45号死亡!3号死亡!2号死亡!4号死亡!1号死亡!6号存活!请按任意键继续. 搜狗拼音输入法全： 七、问

9、题及解决方法问题：无法从第k个人开始报数。解决方法：用while循环，找寻开始报教的编号k,找到后把他报的数标记为1.问题：将Link Li s t .h文献的L inkList类中的行为函数放进Li n k L is t .cpp文 献中出现错误“重定义”。解决办法:将行为函数的定义与声明均放进L i nkList. h文献中。八、心得体会通过对约瑟夫环问题算法的设计，我加深了对数据结构及存储结构的理解，进一 步的理解了课本中所学的各种数据结构，特别是对单链表上基本运算的体现，学 会了如何使用循环链表，比如建立一个循环链表，删除链表中的一个结点，增长 一个结点等等。此外，写代码一定要细心仔细，不能犯不该犯的粗心的错误！注（格式规定）：1 ） 字体采用楷书小四号字，行间距为固定值20磅2）代码用Time New R。ma n字号为五号，行间距固定值16磅