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

《北邮数据结构实验一约瑟夫问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一线性表学生姓名：班级：班内序号：学号：日期：2012年11月7日1．实验要求实验目的Ø熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法Ø学习指针、模板类、异常处理的使用Ø掌握线性表的操作的实现方法Ø学习使用线性表解决实际问题的能力题目4利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。

2、请问最后一个出列的人的编号。2.程序分析2.1存储结构存储结构：循环链表由于头指针储存了元素，因此不需要尾指针2.2关键算法分析1、约瑟夫问题的基本思想：第6页北京邮电大学信息与通信工程学院构造循环链表，从头结点开始从1编号，根据给定的总人数形成具有n个结点的循环链表，用户输入出列人的序号m，然后从头结点开始遍历，遍历第m个结点删除当前结点，然后判断是否只剩一个结点，如果符合，则打印该结点对应序号，如果不符合，继续循环遍历，直到链表里只剩一个结点，打印序号，程序结束。2、删除结点算法：伪代码：voidDeletenode(Person*p,in

3、t&p_num){if(链表为空)throw"ERORR,NULLLIST!";elseif(链表只有一个结点)throw"链表只有一个结点";else{q记录p指向的下一个节点地址；删除p后一结点;p的num更改为下一个结点数据q->num;deleteq;}voidDeletenode(Person*p,int&p_num){if(p==NULL)throw"ERORR,NULLLIST!";elseif(p->next==NULL)throw"链表只有一个结点";else{Person*q=p->next;①p->next=p->next

4、->next;//②删除后一结点p_num=q->num;//③数据更改deleteq;④}图1删除结点示意图算法步骤：第6页北京邮电大学信息与通信工程学院1.由主函数传递来的指针p指向该结点；2.设q指向下一元素：q=p->next;3.摘链，即将q元素从链表中摘除：p->next=q->next;4.数据更改p_num=q->num;5.释放q元素：deleteq;空间复杂度为O（1）3.判断异常情况的算法：boolavailable(longint&m,longint&n)如果m，n输入异常，可以提示再输入，套两个循环分别判断m和n的情况

5、while(1){cout<<"请输入总人数n(大于)"<1）"<

6、验结果令人满意4.总结1、调试时出现的问题及解决的方法：测试时发现输出数据总是与实际不一致，调试时发现循环次数少一次，逐步调试发现for(inti=1;i<=m;i++)语句会使p指向m下一次的结点，改for(inti=1;i

7、健壮性不好，无法处理异常情况，加入之后程序健壮性加强了许多，这个好习惯程序员应该保持。3、下一步的改进：deletenode函数有局限性，可以改进为删除当前地址指向的结点，更有利于函数的应用。第6页