数据结构 抽象建模、实现与应用

本书以理解和实现物理世界里各种联系在信息世界中的逻辑表示以及在计算机中实现数据结构的存储和操作为主线，介绍数据结构的相关知识。主要内容包括数据结构的概念、算法和算法设计的概念，线性表、桟和队列、数组、广义表和字符串、树和二叉树、图、査找、排序等典型数据结构及应用。本书内容凝炼、深入浅出，适合作为髙校理工科及相关专业数据结构课程的教材。

前言
第1章概论1
1.1引言1
1.2数据结构相关概念及术语1
1.3抽象数据类型的表示与实现3
1.4算法与算法分析6
1.4.1算法6
1.4.2算法分析与度量8
1.5小结10
1.6练习10
第2章线性表11
2.1引言11
2.2线性表的抽象数据类型11
2.3线性表的顺序表示与实现15
2.3.1顺序表的定义和特点15
2.3.2顺序表的存储结构15
2.3.3顺序表基本操作的实现与性能分析16
2.4线性表的链式表示与实现19
2.4.1单链表20
2.4.2其他形式的链表24
2.5线性表的应用举例27
2.6小结31
2.7练习31
第3章栈和队列32
3.1引言32
3.2栈的抽象数据类型32
3.3栈的顺序表示与实现33
3.4栈的链式表示与实现36
3.5栈的应用举例37
3.5.1逆序输出问题37
3.5.2最近匹配与比较问题38
3.5.3递归与回溯问题43
3.6队列的抽象数据类型47
3.7队列的顺序表示与实现48
3.8队列的链式表示与实现50
3.9队列的应用举例52
3.10小结53
3.11练习53
第4章数组、广义表和字符串54
4.1引言54
4.2数组54
4.2.1一维数组54
4.2.2二维数组55
4.3特殊矩阵的压缩存储56
4.3.1对称矩阵56
4.3.2对角矩阵57
4.4稀疏矩阵的压缩存储57
4.4.1稀疏矩阵的三元组表示57
4.4.2三元组的顺序表表示58
4.4.3三元组的十字链表表示61
4.5广义表62
4.5.1广义表的概念62
4.5.2广义表的抽象数据类型63
4.5.3广义表的存储结构64
4.6字符串66
4.6.1字符串的抽象数据类型66
4.6.2字符串的存储结构与子串定位67
4.7小结68
4.8练习68
第5章树和二叉树70
5.1引言70
5.2树的定义和基本术语70
5.2.1树的定义70
5.2.2树的逻辑表示71
5.2.3树的基本术语72
5.2.4树的抽象数据类型72
5.3二叉树73
5.3.1二叉树的定义73
5.3.2二叉树的抽象数据类型74
5.3.3二叉树的性质76
5.3.4二叉树的存储结构77
5.3.5二叉树的遍历79
5.3.6二叉树遍历算法的
应用举例81
5.4树和森林85
5.4.1树与二叉树的转换85
5.4.2森林与二叉树的转换86
5.4.3树和森林的遍历87
5.5霍夫曼树88
5.5.1霍夫曼树的定义88
5.5.2霍夫曼树的构造90
5.5.3霍夫曼编码90
5.5.4霍夫曼树和霍夫曼编码的算法实现92
5.6小结94
5.7练习94
第6章图95
6.1引言95
6.2图的定义、基本术语和抽象数据类型95
6.3图的存储方式97
6.3.1邻接矩阵97
6.3.2邻接表99
6.4图的遍历101
6.4.1深度优先遍历101
6.4.2广度优先遍历102
6.4.3图的遍历算法的应用举例103
6.5最小生成树107
6.5.1最小生成树的定义107
6.5.2普里姆算法108
6.5.3克鲁斯卡尔算法111
6.6拓扑排序与关键路径112
6.6.1拓扑排序112
6.6.2AOE网与关键路径113
6.7最短路径问题116
6.7.1单源最短路径问题116
6.7.2所有顶点对之间的最短路径119
6.8小结121
6.9练习122
第7章查找123
7.1引言123
7.2查找表的定义与抽象数据类型123
7.3顺序表的静态查找124
7.3.1顺序查找125
7.3.2折半查找126
7.3.3索引查找129
7.4树表的动态查找130
7.4.1二叉排序树130
7.4.2平衡二叉排序树138
7.4.3B-树141
7.4.4B+树146
7.5哈希表的查找147
7.5.1哈希表的定义147
7.5.2哈希函数的构造方法148
7.5.3处理冲突的方式150
7.5.4哈希表的查找152
7.5.5性能分析153
7.6小结155
7.7练习156
第8章排序157
8.1引言157
8.2排序的定义与分类157
8.2.1排序的定义157
8.2.2排序的分类157
8.2.3排序的数据类型158
8.3插入排序158
8.3.1直接插入排序158
8.3.2希尔排序160
8.4交换排序162
8.4.1简单交换排序162
8.4.2快速排序164
8.5选择排序166
8.5.1简单选择排序167
8.5.2树形选择排序168
8.5.3堆排序169
8.6归并排序173
8.7基数排序175
8.7.1多关键字的排序175
8.7.2基数排序的实现176
8.8各种内部排序方法的比较178
8.9小结179
8.10练习179