数据结构与C++PDF电子书下载

第1章 抽象数据类型和C++语言 1

1.1 抽象数据类型 1

1.1.1 问题的处理 1

1.1.2 抽象数据类型的性质 2

1.1.3 数据结构的封装 2

1.1.4 抽象数据类型的形式化表示 3

1.1.5 ADT线性表 5

1.2 从C到C++ 7

1.2.1 数据类型 7

1.2.2 函数 9

1.2.3 类和对象 10

1.2.4 构造函数 11

1.2.5 析构函数 13

1.3 面向对象的概念 13

1.3.1 继承 13

1.3.2 多重继承 16

1.3.3 多态性 17

1.3.4 动态聚束 20

1.3.5 抽象类 21

1.3.6 操作符重载 21

1.3.7 友元 24

第2章 数组与字符串 26

2.1 数组的表示 26

2.1.1 一维数组 26

2.1.2 二维数组 27

2.1.3 三角矩阵 28

2.2 动态数组 34

2.2.1 动态内存分配 34

2.2.2 设计并实现一个数组类 35

2.2.3 下标操作 37

2.2.4 赋值运算 38

2.2.5 指针转换 39

2.2.6 改变数组的大小 40

2.3.1 类String的定义 41

2.3 字符串 41

2.3.2 字符串的创建与废除 45

2.3.3 赋值运算 46

2.3.4 关系运算 46

2.3.5 串的连接 47

2.3.6 输入输出 48

2.3.7 其它串操作 49

3.1 栈 53

第3章 栈与队列 53

3.1.1 栈的实现 54

3.1.2 栈的应用 58

3.2 通用数据类型 61

3.2.1 模板函数 62

3.2.2 模板类 63

3.3 队列 66

3.3.1 队列的实现 67

3.3.2 队列的应用 73

3.3.3 优先队列 75

第4章 链表 77

4.1 链表的表示 78

4.1.1 链表的逻辑结构 78

4.1.2 结点的表示 79

4.1.3 结点的操作 81

4.1.4 链表的实现 82

4.2 链表的应用 85

4.2.1 多项式相加 85

4.2.2 用链表方式实现的堆栈 90

4.2.3 用链表方式实现队列 92

4.3 链表类 93

4.3.1 链表类的数据成员 93

4.3.2 链表类的函数成员 94

4.3.3 链表类的实现 96

第5章 树 103

5.1 树的定义和基本术语 103

5.2 二叉树 105

5.3.1 基于数组的二叉树 106

5.3 二叉树的表示 106

5.3.2 基于链表的二叉树 108

5.4 二叉树的遍历 110

5.5 二叉树的操作 113

5.5.1 创建一棵二叉树 113

5.5.2 复制二叉树 114

5.5.3 删除一棵二叉树 117

5.5.5 计算树的深度 118

5.5.4 统计叶子结点个数 118

5.6 二叉树类 119

5.7 哈夫曼树 120

5.7.1 哈夫曼编码 120

5.7.2 哈夫曼算法的实现 121

5.8 线索二叉树 126

5.8.1 线索二叉树的概念 126

5.8.2 线索二叉树的实现 128

5.9 树与二叉树的转换 129

6.1 图的基本术语 132

第6章 图 132

6.2 ADT图 134

6.3 图的表示 135

6.4 图的实现 137

6.4.1 图的初始化 139

6.4.2 图的插入和删除操作 140

6.4.3 查找邻接点 143

6.5 图的遍历 144

6.5.1 深度优先搜索 145

6.5.2 广度优先搜索 147

6.5.3 图遍历算法的复杂度 149

6.6 最短路径 150

6.7 最小代价生成树 154

6.7.1 Prim算法 155

6.7.2 Kruskal算法 158

6.8 拓扑排序 161

7.1.1 冒泡排序 163

7.1 几种简单的排序算法 163

第7章 排序 163

7.1.2 选择排序 165

7.1.3 插入排序 166

7.2 快速排序 167

7.2.1 基本思想 167

7.2.2 算法 171

7.2.3 快速排序算法的时间复杂度分析 172

7.3 锦标赛排序 173

7.4 堆排序 177

7.4.1 堆 177

7.4.2 堆类 179

7.4.3 堆的插入和删除操作 180

7.4.4 把一个数组改造成一个堆 183

7.4.5 堆排序算法 186

7.4.6 堆排序算法的时间复杂度分析 189

8.1 顺序表的查找 190

8.1.1 顺序查找 190

第8章 查找 190

8.1.2 二叉查找 191

8.2 二叉查找树 192

8.2.1 二叉查找树的抽象数据类型 192

8.2.2 二叉查找树类 193

8.2.3 二叉查找树的操作 194

8.2.4 二叉查找树操作的时间复杂度 200

8.3.1 AVL树的结点类 201

8.3 AVL树 201

8.3.2 AVL树类 202

8.3.3 AVL树的插入操作 203

8.3.4 AVL树的删除操作 213

8.4 哈希表 218

8.4.1 哈希函数 218

8.4.2 解决冲突的办法 220

8.4.3 哈希表类 222

8.4.4 哈希表的操作 223

参考文献 226