-
第一章绪论
在计算机科学中，数据结构不仅作为一般程序设计的必备知识，而且是设计编译系统、操作系统、数据库系统及其他应用程序的重要基础。第一章绪论将为大家数据结构的基本概念和算法的分析方法。由于使用C语言作为我们的算法实现语言，所以我们还在第一章中为同学们回顾了C语言的主要语法要点。
-
●1.1什么是数据结构
介绍数据结构课程性质、地位，让初学的同学认识到数据结构是一门怎样的课程。
-
●1.2数据结构的相关概念及表示
介绍了数据、数据元素、数据对象、逻辑结构的关概念，及用二元组的表示数据结构的方法。
-
●1.3数据结构的术语
本节主要介绍的数据结构中专业术语，一个数据结构是指带结构的数据元素的集合，包括数据的逻辑结构、存储结构和数据运算。
-
●1.4 算法的描述与分析
本节介绍了什么是算法、算法的5个特性和算法的表达形式。解决某一实际问题时可以有不同的算法，这些不同算法的量化评价就是算法的时、空复杂度分析。
-
●1.5基本数据类型和指针
介绍了C语言中常用的基本数据类型，由于在数据结构中我们常用到指针进行存储单元的引用，所以重点回顾了指针的概念和用法。
-
●1.6数组、结构和联合
介绍了C语言中的数组、结构和联合这几种构造数据类型的概念及用法。数据结构中解决实际问题就是一种现实的抽象，而这种抽象常用数组、结构和联合实现。
-
●1.7自定义类型和函数调用
介绍了C语言中的用户算定义类型及函数的调用，重点讲解了函数调用的值传和址传两种实现方式的区别与联系。
-
第二章线性表
线性表是最简单且最常用的一种数据结构。线性结构的特点是，在数据元素的非空有限集合中，除第一元素无直接前驱、最后一个元素无直接后继外，其余每个数据元素均有唯一的直接前驱和唯一的直接后继。本章将介绍线性表的概念，给出线性表顺序存储结构与链式存储结构两种存储结构，并进一步讨论在相应存储结构上实现线性表的基本运算。
-
●2.1线性表的基本概念及运算
本节中介绍了线性表的概念，线性表中所有元素的排列呈线性关系，除了唯一的开始和结束结点之外，每个结点都有唯一的前趋和后继结点。线性表有初始化、求长度、插入、删除、按序号查找、按值查找6个基本运算。
-
●2.2线性表的顺序存储
顺序表的插入首先要考虑空间上溢的问题，如果有空间允许插入，必须保证插入新元素后依然是一个顺序表。顺序表的删除，必须保证删除元素后依然是一个顺序表，所以如何实现批量移动是本节重点讲述的内容。
-
●2.3线性表
由于顺序表的插入和删除都需要批量移动元素，所以链表存储的插入和删除更为高效，本节重点讲解。单链表有头插法和尾插法两种创建的方式，本节将分别介绍这两种方法，并进行了时间复杂度的分析。单链表虽然实现了空间申请的自由，无须进行预分配，但是由于地址不连续，所以查找只能是从头开始的顺序比对查找。顺序表的插入和删除都需要批量移动表中近一半的元素，本节通过对单链表多个算法的分析、改进，实现了链表的插入和删除的时间复杂度为O(1)，提高了程序效率。链表的设计比较灵活，可以根据应用的需要，设计出合适的数据存储结构，以提高程序的运行效率，本节所讨论的循环链表和双链表就是这样的结构。
-
●2.4顺序表和链表的比较
计算机中数据存储本质就是地址连续与否，所以存储结构对应就有顺序存储和链式存储这两大类，本节针对线性表的这两种存储进行了对比分析。
-
第三章栈和队列
栈和队列是两种重要的抽象数据类型，是一类插入和删除的位置受限的线性表。从数据逻辑结构角度年，它们都是线性结构，应用非常广泛，本章将讨论栈与队列的概念、存储结构和基本运算的实现。
-
●3.1栈
栈是限定仅在一端进行插入或删除的线性表。本节将讲解栈的逻辑结构、和基本运算。栈的顺序存储结构是用一个数组向量来实现栈，通常习惯以数组下标大的一端做栈顶，本节首先讲解了顺序栈的入栈、出栈等基本运算的实现，然后分析了多个顺序栈共享存储空间的问题，并提出了两个共用栈的解决方案。由于插入、删除都在top位置进行，所以链栈实际就是一个用top指针表示的单链表，本节主要讲解了链栈的基本运算。本节主要通过多个链栈的管理、多行文本编辑器纠错、栈实现递归调用三个例题的讲解，说明了栈在计算机中的应用非常广泛。
-
●3.2队列
队列(Queue)是一种运算受限的线性表。它只允许在表的一端进行 插入，而在另一端进行删除。本节主要介绍了队列的逻辑结构和基本运算。本节首先分析了用向量存储队列，所产生假上溢和假下溢现象，引出了循环队列的概念，然后讲解了循环队列的结构及基本运算的实现。由于队列规定了必须在队尾插入、队头删除，所以一个链队列显然需要队头、队尾两个指针才能唯一确定，本节主要讲解了链队列的基本运算及改进算法。本节用队列来实现了迷宫求解问题，讲解了迷宫的数据建模和搜索路径的实现两个关键问题的具体解决方案。
-
第四章串
计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。字符串简称为串，串的处理在计算机非数值计算中占有重要的地位，如信息检索系统、文字编辑等过都是以字符串数据作为处理对象。本章介绍串的概念、存储结构和基本运算的实现算法，重点讨论串的模式匹配算法。
-
●4.1串的基本概念及存储结构
串的概念、顺序存储和链式存储。
-
●4.2串的运算
串运算（求串长度，联结、比较两个字符串，子串的查询，字符串的拷贝，字符串的插入、删除和取子串）相关的C库函数和自定义函数。
-
●4.3串的模式匹配
串的BF和KMP模式匹配算法。
-
第五章数组
数组是由相同性质的数据元素组成的，可以看成是一种扩展的线性数据结构，其特殊性在于数据元素的构成上，从组成线性表的元素角度年，数组可看成是具有某种结构的数据构成的，广义表则是由单个元素或子表构成的。因此数据和广义表中的数据元素可以是单个元素，也可以是一个线性结构。本章中将讲解几种特殊矩阵的压缩存储和稀疏矩阵的相关算法及广义表的概念。
-
●5.1多维数组
数组的定义，矩阵的按行优先存储，矩阵的按列优先存储。
-
●5.2特殊矩阵的压缩存储
对称矩阵，上三角矩阵，下三角矩阵，三对角阵的非零元素按行优先压缩存储到一维数组中，以及转换特殊矩阵下标与一维数组下标的公式。
-
●5.3稀疏矩阵的压缩存储
稀疏矩阵的非零元素的三元组法顺序存储或十字链表法链式存储方法。
-
●5.4广义表的概念及存储
广义表的概念，长度，深度，表头，表尾，链表存储。
-
第六章树和二叉树
线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中的结点间前驱、后继的关系并不具有唯一性。在树形结构中，结点间关系是前驱唯一而后继不唯一，即结点之间是一对多的层次关系。树形结构的应用非常广泛，特别是在文件系统、编译系统、目录组织等方面尤为突出。本章将介绍树和二叉树两种树形结构的概念、存储结构和相关算法。
-
●6.1树的概念
树是一种树形结构，本节讲解树的定义、树的逻辑结构表示和树的基本术语。
-
●6.2二叉树
二叉树是不同于树的树形结构，它们是两种不同的数据结构。二叉树是有序树，每个结点最多有两个孩子，且孩子有左右之分。本小节主要讲解二叉树的定义和二叉树的几个性质。
-
●6.3线索二叉树
所谓线索是利用二叉链表中的空指针域来保存结点的前驱和后继信息，加了线索的二叉树称为线索二叉树。本节以中序线索化二叉树为例讲解线索化的方法。
-
●6.4二叉树、树和森林的转换
树和森林的存储可以借鉴二叉树的链式存储方式，本节介绍将树和森林转换成二叉树的方法。
-
●6.5哈夫曼树
哈夫曼树（HuffmanTree）又称最优二叉树，它是带权路径长度最小的二叉树，通常用来构造最优编码。本节讲解创建哈夫曼树的算法。
-
第七章图
图是比线性表和树更为复杂的一种数据结构，在图中，每个结点可以和其他任何结点相关联，而现实世界中许多非数值的问题都可以抽象为图的的问题。在本章中，我们将学到图的基本概念和两种最常用的邻接矩阵和邻接表这两种存储结构；图的运算介绍深度和广度优先搜索遍历；在生成树中将介绍和分析Prim和Kruskal两种经典算法；最短路径将介绍和讲解Dijkstra和Floyd算法；在应用方面将讲解拓扑排序。
-
●7.1基本概念
本节介绍了图、有向图和无向图、图和子图、路径和回路、连通图、顶点的度、完全图的概念，和图的表示方法及相关术语。
-
●7.2图的存储结构
本节讲解了邻接矩阵的创建及遍历的算法。图的邻接矩阵表示法是用一个二维数组来表示图中顶点之间的相邻关系，N个顶点的邻接矩阵就是一个N阶方阵。邻接表是图的一种链式存储结构，适合存储稀疏图，本节主要讲解了邻接表的创建、查找和输出等算法。
-
●7.3图的遍历算法及其应用
根据搜索路径的方向不同，对图的遍历有深度优先搜索遍历和广度优先搜索遍历两种方法，这是许多图算法的基础，许多问题的求解可以转化为这两种算法及其变形形式。本节通过非连通图的遍历算法、设计算法以求解无向图G的连通分量的个数、设计算法求出无向图G的边数这几个算法讲解了图的应用问题。
-
●7.4最小生成树
在图论中，常常将树定义为一个无回路连通图，而生成树是连通图的极小连通子图。Prim算法使用MST性质构造了最小生成树，设计了如何找到连接u和V-U的最短边来扩充生成树T的算法。构造最小生成树的另一个算法是由克鲁斯卡尔(Kruskal)提出的，按照长度递增的顺序依次选择图中的边，如果该边满足件，则可扩充到生成树中，直到所有的结点都在同一连通分量中为止。
-
●7.5最短路径
求解两点之间的最短路径的问题也是图的典型应用问题之一，本节主要讲解了迪杰斯特拉（Dijkstra）算法求解单源最短路径的问题。求解图中任意两个顶点之间的最短路径，可以依次把有向网络的每个顶点作为源点，重复调用n次DIJKSTRA算法是一种解决方案，而本节所介绍的弗洛伊德(Floyd)算法是使用递推的方式求解多源最短路径。
-
●7.6拓扑排序
可以用有向图中的顶点来表示活动, 弧表示活动之间的优先关系, 这样的有向图称为 (Activity On Vertex network) ，简称为AOV网。本节主要讲解了AOV网的拓扑序列算法，求解整个工程得以顺利完成的一种可行方案。
-
第八章排序
排序的目的是使数据有序，有序的数据可以加速查找过程，因此排序是计算机信息处理中最深用、也是最重要的运算之一。其方法很多，应用也很广泛。本章将介绍排序的基本概念并讨论常用的、经典的排序算法。从算法设计的角度看，这些精彩的算法展示了重要的程序设计思想与巧妙的程序实现技术。
-
●8.1排序的基本概念
主要讲述排序的基本概念。
-
●8.2插入排序
主要讲述插入排序。插入排序又分为直接插入排序，折半插入排序和希尔排序。
-
●8.3交换排序
交换排序。详细介绍冒泡排序和快速排序两种交换排序算法。其中比较重要的是冒泡排序。
-
●8.4选择排序
选择排序。本节主要介绍简单选择，排序和堆排序。其中比较重要的是堆排序。
-
●8.5归并排序
归并排序，本节讨论归并排序是指二路归并排序。
-
●8.6基数排序
介绍不需要关键字比较的排序算法——基数排序。
-
●8.7外排序简介
介绍外排序的基本情况，有兴趣的同学可以看书中的内容，继续学习外排序相关排序算法。