实验一-约瑟夫环问题.docx

数据结构实验报告实验名称:实验一线性表学生姓名: 班级: 班内序号: 学号: 日期: 1 .实验要求一. 实验目的通过选择下面四个题目之一进行实现,掌握如下内容: ?熟悉 C++ 语言的基本编程方法,掌握集成编译环境的调试方法?学习指针、模板类、异常处理的使用?掌握线性表的操作的实现方法?学习使用线性表解决实际问题的能力二. 实验内容题目 4 利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下: 已知 n 个人( n>=1 ) 围坐一圆桌周围,从1 开始顺序编号。从序号为 1 的人开始报数, 顺时针数到 m 的那个人出列; 他的下一个人又从 1 开始报数, 数到 m 的那个人又出列;依此规则重复下去,直到所有人全部出列。请问最后一个出列的人的编号。 2. 程序分析 存储结构单循环链表。线性表简称表,是由零个或多个具有相同类型的数据元素构成的有限序列。链表用一组任意的存储单元存放线性表的各个元素。为了正确表示结点间的逻辑关系, 在存储每个元素值的同时, 还需要存储该元素的直接后继的位置信息,这个信息称为指针或链, 这两部分构成了实际的存储结构, 称为结点。如果单链表终端结点的指针域指向头结点,则整个链表构成一个环,将这种首尾相接的单链表称为单循环链表。示意图: 关键算法分析 1. 关键算法: a 1a 2a n rear ……约瑟夫问题的实质就是在含 n 个元素的循环链表中依次删除第 m 个元素,返回链表中最后一个元素值。即用含 n 个元素的数组初始化循环链表,从第一个元素开始查找第 m-1 个元素, 删除第 m 个元素, 然后从第 m+1 个元素开始继续查找第 m-1 个元素, 删除第 m 个元素,循环此过程直到链表中只剩下最后一个元素。 2. 代码详细分析: [1] rear= new Node; rear->next=rear; for ( int i=0;i<n;i++) { Node *s= new Node; s->data = a[i]; s->next = rear->next; rear->next = s; rear = s; } 采用尾插法用含 n 个元素的数组初始化循环链表 Node *p= rear->next; rear->next = p->next; 初始化指针 p 指向第一个结点; [2] 判断人数 n 或报数 m 是否为 1; [] 人数 n 或报数 m为1 ,将人数 n 赋给 x; [] 当人数不为 1 时,进入循环; [] 初始化计数器 i=1 ; [] 查找第 m-1 个元素, p 指向第 m-1 个元素; [] Node *q= p->next; 初始化指针 q 指向 p->next p->next = q->next; p 的指针域指向 q 的指针域 delete q第m 个元素摘链,删除 q p= p->next 指针 p 后移[] 人数 n减1; [] 尾指针 rear 指向最后的结点 p ,将此结点值赋给 x; [3] 返回 x 的值。 3 .时间复杂度的计算[1] O(n) [2] O(1) [] O(1) [] O(n) [] O(n*m) [] O(n*m) [] O(n) [