《数据结构与C++》求取 ⇩

第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