第1章 绪论 1
1.1数据结构的基本概念 1
1.2抽象数据类型和软件构造方法 4
1.3算法和算法的时间复杂度 5
算法 5
算法设计的目标 7
算法时间效率的度量 7
1.4算法设计 11
1.5算法书写规范 14
1.6本课程内容概述 14
习题一 15
第2章 线性表 17
2.1线性表的抽象数据类型 17
2.2线性表的顺序表示和实现 18
顺序表的存储结构 18
顺序表的操作实现 19
顺序表操作的效率分析 22
顺序表的应用举例 22
2.3线性表的链式表示和实现 26
单链表的存储结构 26
单链表的操作实现 29
单链表操作的效率分析 34
单链表应用举例 35
循环单链表 36
双向链表 37
2.4设计举例 40
2.5本章小结 46
习题二 47
第3章 堆栈和队列 49
3.1堆栈 49
堆栈和堆栈的抽象数据类型 49
堆栈的顺序表示和实现 50
堆栈的链式表示和实现 53
3.2堆栈应用——表达式计算 58
3.3队列 61
队列和队列抽象数据类型 61
顺序队列 62
顺序循环队列的表示和实现 63
链式队列 66
队列的应用 69
3.4优先级队列 71
顺序优先级队列的设计和实现 71
优先级队列的应用 74
3.5本章小结 75
习题三 76
第4章串 79
4.1串 79
串及其基本概念 79
串的抽象数据类型 80
C语言的串函数 81
4.2串的存储结构 83
串的顺序存储结构 83
串的链式存储结构 84
4.3串基本操作的实现算法 85
4.4串的模式匹配算法 90
Brute-Force算法 90
KMP算法 92
Brute-Force算法和KMP算法的比较 96
4.5本章小结 98
习题四 99
第5章 数组 101
5.1数组的实现机制 101
5.2动态数组的设计方法 102
5.3特殊矩阵的压缩存储 105
5.4稀疏矩阵的压缩存储 106
稀疏矩阵的三元组顺序表 106
稀疏矩阵的三元组链表 110
5.5本章小结 111
习题五 112
第6章 递归 114
6.1递归的概念 114
6.2递归算法的执行过程 115
6.3递归算法的设计方法 118
6.4递归过程和运行时栈 120
6.5递归算法的效率分析 122
6.6递归算法到非递归算法的转换 123
6.7设计举例 126
一般递归算法设计举例 126
回溯法及设计举例 129
6.8本章小结 133
习题六 134
第7章 树和二叉树 137
7.1树 137
树的定义 137
树的表示方法 138
树的抽象数据类型 139
7.2二叉树 140
二叉树的定义 140
二叉树抽象数据类型 141
二叉树的性质 141
7.3二叉树的设计和实现 143
二叉树的存储结构 143
二叉链存储结构下二叉树的操作实现 145
二叉树的遍历及其实现 147
7.4线索二叉树 151
7.5哈夫曼树 153
哈夫曼树的基本概念 153
哈夫曼编码问题 155
哈夫曼编码问题设计和实现 156
7.6树的存储结构、转换和遍历 160
树的存储结构 160
树与二叉树的转换 162
树的遍历 163
7.7本章小结 164
习题七 165
第8章图 168
8.1图的基本概念 168
图的基本概念 168
图的抽象数据类型 170
8.2图的设计和实现 171
图的邻接矩阵存储结构 171
图的邻接表存储结构 172
邻接矩阵存储结构下图的操作实现 173
8.3图的遍历 177
图的深度和广度优先遍历算法 177
图的深度和广度优先遍历算法设计和实现 178
8.4最小生成树 181
最小生成树的基本概念 181
普里姆算法 182
普里姆函数设计和实现 183
克鲁斯卡尔算法 186
8.5最短路径 187
最短路径的基本概念 187
从一个顶点到其余各顶点的最短路径 188
狄克斯特拉算法设计和实现 189
8.6本章小结 192
习题八 192
第9章 排序 195
9.1排序的基本概念 195
9.2插入排序 197
直接插入排序 197
希尔排序 199
9.3选择排序 201
直接选择排序 201
堆排序 202
9.4交换排序 207
冒泡排序 207
快速排序 209
9.5归并排序 211
9.6综合应用举例 214
9.7本章小结 215
习题九 216
第10章 查找 218
10.1查找的基本概念 218
10.2静态查找表 219
顺序表 219
有序顺序表 220
索引顺序表 222
10.3动态查找表 224
二叉排序树 224
B/树 231
10.4哈希表 235
哈希表的基本概念 235
哈希函数构造方法 237
哈希冲突解决方法 238
哈希表设计举例 239
10.5本章小结 243
习题十 244
附录A上机实习内容规范 245
附录B上机实习范例 246
参考文献 257