本教材意在加强学生对数据结构的抽象数据类型的理解，提高学生分析问题、解决问题的能力，是针对学生进行数据结构算法的实际套用技能的训练而编写的教材，也可作为教师讲解数据结构及其算法、指导学生上机的参考资料。

本书是为配合数据结构课程的教学及后期数据结构的课程设计而编写的。本教材分为两大部分，一是基本操作，二是综合训练。在基本操作部分，按照数据结构课程的教学内容分别描述了线性、树形、图形、集合四种数据结构的抽象数据类型以及它们的基本操作算法在C语言平台上的设计及实现过程，特别注重对算法的分析及理解，并进行了适当的拓展提问，方便学生更加深入地理解数据结构的抽象数据类型的描述。在综合训练部分，结合教学内容，将线性结构、树形结构、图形结构的套用综合在一起，设计实现了有一定难度的算法。

数据结构是一门研究非数值计算程式设计问题中的计算机操作对象以及它们之间关係和操作等的学科。

数据的组织结构以及对这些结构化数据操作的实现是这门学科的核心问题。而以数据对象、数据关係和基本操作为考察内容的抽象数据类型正好体现了这门学科的研究中心。所以对抽象数据类型的理解是掌握数据结构的基础。

线性结构、树形结构和图形结构是三种基本的抽象数据类型。对这三种抽象数据类型的实现和套用的理解和掌握，不但是学习数据结构的基本要求，也是学习数据结构的基本手段和方法。这三种抽象数据类型除了有空间上的可理解性以外，也具有操作上的易理解性。所以，在学习数据结构的时候，除了建立空间上数据的关係和操作概念以外，通过实际操作实现这些基本抽象数据类型，是降低抽象数据类型的抽象性，提高对数据结构理解能力的一个有效途径。这也是发挥数据结构在设计和实现中主导作用的必经之路。

本书正是从这三种基本抽象数据类型的数据描述、结构与操作分析和算法实现等入手，从实践的角度对抽象数据类型和数据结构进行了讲解和阐述。在基本抽象数据类型空间概念的基础之上，重点讲述了基于这些抽象数据类型、所包含元素及其关係的操作的实现过程。同时，在对本书的学习过程中，希望读者能重点体会：

1．抽象数据类型的概念。即：数据对象、数据关係以及其上的操作。数据及其关係是实现操作的基础。而操作是抽象数据类型特性的真正体现。

2．线性结构、树形结构和图形结构这三种基本抽象数据类型的结构特性和操作特性。对这三种抽象数据类型的理解和套用不仅是其他后续课程的基础，也是套用系统设计实现的基础。

3．算法实现对物理结构的依赖性。抽象数据类型所描述的操作，只是一种逻辑操作，具体的实现依赖于对这个抽象数据类型元素的物理存储结构。比较有代表性的例子就是：以顺序存储结构和链式存储结构为基础的线性表，基本操作的算法实现却完全不同。

4．程式的实现过程大体上是从结构设计、算法设计到算法实现。应该在学习程式设计的开始培养好这种良好习惯。把结构和算法设计作为程式设计的一个重要任务来完成。结构和算法设计上的缺陷，将导致程式的最终失败。

本书内容分为两大部分，一部分是基本操作，另一部分是综合训练。

在基本操作部分中，设计了八个实验。实验一到实验五为线性结构的设计与套用。实验六和实验七分别为树形结构和图形结构的设计与套用。实验八排序是基于线性结构的具体套用，也是数据结构课程中的经典算法。书中每个实验都分为实验目的及要求、实验内容、功能函式的分析设计及原始码和习题四个部分。在基本操作部分中，用较大篇幅讲解了基本操作集的分析设计。

在综合训练部分，力求使读者的水平有大幅提高，设计的思想是既要用到基本操作部分的数据结构的基本操作集，又要使算法设计简便。为方便读者阅读，在原始码旁加注了大量的注释。

书中原始码都已在TC环境中调试成功，供读者在编码时参考。

正确设计程式结构、书写流程图和独立完成编码是非常重要的一种能力，希望读者能够从本书中得到借鉴。

第1部分　基本操作

第1章　顺序存储的线性表——实验一

1.1　实验目的及要求

1.2　实验内容

1.3　功能函式的分析设计及原始码

1.4　习题

第2章　链式存储的线性表——实验二

2.1　实验目的及要求

2.2　实验内容

2.3　功能函式的分析设计及原始码

2.4　习题

第3章　栈——实验三

3.1　实验目的及要求

3.2　实验内容

3.3　功能函式的分析设计及原始码

3.4　习题

第4章　循环伫列——实验四

4.1　实验目的及要求

4.2　实验内容

4.3　功能函式的分析设计及原始码

4.4　习题

第5章　数组——实验五

5.1　实验目的及要求

5.2　实验内容

5.3　功能函式的分析设计及原始码

5.4　习题

第6章　二叉树——实验六

6.1　实验目的及要求

6.2　实验内容

6.3　功能函式的分析设计及原始码

6.4　习题

第7章　图——实验七

7.1　实验目的及要求

7.2　实验内容

7.3　功能函式的分析设计及原始码

7.4　习题

第8章　排序——实验八

8.1　实验目的及要求

8.2　实验内容

8.3　功能函式的分析设计及原始码

8.4　习题

第2部分　综合训练

第9章　迷宫——综合训练一

第10章　稀疏矩阵相乘——综合训练二

第11章　最优二叉树——综合训练三

第12章　最小生成树——综合训练四

第13章　关键路径——综合训练五

第14章　最短路径——综合训练六

参考文献