21世纪高等学校计算机教育实用规划教材PDF电子书下载

第0章C+程序设计语言预备知识 1

0.1一个简单C++语言程序 1

0.1.1 C++程序基本结构 2

0.1.2 C++程序基本组成 2

0.1.3简单的输入/输出 4

0.2指针与引用 5

0.2.1指针 5

0.2.2引用 6

0.3动态存储分配 7

0.4函数 7

0.4.1函数的定义与调用 8

0.4.2函数的参数传递 8

0.4.3函数原型与带默认参数的函数 11

0.4.4重载函数 13

0.5类与对象 14

0.5.1类 14

0.5.2对象 16

0.5.3构造函数与析构函数 17

0.5.4友元函数 19

0.6运算符重载 20

0.6.1用成员函数重载运算符 21

0.6.2用友元函数重载运算符 22

0.7模板 24

0.7.1模板的概念 24

0.7.2函数模板 25

0.7.3类模板 27

第1章 绪论 33

1.1数据结构的产生和发展 33

1.2数据结构研究的内容 34

1.3基本概念和术语 36

1.3.1数据和数据元素 36

1.3.2数据结构 36

1.4算法 38

1.4.1算法的定义及特性 38

1.4.2算法的描述 39

1.4.3算法设计的目标 39

1.4.4算法的分析 39

1.5习题 42

第2章 线性表 44

2.1线性表的逻辑结构 44

2.1.1线性表的定义 44

2.1.2线性表的操作 44

2.2线性表的顺序存储结构 45

2.2.1顺序表 46

2.2.2顺序表基本运算的实现 47

2.2.3小结 51

2.3线性表的链式存储结构 52

2.3.1单链表 52

2.3.2单循环链表 59

2.3.3双链表 61

2.4顺序表和链表的比较 64

2.5线性表的应用 65

2.5.1一元多项式的表示 65

2.5.2一元多项式的存储结构 65

2.5.3一元多项式加法的算法分析与实现 66

2.6习题 68

第3章 栈和队列 72

3.1栈 72

3.1.1栈的逻辑结构 72

3.1.2顺序栈 73

3.1.3链栈 79

3.2队列 82

3.2.1队列的逻辑结构 82

3.2.2顺序队列 82

3.2.3链队列 87

3.3栈的应用 90

3.3.1问题描述 90

3.3.2算法的分析与实现 90

3.4习题 91

第4章串 96

4.1串的逻辑结构 96

4.1.1串的基本概念 96

4.1.2串的基本操作 97

4.1.3常用的C++字符串函数 97

4.2串的顺序存储结构 99

4.2.1顺序串 99

4.2.2顺序串基本操作的实现 101

4.2.3模式匹配 105

4.3串的链式存储结构 107

4.4串的应用 108

4.4.1问题描述 108

4.4.2算法的设计与实现 109

4.5习题 110

第5章 数组和广义表 113

5.1数组 113

5.1.1数组的逻辑结构 113

5.1.2数组的顺序存储结构 113

5.2矩阵的压缩存储 115

5.2.1特殊矩阵 115

5.2.2稀疏矩阵 118

5.3广义表 123

5.3.1广义表的逻辑结构 123

5.3.2广义表的存储结构 125

5.3.3广义表基本操作的实现 127

5.4多维数组的应用 130

5.4.1问题描述 130

5.4.2设计要求 131

5.4.3算法的分析与实现 131

5.5习题 133

第6章 树和二叉树 137

6.1树的逻辑结构 137

6.1.1树的定义 137

6.1.2树的表示方法 138

6.1.3树的基本术语 139

6.1.4树的基本运算 140

6.2树的顺序存储结构 140

6.2.1双亲表示法 140

6.2.2孩子链表表示法 141

6.2.3双亲孩子表示法 143

6.2.4孩子兄弟表示法 144

6.3二叉树的逻辑结构 144

6.3.1二叉树的概念 144

6.3.2二叉树的基本性质 146

6.3.3二叉树的遍历操作 148

6.3.4由遍历序列恢复二叉树 149

6.4二叉树的存储结构 150

6.4.1二叉树的顺序存储结构 150

6.4.2二叉链表 151

6.4.3三叉链表 159

6.5线索二叉树 160

6.5.1线索二叉树的定义及结构 160

6.5.2线索二叉树基本操作的实现 162

6.6树、森林与二叉树的转换 165

6.7树的应用 168

6.7.1哈夫曼树的基本概念 168

6.7.2哈夫曼算法 169

6.7.3哈夫曼编码 172

6.8习题 175

第7章图 179

7.1图的逻辑结构 179

7.1.1图的定义 179

7.1.2图的基本术语 179

7.1.3图的基本操作 184

7.2图的存储结构 185

7.2.1邻接矩阵 185

7.2.2邻接表 191

7.2.3邻接矩阵和邻接表的比较 198

7.3图的遍历 199

7.3.1深度优先搜索遍历 199

7.3.2广度优先搜索遍历 203

7.4生成树和最小生成树 205

7.4.1生成树与生成森林 205

7.4.2最小生成树 207

7.5最短路径 213

7.5.1单源最短路径 213

7.5.2所有顶点对之间的最短路径 216

7.6 DAG图及其应用 219

7.6.1 DAG的概念 219

7.6.2 AOV网与拓扑排序 221

7.6.3 AOE网与关键路径 224

7.7习题 229

第8章 排序 235

8.1概述 235

8.1.1排序的基本术语 235

8.1.2排序方法的分类 236

8.1.3排序算法的基本操作和存储方式 237

8.1.4排序算法性能评价 237

8.2插入排序 239

8.2.1直接插入排序 239

8.2.2折半插入排序 240

8.2.3希尔排序 242

8.3交换排序 244

8.3.1冒泡排序 244

8.3.2快速排序 245

8.4选择排序 248

8.4.1直接选择排序 249

8.4.2堆排序 250

8.5归并排序 256

8.6基数排序 259

8.7各种内排序方法的比较和选择 262

8.8习题 263

第9章 查找 267

9.1概述 267

9.1.1基本概念 267

9.1.2查找算法的性能 268

9.2线性表的查找 268

9.2.1顺序查找 269

9.2.2二分查找 270

9.2.3分块查找 273

9.3树表的查找 275

9.3.1二叉排序树 275

9.3.2平衡二叉树 282

9.4散列表的查找 291

9.4.1散列表的概念 291

9.4.2常用的散列函数 292

9.4.3处理冲突的方法 294

9.4.4散列表上的运算 298

9.4.5查找性能的分析 301

9.5习题 302

附录 实验内容 306

实验1线性表 306

实验2栈和队列 307

实验3串 307

实验4数组和广义表 308

实验5树和二叉表 309

实验6图 309

实验7排行 310

实验8查找 310

参考文献 312