《北邮数据结构实验一题目4》由会员分享，可在线阅读，更多相关《北邮数据结构实验一题目4（6页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学电信工程学院第 1 页2008 级数据结构实验报告实验名称： 实验一 线性表学生姓名： 班 级： 2008211113班内序号： 学 号： 日 期： 2009 年 10 月 25 日1实验要求a. 实验目的实验目的通过选择任一题目进行实现，掌握如下内容：熟悉 C+语言的基本编程方法，掌握集成编译环境的调试方法学习指针、模板类、异常处理的使用掌握线性表的操作的实现方法学习使用线性表解决实际问题的能力b. 实验内容实验内容利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知 n 个人（n=1）围坐一圆桌周围，从 1 开始顺序编号。从序号为 1 的人开始报数，顺时针数到 m 的那个人出
2、列；他的下一个人又从 1 开始报数，数到m 的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。北京邮电大学电信工程学院第 2 页2. 程序分析2.1 存储结构存储结构:单链循环链表 示意图如下:n1n2n3n4 n firstrear北京邮电大学电信工程学院第 3 页2.2 关键算法分析关键算法思想描述和伪代码描述：关键算法关键算法 1 1：将轮流次数为特殊数字 1 时单独考虑，解决不带头结点的链表带来的循环人数为 1 和大于 1 时操作不一致的问题。伪代码：1.判断循环人数是否为 1。2.如果是则直接输出从 1n 的出列顺序，结束程序。3.如果不是则继续后面的
3、代码。C+实现：if(m = 1) coutnext;temp = first-next;first-next = temp-next;delete temp;时间复杂度与空间复杂度：时间复杂度与空间复杂度： 算法一时间复杂度与空间复杂度均为O(1)。 算法二在程序中被执行了n次，故总的时间复杂度为O(n*m);空间从占用n个节点的内存逐步 释放为空，故空间复杂度为O(n/2)。2.3 其他程序中在处理指针是应该十分小心，避免出现指针悬挂和内存泄漏。北京邮电大学电信工程学院第 5 页3. 程序运行结果开始查找并删除第 m 个元素输出：出列顺 序 1 到 n结 束输入 n,mn1 或 m1？否是
4、m=1？是输出第 m 个元素否建立循环链表输出最后一个元 素北京邮电大学电信工程学院第 6 页测试条件：n 的数量级控制在 10000 内，当 m=n=10000 时，程序耗费的时间大约为 7 秒。但是当不依次输出出列顺序时，当 m=n=10000 时，程序耗费的时间小于 1 秒！可见输 出出列顺序大大增加了时间复杂度。测试结论：本程序可得出约瑟夫问题的正确答案，运算速度较快。4. 总结1、调试时出现过程序崩溃的问题，主要原因为指针引删除错误。开始时没有考虑到最后一 个人需要单独考虑，因为如果不单独考虑，则会使得 first 和 temp 两个指针指向同一快堆 内存，导致指针悬挂。解决方法很简
5、单，将循环删除次数减少为 n-1 次，最后一个数据先 不用 temp 指针，直接用 first 将其删除即可。2、初始时没有将 m=1 情况单独考虑，由于不带空头结点，无法查找 1 个结点的前一个结 点，因而当 m=1 时出错。后把 m=1 直接单独处理，避免没有头结点的情况下无法将删除 头结点于其他节点相同处理的情况，也避免了建立了链表之后单独处理 m=1 时析构每个节 点的操作。3、心得体会，编程解决约瑟夫问题需要对链表的构造、有无头结点的操作十分熟悉，对删 除节点时要更加细心。在写程序的过程中，应该时刻注意程序完备性，对堆内存操作时避 免内存泄漏和指针悬挂。在写算法时，选择合适的存储结构十分重要，甚至可以事半功倍。3、改进：本函数主要时 c 语言的风格，主要考虑到本程序算法简单，没有必要建立类实现， 用 c 语言的结构化风格效率更高，但是扩展性变差，可以考虑使用类进行封装，提高扩展 性。
