2023年数据结构约瑟夫环实验报告2.pdf
伏 倒 咛洗石n 数据结构课程实验报告书RMAL姓名:徐鑫学号：_ _ _ _ _ _ _ _专 业:物 联 网 工 程班级:16042023年 10 月15 日一、实验目的1.掌握线性表特性2.纯熟掌握线性表的基本操作3 .运用线性表设计算法并实现二、实验内容1.解决约瑟夫环问题：已知n 个人（以 编 号 1,2,3.n 分别表达）围坐在一张圆桌周边。从编号为k 的人开始报数，数到m的那个人出列；他的下一个人又从 1 开始报数，数 到 m的那个人又出列；依此规律反复下去，直到圆桌周边的人所有出列。2.基本规定：1）根据题目规定设计解决约瑟夫环应用问题的数据结构。2）规定采用C+编程语言实现设计的算法。三、设计思绪1 .数据逻辑关系的分析。令将 人的顺序简朴编号，从 1 至 Un;。土 构造一个循环链表，可以解决首位相连的问题；4s将人的编号插入到结构体的Da t a 域中；布应历人的编号，输出参与的人的编号；开始报数，从头报数，报 到 k 的人出局（删除此结点），并释放此结点。直到人数只有一个人时，退出循环，输出获胜的人。2.存储结构设计（建立约瑟夫环）（循环结束条件）3.算法的核心思想说明口拟定需要删除的位置；口。设立并删除该位置。已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，假如获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设立为该位置，继而删掉该位置。反复进行上述拟定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1 .类的声明和定义（规定给出完整的类声明和核心成员函数的定义）o b#if n def Joseph_H#d e fin e J o seph_H#include using namespac e std;st r uct N o d e/结点（int data;/存储数据woNod e*nex t；下一个节点的地址）；clas s Circul a rL i nkL i s t/单向循环链表类publ i c:Circular L in k L i s t()构造函数。o f irs t=n ew N ode;3 first-da t a=NULL;市 r st-next=f i rst;8 g Circ u 1 a rL i n k L ist()d el e t e f i rs8V o id C r eateLi n kLi s t(in t a,i nt n)；3 voi d P r int L ink L ist();遍历链表g v o id Joseph(int k,i n t n);约瑟夫环实现p riva t e:o de*f irst;)；#end i f2.算法实现#include Jo s e p h.h#i n c lu d e#i n c 1 u de v o id Ci r cula r Li n kList:：C reate L i(g No d e*s,*r=first;/尾指针初始化g f o r (int i=0；i data=a i；o Mrnext=s;析构函数创建单I句循环链表n kList(int a,in t n)3 s r=s;o eg rnext=firstn e xt;循环void C i r c u 1 a rLinkList:P r i ntL i nkList()(g in t c o unt=0;/计数器N o d e *r=f i r s t-next；8d o o cout setw (3)r data;oc o u n t+；Q r=rnext;。i f(co u n t%10=0)co u t endl n e x t);/当链表循环到第一节点时跳出循环gocout end 1 ；)void CircularLinkList:Jose p h(int k,i n t n)(int m;e COUt ”-请输入约瑟夫密码：”；Min m;输入约瑟夫密码Node*pre,*p;s pre=first;/工作指针初始化。p=pre-ne x t;for(in t i=0;i next;。叩=pre-ne x t;0 0 0 int c ount=1;/计数器初始化，约瑟夫问题至少有两个成员a cou t n*n、w h i le(pr e!=p)d 6(6 if(co u n t=m)/假如计数器等于密码。Sleep(l*1000);执行挂起一段时间(1秒)6cout data next=p-next;g。de 1 ete q;/删除死亡结点Q g p=prenext;oocoun t=1;/计数器重新计数00|else0 gopre=pre-nex t;工作指针后移go op=p-n e x t;8。co u nt+;计数器加一0 0|60|6cout*n”；。cou t s etw(2 6)da t a ”号存活！请输入参与人数：6C:Wi n d owssystem 32cmd.exe X约瑟夫环游戏一 请输入参与人数：6对所有人进行编号！编号如下：1 2 3 4 5 6一 请输入从第几人开始：2六、实验调试HB C:Wi n d owssyste m 3 2cm d.exeX约 瑟 夫 环 游 戏 请输入参与人数：6对所有人进行编号！编号如下：1 2 3 4 5 6一请输入从第几人开始：2一请输入约瑟夫密码：45号死亡！3号死亡！2号死亡！4号死亡！1号死亡！6号存活！请按任意键继续.搜 狗 拼 音 输 入 法 全：七、问题及解决方法问题：无法从第k 个人开始报数。解决方法：用w hile循环，找寻开始报数的编号k,找到后把他报的数标记为1.问题：将 Link L is t.h 文献的L inkList类中的行为函数放进L i nkLis t.cpp文献中出现错误“重定义”。解决办法:将行为函数的定义与声明均放进L i nkList.h 文献中。八、心得体会通过对约瑟夫环问题算法的设计，我加深了对数据结构及存储结构的理解，进一步的理解了课本中所学的各种数据结构，特别是对单链表上基本运算的体现，学会了如何使用循环链表，比如建立一个循环链表，删除链表中的一个结点，增长一个结点等等。此外，写代码一定要细心仔细，不能犯不该犯的粗心的错误！注（格式规定）：1 ）字体采用楷书小四号字，行间距为固定值2。磅2）代码用Time New R o ma n字号为五号，行间距固定值1 6磅
