2023年数据结构约瑟夫环实验报告新编.docx
他仅冲洗石n数据结构课程实验报告书姓名：徐鑫学号：专业:物联网工程班级:16042023年 10 月15 日一、实验目的.掌握线性表特性1 .纯熟掌握线性表的基本操作.运用线性表设计算法并实现二、实验内容.解决约瑟夫环问题：已知n个人（以编号1,2, 3. . n分别表达）围坐在一 张圆桌周边。从编号为k的人开始报效，数到m的那个人出列；他的下一个人又 从1开始报数，数到m的那个人又出列；依此规律反复下去，直到圆桌周边的人 所有出列。1 .基本规定：1）根据题目规定设计解决约瑟夫环应用问题的数据结构。2）规定采用C+ +编程语言实现设计的算法。三、设计思绪.数据逻辑关系的分析。令将人的顺序简朴编号，从1到n;。o中构造一个循环链表，可以解决首位相连的问题；他 将人的编号插入到结构体的Dat a域中；电遍历人的编号，输出参与的人的编号；中 开始报数，从头报数，报到k的人出局（删除此结点），并释放此结点。 直到人数只有一个人时，退出循环，输出获胜的人。1 .存储结构设计 p re p, c o unt=2（建立约瑟夫环）preP（循环结束条件）2 .算法的核心思想说明口拟定需要删除的位置；口。设立并删除该位置。已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，假如 获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际 长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设立 为该位置，继而删掉该位置。反复进行上述拟定位置和删除位置的操作，直到顺序表为空。四、数据结构设计1 .类的声明和定义（规定给出完整的类声明和核心成员函数的定义）3 0 #if n def Joseph_H# d e fin e J o seph_H#include <i o st r eam> 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 ()构造函数。» 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.h"i n c lu d e <windows, h ># i n c 1 u de < i om a n i p >void Ci r cula r Li n kList:： C reate L i(g Nod e *s, *r = 尾指针初始化。 for (int i = 0 ； i < n; i +) / /尾插法008。 s = n e w Node；，s->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 «setw (3)« r >data;维 o u n t +；。 r = r->next;。i f (co u n t % 10 = 0)o »co u t« endl<<"。 whil e (r != first->n ext);/ /当链表循环到第一节点时跳出循环 w®cout « 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 < k-l;i+)0000p re = prc->next;gp pre->ne x t;"0 Ioint count = 1;/计数器初始化，约瑟夫问题至少有两个成员00 COU t « * * * * * * * 丈 火* 大* * * *»w h i Ie (pr e != p)00 。 -if (cou nt = m)/假如计数器等于密码皿。 Sleep(l * 1000)，执行挂起一段时间(1秒)。cout <<setw(26)« p ->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 ;工作指针后移3g 叩=p-> next;8g c o u nt+;/ 计数器加一0 o J»cout «* * * * * * * * * * 大* n "；， cou t « s etw( 2 6)<< p>da t a vv "号存活！" << endl； / / 显示最后存活 的delet e p; / /删除结点p« system( " p aus e ")；)五、程序测试与实现1 .程序在调试过程中出现的问题及解决办法.程序运营过程及结果界面血 C:Windowssystem32cmd.exe X约瑟夫环游戏一请输入参与人数：6国 C:Windowssystem32cmd.exe X约瑟夫环游戏>>请输入参与人数：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号存活!请按任意键继续. 搜狗拼音输入法全： 七、问题及解决方法问题：无法从第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磅
