目录 1
第1章课程概论 1
1.1课程的初步认识 1
1.2数据结构的基本概念 3
1.2.1 基本术语 3
1.2.2数据结构的概念 4
1.2.3逻辑结构和物理结构 4
1.2.4数据结构形式定义 5
1.3数据类型及面向对象概念 6
1.3.1数据类型概述 6
1.3.2抽象数据类型 6
1.3.3实现方法 7
1.3.4面向对象的概念 9
1.4算法及算法分析 10
1.4.1 算法特性 10
1.4.2算法描述 11
1.4.3算法设计的要求 11
1.4.4算法分析 12
1.5实习一：常用算法 14
第2章线性表 15
2.1线性表实例及概念 15
2.2线性表的存储方式 17
2.2.1线性表的顺序存储结构 17
2.2.2线性表的链式存储结构 18
2.3线性表的类定义及其实现 21
2.3.1顺序表的类定义及实现 21
2.3.2单链表的类定义及实现 26
2.3.3静态链表的类定义及实现 31
2.3.4双向循环链表的类定义及实现 33
2.4实习二：顺序表演示程序 35
2.4.1 问题说明 35
2.4.2界面外观及功能要求 36
2.4.3实现要点 36
2.4.4类定义 37
2.4.6界面功能的实现 38
2.4.5组件设置 38
2.4.7程序清单 39
第3章栈 42
3.1 栈的应用实例及概念 42
3.2栈的存储方式 43
3.2.1 栈的顺序存储结构 44
3.2.2栈的链式存储结构 45
3.3栈的类定义及其实现 45
3.3.1顺序栈的类定义及实现 46
3.3.2链栈的类定义及实现 48
3.4应用实例 50
3.4.1 表达式中括号配对的合法性检查 50
8.2.4二叉树的类定义 1 51
3.4.2表达式求值 51
3.5实习三：链栈演示程序 55
3.5.1 问题说明 55
3.5.2界面外观及功能要求 56
3.5.3实现要点 56
3.5.4类定义 56
3.5.5组件设置 57
3.5.6界面功能的实现 57
3.5.7程序清单 58
第4章队列 61
4.1 队列的应用实例及概念 61
4.2队列的存储方式 62
4.2.1 队列的链式存储结构 63
4.2.2队列的顺序存储结构 64
4.3队列的类定义及其实现 66
4.3.1 循环队列的类定义及实现 66
4.3.2链队列的类定义及实现 68
4.4应用实例 71
4.5.1 问题说明 73
4.5实习四：循环队列演示程序 73
4.5.2界面外观及功能要求 74
4.5.3实现要点 74
4.5.4类定义及其实现 75
4.5.5组件设置 76
4.5.6界面功能的实现 76
4.5.7程序清单 76
5.1 串的应用实例及概念 80
第5章串 80
5.2.1顺序存储结构 82
5.2串的存储结构 82
5.2.2链式存储结构 83
5.3顺序串的类定义及实现 84
5.3.1 顺序串的类定义 84
5.3.2求子串及子串定位操作的实现 85
5.3.3删除、插入及替换操作的实现 87
5.4实习五：串的演示程序 90
5.4.1 问题说明 90
5.4.2界面外观及功能要求 90
5.4.3实现要点 91
5.4.4类定义 91
5.4.5组件设置 92
5.4.6界面功能的实现 92
5.4.7程序清单 93
第6章二维数组 96
6.1二维数组应用实例及概念 96
6.2二维数组的存储方式 97
6.3矩阵的类定义及实现 99
6.3.1矩阵的类定义 99
6.3.2矩阵类定义的实现 100
6.4矩阵的压缩存储 102
6.4.1对称矩阵的压缩存储 103
6.4.2对角矩阵的压缩存储 103
6.4.3稀疏矩阵的压缩存储 104
6.5稀疏矩阵的类定义及实现 107
6.5.1稀疏矩阵类定义 107
6.5.2稀疏矩阵类定义的实现 108
6.6.2界面外观及功能要求 111
6.6实习六：八皇后演示程序 111
6.6.1 问题说明 111
6.6.3实现要点 112
6.6.4线程类定义 113
6.6.6界面功能的实现 114
6.6.5组件设置 114
6.6.7程序清单 115
第7章广义表 119
7.1 广义表的定义与基本运算 119
7.2广义表的存储方式 121
7.2.1头尾表示法 121
7.2.2儿子兄弟表示法 123
7.3广义表的类定义及实现 124
7.3.1 广义表的类定义 124
7.3.2取头、取尾及合并操作的实现 125
7.3.3建立广义表的存储结构 125
7.3.4打印广义表 129
7.4广义表的递归算法 130
7.4.1 广义表的相等比较 131
7.4.2广义表的成员判别 132
7.4.3广义表的复制 132
7.4.4求广义表的深度 133
7.5实习七：广义表演示程序 135
7.5.1问题说明 135
7.5.2界面外观及功能要求 135
7.5.3实现要点 136
7.5.4类定义及实现 136
7.5.5组件设置 137
7.5.6界面功能的实现 137
7.5.7程序清单 138
第8章树与二叉树 143
8.1树的基本概念 143
8.1.1树的定义及应用 143
8.1.2树的逻辑表示 144
8.1.3基本术语 145
8.1.4树的基本操作 146
8.2.1定义 147
8.2.2基本性质 147
8.2二叉树 147
8.2.3存储结构 149
8.2.5 二义树类定义的买现 152
8.2.6二叉树的遍历 155
8.3排序二叉树 159
8.3.1排序二叉树的定义 159
8.3.2排序二叉树的类定义 159
8.3.3排序二叉树类定义的实现 160
8.4树与森林 161
8.4.1树的存储结构 161
8.4.2森林与二叉树的转换 163
8.4.3树的遍历 164
8.5.1哈夫曼树的定义 165
8.5哈夫曼树 165
8.5.2哈夫曼树的构造 166
8.5.3哈夫曼编码 167
8.6实习八：二叉树遍历演示程序 169
8.6.1问题说明 169
8.6.2界面外观及功能要求 169
8.6.3实现要点 170
8.6.4类定义及实现 170
8.6.5组件设置 171
8.6.6界面功能的实现 171
8.6.7程序清单 172
9.1 图的实例及概念 176
9.1.1实例及定义 176
第9章图 176
9.1.2基本术语 178
9.1.3基本操作 180
9.2存储方式 180
9.2.1邻接矩阵 180
9.2.2邻接表 182
9.2.3邻接多重表 183
9.3图的遍历 185
9.3.1 图的类定义 185
9.3.2深度优先搜索遍历 186
9.3.3广度优先搜索遍历 188
9.4 图的应用 190
9.4.1拓扑排序 190
9.4.2最短路径 194
9.5实习九：图的遍历演示程序 196
9.5.1 问题说明 196
9.5.3实现要点 197
9.5.2界面外观及功能要求 197
9.5.4类定义及其实现 198
9.5.5组件设置 198
9.5.6界面功能的实现 198
9.5.7程序清单 199
第10章查找 203
10.1查找的有关概念 203
10.2静态查找表 204
10.2.1顺序表的查找 204
10.2.2有序表的查找 206
10.2.3静态树表的查找 209
10.2.4索引顺序表的查找 212
10.3动态查找表 213
10.3.1排序二叉树的查找 213
10.3.2 B-树与B+树 218
10.4哈希表 223
10.4.1 哈希表的概念 223
10.4.2哈希函数的种类 225
10.4.3冲突的处理方法 228
10.4.4哈希表的查找 229
10.5实习十：排序二叉树演示程序 230
10.5.1 问题说明 230
10.5.2界面外观及功能要求 230
10.5.3实现要点 231
10.5.4类定义及其实现 232
10.5.5组件设置 232
10.5.6界面功能的实现 233
10.5.7程序清单 233
第11章排序 237
11.1排序的有关概念 237
11.2简单的排序算法 239
11.2.1直接插入排序 240
11.2.2 冒泡排序 242
11.2.3简单选择排序 244
11.3快速排序法 246
11.3.1快速排序 246
11.3.2树形选择排序 249
11.3.3堆排序 250
11.3.4归并排序 254
11.4基数排序 257
11.5实习十一：排序算法演示程序 260
11.5.1 问题说明 260
11.5.2界面外观及功能要求 260
11.5.3实现要点 261
11.5.4线程类定义 261
11.5.5可视化功能的实现 262
11.5.7界面功能的实现 263
11.5.6组件设置 263
11.5.8程序清单 264
第12章外部排序 267
12.1外部排序概述 267
12.2多路归并排序 268
12.2.1 多路归并与败者树 268
12.2.2败者树类定义 269
12.2.3 调整算法 270
12.2.4初建树算法 271
12.2.5 K路归并算法 271
12.3置换选择排序 273
附录 276
附录A C++概要 276
附录B C++Builder开发环境概述 280
附录C参考文献 281