上海交大 数据结构与算法实验指导书

数据结构与算法实习指导书上海交通大学电院数据结构大平台课程组目录1. 关于实习步骤的要求和建议2. 上机实习实习一线性结构实习二树和二叉树实习三查找实习四图3. 实习报告样例1. 关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规 范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的程 序编制风格，培养严谨、科学、高效的工作方式。在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出 一个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自 己。有的学生不屑于按实习步骤规范去做，甚至对于实习步骤的要求和建 议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范不但 可以培养科学化的工作作风，而且还能有效地避免错误。具体的步骤机规范如下：1. 问题分析与系统的结构设计：充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照 以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操 作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考 虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个 子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示则更加清晰，这样便完成了系统结构设计。2. 详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。用 IF、 WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的 是避免陷入细节。在编码时，可以对详细设计的结果进一步求精，用高级语言 表示出来。程序的每一行最好不超过60个字符。每个子程序（或过程、函数）通 常不要太长，以40行为宜。子程序（或过程、函数）包含的程序行数太多， 易于造成理解的困难。控制IF、WHILE等语句的连续嵌套的深度应加以控 制。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外 （如：x = x + 1;注释为x加1，没有什么意义），都应加以注释。这会对程序 的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信 息，用于验证和你的设想是否一致。另外，对于输入输出语句，必须对它们的 作用加以说明。否则，在调试程序时，无法了解系统需要输入什么，系统输出 的又是什么。程序的书写，必须按照一定的规范，如保留字小写时涂黑等等。3. 上机准备和静态检查上机准备：高级语言文本熟悉机器的用户手册，熟悉常用的命令。准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具 可供利用，可以自己先设计一些以供使用。静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以 全面地了解该程序的逻辑。4. 上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联 调。调试正确后将源程序和运行结果加以列印输出。5. 实习报告的整理需求及规格说明问题描述，求解的问题是什么。设计：设计思想：存储结构、主要的算法思想。设计表示：子程序（过程或函数）的规格说明，通过调用关系图表示它们之间的调用关系。实现注释：详细设计表示：主要算法的框架。用户手册：使用说明。调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体 会、时空复杂度等。附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运 行结果数据。提倡用英文描述。 实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实 验报告纸上，或以电子文档的形式进行书写。2. 上机实习以下的实习题目配合课程的进度，请同学们务必自己完成。为了锻 炼自己的应用各种不同的数据结构的能力，尽可能的多作一些题目 是非常必要的。在完成各种不同题目的过程中，对各种算法的时、 空复杂性的分析，将帮助您在更高的角度解决各种应用问题。为了减轻同学的负担，我们对同学的实习报告进行了精简。本实习 报告中的题目分以下几种类型：1、实习题：必须按照实习报告的规范完成。每个实习的第一 题都是实习题，必须编写详细的实习报告。实习报告的书 写方法，请参阅本指导书的第3部分：实习报告的样例。2、作业题：同样必须完成。只需交代清楚题目的解法，辅以 求解程序和注释，使得别人能够看懂你的算法和程序即 可。不必象实习题那样书写完整的实习报告。3、选作题：鼓励同学选作的题目，尤其是学有余力的同学。以下为各次实习作业:实习一线性结构1、（实习题）请写出计算两个以单链接表表示的多项式相乘的程序。2、（作业题）已知两个单链表A和B分别表示两个集合，其元素递增排列。请编写程序求集合A和B的交集C = A B，要求单链表C按其元素递 增排列，并利用原表（即表A和表B）的结点空间存放表C。3、（作业题）假设有二个栈共同使用一块顺序存储的空间，为简单起见可 设为共同使用数组int a200）。它们的栈底分别设在数组的两端，而栈 顶指针在进行插入操作时，向中间方向移动。请给出进出栈的程序。4、（选作题）将具有头结点的单链表的所有指针全部进行倒向。要求使用的 额外空间只能为0（1）,时间代价只能为O（n），其中n为结点个数。注意：如下图1所示的单链表，倒向之后将如图2所示。图1、倒向之前的单链表head图2、倒向之后的单链表实习二树和二叉树1、（实习题）请编写一个程序，确定二叉树的特征。如：每个节点的层次， 从根到该节点的枝长（路径长度），子孙的个数及祖先的个数。每个节点 在前序、中序、后序中的访问的序号。2、（作业题）设二叉树的结点的数据场之值仅为一大写英文字母。其前序和 中序的遍历结果（打印结点的数据场之值）分别保存在字符串数组 preorderN及inorderN之中，其中N未常数。请设计程序以标准形式形 式存储保存该二叉树。3、（作业题）设树的根结点的层号为1，而其他各层上的结点的层号比其父结 点的层号大1。另外设该树中的结点的数据场之值为正整数。这样数对（Ik， Wk）就表示了该树中的结点的层号和其数据场之值。从键盘上依次输入m个数 对，如：（I，W），（ I，W），（I，W）；这些数对是按照结点的前序 序列给出的。注意这是用 层号+前序 表示二棵树的方法。如：（1，A）,(2, B) , (2, C) , (3, E) , (4, G) , (3, F) , (2, D) , (3, X),(3, Y) , (3, Z)；它所表示的树如图3所示。请编写程序，以标准形式存 储这棵树。为了简单起见，可设这棵树上的结点的度数最大为3,结点的存储 形式为：data parent sonl son2 son3其中：data域为结点的数据场，parent域为结点的父亲结点的地址， sonl, son2, son3分别给出结点的三个儿子的地址。图3、一课三次树4、(选作题)用标准形式给出了一棵度为三的树(每个结点包含数据场、指 向儿子节点的指针场，可参阅上题)。设该三次树的数据场的值为一个字 符，请编写一个程序，以树的两维形式表示打印节点的值。注意：图3即为 树的二维表示形式。在实现时，为了方便可用打点的方法代替直线。实习三查找1、(实习题)从键盘上输入一串正整数，最后输入一 1作为输入结束的标 志。如输入的序列为：2, 5, 7, 23, 48, 96，-1。请以这些正整数 的值作为二叉排序树中的结点的数据场之值，建立一棵二叉排序树。注意：请采用动态存储方法保存这棵二叉排序树，事先并未知道该二叉排序 树中的结点的个数。2、(作业题)已知一棵排序二叉树，树中结点的形式为：datainfoleft right其中，data给出结点的数据场，info给出本结点的左子树中的结点总数， left和 right分别给出本结点的左儿子和右儿子的地址。数据场data和info 的类型皆为int。又已知该二叉排序树的根结点的地址为root。请设计二个 函数，分别实现下述功能：1. 按递增序找出该二叉排序树中的第i个小的结点。2. 插入数据场之值为x的结点，并仍应保持该二叉排序树的性质不 变。3、（作业题）已知一棵二叉排序树，其根结点的地址为root。请编写一个程 序，构造出一棵具有相同结点的完全二叉树，且它同样是二叉排序树。4、（选作题）在平衡的排序二叉树的中，试编写删除具有给定关键字的结点 的函数。实习四图1、（实习题）以数偶的形式依次从键盘上输入一串数据。如：（A，B）为从起 始结点（其数据场之值为一大写的英文字母A ），到终止结点（其数据场 之值为一大写的英文字母B）的无向边。最后输入（Z，Z）表示输入结 束。请用无向图的邻接多重表存储该无向图，并注意一定要使用动态存储 结构。2、（作业题）已知一以动态存储结构形式存储的，以邻接多重表表示的无向 图。请用KRUSKAL算法求出它的最小代价生成树。3、（作业题）已知一以邻接矩阵形式存储的AOV图。请求出它的所有的合 理的拓扑排序的序列。4、（选作题）已知一以动态存储结构形式存储的，以邻接表表示 的有向图。请求出它的强连通分量。3、实习报告样例一、实习题：约瑟夫（Josephus）问题：设有n个人围成一个圆圈，任意给定一个正整数m,从第 一个人开始顺时针计数，计到第m个人，将其从圆圈中除去。然后再从下一个人开始，周 而复始，直到圆圈中只剩一个人为止，那么剩下的那个人就是赢家。1.需求分析和说明分析约瑟夫问题：n个人围成圈，从第一个人开始，数到第m个人，删除并以下一个 人开始进行第二轮操作，直到最后一个人作为优胜者。例如n=6, m=3,处理过程下 图。形成线性关系；处理为逐个删除，故用链式结构合适；又人员围成圆2.设计n个人围圈，圈，所以此链式结构采用循环方式较好；排号按照一个方向进行，故数据结构采用带 头结点的单向循环链表。假设人员以首次的编号命名，对每个人员采用编号和姓名加 以描述。存储结构：struct person (int char定义人员信息，包括序号和姓名no;name10;/circlinklist.h单向循环链表类template class CircLinkList (CircLinkListNode *head, *tail;/指向表头结头和尾结点CircLinkListNode *currPtr; /指向当前工作结点CircLinkListNode *prevPtr；/指向当前工作结点的前一结点int size;/表中元素的个数int position;/表中当前元素所在的元素序号(位置)public:CircLinkList ()； CircLinkList ()；void Clear ()；/析构函数链表置空构造函数int Length ( ) const return size;；bool IsEmpty ( ) const return (size=0);；bool IsEnd ( ) const return (currPtr=tail);；int CurrentPosition() const return position;ElemType Data ( ) const;void GoNext ();void Reset(int pos)；/求链表长度/判断链表是否空当前结点是否是尾结点/返回当前结点的序号/返回当前指针所指的结点中的元素值/将当前指针指向当前结点后面的一个结点/将当前指针指向序号为pos的结点CircLinkListNode *Find ( ElemType e );查找从当前结点起第一个元素值为e的结点/各种位置上的插入操作void InsertFront (const ElemType e )；/在首结点位置上插入元素值为e的新结点void InsertTail (const ElemType e )；/在尾结点之后插入元素值为e的新结点，使其成为新的尾结点void InsertAt (const ElemType e )；/在当前结点位置上插入元素值为e的新结点，原来的当前结点成为其后一个结点void InsertAfter (const ElemType e )；/在当前结点之后插入元素值为e的新结点ElemType RemoveFront();删除首结点，并返回其元素值ElemType RemoveAt();删除当前结点，并返回其元素值;算法思想：声明一个person类型的单向循环链表。从键盘顺序输入n个人的姓名，建立约瑟夫环。计 数并逐个读取并删除第m个人，直到链表为空，其中最后一个被读出的即优胜者。调用关系：程序任务简单，故设计在一个main()函数内，只设计类成员函数的调用，无另外的子 程序或函数。算法实现框架：3. 用户手册：运行程序，按照屏幕提示分别输入圈内人数n，正整数m和n个人的姓名，之后屏幕 将显示按照输入次序排好的人员被逐个删除的次序，最后显示最后的出优胜者。4. 调试报告：时间复杂度分析：该算法在建立时的时间复杂度为O(n)，删除时时间耗费在逐个数元素上，按照第m 个删除的原则，不妨将n个元素分成若干组，每组m个人，n个人最多分n/m+1组。 扩展最后一组，使其也是m个人，对组内元素从1到m排号，每组排号为m的只数到一次 便被删除；第二圈数每组排号为1的被删除，每个元素数过2次；第三圈数每组排 号为2的被删除，每个元素数过3次；最后，第m圈，每组排号为m-1的被删除，每个 元素数过m次；故总删除总的时间为：(n/m+1)(1+2+3+. +m)=m(m+1)(n/m+1)/2， 时间复杂度为：O (n*m)；缩小最后一组，使其是0个人，同上可得删除总的时间 为：(n/m)(1+2+3+.+m)=m(m+1)(n/m)/2，时间复杂度也为：O (n*m)；综合建立和删除，算法时间复杂度为：O (n*m)算法改进思路：在对元素数数删除过程中，总是要去判断是否是头结点并绕过它，可以改进一 下，去掉头结点，由此看来，并非链式结构带有头结点都有益处。改进后性能可 以提高，但时间复杂度依然为：O (n*m)5. 附录源程序清单/josephusRing.cpp#include #include circlinklist.hstruct person (定义人员信息，包括序号和姓名intno;char name10;；void main() (CircLinkList josephusRing;声称一个单向循环链表类对象person temp;int i;int n, m; /共有n个人，计数到m删除从键盘输入总人数ncoutn;coutendl;从键盘输入计数标准mcoutm;coutendl;顺序输入n个人的姓名，建立约瑟夫环coutInput every persons name:endl;for (i=1; itemp.name;输入姓名temp.no=i;/将输入次序作为人员编号 josephusRing.InsertTail(temp); /将新来人员信息加入到链表尾部计数并逐个删除第m个人，直到链表为空josephusRing.Reset(1); 当前结点设置为首结点i=0;coutDeleted order: endl;while (!josephusRing.IsEmpty() ( 以链表为空作为结束条件josephusRing.GoNext(); /将当前结点设置为当前结点的下一个结点if (josephusRing.CurrentPosition()!=0) i+;如果当前结点不是头结点，计数值加1,否则跳过头结点，计数值不变if (i=m) ( /如果计数到m，要删除当前结点temp=josephusRing.RemoveAt();删除当前结点，当前结点顺其next指针变为下一个结点couttemp.no temp.nameendl; 将删除的结点中的值在屏幕输出如果当前结点非头结点，已经进入下一轮计数，计数器值设置为1 如果当前结点为头结点，还未进入下一轮计数，计数器值设置为0 if (josephusRing.CurrentPosition()!=0)i=1;else i=0;、coutThe winner is: temp.nameendl; 返回优胜者姓名测试数据：_6个人，非别为Ann、Bill、Cherry、David、Elan、Fred，每次删除第3个人，预计运行结 果为：逐次删除Cherry、Fred、David、Bill、Elan、Ann，赢者为：Ann测试及运行结果：Input the number of people: 6Input every persons name: 3Input every persons name:AnnBillCherryDavidElanFredDeleted order:3 Cherry6 Fred4 David2 Bill5 Elan1 AnnThe winner is: Ann运行结果分析：运行结果符合预定目标