课程内容介绍 　　程序的构成与数据结构是两个不可分割的问题。对程序构造进行系统而科学的研究，首先必是对包含复杂数据集合的大型程序而言，因而数据结构是设计与实现编译程序，操作系统，数据库系统及其它系统程序和大型应用程序的重要基础，是介于数学，计算机硬件，软件之间的一门核心课程，是计算机学科中一门综合性的专业基础课。 　　“数据结构”是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并对进行性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础，数据结构课程是计算机专业的一门核心的关键性课程。 第1章 绪 论 　　数据结构被称为是计算机科学的两大支柱之一。著名的计算机科学家P.Wegner指出："在工业革命中起核心作用的是能量，而在计算机革命中起核心作用的是信息"。计算机科学就是"一种关于信息结构转换的科学"。 第2章 线性表 　　线性结构的特点是：在数据元素的非空有限集合中，存在唯一的首元素和唯一的尾元素，首元素无直接前驱，尾元素无直接后继，集合中其它每个数据元素均有唯一的直接前驱和唯一的直接后继。本章将首先介绍线性表的抽象数据类型定义，然后给出实现线性表的两种存储结构──顺序存储结构与链式存储结构，进一步给出在相应存储结构上实现的线性表运算。 第3章 栈和队列 　　在第2章中，我们学习了线性表，其中对于线性表的操作允许在表的任何位置进行，使用比较灵活，同时也使得实现操作时需要考虑的因素较多。本章介绍的限定性线性表是一类操作受限制的特殊线性表，其特殊性在于限制线性表插入和删除等运算的位置。堆栈和队列在各种类型的软件系统中应用广泛。堆栈技术被广泛应用于编译软件和程序设计中，在操作系统和事务管理中广泛应用了队列技术。讨论堆栈与队列的结构特征与操作实现特点，有着重要的意义。 第4章 串 　　计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。字符串处理在语言编译、信息检索、文字编辑等问题中，有广泛的应用。在这一章，我们将讨论串的基本存储结构和基本操作。 第5章 数组和广义表 　　数组和广义表，可看成是一种扩展的线性数据结构。其特殊性不象栈和队列那样表现在对数据元素的操作受限制，而是反映在"数据元素"的构成上。在线性表中，每个数据元素都是不可再分的原子类型；而数组和广义表中的数据元素可以推广到是一种具有特定结构的数据。本章以抽象数据类型的形式讨论数组和广义表的定义与实现，使读者加深对这两种特殊的线性结构的理解。 第6章 树和二叉树 　　前面2-5章介绍了线性逻辑结构，本章和下一章将分别介绍树和图这两种非线性逻辑结构。线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构的特征是结点间关系前驱、后继的则不具有唯一性。其中在树型结构中结点间关系是唯一前驱而后继不唯一，即结点之间是一对多的关系；图结构中结点间前驱与后继可不唯一，即结点之间是多对多的关系。直观地看，树结构是指具有分支关系的结构（其分叉、分层的特征，类似于自然界中的树）。树形结构应用非常广泛，特别是在大量数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。树和图的理论基础部分属离散数学内容，而在数据结构中所讨论的重点是关于树和图的结构存储及操作实现技术。本章主要讨论树型结构的特性、存储及其操作实现。 第7章 图 　　图作为一种非线性数据结构，被广泛应用于多个技术领域，诸如系统工程、化学分析、统计力学、遗传学、控制论、计算机的人工智能、编译系统等领域，在这些技术领域中把图结构作为解决问题的数学手段之一。在离散数学中侧重于对图的理论进行系统的研究。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。 图结构与表结构和树结构的不同表现在结点之间的关系上，线性表中结点之间的关系是一对一的，即每个结点仅有一个前驱和一个后继（若存在前驱或后继时）；树是按分层关系组织的结构，树结构中结点之间关系是一对多，即一个双亲可以有多个孩子，每个孩子结点仅有一个双亲；对于图结构，图中结点之间的关系可以是多对多，即一结点和其它结点关系是任意的，可以有关也可以无关。由此看出：图G 树T 表L，图是一种比较复杂的非线性数据结构。 第8章 动态存储管理（自学） 第9章 查找 　　在前几章介绍了基本的数据结构部分，包括线性表、树、图结构，并讨论了这些结构的存储映象，以及定义在其上的相应运算。从本章开始，将进入介绍数据结构中的重要技术部分-查找和排序。在非数值运算问题中，数据存储量一般很大，为了在大量信息中找到某些值，就需要用到查找技术，而为了提高查找效率，就需要对一些数据进行排序。查找和排序的数据处理量几乎占到总处理量的80%以上，故查找和排序的有效性直接影响到基本算法的有效性，因而查找和排序是重要的基本技术。 第10章 内部排序 　　当进行数据处理时，经常需要进行查找操作, 而为了查得快找得准，通常希望待处理的数据按关键字大小有序排列，因为这样就可以采用查找效率较高的折半查找法。由此可见，排序是计算机程序设计中的一种基础性操作，研究和掌握各种排序方法非常重要的。本章将介绍排序的基本概念并讨论五类重要的排序方法。 第11章 外部排序（自学） 　　在前面讨论的各种排序方法中，待排序记录及有关信息都是存储在内存中的，整个排序过程也全部是在内存中完成的，不涉及数据的内外存交换，因此统称为内部排序。若待排序的记录数n很大，以致内存容纳不下时，排序过程必须借用外部存储器才能完成，我们称这类排序为外部排序。外部排序方法与各种外存设备的特征有关，所以在讨论外部排序的基本方法之前，我们先简单地介绍一下有关外存信息存取的特点。