北邮数据结构实验一约瑟夫问题.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一 线性表学生姓名：班 级： 班内序号： 学 号： 日 期： 2012年11月7日1 实验要求实验目的 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力题目4利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。2. 程序分析2.1 存储结构存储结构：循环链表由于头指针储存了元素，因此不需要尾指针2.2 关键算法分析1、约瑟夫问题的基本思想：构造循环链表，从头结点开始从1编号，根据给定的总人数形成具有n个结点的循环链表，用户输入出列人的序号m，然后从头结点开始遍历，遍历第m个结点删除当前结点，然后判断是否只剩一个结点，如果符合，则打印该结点对应序号，如果不符合，继续循环遍历，直到链表里只剩一个结点，打印序号，程序结束。2、删除结点算法：伪代码：void Deletenode(Person* p,int &p_num)if (链表为空) throw ERORR,NULL LIST! ;else if (链表只有一个结点) throw 链表只有一个结点;elseq记录p指向的下一个节点地址；删除p后一结点;p的num更改为下一个结点数据q-num;delete q;void Deletenode(Person* p,int &p_num)if (p=NULL) throw ERORR,NULL LIST! ;else if (p-next=NULL) throw 链表只有一个结点;elsePerson *q=p-next; p-next=p-next-next;/ 删除后一结点p_num=q-num;/ 数据更改delete q; 图1 删除结点示意图算法步骤：1. 由主函数传递来的指针p指向该结点；2. 设q指向下一元素：q = p-next;3. 摘链，即将q元素从链表中摘除：p-next = q-next;4. 数据更改p_num=q-num;5. 释放q元素：delete q;空间复杂度为O（1）3. 判断异常情况的算法：bool available(long int &m,long int & n)如果m，n输入异常，可以提示再输入，套两个循环分别判断m和n的情况while(1)cout请输入总人数n(大于)endl;判断n ,如果不满足直接进入下一次循环满足情况继续进行while(1)cout1）endl;判断m情况不符合，再次输入符合，退出循环3. 程序运行结果1、测试主函数流程：流程图如图2所示图2 流程图示意图2、测试条件：由于变量m，n都为long int型，最大大概能测试10的6次方的数字；3、测试结论若输入异常：测试结论：顺利完成计算，实验结果令人满意4. 总结1、 调试时出现的问题及解决的方法：测试时发现输出数据总是与实际不一致，调试时发现循环次数少一次，逐步调试发现for (int i=1;i=m;i+)语句会使 p指向 m下一次的结点，改for (int i=1;im;i+)之后程序就正常进行了2、 心得体会：以后程序编完后一定要多多调试，单步调试有助于找出出错的语句，这就要求每个语句都要单独成行，便于找出错误；有一些隐性的错误不易发现，比如剩下最后一个结点，一开始的时候忘记delete释放空间，后来在整体规划的时候发现系统释放空间有问题；开始时没有加入available函数，程序健壮性不好，无法处理异常情况，加入之