数据结构教程（第二版）

第1章?绪论
1.1?什么是数据结构1
*1.2?数据结构的发展简史及其在计算机科学中的地位5
1.3?算法5
1.3.1?算法及其性质5
1.3.2?基本算法7
1.3.3?算法的描述8
1.4?算法分析12
1.4.1?时间复杂度12
1.4.2?空间复杂度15
1.4.3?其他方面16
习题16
第2章?线性表
2.1?线性表的定义及其基本操作21
2.1.1?线性表的定义21
2.1.2?线性表的基本操作22
2.2?线性表的顺序存储结构23
2.2.1?顺序存储结构的构造23
2.2.2?几种常见操作的实现25
2.2.3?顺序存储结构小结30
2.3?线性链表及其操作31
2.3.1?线性链表的构造31
2.3.2?线性链表的基本算法34
2.4?循环链表及其操作50
2.5?双向链表及其操作53
2.5.1?双向链表的构造53
2.5.2?双向链表的插入与删除算法54
*2.6?链表的应用举例57
2.6.1?链式存储结构下的一元多项式相加57
2.6.2?打印文本文件的最后n行60
习题63
第3章?数组
3.1?数组的概念69
3.2?数组的存储结构69
3.3?矩阵的压缩存储71
3.3.1?对称矩阵的压缩存储72
3.3.2?对角矩阵的压缩存储73
3.4?稀疏矩阵的三元组表表示74
3.4.1?稀疏矩阵的三元组表存储方法74
*3.4.2?稀疏矩阵的转置算法75
*3.4.3?稀疏矩阵的相加算法78
*3.4.4?稀疏矩阵的相乘算法79
*3.5?稀疏矩阵的链表表示81
3.5.1?线性链表存储方法82
3.5.2?带行指针向量的链表存储方法83
3.5.3?十字链表存储方法83
3.6?数组的应用举例88
3.6.1?一元多项式的数组表示88
3.6.2?n阶魔方89
习题91
第4章?堆栈和队列
4.1?堆栈的概念及其操作95
4.1.1?堆栈的定义95
4.1.2?堆栈的基本操作96
4.2?堆栈的顺序存储结构96
4.2.1?顺序堆栈的构造97
4.2.2?顺序堆栈的基本算法97
*4.2.3?多个堆栈共享连续空间99
4.3?堆栈的链式存储结构102
4.3.1?链接堆栈的构造103
4.3.2?链接堆栈的基本算法103
4.4?堆栈的应用举例106
4.4.1?符号匹配检查106
4.4.2?数制转换107
4.4.3?堆栈在递归中的应用108
4.4.4?表达式的计算113
4.4.5?又一个趣味游戏——迷宫117
4.5?队列的概念及其操作120
4.5.1?队列的定义120
4.5.2?队列的基本操作121
4.6?队列的顺序存储结构121
4.6.1?顺序队列的构造121
4.6.2?顺序队列的基本算法123
4.6.3?循环队列124
4.7?队列的链式存储结构127
4.7.1?链接队列的构造127
4.7.2?链接队列的基本算法128
习题131
第5章?广义表
5.1?广义表的基本概念136
5.2?广义表的存储结构137
*5.3?多元多项式的表示141
习题143
第6章?串
6.1?串的基本概念145
6.1.1?串的定义145
6.1.2?串的几个概念146
6.2?串的基本操作146
6.3?串的存储结构148
6.3.1?串的顺序存储结构149
6.3.2?串的链式存储结构150
6.4?串的几个操作151
习题157
第7章?树与二叉树
7.1?树的基本概念158
7.1.1?树的定义158
7.1.2?树的逻辑表示方法160
7.1.3?基本术语161
7.1.4?树的性质163
7.1.5?树的基本操作164
*7.2?树的存储结构164
7.2.1?多重链表表示法165
7.2.2?三重链表表示法166
7.3?二叉树167
7.3.1?二叉树的定义167
7.3.2?二叉树的基本操作168
7.3.3?两种特殊形态的二叉树169
7.3.4?二叉树的性质169
*7.3.5?二叉树与树、树林之间的转换171
7.4?二叉树的存储结构174
7.4.1?二叉树的顺序存储结构174
7.4.2?二叉树的链式存储结构176
7.5?二叉树与树的遍历180
7.5.1?二叉树的遍历181
7.5.2?由遍历序列恢复二叉树189
7.5.3?二叉树的等价性190
*7.5.4?树和树林的遍历191
7.5.5?基于二叉树遍历操作的算法举例192
7.6?线索二叉树199
7.6.1?线索二叉树的构造200
7.6.2?线索二叉树的利用201
*7.6.3?二叉树的线索化204
*7.6.4?线索二叉树的更新205
7.7?二叉排序树206
7.7.1?二叉排序树的定义206
7.7.2?二叉排序树的建立206
*7.7.3?在二叉排序树中删除结点209
7.7.4?二叉排序树的查找212
*7.8?平衡二叉树215
7.9?哈夫曼树及其应用222
7.9.1?哈夫曼树的概念222
*7.9.2?哈夫曼编码223
习题227
第8章?图
8.1?图的基本概念233
8.1.1?图的定义和基本术语233
8.1.2?图的基本操作237
8.2?图的存储方法238
8.2.1?邻接矩阵存储方法238
8.2.2?邻接表存储方法240
*8.2.3?有向图的十字链表存储方法244
*8.2.4?无向图的多重邻接表存储方法245
8.3?图的遍历246
8.3.1?深度优先搜索247
8.3.2?广度优先搜索