第1章 概述 1
1.1数据结构的基本概念 2
1.2抽象数据类型 5
1.2.1抽象数据类型的定义 5
1.2.2抽象数据类型的描述 6
1.3算法的特性与算法的描述 7
1.3.1算法的定义 7
1.3.2算法的特性 7
1.3.3算法的描述 8
1.4算法分析 9
1.4.1算法设计的要求 9
1.4.2算法效率评价 10
1.4.3时间复杂度 11
1.4.4空间复杂度 13
1.5如何学好数据结构 14
1.5.1数据结构课程的地位 14
1.5.2数据结构课程的重要性 14
1.5.3如何学好数据结构 15
第2章 C语言基础 17
2.1开发环境介绍 18
2.1.1 Turbo C 2.0开发环境介绍 18
2.1.2 Visual C+++ 6.0开发环境介绍 20
2.2递归与非递归 24
2.2.1函数的递归调用 24
2.2.2递归函数应用举例 25
2.2.3一般递归转化为非递归（使用迭代） 27
2.3指针 28
2.3.1指针变量 28
2.3.2指针变量的引用 29
2.3.3指针与数组 30
2.3.4函数指针与指针函数 35
2.4参数传递 42
2.4.1传值调用 42
2.4.2传地址调用 43
2.5结构体与共用体 46
2.5.1结构体的定义 46
2.5.2指向结构体的指针 48
2.5.3共用体及应用 49
2.6动态内存分配与释放 50
2.6.1内存动态分配与释放 50
2.6.2链表 51
2.7小结 56
2.8习题 57
第3章 线性表 59
3.1线性表的概念及抽象数据类型 60
3.1.1线性表的定义 60
3.1.2线性表的抽象数据类型 61
3.2线性表的顺序表示与实现 62
3.2.1线性表的顺序存储结构 62
3.2.2顺序表的基本运算 63
3.2.3顺序表基本运算的算法分析 66
3.3顺序表的应用举例 67
3.4线性表的链式表示与实现 72
3.4.1单链表的存储结构 72
3.4.2单链表上的基本运算 74
3.5单链表应用举例 79
3.6循环单链表 87
3.6.1循环链表的链式存储 87
3.6.2循环单链表的应用 88
3.7双向链表 93
3.7.1双向链表的存储结构 93
3.7.2双向链表的插入操作和删除操作 94
3.8双向链表的应用 96
3.9静态链表 99
3.9.1静态链表的存储结构 99
3.9.2静态链表的实现 100
3.9.3静态链表的应用 102
3.10各种线性表的操作 104
3.11一元多项式的表示与相乘 111
3.11.1一元多项式的表示 112
3.11.2一元多项式相乘 113
3.12小结 117
3.13习题 118
第4章 栈 121
4.1栈的表示与实现 122
4.1.1栈的定义 122
4.1.2栈的抽象数据类型 123
4.2栈的顺序表示与实现 124
4.2.1栈的顺序存储结构 124
4.2.2顺序栈的基本运算 125
4.2.3共享栈的问题 127
4.3栈的应用举例 129
4.4栈的链式表示与实现 132
4.4.1栈的存储结构 133
4.4.2栈的基本运算 133
4.4.3链栈的应用 136
4.5栈的应用举例 137
4.5.1数制转换 137
4.5.2括号配对 139
4.5.3行编辑程序 141
4.6栈与递归的实现 143
4.6.1递归 143
4.6.2消除递归 146
4.7栈的应用举例 152
4.7.1表达式的转换与运算 152
4.7.2表达式的运算举例 154
4.8小结 158
4.9习题 159
第5章 队列 161
5.1队列的定义 162
5.1.1队列的定义 162
5.1.2队列的抽象数据类型 162
5.2队列的顺序存储及实现 163
5.2.1顺序队列的表示 163
5.2.2顺序队列的“假溢出” 166
5.2.3顺序循环队列的表示 167
5.2.4顺序循环队列的实现 168
5.2.5顺序循环队列实例 170
5.3队列的链式存储及实现 173
5.3.1链式队列的表示 173
5.3.2链式队列的实现 175
5.3.3链式队列实例 177
5.4双端队列 181
5.4.1双端队列的定义 181
5.4.2双端队列的应用 181
5.5队列在杨辉三角中的应用 184
5.5.1杨辉三角 184
5.5.2杨辉三角的队列构造 185
5.5.3杨辉三角队列的实现 185
5.6小结 189
5.7习题 190
第6章 串 191
6.1串 192
6.1.1串的定义 192
6.1.2串的抽象数据类型 192
6.2串的顺序表示与实现 195
6.2.1串的顺序存储结构 195
6.2.2串的基本运算 196
6.3串的应用举例 201
6.4串的堆分配表示与实现 202
6.4.1堆分配的存储结构 202
6.4.2堆串的基本运算 203
6.5堆串的应用举例 209
6.6串的链式存储表示与实现 210
6.6.1串的链式存储结构 210
6.6.2链串的基本运算 212
6.7链串的应用举例 217
6.8串的模式匹配 219
6.8.1经典的模式匹配算法 Brute-Force 219
6.8.2 KMP算法 220
6.8.3模式匹配应用举例 226
6.9小结 230
6.10习题 230
第7章 数组 233
7.1数组 234
7.1.1数组的定义 234
7.1.2数组的抽象数据类型 235
7.2数组的顺序表示与实现 235
7.2.1数组的顺序存储结构 236
7.2.2数组的基本运算 237
7.2.3数组的应用举例 239
7.3特殊矩阵的压缩存储 241
7.3.1对称矩阵的压缩存储 241
7.3.2三角矩阵的压缩存储 242
7.3.3对角矩阵的压缩存储 243
7.4稀疏矩阵的压缩存储 243
7.4.1稀疏矩阵的定义 244
7.4.2稀疏矩阵抽象数据类型 244
7.4.3稀疏矩阵的三元组表示 245
7.4.4稀疏矩阵的三元组实现 246
7.5稀疏矩阵的应用举例 252
7.5.1稀疏矩阵相乘的三元组表示 252
7.5.2稀疏矩阵的相乘三元组实现 254
7.6稀疏矩阵的十字链表表示与实现 257
7.6.1稀疏矩阵的十字链表表示 257
7.6.2十字链表的实现 258
7.7稀疏矩阵的十字链表实现应用举例 261
7.8小结 266
7.9习题 267
第8章 广义表 269
8.1广义表 270
8.1.1广义表的定义 270
8.1.2广义表的抽象数据类型 271
8.2广义表的头尾链表表示与实现 271
8.2.1广义表的头尾链表存储结构 272
8.2.2广义表的基本运算 273
8.2.3广义表的应用举例 275
8.3广义表的扩展线性链表表示与实现 278
8.3.1广义表的扩展线性链表存储 278
8.3.2广义表的基本运算 279
8.3.3采用扩展线性链表存储结构的广义表应用举例 282
8.4小结 284
8.5习题 285
第9章 树 287
9.1树 288
9.1.1树的定义 288
9.1.2树的逻辑表示 289
9.1.3树的抽象数据类型 290
9.2二叉树 291
9.2.1二叉树的定义 291
9.2.2二叉树的性质 293
9.2.3二叉树的抽象数据类型 294
9.3二叉树的存储表示与实现 295
9.3.1二叉树的顺序存储 296
9.3.2二叉树的链式存储 296
9.3.3二叉树的基本运算 297
9.4二叉树的遍历 301
9.4.1二叉树遍历的定义 301
9.4.2二叉树的先序遍历 301
9.4.3二叉树的中序遍历 303
9.4.4二叉树的后序遍历 305
9.5二叉树的遍历的应用举例 307
9.5.1二叉树的创建 308
9.5.2二叉树的输出 311
9.5.3二叉树的计数 315
9.6二叉树的线索化 318
9.6.1二叉树的线索化定义 318
9.6.2二叉树的线索化 319
9.6.3线索二叉树的遍历 321
9.6.4线索二叉树的应用举例 323
9.7树、森林与二叉树 326
9.7.1树的存储结构 326
9.7.2树转换为二叉树 328
9.7.3森林转换为二叉树 330
9.7.4二叉树转换为树和森林 330
9.7.5树和森林的遍历 331
9.8哈夫曼树 332
9.8.1哈夫曼树的定义 332
9.8.2哈夫曼编码 334
9.8.3哈夫曼编码算法的实现 334
9.9树与二叉树的应用举例 340
9.9.1相似二叉树 340
9.9.2由先序和中序、中序和后序确定二叉树 341
9.9.3树的孩子兄弟链表应用举例 347
9.10小结 350
9.11习题 350
第10章 图 353
10.1图的定义与相关概念 354
10.1.1图的定义 354
10.1.2图的相关概念 354
10.1.3图的抽象数据类型 357
10.2图的存储结构 358
10.2.1邻接矩阵表示法 358
10.2.2邻接表表示法 360
10.2.3十字链表表示法 361
10.2.4邻接多重链表表示法 362
10.3图的应用举例 364
10.3.1采用邻接矩阵创建图 364
10.3.2采用邻接表创建图 367
10.4图的遍历 370
10.4.1图的深度优先遍历 370
10.4.2图的广度优先遍历 373
10.4.3图的遍历应用举例 375
10.5图的连通性问题 377
10.5.1无向图的连通分量与生成树 378
10.5.2最小生成树 379
10.6有向无环图 384
10.6.1 AOV网与拓扑排序 384
10.6.2 AOE网与关键路径 387
10.6.3关键路径应用举例 392
10.7最短路径 396
10.7.1从某个顶点到其余各顶点的最短路径 397
10.7.2每一对顶点之间的最短路径 402
10.8图的应用举例 406
10.8.1距离某个顶点的最短路径长度为k的所有顶点 406
10.8.2求图中顶点u到顶点v的简单路径 409
10.9小结 411
10.10习题 412
第11章 查找 413
11.1查找的基本概念 414
11.2静态查找 414
11.2.1顺序表的查找 415
11.2.2有序顺序表的查找 416
11.2.3索引顺序表的查找 418
11.2.4静态查找应用举例 420
11.3动态查找 422
11.3.1二叉排序树 423
11.3.2平衡二叉树 430
11.4 B-树与B+树 438
11.4.1 B-树 438
11.4.2 B+树 446
11.5哈希表 447
11.5.1哈希表的定义 447
11.5.2哈希函数的构造方法 448
11.5.3处理冲突的方法 449
11.5.4哈希表应用举例 451
11.6小结 454
11.7习题 455
第12章 排序 457
12.1排序的基本概念 458
12.2插入排序 459
12.2.1直接插入排序 459
12.2.2折半插入排序 460
12.2.3希尔排序 461
12.2.4插入排序应用举例 462
12.3选择排序 464
12.3.1简单选择排序 464
12.3.2堆排序 465
12.3.3选择排序应用举例 470
12.4交换排序 471
12.4.1冒泡排序 471
12.4.2快速排序 473
12.4.3交换排序应用举例 475
12.5归并排序 479
12.5.1归并排序算法 479
12.5.2归并排序应用举例 481
12.6基数排序 482
12.6.1基数排序算法 483
12.6.2基数排序应用举例 486
12.7各种排序算法的比较 489
12.8 排序算法应用举例 490
12.9小结 494
12.10习题 495
参考文献 496