第一部分 数据结构的基本概念 2
第1章 绪论 2
1.1数据结构概述 2
1.1.1几个非数值计算问题 2
1.1.2数据结构在计算机学科中的地位 3
1.1.3数据结构课程的发展史 4
1.1.4数据结构课程的学习特点 4
1.2基本概念及术语 4
1.2.1关于数据的基本概念 4
1.2.2关于数据结构的基本概念 5
1.2.3关于数据类型的基本概念 5
1.3算法和算法分析 6
1.3.1算法的概念与特性 7
1.3.2算法时间效率的度量 8
1.3.3算法空间效率的度量 9
1.4用C语言描述数据结构和算法：知识回顾 10
习题与上机实验题 12
第二部分 基本的数据结构 16
第2章 线性表 16
2.1线性表的基本概念及运算 16
2.1.1线性表的定义和术语 16
2.1.2线性表的抽象数据类型 16
2.2线性表的顺序存储结构 17
2.2.1顺序表的定义及特点 17
2.2.2顺序表的类型定义 18
2.2.3顺序表上基本操作的实现 18
2.2.4一个应用实例 23
2.2.5顺序表的总结 25
2.3线性表的链式存储结构 25
2.3.1单链表的定义及特点 26
2.3.2单链表上基本操作的实现 27
2.3.3循环链表 30
2.3.4双向链表 31
2.3.5静态链表 32
2.4线性表的应用举例 34
2.4.1用线性表表示集合 34
2.4.2用线性表表示一元多项式 34
习题与上机实验题 36
第3章 栈和队列 39
3.1栈 39
3.1.1栈的定义和抽象数据类型描述 39
3.1.2栈的顺序存储结构 40
3.1.3栈的链式存储结构 42
3.2栈的应用举例 43
3.2.1数制转换 43
3.2.2括号匹配的检验 44
3.2.3表达式求值 44
3.2.4栈与递归 47
3.3队列 50
3.3.1队列的定义和抽象数据类型描述 50
3.3.2队列的链式存储结构 50
3.3.3队列的顺序存储结构 52
3.4队列的应用举例 54
3.4.1打印杨辉三角形 54
3.4.2停车场管理 55
习题与上机实验题 55
第4章串 59
4.1串的定义 59
4.1.1串的基本概念 59
4.1.2串的抽象数据类型 60
4.2串的存储结构 60
4.2.1串的顺序存储结构 60
4.2.2串的链式存储结构 63
4.3串的模式匹配 64
4.3.1朴素的模式匹配算法 64
4.3.2 KMP算法 65
4.4串的应用举例 69
4.4.1文本编辑 69
4.4.2建立词索引表 70
习题与上机实验题 73
第5章 数组 76
5.1数组的定义和特点 76
5.1.1数组的定义 76
5.1.2数组的特点 77
5.2数组的顺序存储表示 77
5.3矩阵的压缩存储 79
5.3.1特殊矩阵的压缩存储 79
5.3.2稀疏矩阵的压缩存储 81
5.4矩阵的应用举例 85
习题与上机实验题 88
第6章 广义表 90
6.1广义表的基本概念 90
6.2广义表的存储结构和基本运算 91
6.3广义表的应用举例 94
习题与上机实验题 96
第7章 树和二叉树 98
7.1树的定义和术语 98
7.2二叉树 100
7.2.1二叉树的定义 100
7.2.2二叉树的性质 101
7.2.3二叉树的存储结构 103
7.3二叉树的遍历 105
7.3.1递归形式的先、中、后序遍历 105
7.3.2非递归形式的先、中、后序遍历 106
7.3.3层序遍历 109
7.3.4二叉树遍历的应用举例 109
7.4二叉树的线索化 110
7.4.1线索二叉树的概念 110
7.4.2线索二叉树的遍历 112
7.4.3二叉树的线索化过程 112
7.5树和森林 113
7.5.1树的存储结构 113
7.5.2树、森林与二叉树的相互转换 115
7.5.3树和森林的遍历 116
7.6哈夫曼树及其应用 116
7.6.1哈夫曼树的定义 116
7.6.2哈夫曼编码及数据压缩 119
7.6.3哈夫曼编码的实现 120
习题与上机实验题 121
第8章图 124
8.1图的基本概念 124
8.2图的存储结构 127
8.2.1数组表示法 127
8.2.2邻接表 129
8.3图的遍历 131
8.3.1深度优先搜索 131
8.3.2广度优先搜索 132
8.3.3图的遍历的应用举例 134
8.4最小生成树 134
8.4.1普里姆算法 134
8.4.2克鲁斯卡尔算法 136
8.5有向无环图及其应用 137
8.5.1拓扑排序 137
8.5.2关键路径 139
8.6最短路径 143
8.6.1单源最短路径 144
8.6.2任意两个顶点之间的最短路径 146
习题与上机实验题 148
第三部分 数据结构的基本技术 152
第9章 查找 152
9.1查找的基本概念 152
9.2基于线性表的查找 153
9.2.1顺序查找 154
9.2.2折半查找 155
9.2.3分块查找 157
9.3基于树的查找 158
9.3.1二叉排序树 158
9.3.2平衡二叉排序树 163
9.3.3 B-树和B+树 166
9.4基于散列表的查找 170
9.4.1散列表的定义及术语 171
9.4.2散列函数的构造方法 171
9.4.3处理冲突的方法 173
9.4.4散列表的插入 175
9.4.5散列表的查找及性能分析 177
习题与上机实验题 177
第10章 排序 181
10.1概述 181
10.1.1排序的基本概念 181
10.1.2内部排序方法 182
10.2插入排序 183
10.2.1直接插入排序 183
10.2.2折半插入排序 184
10.2.3表插入排序 185
10.2.4希尔排序 187
10.3交换排序 189
10.3.1冒泡排序 189
10.3.2快速排序 190
10.4选择排序 193
10.4.1简单选择排序 193
10.4.2树形选择排序 194
10.4.3堆排序 195
10.5归并排序 199
10.6基数排序 200
10.6.1多关键字排序 200
10.6.2链式基数排序 201
10.7各种内部排序方法的性能比较 204
10.8外部排序 204
10.8.1外部排序过程 205
10.8.2多路平衡归并 206
10.8.3置换-选择排序 209
10.8.4最佳归并树 211
习题与上机实验题 213
参考文献 217