数据结构与算法设计实验指导书

1、数据结构与算法设计实验指导书西华大学计算机与软件工程学院计算机系2019.2数据结构与算法设计是计算机类相关专业的一门核心基础课程，也是 计算机程序设计的重要理论技术基础，更是考研专业课之一。主要介绍线性结构、 树结构、图结构、集合四种基本逻辑结构及存储实现，在此基础上介绍一些典型 的算法设计技术和时间效率分析。课程的主要任务是培养学生的算法设计能力及 良好的程序设计习惯。通过学习，要求学生掌握典型算法的设计思想及程序实现， 能够根据实际问题选取合适的存储方案设计出简洁、高效、实用的算法，为后续 课程的学习及软件开发打下良好的基础。学习该课程，实验是一个关键的环节； 在理解算法的基础上，上机实

2、验是最佳途径。因此，实验环节的好坏是能否学好 本课程的关键。为了更好地配合学生实验，特编写本实验指导书。第1章实验指导1.1实验意义实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的 一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于 原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作 所需要的动手能力；另一方面，能使书上知识变活，起到深化理解和灵活掌握教学内容 的目的。平时的练习较偏重于如何编写功能单一的小算法，而实验题是软件设计的综合 训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧

3、，多人合作， 以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比 任何教师都严厉的检查者。1.2实验步骤常用软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然 数据结构课程中的实验题目远不如实际问题中的复杂程度高但为培养一个软件工作者所应 具备的科学工作方法和作风，也应该遵循以下五个步骤来完成实验题目：问题分析和任务定义设计之前，首先应该充分分析和理解问题，明确问题要求做什么，限制条件是什么等。 本步骤强调的是做什么，而不是怎么做。对问题的描述应该避开算法和所涉及的数据类型， 而对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以

4、及输入的形式； 输出数据的类型、值的范围及输出的形式；若是会话式的输入，那么结束标志是什么是否 接受非法的输入，对非法输入的回答方式是什么等。还应为调试程序准备好测试数据，包括 合法的输入数据和非法形式的输入数据。逻辑设计和详细设计逻辑设计，定义相应的数据类型，并按以数据结构为中心的原则划分模块，定义主程序 和各个抽象数据类型。详细设计，定义相应的存储结构写出各个函数的伪码算法。在这个 过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型 的实现尽可能做到数据封装，数据操作的规格说明尽可能明确具体。作为逻辑设计的结果， 应写出每个抽象数据类型的定义（包括数据结构的描

5、述和每个操作的功能说明），各主要模块 的算法，画出模块之间的调用关系图。详细设计的结果是对数据结构和操作的进一步求精， 写出数据存储结构的类型定义，写出函数形式的伪码算法。在求精的过程中，应该尽量避免 陷入具体编程语言的语法细节，不必过早给出辅助的数据结构和局部变量等。注：设计不是编码。编码实现和静态检查编码是把详细设计结果编写为具体的程序。在上机之前严格的静态检查是必不可少的。 静态检查的通常做法如下：（1）用设计好的测试数据，逐步执行程序（逐个测试每一个模块的正确性）；（2）需深入理解程序的执行逻辑，再加入一些注解和断言。上机准备和上机调试上机准备包括以下几个方面：（1）注意同一种高级语言

6、不同版本之间的语法差别。（2）熟悉语言的集成开发环境IDE （参阅用户手册），尤其熟悉常用操作的快捷键。（3）掌握调试工具的用法，设计测试数据并手工执行得出正确结果。（4）上机调试程序时要带该语言的教材、参考手册。调试最好逐个模块进行，自底向上即 先调试低层的函数；调试过程中借助开发环境提供的各种调试功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应确定疑点，通过修改程序来证实或绕过它。调试正确后，认真整理源程序及其注释，形成风格良好的源程序清单和执行结果。5撰写实验报告按实验报告的具体要求和规范撰写。1.3实验报告按照西华大学计算机与软件工程学院上机实验报告要求撰写实验报告

7、。1.4实验考核实验成绩构成，如下：编程技术：30%测试分析：20%实验报告：50%2.1实验1线性表应用顺序表目的要求掌握线性表顺序存储结构的特点。掌握线性表顺序存储结构的常见算法。实验内容输入一组整型元素序列（不少于10个），建立顺序表。.在该顺序表中进行顺序查找某一元素，查找成功返回1,否则返回0。.判断该顺序表中元素是否对称，对称返回1,否则返回0。4.实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后面为偶数。.输入整型元素序列（不少于10个），利用有序表插入算法建立一个有序表。利用算法5建立两个非递减有序表，并把它们合并成一个非递减有序表。在主函数中设计一个简单菜单，调用上述算

8、法。实验说明算法1至算法6的有关函数用头文件方式存储，主函数包含该头文件。存储定义const int MAXSIZE=15 ; 表中元素的最大个数typedef int ElemType;元素类型typedef struct listElemType elemMAXSIZE; / 静态分配int length; /表的实际长度 SqList ;/顺序表的类型名建立顺序表时，利用随机函数自动产生数据。单向链表目的要求掌握单链表的存储特点及其实现。掌握单链表的插入与删除算法的程序实现。实验内容随机产生或键盘输入一组元素（不少于10个元素），建立一个带头结点的单链表。把单链表中的元素逆置（不允许申请

9、新的结点空间。删除单链表中所有的偶数元素结点。编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，利用该函数建立一个 非递减有序单链表。利用算法4建立两个非递减有序单链表，然后合并成一个非递增链表。把算法1建立的链表分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量 利用已有存储空间），在主函数中设计一个简单菜单，调用上述算法。实验说明结点类型定义typedef int ElemType; 元素类型typedef struct LNodeElemType data ;struct LNode * next ; LNode, *pLinkList ;为了简单，采用带头结点的单链表。

10、三、双向链表目的要求掌握双向链表的存储结构及其实现。掌握双向链表的插入与删除算法的程序实现。实验内容利用尾插法建立一个双向链表。.遍历双向链表。实现双向链表中删除一个指定元素。在非递减有序双向链表中实现插入元素e仍有序的算法。.判断双向链表中元素是否对称，若对称返回1,否则返回0。.设元素为正整型，实现算法把所有奇数排列在偶数之前。.在主函数中设计一个简单菜单，调用上述算法。实验说明双向链表的类型定义typedef int ElemType; 元素类型typedef struct DuLNodeElemType data;DuLNode *prior, *next; DuLNode, *pDu

11、LinkList;目的要求掌握栈、队列的思想及其存储实现。掌握栈、队列的常见算法的程序实现。实验内容采用链式存储实现栈的初始化、入栈、出栈操作。.采用顺序存储实现栈的初始化、入栈、出栈操作。采用链式存储实现队列的初始化、入队、出队操作。.采用顺序存储实现循环队列的初始化、入队、出队操作。在主函数中设计一个简单菜单，调用上述算法。实验说明1 .顺序栈类型定义const int MAX=20 ; / 栈的最大值typedef structElemType *base ;int top ; SqStack;顺序队列类型定义const int MAX=20 ; /队列的最大长度E SMtElemTyp

12、e *base ;int front，rear ； SqQueue ；2.2实验2二叉树应用目的要求掌握二叉树的存储实现。.掌握二叉树的遍历思想。掌握二叉树的常见算法的程序实现。实验内容输入字符序列，建立二叉链表。中序遍历二叉树：递归算法。.中序遍历二叉树：非递归算法。（最好也实现先序，后序非递归算法）.求二叉树的高度。.求二叉树的叶子数。借助队列实现二叉树的层次遍历。在主函数中设计一个简单的菜单，调用上述算法。实验说明1.类型定义二叉链表存储#define ElemType char / 元素类型typedef struct BiTNodeElemType data;BiTNode *Lch

13、ild, *Rchild ; BiTNode, *pBiTree ;元素类型可根据实际需要选取。2.3实验3图的应用目的要求掌握图的存储策略及其存储实现。掌握图的深度、广度优先遍历的算法策略及其程序实现。掌握图的常见算法策略及其程序实现。实验内容.键入或随机生成数据，建立一个有向图的邻接表。.输出该邻接表。.以有向图邻接表为基础上，计算各顶点的度并输出。.以有向图邻接表为基础，输出其拓扑排序序列。.采用邻接表存储，实现无向图的非递归DFS遍历。.采用邻接表存储，实现无向图的BFS优先遍历。判断无向图任意两个顶点间是否有路径，若有则输出路径上的顶点序列。在主函数中设计一个简单的菜单，调用上述算法

14、。实验说明1.类型定义（邻接表存储）typedef struct ArcNode;int adjvex ;struct ArcNode *nextarc ;int weight; / 边的权 ArcNode ; / 表结点typedef VertexType int; / 顶点元素类型typedef struct VNodeint degree, indegree; / 顶点的度，入度VertexType data;ArcNode *firstarc; VNode /*头结点*/, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int

15、 vexnum, arcnum; 顶点的实际数，边的实际数 ALGraph ;上述类型定义可根据情况适当调整。2.4实验4集合应用一、排序算法目的要求1.掌握常见排序算法的策略、适用条件和程序实现。实验内容实现选择排序、插入排序和冒泡排序。实现快速排序的非递归算法（可借助栈实现。实现堆排序算法。实现折半插入排序。采用链式存储结构实现：选择排序、插入排序和冒泡排序。在主函数中设计一个简单菜单，调用上述算法。实验说明1.类型定义const int MAXSIZE=20; /参加排序元素的最大个数 typedef struct listint key ; RedType;typedef structRedTyperMAXSIZE+1;int length ; /参加排序元素的实际个数 SqList ;二、查找算法目的要求1.掌握折半查找算法的思想及程序实现。2 .掌握BST的建立、查找、插入、删除算法策略及其程序实现。选择合适的散列函数，实现不同冲突处理方法的散列表建立与查找。实验内容1.利用实验1