数据结构与算法（高职高专计算机技能型紧缺人才培养规划教材计算机软件技术专业）

　　内容提要数据结构是计算机软件相关专业的核心课程之一，主要讲授数据结构和算法的原理、方法和技术。从研究对象来说，包括向量、链表、矩阵、堆栈、队列、串、树和图等；从常用算法来说，包括查找和排序等。本书的每一章都从数据结构的基本思想出发，一直讲授到标准模板库（STL）的有关内容。通过本书的学习，读者可以熟悉C++开发技术，特别是面向对象的程序设计；掌握算法设计和数据结构设计的基本方法；掌握如何评价、选择和使用各种库函数所实现的算法；理解并学会使用STL。本书可作为高职高专院校计算机软件专业教材，也可作为计算机软件专业本科学生的参考书，对于从事计算机软件开发的技术人员也有一定参考价值。

暂缺《数据结构与算法（高职高专计算机技能型紧缺人才培养规划教材计算机软件技术专业）》作者简介

第1章　面向对象程序设计基础　1
1.1　C++基本特征　1
1.1.1　重载　1
1.1.2　缺省参数函数与内置函数　3
1.1.3　引用及其使用　3
1.1.4　动态内存分配　7
1.2　类和对象　8
1.2.1　声明类和对象　9
1.2.2　在类外定义成员函数　10
1.2.3　类数组.类指针与函数的类参数　11
1.2.4　this指针　14
1.3　构造函数与析构函数　15
1.3.1　构造函数　15
1.3.2　析构函数　16
1.4　继承与派生　17
1.4.1　建立派生类　18
1.4.2　公用派生类与私有派生类　19
1.4.3　保护成员　20
1.4.4　友元函数与友元类　20
1.5　C++模板　23
1.5.1　函数模板　23
1.5.2　类模板　25
习题　26
第2章　数据结构导论　31
2.1　数据结构的基本概念　31
2.1.1　几个实例　31
2.1.2　数据结构的术语　33
2.1.3　抽象数据类型及其实现　34
2.2　算法描述　35
2.2.1　算法的特性　35
2.2.2　算法描述与通用性　35
2.2.3　类和算法的测试　38
2.3　C++标准模板库简介　38
2.4　算法分析初步　41
习题　44
第3章　向量　47
3.1　向量的基本知识　47
3.1.1　线性表的定义　47
3.1.2　向量的存储结构　47
3.2　向量运算　48
3.2.1　向量运算简介　48
3.2.2　插入算法与删除算法　49
3.3　简易向量类　52
3.3.1　简易向量类及其实现　52
3.3.2　简易向量类的测试　54
3.4　标准模板向量类　55
3.4.1　模板向量类的构造器及下标运算符　55
3.4.2　模板向量类的迭代器　56
3.4.3　模板向量类的成员函数　58
3.4.4　insert类算法和erase类算法分析　58
3.4.5　模板向量类的一般表示　61
3.5　模板向量容器的测试类　62
3.5.1　模板向量测试类的数据输入　62
3.5.2　模板向量测试类的源代码　63
3.5.3　模板向量测试类的使用　66
3.6　矩阵类　67
3.6.1　矩阵容器的描述　68
3.6.2　模板矩阵类的使用　69
习题　71
第4章　链表　73
4.1　链表存储结构的基本知识　73
4.1.1　单链表与指针　73
4.1.2　单链表的基本运算　75
4.2　简易的单链表类　79
4.2.1　单链表类源代码　79
4.2.2　单链表类的测试　80
4.3　循环链表和双向链表　82
4.3.1　循环链表　82
4.3.2　双向链表　82
4.4　标准模板双向链表类　83
4.4.1　模板链表类的一般表示　84
4.4.2　构造器　84
4.4.3　模板链表类的迭代器　85
4.4.4　模板链表类的成员函数　87
4.5　模板链表容器的测试类　89
4.5.1　模板链表测试类的数据输入　89
4.5.2　模板链表测试类的源代码　89
4.5.3　模板链表测试类的使用　93
习题　95
第5章　栈和队列　97
5.1　栈　97
5.1.1　栈的定义及运算　97
5.1.2　栈的向量存储结构　98
5.1.3　简易向量栈类　98
5.1.4　栈的链表存储结构　102
5.1.5　简易链表栈类　103
5.2　模板栈容器　108
5.2.1　模板栈容器的实现　108
5.2.2　栈的接口　109
5.2.3　使用栈容器　110
5.3　队列的基本知识　115
5.3.1　队列的定义及运算　115
5.3.2　队列的向量存储结构　116
5.3.3　简易的循环队列类　117
5.3.4　队列的链表存储结构　120
5.4　模板队列容器　124
5.4.1　deque容器　124
5.4.2　queue容器　125
习题　128
第6章　字符串　133
6.1　字符与字符串的概念　133
6.2　C风格字符串的存储结构与运算　134
6.2.1　C风格字符串的顺序存储结构　134
6.2.2　C风格字符串的链表存储结构　135
6.2.3　C风格字符串的运算　136
6.3　字符串类　138
6.3.1　字符串类对象的声明　139
6.3.2　字符串类的构造器　140
6.3.3　字符串类的运算　141
6.4　模板容器与字符串类　144
习题　148
第7章　查找　151
7.1　查找方法概述　151
7.2　顺序查找　152
7.2.1　简单顺序查找方法　152
7.2.2　一般线性表的顺序查找　153
7.3　有序表的查找　156
7.3.1　有序表的建立　156
7.3.2　有序表的折半查找法　157
7.3.3　折半查找法的应用　161
7.4　标准模板库的查找算法　164
7.4.1　STL迭代器　164
7.4.2　STL查找运算　165
7.5　哈希表及其查找　169
7.5.1　哈希表与哈希函数　169
7.5.2　设计哈希函数　171
7.5.3　闭散列方法　173
7.5.4　哈希类的向量版本　176
7.5.5　开散列方法与哈希类的链表版本　179
习题　183
第8章　排序　187
8.1　排序基本概念　187
8.2　3种基本的排序方法　188
8.2.1　直接插入排序　188
8.2.2　冒泡排序　189
8.2.3　选择排序　191
8.2.4　基本排序方法的向量版本　192
8.3　高级排序方法　194
8.3.1　希尔排序　194
8.3.2　快速排序　195
8.3.3　归并排序　198
8.3.4　基数排序　200
8.4　标准模板库的通用排序方法　202
习题　209
第9章　树　212
9.1　二叉树　212
9.1.1　树的常用术语　212
9.1.2　二叉树的定义　213
9.1.3　二叉树的重要性质　213
9.1.4　二叉树的存储结构　214
9.2　遍历二叉树　215
9.2.1　先根遍历　216
9.2.2　中根遍历　217
9.2.3　后根遍历　218
9.2.4　按层遍历　219
9.2.5　二叉树遍历算法的应用　220
9.3　二叉链表模板类　221
9.3.1　二叉链表类的输入类　222
9.3.2　二叉链表类的模板结点类　222
9.3.3　二叉链表基类　223
9.3.4　二叉链表类派生的应用类　228
9.4　二叉搜索树模板类　231
9.4.1　二叉搜索树的基本知识　231
9.4.2　定位函数与查找算法的实现　235
9.4.3　二叉搜索树类及其测试　237
9.4.4　二叉搜索树插入算法与删除算法的实现　240
9.4.5　输出二叉树结点表算法的实现　245
习题　248
第10章　图　250
10.1　图的基本概念和术语　250
10.1.1　图的概念　250
10.1.2　路径和回路　251
10.1.3　连通图　251
10.1.4　顶点的度　252
10.2　图的存储结构　252
10.2.1　邻接矩阵　252
10.2.2　基于邻接矩阵的模板图类　253
10.2.3　邻接链表　258
10.2.4　基于邻接链表的模板图类　259
10.3　图的遍历及其应用　264
10.3.1　图的深度优先搜索遍历　265
10.3.2　图的广度优先搜索遍历　268
10.3.3　图遍历的应用　269
10.3.4　图的遍历类　272
10.4　图的生成树　276
10.4.1　生成树的概念　276
10.4.2　最小生成树　277
10.4.3　Prim算法　280
10.4.4　Kruskal算法　284
10.5　最短路径　288
10.5.1　单源顶点最短路径问题求解　289
10.5.2　关于源点最短路径的讨论　292
习题　294