数据结构

第1章 绪论1
1.1 数据结构的研究内容和作用1
1.2 数据结构相关的基本概念3
1.2.1 基本概念3
1.2.2 数据结构3
1.3 算法及其描述和分析5
1.3.1 算法及其设计原则5
1.3.2 算法的描述5
1.3.3 算法效率的衡量方法6
1.3.4 算法的存储空间需求7
习题18
第2章 线性表10
2.1 线性表的逻辑结构10
2.1.1 线性表的定义10
2.1.2 线性表的基本操作11
2.2 线性表的顺序表示及其实现12
2.2.1 顺序表12
2.2.2 顺序表上的基本操作实现13
2.2.3 顺序表应用举例17
2.3 线性表的链式表示及其实现18
2.3.1 单链表18
2.3.2 单链表基本运算及其实现19
2.3.3 循环链表23
2.3.4 双向链表24
2.3.5 静态链表26
2.4 一元多项式的表示27
2.5 线性表的应用举例29
习题230
第3章 栈和队列33
3.1 栈33
3.1.1 栈的定义及基本运算33
3.1.2 栈的存储与操作实现34
3.1.3 栈的应用举例36
3.2 队列43
3.2.1 队列的定义及基本运算43
3.2.2 队列的存储表示和操作的实现44
3.2.3 队列应用举例47
习题350
◆数据结构目 录第4章 串52
4.1 串的定义、表示和实现52
4.1.1 串的基本概念52
4.1.2 串的基本操作53
4.2 串的存储和基本运算实现54
4.2.1 串的定长顺序存储与基本运算实现54
4.2.2 串的堆存储与基本运算实现56
4.2.3 串的块链存储与基本运算实现57
4.3 串的模式匹配58
4.3.1 简单模式匹配算法58
4.3.2 改进的模式匹配算法59
4.4 串的应用举例63
习题465
第5章 数组和广义表66
5.1 数组66
5.1.1 数组的定义66
5.1.2 数组的顺序存储结构66
5.2 特殊矩阵的压缩存储 68
5.2.1 对称矩阵 68
5.2.2 下(上)三角矩阵 69
5.2.3 对角矩阵69
5.3 稀疏矩阵的压缩存储70
5.3.1 稀疏矩阵定义70
5.3.2 稀疏矩阵的压缩存储方法--三元组表70
5.3.3 稀疏矩阵的压缩存储方法--十字链存储法74
5.4 广义表75
5.4.1 广义表的概念和基本操作75
5.4.2 广义表的存储结构76
5.4.3 广义表基本操作的实现79
习题582
第6章 树和二叉树84
6.1 树的类型定义84
6.2 二叉树85
6.2.1 二叉树的类型定义85
6.2.2 二叉树的几个特性86
6.2.3 二叉树的基本操作87
6.3 二叉树的存储87
6.3.1 顺序存储结构87
6.3.2 链式存储结构88
6.4 二叉树的操作90
6.4.1 二叉树的遍历90
6.4.2 二叉树的其他操作算法举例92
6.5 线索二叉树94
6.5.1 二叉树的线索链表94
6.5.2 以中序线索链表为存储结构的中序遍历96
6.5.3 线索链表的生成96
6.6 树和森林97
6.6.1 树的存储结构97
6.6.2 树、森林与二叉树的相互转换101
6.6.3 树、森林的遍历102
6.6.4 应用举例103
6.7 哈夫曼树及其应用104
6.7.1 最优二叉树的定义104
6.7.2 最优二叉树的构造方法105
6.7.3 最优前缀编码106
6.7.4 哈夫曼编码算法的实现108
习题6110
第7章 图112
7.1 图的基本概念112
7.1.1 图的定义和术语112
7.1.2 图的基本操作116
7.2 图的存储结构116
7.2.1 邻接矩阵117
7.2.2 邻接表119
7.3 图的遍历121
7.3.1 深度优先遍历121
7.3.2 广度优先遍历123
7.4 图的连通性124
7.4.1 图的连通性及其判定124
7.4.2 生成树与最小生成树125
7.5 有向无环图及其应用129
7.5.1 有向无环图的概念129
7.5.2 AOV网与拓扑排序130
7.5.3 AOE网与关键路径133
7.6 最短路径139
7.6.1 求某一顶点到其余各顶点的最短路径139
7.6.2 求任意一对顶点之间的最短路径142
7.7 应用举例144
习题7148
第8章 查找151
8.1 静态查找表151
8.1.1 顺序查找152
8.1.2 有序表的折半查找153
8.1.3 分块查找155
8.2 动态查找表156
8.2.1 二叉排序树156
8.2.2 平衡二叉树160
8.2.3 B-树和B+树165
8.3 哈希表171
8.3.1 哈希表与哈希方法171
8.3.2 常用的哈希函数172
8.3.3 处理冲突的方法174
8.3.4 哈希表的查找分析176
习题8177
第9章 排序179
9.1 内排序算法179
9.1.1 插入排序179
9.1.2 交换排序186
9.1.3 选择排序189
9.1.4 二路归并排序193
9.1.5 基数排序195
9.2 外排序算法199
习题9200
参考文献203