数据结构实验指导书.doc

数据结构实验指导书上海交通大学电院数据结构课程组目录1. 关于实习步骤的要求和建议2. 上机实习实习一 链表实习二 栈和队列实习三 树和二叉树实习四 查找实习五 图实习六 排序3. 注意事项1 关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范不但可以培养科学化的工作作风，而且还能有效地避免错误。具体的步骤机规范如下：1 问题分析与系统的结构设计： 充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。2 详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF 、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码是，可以对详细设计的结果进一步求精，用高级语言表示出来。程序的每一行最好不超过 60 个字符。每个子程序（或过程、函数）通常不要太长，以 40 行为宜。子程序（或过程、函数）包含的程序行数太多，易于造成理解的困难。控制 IF 、WHILE 等语句的连续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外（如：x = x + 1; 注释为 x 加 1，没有什么意义），都应加以注释。这会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。另外，对于输入输出语句，必须对它们的作用加以说明。否则，在调试程序时，无法了解系统需要输入说明，系统输出的又是什么。程序的书写，必须按照一定的规范，如保留字小写时涂黑，或者大写等等。具体的要求可参看软件工程中的有关规定。3 上机准备和静态检查上机准备：l 高级语言文本l 熟悉机器的用户手册，熟悉常用的命令。l 准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可供利用，可以自己先设计一些以供使用。l 静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序的逻辑。4 上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确后将源程序和运行结果加以列印输出。5 实习报告的整理l 需求及规格说明问题描述，求解的问题是什么。l 设计：设计思想：存储结构、主要的算法思想。设计表示：子程序（过程或函数）的规格说明，通过调用关系图表 示它们之间的调用关系。实现注释：详细设计表示：主要算法的框架。l 用户手册：使用说明。l 调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等。l 附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡用英文描述。l 实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实验报告纸上，或以电子文档的形式进行书写。2 上机实习 以下的实习题目配合课程的进度，请同学们自己务必完成。为了锻炼自己的应用各种不同的数据结构的能力，尽可能的多作一些题目是非常必要的。在完成各种不同题目的过程中，对各种算法的时、空复杂性的分析，将帮助您在更高的角度解决各种应用问题。实习一 链表1、设有一个双链表， 每个结点中除有 PRIOR，NEXT 及 DATA(可设为 正整数) 三个域之外，还有一个专门记录访问该结点次数的数据域 FREQ ，其值在初始化时为零。每当在链表中进行一次 SEACHL，KEY 时，则数据域 DATA 之值等于 KEY 的结点，其 FREQ 域之值将加一。并使该双链表中结点按 FREQ 之值的递减顺序排列，FREQ 值越大的结点越靠近散双链表的头结点。 请编写符合上述要求的 SEACH(L，KEY) 程序。2、请写出计算两个以 单链接表表示的多项式相乘的程序。3、在计算 机 上先输入一串正整数的序列。请编写一个程序，首先用链接表 存储该序列。然后执行删除操作，即先从链表中找出最小的结点，删除它 。然后再在剩余的链表中，找出最小的结点，再删除之。直至表空为止。4、已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列。请编写程序求集合 A 和 B 的交集 C = AB，要求单链表C按其元素递增排列，并利用原表（即表A和表B）的结点空间存放表C。5、将具有头结点的单链表的所有指针全部进行导向。要求使用的额外空间只 O(1),时间代价只能为O(n)，其中 n 为结点个数。 6、假设有两个按元素值非递减有序排列的线性表A和B，均以单链表作存储结 构，请编写程序将表A和表B归并成一个按元素非递减有序（允许值相同） 排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。实习二 栈和队列1 假设以带头结点的循环链接表表示队列，并且只设一个指向队尾结点的指 针，请给出进出队的完整的程序。2、假设有 N 个栈共同使用一块顺序存储的空间，为简单起见可设为共同使用 数组 int a200。初始状态为各栈等分备用空间。每当有某栈上溢时， 按下述方法调整各栈的备用空间；将全部备用空间的 X 均分给各栈，其 余 （100 - X）% 按上一次调整以来各栈的增长的比例分配给各栈，请给 出这 N 个栈的出、入栈算法。3、参见教科书第 130 页习题43。请问：a. 如进栈的车厢的序列为 1、2、3、4, 则出栈的序列有那些种？b. 给出当进栈的车厢的序列为 1、2、3、4、N 时，所有出栈的序列的程序。4、 假设有 二 个栈共同使用一块顺序存储的空间，为简单起见可设为共同使 用数组 int a200。它们的栈底分别设在数组的两端，而栈顶指针在进 行插 入操作时，向中间方向移动。请给出进出栈的程序。5、在一次舞会上，来了许多男士和女士。这些男士和女士分别排队进入舞 厅。第一个舞曲开始后，男士和女士按照队列顺序配对并走入舞池。当男 士多于女士时，配对剩余的男士仍然在队列中。一曲终了，跳完舞的男士排 在队尾，女士排成新的队列。下一舞曲开始时，男女重新按照队列顺序配对 跳舞。当女士多于男士时，配对剩余的女士仍然在队列中，等待下一曲配 对。现在要求按照队列中的先后顺序打印出第一轮配好对的人员名单和剩余 人员的名单。实习三 树和二叉树1。在计算机上首先输入前序及中序周游一棵二叉树的结果，为简单起见可以假 定该二叉树的结点的数据场之值仅为一大写英文字母。请给出该二叉树的后序周游结果，并以二叉链接形式存储该二叉树。2、两棵二叉树称作相似的，它们要么全为空。要么不是空树但它们的左子树相似且右子树相似。请设计一个程序判断两棵二叉树是否相似。3请编写一个程序，确定二叉树的特征。如：每个节点的层次，从根到该节点的枝长（路径长度），子孙的个数及祖先的个数。每个节点在前序、中序、后序中的访问的序号。4、用标准形式给出了一棵度为三的树（每个结点包含数据场、指向儿子节点 的指针场），设该三次树的数据场的值为一个字符，请编写一个程序，以树的两维形式表示打印节点的值。 5、如果在二叉树的定义中允许出现具有相同关键字的结点。试编写以动态 存储结构存储的排序二叉树的插入及删除程序。6、从键盘上输入若干个数对，如：( I1，W1)，( I2，W2)，( Im， Wm)；其中I1，I2， Im 是本结点的层号。注意：根结点的层号为1， 其他各层上的结点的层号依次比上一层的结点的层号大 1。另外：W1， W2，Wm 是结点的前序(即先根次序)序列。这是用层号前序表示树 的一种方法。请编写一段程序，存储这棵树。为了简单起见，设这棵树上 的结点的度数最大为3，结点的存储形式为： data parentson1 son2 son3其中：data 域为结点的数据场，parent 域为结点的双亲结点的地址，son1，son2，son3分别给出结点的三个儿子的地址。实习四 查找1、 已知整数数组 int an+1。其中，a1，a2， an-2，an1 已被整理为最小化堆，a0 不用。在将a1，a2， an-1，an 整理成最小堆时，可分两步进行：1、先找出an 之值的插入位置； 2、再进行适当的位置移动即可。现仅仅考虑第一步，找出an之值的插入位置。请设计一个程序加以完成。注意该程序的时间复杂性必须为O(log2log2n)，并加以证明。2、 已知一以数组形式存储的有序表。 请用 FIBONACCI 查找法， 编制查找具有给定关键字KEY 的结点的程序。3、 从键盘上输 入一串正整数， 最后输入1作为输入结束的标志。如输入的序列为：2，5，7，23，48，96，-1。请以这些正整数的值作为二叉排序树中的结点的数据场之值，建立一棵二叉排序树。然后，给定一个正整数值，设其为key，在该二叉排序树中查找关键字为key 的结点。若存在，将将该关键字更新为 x，并仍应保持该二叉排序树的性质不变。注意：不能采用数组保存这棵二叉排序树，因为事先并未已知二叉排序树中的结点的个数。4、 已知一棵排序二叉树，树中结点的形式为： data info left right其中，data 给出结点的数据场，info 给出本结点的左子树中的结点总数，left和 right 分别给出本结点的左儿子和右儿子的地址。数据场data 和info的类型皆为 int。又已知该二叉排序树的根结点的地址为 root。请设计二个函数，分别实现下述功能：1 按递增序找出该二叉排序树中的第 i 个结点。2 插入数据场之值为 x 的结点，并仍应保持该二叉排序树的性质不变。5、 已知一棵二叉排序树，其根结点的地址为 root。请编写一个程序，构造出一棵具有相同结点的满二叉树，且它同样是二叉排序树。提示：可利用中序遍历，分别找出各个结点序列的中点元素，然后重新构造一棵二叉排序树。6、给定一个正整数的序列 Aa1, a2 a3, , an, 首先构造一个单链接表。然后，输入一个待查正整数的序列 B = b1, b2, b3, , b3n, 而且bk A，1kn。由于 B 的个数多于A，所以在查找时必定有重复的正整数出现。请设计一个程序，在找到一个正整数之后，将相应的结点向单链表的表首结点移动一个。7、(选做) 在平衡的排序二叉树的中，试编写删除具有给定关键字的结点的程序。 实习五 图1 以 数 偶 的 形 式 输 入 一 串 数 据。 如：( A，B ) 为 从 起 始 结 点， 其 数 据 场 之 值 为 一 大 写 的 英 文 字 母A， 到 终 止 结 点，其 数 据 场 之 值 为 一 大 写 的 英 文 字 母 B 的 无 向 边。 请 用 无 向 图 的邻 接 多 重 表 存 储 该 无 向 图， 并 注 意 一 定 要 使 用 动 态 存 储 结 构。 如 果 该 数 偶 代 表 有 向 边 的 话，请 用 有 向 图 的 十 字 链 表 存 储 该 有 向 图， 并 注 意 也 要 使 用 动 态 存 储 结 构。2 已 知 一 以 动 态 存 储 结 构 形 式 存 储 的， 以 邻 接 表 表 示 的 有 向 图。 请 求 出 它 的 强 连 通 分 量。3 已 知 一 以 动 态 存 储 结 构 形 式 存 储 的， 以 邻 接 多 重 表 表 示 的 无 向 图。 请 用 KRUSKAL 算 法 求 出 它 的 最 小 代 价 生 成 树。4 已 知 一 以 邻 接 矩 阵 形 式 存 储 的 AOV 图。 请 求 出 它 的 所 有 的 合 理 的 拓 扑 排 序 的 序 列。5 已 知 一 以 动 态 存 储 结 构 形 式 存 储 的， 以 邻 接 多 重 表 表 示 的 无 向 图。 请 编 写 一 个 统 一 的 程 序， 用 以 求 解 最 小 代 价 生 成 树 问 题 及 源 点 至 其 它 顶 点 间 的 最 短 距 离 问 题。可 由 使 用 者 指 明 究 竟 求 解 哪 个 问 题。6 已 知 一 以 动 态 存 储 结 构 形 式 存 储 的， 以 邻 接 表 表 示 的 有 向 图。 请 使 用 非 递 归 的 方 法 编 写 该 有 向 图 的 深 度 及 广 度 优 先 的 遍 历 程 序。 实习六 排序1、编 写 一 个 程 序， 查 找 未排序 序 列 中 第 K 个 最 小 的 元 素， 要 求 使 用 类 似 快 速 分 类 的 算 法。 并 简 单 讨 论 一 下 在 最 坏 情 况 下， 所 耗 费 的 时 间。2、如 果 有17000 个 不 同 的 正 整 数 组 成 的 序 列， 每 个 正 整 数 都 在 0 至19999 之 间。 请 使 用 适 当 的 散 列 函 数， 使 得 将 该 序 列 进 行 分 类 的 时 间 复 杂 性 为 O（N） 级。 注 意 此 处 并 不 限 制 辅 助 内 存 的 多 少。3、写 一 个 利 用 合 并 分 类 法 进 行