绪章绪论

本讲我们将从三个方面简单介绍这门课程的概况，就是为什么学习这门课程，学什么和怎么学。

●0.1数据结构介绍

本讲具体介绍为什么学习这门课程，学什么内容和怎么学好数据结构。

第一章数据结构

信息技术的迅速发展，为计算机的发展提供了更为广阔的应用空间。计算机的应用领域不再局限于科学计算，已广泛应用于控制、管理和数据处理等非数值计算的处理工作中，与之相应地，计算机加工处理的对象也由纯粹的数值发展到字符、图、表、超文本等一些具有结构的数据对象，因此非常有必要去研究这些带有结构的数据对象及其相关的算法。
数据结构是计算机科学与技术专业的一门核心专业基础课程，研究各种数据表示的抽象逻辑结构以及其上的运算操作。数据结构既要对求解的问题进行抽象描述，又要能给出对具体问题的解决算法。在这一章中，我们将一起学习数据结构的有关基本概念及算法的分析方法，是后续学习内容的基础。

●1.1数据结构的基本概念

本节将介绍数据结构有关的常用的基本概念与术语——数据、数据元素、数据对象、数据类型、抽象数据类型、数据结构，了解数据结构的抽象数据类型的描述方法，重点介绍数据的逻辑结构和存储结构，理解二者之间的区别，这些基本概念与术语将贯穿本门课程的整个学习过程。

●1.2算法

随着计算机的发展，算法在计算机方面已有广泛的发展及应用。这一节我们将了解什么是算法，算法有哪些基本特征，设计一个算法有哪些要求，如何评价一个算法，要求掌握计算语句频度，计算算法的时间和空间复杂度的方法，为以后的算法设计分析做准备。

第二章线性表

数据结构分线性结构和非线性结构，线性表是一种典型的线性结构，也是一种非常基本的数据结构，是学习其他数据结构的基础。本章将介绍线性表的基本概念及其两种实现方法——顺序表和链表。

●2.1线性表

线性结构的特点是数据元素存放在非空有限集合中，并且满足如下几个条件：（1）存在唯一的“第一个”数据元素；（2）存在唯一的“最后一个”数据元素；（3）除第一个数据元素之外，集合中的每一个数据元素都只有一个前驱；（4）除最后一个数据元素之外，集合中的每一个数据元素都只有一个后继。本节我们将学习什么是线性表，线性表有哪些特点，如何定义线性表的抽象数据类型，以及如何用线性表的基本操作实现一些复杂的操作。
学完本章，要求能够从时间和空间复杂度的角度，综合比较线性表两种存储结构的不同特点及其适用场合，会运用线性表解决实际问题。

●2.2顺序表

顺序表是线性表顺序存储的实现，是最简单的数据组织方法，它使用方便，可以对数据元素进行高效的随机存取，但对插入、删除等操作效率较低。本节将介绍顺序表的定义，基本操作（建立、查找、插入和删除等）及程序实现，通过若干示例讲解顺序表的应用。要求能够编程实现相关内容，并掌握调试程序的方法。

●2.3链表

链表是线性表链式存储的实现，是本章的重点和难点，要学好本节内容，需要具有扎实的指针操作和内存动态分配的编程技术。本节以单链表为例，介绍链表结构实现线性表操作的基本方法，在此基础上，引出循环链表、双链表等其他链表形式，并通过考研、面试经常遇到的问题讲解链表的各种应用。

第三章栈和队列

栈和队列是两种在计算机程序设计中广泛运用的特殊的线性表，他们的插入删除操作只能在表的“端点”进行。要求掌握栈和队列的特点，学会运用栈和队列解决实际问题。

●3.1栈

栈是如果所有的操作均被限定在一端的线性表。本节介绍了栈的概念、栈的特点、栈的两种实现方式——顺序栈和链栈。要求掌握两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。

●3.2队列

队列是一端仅允许插入元素，而另一端仅允许删除元素的线性表，本节介绍队列的概念、队列的特点、队列的两种实现方式——循环队列和链队列。要求掌握两种队列的基本操作实现算法．持别注意队满和队空的描述方法。

第四章字符串和数组

本章主要介绍串和数组的基本概念、字符串的匹配运算及矩阵的压缩存储方式。

●4.1数组

串是一种特殊的线性表，组成串的基本数据元素是计算机能识别的符号集，一般是指由字符、数字和标点符号组成的符号集。它的基本操作与线性表的操作类似，又有其特殊的地方。由于已经学过线性表的基本操作，串的基本操作可以自行学习。本节主要介绍字符串的匹配算法：朴素模式匹配算法及KMP算法，要求理解KMP算法的基本思想及实现方法。

●4.2字符串

在高级程序设计语言中，数组是一种重要的数据类型。本节主要介绍数组定义及表示方式，要求掌握数组在以行为主的存储结构中的地址计算方法。介绍了特殊矩阵的压缩存储方法，要求掌握对特殊矩阵进行压缩存储时的下标变换公式。本节还介绍了稀疏矩阵的压缩存储方法及稀疏矩阵转置运算的实现，要领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

第五章树

在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。非线性结构是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树形结构是一类十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。本章主要介绍树的基本概念以及最典型的树结构——二叉树的相关概念及基本操作。

●5.1 树的基本概念

本节主要介绍树的基本概念和术语，要求理解这些基本概念，后面的讲解会用到这些概念。

●5.2二叉树

本节主要介绍二叉树的基本概念及二叉树的性质及二叉树的遍历方法，要求掌握二叉树的结构特性，了解相应的证明方法。遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其他操作。

●5.3线索二叉树

遍历二叉树是以一定规则将二叉树中所有结点排列为一个线性序列，得到二叉树结点的先序序列、中序序列或后序序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。这实质上是对一个非线性结构进行线性化的操作。为了保存结点在某种遍历序列中得到的直接前驱和直接后继的位置信息，可在二叉链表存储结构中增加两个指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索，增加了线索的二叉树称为线索二叉树。
本节主要介绍了线索二叉树的定义、建立线索二叉树和遍历线索二叉树的方法，要求理解线索二叉树的概念，掌握线索二叉树的相关操作算法及其实现方法。

第六章图

图是一种较线性表和树更为复杂的非线性结构。在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。然而在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的，图中任意两个结点之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电信工程、计算机科学以及数学的其它分支中。
本章主要介绍图的基本概念、图的遍历方式及图的各种应用，希望同学们能学会运用图论的主要算法解决生活中的实际问题，达到运用自如的程度。

●6.1图的基本概念

本节主要介绍了图的定义和术语、图的两种存储结构（邻接矩阵和邻接表），要求熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。

●6.2 图的遍历

本节主要介绍图的两种遍历策略：深度优先搜索和广度优先搜索，要求熟练掌握深度优先搜索的递归形式和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。

●6.3最小生成树

本节主要介绍两种求最小生成树问题的方法：Prim算法和Kruskal算法，要求理解两种算法的基本思想，掌握其实现方法。

●6.4最短路径问题

交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。
一般有两类最短路径算法：单源最短路径和多源最短路径，本节主要介绍单源最短路径Dijkstra算法，要求理解该算法的基本思想并掌握其实现方法。

●6.5拓扑排序

有向图中，顶点表示活动，有向边表示活动的优先关系，这个有向图叫做顶点表示活动的网络，简称为AOV网。AOV网中不能出现有向回路（或称有向环）。在AOV网中如果出现了有向环，则意味着出现死循环。因此，对给定的AOV网，应先判断它是否存在有向环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。本节介绍拓扑排序算法及其实现，要求理解该算法并能用程序实现。

第七章查找

查找和排序是数据处理中经常使用的两个重要运算，在系统程序和应用程序中均有广泛的应用。本章主要讨论讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表、树表和哈希表，并对衡量查找表的主要操作——平均查找长度进行讨论。

●7.1查找的基本概念

本节主要介绍查找的基本概念，查找的分类，及平均查找长度的定义。要求理解什么是查找，能够根据情况计算平均查找长度。

●7.2线性表的查找

静态表可用顺序表或者线性链表表示，本节只讨论顺序表的三种查找方法：顺序查找、折半查找和分块查找。要求理解三种查找方法的基本思想，能实现顺序查找和折半查找的实现过程，掌握三种方法的平均查找长度分析方法。

●7.3树表的查找

树表的查找是一种动态查找，查找表结构在查找的过程中动态生成，在查找的过程中如果查找成功，就返回，否则插入该关键字。本节主要介绍二叉查找树的查找方法和四种平衡二叉树方法，要求掌握二叉查找树构造和查找过程，掌握它的平均查找长度计算方法，理解平衡二叉树的实现原理。

●7.4散列查找

前面的顺序查找和树表查找都是基于比较的查找，哈希查找是基于计算的查找，通过哈希函数计算得到关键字的地址。哈希查找技术的核心就是如何构造一个好的哈希函数，把散列地址均匀地分布在哈希表的整个地址空间内。要求掌握哈希表的构造方法，深刻理解哈希表与其他结构的表的实质性的差别，理解并掌握哈希查找、哈希函数的基本原理和冲突处理算法。

第八章排序

排序是数据处理领域最常用的一种运算。排序的目的之一是为了提高查找效率。由前述章节可知，对一个无序的顺序线性表进行查找，其时间复杂度为O(n)，若在排序的基础上进行折半查找则时间复杂度可提高到O(log n)，效果显著。学习和研究各种排序方法是计算机工作者必须面对的重要课题之一。
本章主要讨论比较插入排序、交换排序、选择排序、归并排序、基数排序等各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每类排序方法中，从简单方法入手，重点讨论性能先进的高效方法（如，插入排序类中的希尔排序、交换排序类中的快速排序、选择排序类中的堆排序等）。要求理解这些排序算法，并能用计算机实现，理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的，掌握每种算法的时间复杂度和空间复杂度，学会运用各种内部排序方法解决实际问题。

●8.1排序的基本概念

排序是将一个无序的数据元素序列重新排列成按关键字有序的序列。本节主要介绍排序的定义、分类、稳定性、方法及排序算法的性能评价标准。

●8.2插入排序

插入排序的基本思想是把一个记录插入到已排好序的有序表中，使这个记录数增1的序列仍然有序。本节主要介绍几种插入类排序方法：直接插入排序，折半插入排序和希尔排序。要求了解各种方法的排序过程，掌握各种排序方法的时间复杂度的分析方法。

●8.3交换排序

借助于“交换”的思想进行排序的方法为交换排序法，其基本思想是：比较两个待排序记录的关键字，若为逆序则相互交换位置，否则保持原来的位置不变。这一节主要讨论两种交换排序法：冒泡排序和快速排序。要求了解两种算法的基本思想，能够提出对两种基本算法的改进方法，计算它们在最好、平均和最坏情况下的时间复杂度和空间复杂度。

●8.4选择排序

选择排序法的基本思想是：每趟在n-i+1(i=1，2，…，n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。本节主要介绍简单选择排序、树形形选择排序和堆排序三种方法。要求了解每一种方法的排序过程，掌握它们的时间复杂度的分析方法。

●8.5归并排序和基数排序

归并排序的基本思想是：将两个或两个以上的有序序列归并成一个新的有序序列的过程。本节将以2-路归并排序为例进行阐述。基数排序是和前面所述的各类排序方法完全不相同的一种排序方法，它不需要进行关键字的比较和记录的移动（交换），是一种基于多关键字排序的思路而对逻辑关键字进行排序的一种内部排序方法，又称桶排序或分配方法排序。要求了解两种方法的基本思想及时间复杂度分析方法。