1、中南大学级数据结构与算法实验指导书数据结构与算法实验指导书郁松软件学院第一部分：数据结构实验步骤和实验报告规范一、数据结构实验步骤随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如实际中真正的软件系统，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的5个步骤：1、问题分析和任务定义通常，实验题目的陈述比较简洁，或者说有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限
2、制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。2、数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。详细设计则为定
3、义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出过程或函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。3、编码实现和静态检查编码是把详细设计的
4、结果进一步求精为程序设计语言程序。如何编写程序才能较快地完成调试是特别要注意的问题。程序的每行不要超过60个字符。每个过程（函数）体一般不要超过40行，最长不得超过60行，否则应该分割成较小的过程（函数）。要控制if语句连续嵌套的深度，分支过多时应考虑使用switch语句。对函数功能和重要变量进行注释。一定要按格式书写程序，分清每条语句的层次，对齐括号，这样便于发现语法错误。在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是
5、极为有害的。对一般的程序设计者而言，当编写的程序长度超过50行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先检查单个模块）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。4上机准备和上机调试上机准备包括以下几个方面： 熟悉C、C+、Java等语言用户手册或程序设计指导书。 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”
6、。学生应该熟练运用高级语言的程序调试器DEBUG调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思冥想”，而应借助系统提供的调试工具确定错误。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。5、总结和整理实验报告二、数据结构实验报告规范实习报告的开头应给出题目、班级、姓名、学号和完成
7、日期，并包括以下7个内容：1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：输入的形式和输入值的范围；(输出的形式；(程序所能达到的功能；(测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。4调试分析内容包括：调试过程中遇
8、到的问题是如何解决的以及对设计与实现的回顾讨论和分析；算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。5用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。6测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。7附录带注释的源程序代码。值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写。另附：实验报告封面中南大学数据结构与算法课程实验实验报告题 目 学生姓名 学生学号 专业班级 第三部分：数据结构实验内容实验一 线性表的操作一、实验目的
9、1、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。2、熟练运用掌握的线性表的操作，实现一元n次多项式的加法运算二、实验内容顺序存储的线性表有一些弱点，其一，插入与删除元素需要大量移动元素；其二，预先分配存储空间时必须按最大的空间来分配。其三，表长难以扩充。链式存储结构的特点是用一组任意的存储单元存储线性链表的数据元素，与顺序表的区别在于链式存储的存储单元可以是连续的，也可以是不连续的。为了实现这种结构，链表采取由两部分信息组成数据元素ai的存储映像，称为结点。结点包括两个域，其中存储数据信息的域称为数据域，存储直接后继信息的称为指针域。指针域
10、中存储的信息叫做指针或链。这样，n个结点链接成一个链表，即为线性表（a1,a2,a3,an）。符号多项式的操作，已经成为表处理的典型用例，在数学上，一个一元多项式pn(x)可以按升幂写成：pn(x)=p0+p1x+p2（x的2次幂）+pn（x的n次幂），也可以按照降幂来排列。它由n+1个系数唯一确定。因此，在计算机里，它可用一个线性表P来表示：P=(p0,p1,p2,pn),显然，在通常的应用中，多项式的次数变化很高且很大，此种表示将造成内存的很大浪费。所以在实际应用中通常只记录多项式的系数非零的项，也就是系数非零项的次数和对应的非零系数。本次实验主要完成以下的内容： 线性表基本操作的实现，分
11、别采用数组和链表结构实现线性表，实现线性表的基本操作。 利用实现的线性表，存储一元n次多项式，完成多项式的输入、显示；实现多项式的加法操作 可选内容：设计实现一个处理100位以内的长整数加减运算的程序。三、实验要求1、参考书上算法，编出程序。2、上机运行本程序。3、保存和打印出程序的运行结果，并结合程序进行分析。4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。实验二 栈的基本操作一、实验目的熟练掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。理解栈在数据处理中扮演的角色，运用栈结构实现具体的应用。二、实验内容栈是数据结构中一个非常重要的结构。表达式计算是掌
12、握程序设计语言的重要部分之一，也是栈的应用的一个典型例子。本次实验的主要内容是利用栈的基本操作，设计一个程序，实现用算符优先法对算术表达式求值的过程。对本设计系统实现+、-、*、/、%和乘方（）运算。符合要求，同时提高自己的编程能力。实现算术表达式求值。选作内容：提供对小数点的支持，允许输入的表达式中出现多位数字和小数点。三、实验要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3在程序的编写中尽量与专业的编程规范靠拢，系统代码采用结构化的编程方式，力求设计代码以及注释等规范，4保存和打印出程序的运行结果，并结合程序进行分析。实验三 二叉树的基本操作一、实验目的1、掌握用指针类型描述、访问
13、和处理二叉树的运算；2、掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；3、熟练掌握递归程序设计方法、以及栈的应用二、实验内容以二叉链表作存储结构，编写程序，实现如下的功能：1、根据输入的数据建立一个二叉树；2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和最小值。4、（选作内容）试编写按层次顺序遍历二叉树的算法。参考算法思想：要采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到
14、队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉树的目的。三、 实验要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3在程序的编写中尽量与专业的编程规范靠拢，系统代码采用结构化的编程方式，力求设计代码以及注释等规范，4保存和打印出程序的运行结果，并结合程序进行分析。实验四 Huffman编码一、实验目的1、理解哈夫曼树及其应用。2、掌握生成哈夫曼树的算法。二、实验内容设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：1、根据所提供的字母数据建立一个Huffman树；2、根据生成的Huffman树的结构，显示输出多由字母的Huf
15、fman编码。3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。三、 实验要求1认真阅读和掌握本实验的算法。2上机将本算法实现。3在程序的编写中尽量与专业的编程规范靠拢，系统代码采用结构化的编程方式，力求设计代码以及注释等规范，4保存和打印出程序的运行结果，并结合程序进行分析。字母频度表实验五、 快速排序一、实验目的：掌握快速排序的算法。二、实验内容：排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法，是计算机工作者的一项重要工作课题。冒泡排序想来大家都很熟悉，它是一
16、种想法很自然的排序方法。快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两个部分。其中，一部分记录的关键字均比另一部分小，则可分别对两个部分的记录进行排序，以达到整个序列的有序。假设待排的序列为RS, RS+1, RS+2,， RT,首先任意选取一个记录，RS作为枢轴，然后重新排列其它记录。将所有关键字比它小的记录都放在它的前面，其它所有关键字比它大的记录放在它的后面。由此可以将记录以“枢轴”为界，将记录分为两个子序列，这个过程称为一趟快速排序。以后再分别对两个子序列进行快速排序，重复进行这个过程，直到整个序列全部有序为止。快速排序的平均时间为 Tavg(n)
17、=kn ln n，其中n为待排记录的个数。K为某个常数，经验证明在所有的同数量级的先进排序方法之中，快排的k最小。因此，就平均时间而言，快排是被认为最好的内部排序方法。三、实验要求：1、 读懂理解数据结构教材中的冒泡排序的算法。2、 基于冒泡排序，读懂理解快速排序的算法。3、 编写冒泡排序、快速排序的程序，上机调试。进行排序分析。构造多组数据，将编写的排序算法用多组数据进行测试，记录排序使用的时间：a) 针对所实现的每种排序方法，产生多组随机数据进行多次排序试验，统计每次试验的性能，记录并计算每个算法的平均时间。b) 针对所实现的每种排序方法，产生特殊数据进行排序试验，统计每次试验的性能，记录并计算每个算法的最好时间、最坏时间。c) 针对各种排序方法，对同一组数据进行排序试验，统计每次试验的性能，记录并对比每种排序算法的执行时间。
