数据结构实验指导教程杨海军计算机与互联网

　　《数据结构实验指导教程（C语言版）》中预备知识，介绍项目中实验环境、程序组织方式和管理方法，讲解程序及算法的效率估算方法和分析技巧，描述一般测试技术和调试方法，以及测试数据与测例的设计安排技巧；基础实验，先安排重要的验证性实验，然后设计基于基本数据结构的简单应用实验；综合实验（即课程设计），介绍在一个项目中选择和使用多种基本数据结构的依据和方法，讲解如何有效地将它们融合在一起解决实际的复杂应用问题。

　　本教程在内容选取及编排顺序上，与《数据结构（C语言版）》（978-7-302-14751-0，清华大学出版社出版）保持一致，可作为高等院校计算机及相关专业数据结构课程的实验教材。

第1章 预备知识
1.1 软件开发过程与设计原理
1.1.1 软件开发的一般步骤
1.1.2 软件设计的基本原理
1.2 C语言程序的组织与管理
1.2.1 C语言程序的构成
1.2.2 较大程序的实现方法和项目管理
1.2.3 程序的生成与调试
1.3 程序测试初步
1.3.1 程序测试的基本概念
1.3.2 软件测试的技术分类
1.3.3 测试环境的构建
1.3.4 测例设计
1.4 程序效率的事前估算与事后统计
1.4.1 程序的时间复杂度
1.4.2 程序运行时间获取
1.5 实验环境
1.5.1 Linux实验环境
1.5.2 Windows实验环境

第2章 线性表
2.1 知识点
2.1.1 线性表的逻辑结构
2.1.2 线性表的物理结构
2.2 基础实验
2.2.1 实验一：顺序表操作实验
2.2.2 实验二：单链表操作实验
2.3 简单应用实验
2.3.1 适用线性表结构的一般特征分析
2.3.2 在C／C  环境下，应用基础实验中已实现的线性表结构的几点提示
2.3.3 应用实验一：一元多项式的相加
2.3.4 应用实验二：城市链表
2.4 小结

第3章 栈与队列
3.1 知识点
3.1.1 栈的逻辑结构
3.1.2 栈的物理结构
3.1.3 队列的逻辑结构
3.1.4 队列的物理结构
3.2 基础实验
3.2.1 实验一：顺序栈的操作实验
3.2.2 实验二：顺序循环队列的操作实验
3.3 简单应用实验
3.3.1 适用栈和队列结构的一般特征分析
3.3.2 在C／C  环境下，应用基础实验中已实现的栈与队列的几点提示
3.3.3 应用实验一：迷宫问题
3.3.4 应用实验二：病人看病模拟程序
3.4 小结

第4章 字符串
4.1 知识点
4.1.1 串的逻辑结构
4.1.2 串的物理结构
4.2 基础实验
4.2.1 实验一：串的动态数组存储表示操作实验
4.2.2 实验二：串的模式匹配实验
4.3 简单应用实验
4.3.1 适用串结构的一般特征分析
4.3.2 在C／C  环境下，应用基础实验中已实现的串结构的几点提示
4.3.3 应用实验：建立词索引表（说明：具体内容要求满足课本p86内容）
4.4 小结

第5章 数组
5.1 知识点
5.1.1 数组的逻辑结构
5.1.2 数组的物理结构
5.1.3 矩阵的压缩存储
5.1.4 广义表的逻辑和存储结构
5.2 基础实验
5.2.1 实验一：稀疏矩阵的三元组顺序存储结构的基本r/>5.2.2 实验二：稀疏矩阵的十字链表存储结构的基本r/>5.2.3 实验三：广义表的操作实验
5.3 简单应用实验
5.3.1 适用数组结构和广义表结构的一般特征分析
5.3.2 在C／C  环境下，应用基础实验中已实现的数组和广义表的几点提示
5.3.3 应用实验：广义表的应用
5.4 小结

第6章 二叉树与树
6.1 知识点
6.1.1 二叉树和树的逻辑结构
6.1.2 二叉树和树的物理结构
6.2 基础实验
6.2.1 实验一：二叉树的二叉链表存储表示操作实验
6.2.2 实验二：树的孩子-兄弟链表存储表示操作实验
6.3 简单应用实验
6.3.1 适用二叉树结构的一般特征分析
6.3.2 在C／C  环境下，应用基础实验中已实现的二叉树结构的几点提示
6.3.3 应用实验一：赫夫曼树和赫夫曼编码
6.3.4 应用实验二：联赛的构造
6.4 小结

第7章 图
7.1 知识点.
7.1.1 图的逻辑结构
7.1.2 图的物理结构
7.2 基础实验
7.2.1 实验一：图的邻接矩阵存储结构的操作实验
7.2.2 实验二：图的邻接表存储结构的操作实验
7.3 简单应用实验
7.3.1 适用图结构的一般特征分析
7.3.2 在C／C  环境下，应用基础实验中已实现的图结构的几点提示
7.3.3 应用实验一：生成树（Prim算法）
7.3.4 应用实验二：路径问题
7.4 小结

第8章 查找表
8.1 知识点
8.1.1 静态查找表
8.1.2 动态查找表
8.1.3 哈希表
8.2 基础实验
8.2.1 实验一：折半查找操作实验
8.2.2 实验二：二叉排序树操作实验
8.3 简单应用实验
8.3.1 在C／C  环境下，应用基础实验中已实现的查找方法的几点提示
8.3.2 应用实验：装箱问题
8.4 小结

第9章 排序
9.1 知识点
9.1.1 排序的基本概念
9.1.2 排序算法基本性能比较
9.2 基础实验
9.2.1 实验一：插入排序操作实验
9.2.2 实验二：选择排序操作实验
9.2.3 实验三：交换排序操作实验
9.2.4 实验四：归并排序与基数排序操作实验
9.3 简单应用实验
9.4 小结

第10章 课程设计
10.1 课程设计的目的和要求
10.2 课程设计的实施步骤
10.3 课程设结报告的撰写规范
10.4 课程设计案例
10.4.1 设计一：五泉山公园导游系统的设计与实现
10.4.2 设计二：航空票务管理系统的设计与实现
附录 实验报告格式
参考文献

　数据结构是计算机程序设计的重要基础，如何培养学生的实际动手能力，从而解决具体问题就是本课程的基本任务之一。我们在实际教学中发现，虽然学生对数据结构基本概念及基础操作有一定认识，但仍然难以独立设计测试环境和测例，在面对具体应用问题时，缺乏选择适当的数据结构及实现算法的能力。我们认为，解决以上问题是数据结构教学中存在的“难教难学”状况的重要途径，为此，编写了这本《数据结构实验指导教程》。本实验教程通常理论及实验教学内容以“基本数据结构—实现”和“问题识别—设计实现”的层行组织。为了降低学，导入了软件设计的基本概念，安排了测试环境、测例设计的基础内容，同时在基础实验与综合应用实验间安排了简单应用实验，以实现从概念到简单应用再到复杂应用滑过渡。简单应用实验选择比较单一的实际问题，分析其逻辑结构，然后考虑在计算机环境下如何表达其结构，再利用现有四种基本数据结构中的一种算法来实现和完成。综合应用实验一般较复杂，需要利用多种基本数据结构来完成。基础实验部分对应“基本数据结构—实现”层次，用以深化数据结构基本概念及其机器实现；简单应用实验部分和综合应用实验部分对应“问题识别—设计实现”层次，先识别具体问题含哪些基本数据结构，再根据前面的实现来完成设计。本书从内容上共分三部分。
　　 预备知识：对项目中实验环境、程序组织方式和管理方法有较深认识，需要理解程序及算法的效率估算方法和分析技巧，掌握一般测试技术和调试方法，尤其是测试数据及测例的设计安排。
　　 基础实验：紧贴数据结构要点，以及基于基本数据结构的简单应用。目的在于使学生能面对问题，识别基本数据结构，会编程应用已有存储结构和算法实现。
　　 综合实验（或课程设计）：介绍在一个项目中使用多种基本数据结构的方法，注重选择基本数据结构的依据，以及如何有效地将它们融合在一起。本书□□章由杨海军编写，第2、4、6、8章由马彦编写，第3、5、7、9、10章由叶燕文编写。杨海军负责全书的规划和统稿，马彦、叶燕文负责全书的编排。本书在编写过程中参考了诸多同行的文章和著作（见书后所附参考文献），在此一并致谢。由于编者的知识有限，书中疏漏之处在所难免，恳请专家和读者批评指正。

第pan>章预备知识

了解软件开发的基本过程和步骤，掌握软件设计的基本原理，熟悉高级语言编程工具以及测试调试的主要概念和方法，不仅能够有效地表示和实现数据结构及相关算法，也是完成本教程实验的重要保证。

1.pan>软件开发过程与设计原理

1.1.pan>软件开发的一般步骤

通常依据生命周期（Life Cycle）理论将软件开发步骤分为需求分析、软件设计、编码实现、测试及维护五个阶段。软件生命周期是指这样一个过程：从用户需求开始，经过开发、交付使用，在使用中不断地增补修订，直至软件报废。需求分析阶段的主要任务是地确定“软件系统必须做什么”，及确定软件系统必须具备能。概要设计就是决定软件由哪些模块组成、每个模能以及模块间的调用关系和参数传递情况；同时决定该软件要存储的数据、这些数据的组成和相互关系，即设计该软件体数据结构或数据库结构。利用程序流程图、伪码等工具，将概要设计阶段确定每个模块的能转换为的、结构化的过程描述是详细设计阶段的主要任务。编码阶段就是把每个模块的控制结构转换成计算机可接受的程序代码，即写成以某特定程序设计语言表示的“源程序”。测试是保证软件质量的重要手段，其主要方式是利用测例检验软件的各个组成部分是否满足规格要求。一般的，将测试分为模块测试、集成测试和确认测试。软件正式运行后，入软件维护阶段，它可以持续几年甚至几十年，它是软件生存期中时间长的阶段。

1.1.2软件设计的基本原理

模块（Module）是构成程序的基本构件，是基本的设计元素。通常使用软件结构概念表示程序是由哪些模块构成的，以及这些模块相互间的关系。软件结构以层次表示程序的系统结构，即一种控制的层次体系，表示了软件元素（模块）之间的关系，如调用关系含关系、从属关系和嵌套关系等，并不表示软件执行的具体过程。

介绍几个与软件结构相关的概念。

1.模块化

模块是由边界元素限定的相邻程序元素的序列，且有一体标识符代表它，如过程、函数、子程序、宏等。

模块化(（Modularity）是将系统划分为若干个模块，每个模块完成一能。模块化的目的是将系统“分而治之”，因此能够降低问题的复杂性，使软件结构清晰，易修改、易阅读、易理解，因而也有助于提高软件的可靠性，同时使得系统各个部分可以并行开发，提高软件的生产率。但并非模块分得越小越好，原因是随着模块规模变小，模块的数量会增多，这样会引起模块之间接口的复杂度和工作量增加。

提高模块质量在于提高模块独立性。模块独立性的准则用耦合性和内聚性来衡量行系统模块划分时尽量做到高内聚、低耦合，即要使模块的内部联系尽可能地强，而模块间的外部联系尽可能地弱，这样就尽可能地提高模块的相对独立性。C语言开发中，一个模块对应一个函数或宏，也就是说采用函数和宏实现模块。

2.软件结构的描述

通常采用软件结构概念来描述软件的组成模块、各能以及模块间通信协调的方法和方式，反映了软件的静态特性。软件结构决定了整个系统的结构，也确定了系统的质量。软件结构图、层次图是描述软件结构的常用工具。

（pan>）软件结构图

软件结构图是描述软件结构的图形表示方法。它以特定的符号表示模块、模块间的调用关系和模块间信息的传递。软件结构图的主要元素有模块、调用和数据。

·模块：用矩形框表示，框中写有模块的名字，说明模能。模块是程序对象有名字的集合。如图1-pan>中的“计算通信费用”“计算市话费”等。

调用：从一个模块指向另一个模块的箭头表示前一模块对后一模块的调用，一般是上层调用下层。在图1-pan>中，在计算通信费用模块中调用计算市话费、计算国内长途费和计算国际长途费三个模块。

数据：调用箭头边上的短箭头表示调用时从一个模块传送给另一模块的数据。通常在短箭头应注有信息的名字，如图1-pan>所示。

数据又分为数据信息和控制信息两类，如果要区分这两类信息，通常可用尾端带有空心圆的短箭头表示数据信息，用尾端带有实心圆的短箭头表示控制信息。有的结构图对这两种信息不加以区别，一律用注有信息名的短箭头来表示。

（2）层次图

层次图用来描绘软件的层次结构，层次图中的一个矩形框代表一个模块，方框间的连……