本书介绍了数据结构的相关知识和基本概念以及数据结构的使用方法
数据结构与算法
王立柱 编著
基于STL（Standard Template Library）框架描述数据结构是大势所趋，而在自实现的STL框架下实现数据结构，几乎是每一个程序爱好者的理想。本书作者根据多年的教学经验，帮助读者实现了这个理想。
本书特点
面向更广大的读者。本书在开始就介绍了从C到C++的过程，只学过C语言的读者也可以很顺利地进入C++的学习。
自实现STL框架。本书实现了STL的String、Vector、List和适配器的简化版，读者不仅可以学习泛型程序设计，而且为实现数据结构提供了有力工具。
多媒体软件既助教又助学。配套的多媒体软件使结构、算法、代码、运行过程和结果综合展现，使复杂抽象的算法和程序变得简单，对排序、堆、平衡二叉树、最短路径等难度很大的算法，效果尤其明显，对初学者更是意义非凡。
本书适用于三种读者：只学过C的、只学过C++的，或学过C和C++的。
第1章比较详细地介绍从C到C++的过程。通过这一章，只学过C的读者，可以很顺利地进入C++；只学过C++的读者，可以居高临下地学习C；学过C和C++的读者，可以从发展的角度深刻地领会C++。
第2章~第4章实现了容器和算法标准库的String、Vector、List和适配器的简化版，使读者不仅学习了泛型程序设计，而且为实现数据结构提供了有力工具。
第5章~第13章主要是在定义STL框架下描述的数据结构。
本书将一些经典的算法纳入相应的数据结构。例如，将快速排序和幂集归入二叉树前序遍历，将汉诺塔问题并入二叉树中序遍历，把哈夫曼树作为堆的直接应用，把八皇后和迷宫问题分别放在树和图的深度优先遍历中解决，更全面地体现了学习数据结构的意义。
本书为了保持连贯性，特别将算法性能分析放在最后一章，先让读者集中精力学习算法设计和实现，在熟悉了大量经典算法的基础上，最后结合排序算法学习算法性能分析，即算法的时间和空间复杂度分析。
本书配有用Authorware开发的多媒体课件，既可助教又可助学，直观生动，使复杂抽象的算法和程序变得简单，对排序、堆、平衡二叉树、最短路径等难度很大的算法，效果尤其明显，对初学者更是意义非凡。
本书提供教学课件和源代码，读者可以登录华章网站（http://www.hzbook.com）下载。
读者如有问题或发现错误，欢迎直接与作者联系（E-mail:tjwanglizhu@163.com），作者将不胜感激。
王立柱
2013年4月
计算机\数据结构
基于STL（Standard Template Library）框架描述数据结构是大势所趋，而在自实现的STL框架下实现数据结构，几乎是每一个程序爱好者的理想。本书作者根据多年的教学经验，帮助读者实现了这个理想。
本书特色：
面向更广大的读者。比较详细地介绍了从C到C++的过程，只学过C语言的读者，也可以很顺利地进入C++的学习。
自实现STL框架。实现了STL的String、Vector、List和适配器的简化版，使读者不仅可以学习泛型程序设计，而且为实现数据结构提供了有力工具。
多媒体软件既助教又助学。配套的多媒体软件使结构、算法、代码、运行过程和结果综合展现；直观生动，使复杂抽象的算法和程序变得简单，对排序、堆、平衡二叉树、最短路径等难度很大的算法，效果尤其明显，对初学者更是意义非凡。
王立柱：暂无
出版者的话
编委会
丛书序言
前言
教学建议
第1章 从C到C++ 1
1.1 从数组到顺序表 1
1.1.1 数组的局限性 1
1.1.2 顺序表的声明 2
1.1.3 顺序表的实现 4
1.1.4 删除顺序表的重复数据 7
1.1.5 数据抽象 8
1.2 C语言的局限性 10
1.3 C++基础知识 13
1.3.1 变量和const常量 13
1.3.2 输入/输出 13
1.3.3 内联函数 16
1.3.4 运算符重载 17
1.3.5 函数重载 18
1.3.6 引用型 19
1.3.7 构造函数 25
1.3.8 提取符和插入符重载 25
1.3.9 默认参数 27
1.3.10 new和delete运算符 28
1.4 C++顺序表类 28
1.4.1 从C顺序表到C++顺序表类 28
1.4.2 顺序表类的实现 32
1.4.3 复制构造函数 33
1.4.4 复制赋值运算符重载 34
1.4.5 下标运算符重载 35
1.4.6 构造函数与初始化 36
1.4.7 new和delete运算符与构造和析构 36
1.4.8 类定义 37
1.5 函数模板和类模板 37
1.5.1 函数模板 37
1.5.2 顺序表类模板 40
1.6 继承和多态性 41
1.6.1 构造函数的参数初始化表 41
1.6.2 继承 43
1.6.3 受保护成员 45
1.6.4 多态性和虚函数 46
1.6.5 虚析构函数 49
1.6.6 纯虚函数和抽象类 50
习题 52
第2章 String类 55
2.1 String类的声明 55
2.2 String类的实现 57
2.2.1 构造和析构 57
2.2.2 成员赋值运算符 59
2.2.3 成员转换 60
2.2.4 串连接 61
2.2.5 关系运算 64
2.2.6 求子串 65
2.2.7 子串插入 67
2.2.8 子串删除 69
2.2.9 下标运算符 71
2.2.10 字符查找 71
2.2.11 输入/输出 71
2.3 模式匹配 73
2.4 深入讨论 74
2.4.1 转换赋值运算符函数的替代 74
2.4.2 成员函数“类串+C串”的替代 75
2.4.3 explicit修饰符 75
习题 76
第3章 向量类模板Vector 78
3.1 Vector定义 78
3.2 通用算法和迭代器 81
3.3 Vector的插入和删除函数 84
3.4 求素数 85
3.5 函数对象 86
3.6 深入讨论——函数模板实例化中的问题 88
习题 88
第4章 链表类模板和适配器 90
4.1 链表类模板List 90
4.2 适配器 97
4.2.1 链栈 97
4.2.2 链队列 98
4.2.3 优先级链队列 98
习题 99
第5章 二叉树 100
5.1 二叉树的基本概念 100
5.2 二叉树的性质 101
5.3 二叉树的存储结构 102
5.3.1 二叉树顺序存储结构 102
5.3.2 二叉树链式存储结构 103
5.4 二叉树层次遍历 105
5.4.1 层次遍历 105
5.4.2 把二叉树的顺序存储转化为链式存储 108
5.4.3 垂直输出二叉树 108
5.5 二叉树前序遍历 111
5.5.1 前序遍历递归算法 111
5.5.2 前序遍历非递归算法 112
5.5.3 快速排序 112
5.5.4 集合的幂集 114
5.6 二叉树中序遍历 116
5.6.1 中序遍历递归算法 116
5.6.2 中序遍历非递归算法 117
5.6.3 汉诺塔递归算法 117
5.7 二叉树后序遍历 119
5.7.1 后序遍历递归算法 119
5.7.2 后序遍历非递归算法 119
5.7.3 求二叉树的深度以及二叉链表的复制和删除 120
5.7.4 把二叉树的顺序存储转化为链式存储的递归算法 121
5.7.5 由前序和中序序列建立二叉链表 122
习题 123
第6章 堆 124
6.1 小根堆Heap类 124
6.2 堆排序 129
6.3 哈夫曼树 131
6.3.1 哈夫曼树的定义 131
6.3.2 建立哈夫曼树 132
6.3.3 哈夫曼编码 133
习题 134
第7章 树 135
7.1 树的基本概念和存储 135
7.2 Tree类 138
7.3 树的遍历 141
7.4 八皇后 144
习题 147
第8章 图 148
8.1 图的基本概念 148
8.2 Graph类 151
8.3 图的遍历 160
8.3.1 广度优先遍历 160
8.3.2 深度优先遍历 162
8.4 最小生成树 163
8.4.1 普里姆算法 164
8.4.2 克鲁斯卡尔算法 170
8.5 最短路径 173
8.5.1 求单源最短路径的迪克斯特拉算法 173
8.5.2 所有顶点对之间的最短带权路径 179
8.5.3 一顶点对之间的最短带权路径 183
8.6 拓扑序列 186
8.7 关键路径 189
8.8 迷宫求解 194
习题 197
第9章 二叉搜索树 198
9.1 类型声明与实现 198
9.2 中序迭代器 203
9.3 频率统计 206
9.4 中序线索二叉树 207
习题 208
第10章 平衡二叉搜索树 209
10.1 动态平衡方法 209
10.2 平衡二叉搜索树类型 213
习题 216
第11章 B树 217
11.1 线性索引 217
11.2 静态m路搜索树 218
11.3 B_树 219
11.4 B+树 223
习题 224
第12章 散列 225
12.1 散列表 225
12.2 散列函数 226
12.2.1 平方取中法 226
12.2.2 除留余数法 227
12.2.3 折叠法 227
12.2.4 数字分析法 228
12.3 分离链接法 228
12.4 开放定址法 230
12.4.1 线性探查法 231
12.4.2 平方探查法 231
12.4.3 双散列函数探查法 231
习题 231
第13章 排序和性能分析 232
13.1 性能分析 232
13.1.1 时间复杂性分析 232
13.1.2 空间复杂性分析 233
13.2 插入排序 234
13.2.1 直接插入排序 234
13.2.2 折半插入排序 235
13.2.3 希尔排序 237
13.3 交换排序 238
13.3.1 起泡排序 238
13.3.2 快速排序 239
13.4 选择排序 240
13.4.1 直接选择排序 240
13.4.2 堆排序 241
13.4.3 锦标赛排序 242
13.5 归并排序 246
13.5.1 归并 246
13.5.2 迭代归并排序 247
13.6 基数排序 248
13.7 外排序 249
13.7.1 外排序的基本过程 250
13.7.2 k路归并 251
习题 253
