北邮数据结构实验一题目

1、2008级数据结构实验报告实验名称： 实验一 线性表学生姓名： 班 级： 2008211113班内序号： 学 号： 日 期： 2009年10月25日1 实验要求a. 实验目的通过选择任一题目进行实现，掌握如下内容：Ø 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法Ø 学习指针、模板类、异常处理的使用Ø 掌握线性表的操作的实现方法Ø 学习使用线性表解决实际问题的能力b. 实验内容利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个

2、人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。2. 程序分析2.1 存储结构 存储结构:单链循环链表 first示意图如下:n1n3n2 rear····· n n42.2 关键算法分析关键算法思想描述和伪代码描述：关键算法1：将轮流次数为特殊数字1时单独考虑，解决不带头结点的链表带来的循环人数为1和大于1时操作不一致的问题。伪代码：1. 判断循环人数是否为1。2. 如果是则直接输出从1n的出列顺序，结束程序。3. 如果不是则继续后面的代码。C+实现：if(m = 1) cout<

3、;<"最后出列的是： "<<n<<endl;return;关键算法2：删除每次循环的第m号数据。实现时用头指针移动，查找第m-1个数据，然后删除第m个数据，头指针后移。伪代码：1. 借助first指针，first指针后移，移动m-1次。2. 建立临时指针变量指向m个数据。3. first指针指向m+1个数据。4. delete第m个数据。C+实现：for (int j = 1 ; j < m-1 ; j+) first = first->next;temp = first->next;first->next = temp

4、->next;delete temp;时间复杂度与空间复杂度：算法一时间复杂度与空间复杂度均为O(1)。算法二在程序中被执行了n次，故总的时间复杂度为O(n*m);空间从占用n个节点的内存逐步释放为空，故空间复杂度为O(n/2)。2.3 其他程序中在处理指针是应该十分小心，避免出现指针悬挂和内存泄漏。开始3. 程序运行结果输入n,m是n<1或m<1？否是m=1？否输出：出列顺序1到n建立循环链表查找并删除第m个元素输出第m个元素输出最后一个元素结 束测试条件：n的数量级控制在10000内，当m=n=10000时，程序耗费的时间大约为7秒。但是当不依次输出出列顺序时，当m=n=

5、10000时，程序耗费的时间小于1秒！可见输出出列顺序大大增加了时间复杂度。测试结论：本程序可得出约瑟夫问题的正确答案，运算速度较快。 4. 总结1、调试时出现过程序崩溃的问题，主要原因为指针引删除错误。开始时没有考虑到最后一个人需要单独考虑，因为如果不单独考虑，则会使得first和temp两个指针指向同一快堆内存，导致指针悬挂。解决方法很简单，将循环删除次数减少为n-1次，最后一个数据先不用temp指针，直接用first将其删除即可。2、初始时没有将m=1情况单独考虑，由于不带空头结点，无法查找1个结点的前一个结点，因而当m=1时出错。后把m=1直接单独处理，避免没有头结点的情况下无法将删除头结点于其他节点相同处理的情况，也避免了建立了链表之后单独处理m=1时析构每个节点的操作。3、心得体会，编程解决约瑟夫问题需要对链表的构造、有无头结点的操作十分熟悉，对删除节点时要更加细心。在写程序的过程中，应该时刻注意程序完备性，对堆内存操作时避免内存泄漏和指针悬挂。在写算法时，选择合适的存储结构十分重要，甚至可以