数据结构与算法分析c++描述
1. 引论
1.1. 本书讨论的内容
写出一个可以工作的程序是不够的，如果这个程序是在大规模的数据集上运行，那么运行时间就成了问题。 针对大规模的输入，我们要学会：
- 估计程序的运行时间 算法导论中有更详细的数学描述
- 在尚未编码的情况下比较两个程序的运行时间
- 提高程序的运行速度以及确定程序瓶颈的技巧
1.2. 数学知识复习
- 指数
- 对数
- 级数
- 模运算
- 证明方法
- 归纳法证明
- 通过反例证明
- 反证法证明
1.3. 递归的简单介绍
四条关键基本法则： 基准情况(base case):可以直接算出函数的值而不需要求助递归。 不断推进：对于那些要求递归解决的情形，递归调用必须总能朝着一个基准情形推进。 设计法则：假设所有的递归调用都能运行，没有必要去试图追踪大量的细节。 合成效益法则：在解决一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
1.4. c++类
1.4.1. 基本class语法
信息隐藏：将不需要对外部呈现的变量和信息定义在private标号下。
1.4.2. 特别的构造函数与访问函数
- 默认参数
- 初始化列表：代替赋值语句可以节省很多时间
如果一个数据成员是
const的就只能在初始化列表中进行初始化； 如果一个数据成员是不具有零参数的构造函数的类类型，该成员也必须在初始化列表中进行初始化。class IntCell { Public: explicit IntCell(int initialValue = 0) : storedValue( initialValue ) {} } explicit构造函数 所有的单参数构造函数都必须是explicit的，避免后台的类型转换。- 常量成员函数
在函数的声明后加一个
const关键字。 只进行检测但不改变对象的状态的成员函数称为访问函数，与之对应的是修改函数。
1.4.3. 接口与实现的分离
- 预处理命令
避免一个接口被读取两次
#ifndef IntCell_H #define IntCell_H …… #endif - 作用域运算符 通过这个将成员函数声明为类的一部分。
- 签名必须精确匹配
- 如基本类型一样声明对象
1.4.4. vector和string
使用vector来增强c语言中的内置数组。
使用string来增强c语言中的仅仅视作内置数组的字符串数组。
1.5. c++细节
1.5.1. 指针
一个例子：
int main() {
IntCell *m;
m = new IntCell(0);
m->write(5);
cout << "Cell contents: " << m->read() << endl;
delete m;
return 0;
}
- 声明
- 动态对象创建
- 垃圾收集以及
delete在一些语言中，当一个对象不再引用时，就纳入自动垃圾收集的范围。 在c++中可以使用自动变量来实现内存的自动释放。 - 指针的赋值和比较
- 通过指针访问对象的成员
1.5.2. 参数传递
- 传值(
call by value)int avg(int n) - 常量引用(
call by constant reference)int avg(const int &n) - 传址(
call by reference)int avg(int &n)
选用的原则：
- 如果形参能够改变实参的值，必须传址
- 否则
- 若是简单类型，传值
- 若是类类型，常量引用
总结如下：
- 按值调用适用于被函数更改的小对象。
- 按常量引用调用适用于不被函数更改的大对象。
- 引址调用适用于所有可以被函数更改的对象。
1.5.3. 返回值传递
同样的，返回值传递也可以有三种方式。
多数情况下不使用地址返回，而是直接使用返回值。 如果返回的对象是类类型的，比较常用常量引用返回。 需要注意的是这个引用对象的生命周期要长于这个被调用的函数，否则返回的是一个非法的地址。 如下例所示：
const string& findMax(const vector<string> & arr) {
int maxIndex = 0;
for (int i = 1; i < arr.size(); i++) {
if (arr[maxIndex] < arr[i])
maxIndex = i;
}
return arr[maxIndex];
}
问题：如何理解这里的常量？
这里的const指的是这个函数调用本身不能作为复制语句的左值，或者说这个函数调用整体不能被修改。例如：
const int & getInt(int &n)
{
return n;
}
int main() {
int n = 1;
getInt(n)++; // false
getInt(n) = 2; // false
int a = getInt(n); // correct
}
参考：函数返回值是const或者const引用,以引用方式接收的接受者不能对齐做修改，但是以拷贝方式接收的接受者是可以修改自己新拷贝的值的。如下所示：
const int & getInt(int &n)
{
return n;
}
int main()
{
int n=1;
int a = getInt(n); a++; // permit, &a != &n
const int &b = getInt(n); b++; // not permit
}
更好的例子可以查看1.7.2中的阐述。
1.5.4. 引用变量
可以分为引用变量和常量引用变量， 类似于变量别名的概念。
const string& findMax(const vector<string> & arr) {
int maxIndex = 0;
for (int i = 1; i < arr.size(); i++) {
if (arr[maxIndex] < arr[i])
maxIndex = i;
}
return arr[maxIndex];
}
// 引用变量
string x = findMax(a);
// 常量引用变量
const string &x = findMax(a);
1.5.5. 三大函数
析构函数 释放一个对象所占用的所有资源
复制构造函数
定义形式：
IntCell::IntCell(const InCell & rhs)
可以通过如下的形式进行调用:
- 声明的同时初始化，注意与
=操作符区分开。 - 使用按值调用传递
- 通过值返回对象
注意以上的后两种情况构造了用户不可见的临时对象。
operator= 将其应用于每个数据成员来实现。
默认值带来的问题
这里的默认值指的是三大函数的默认值。图1-13显示了三大函数的默认值。
问题：如果数据成员是指针，以上默认值不可用的情况下，该如何设置？
在复制构造的时候，如果这是直接复制这个指针，那么我们得到的两个类实例实际上指向了同一个对象，实际上我们期望得到的是整个对象的克隆。
简单来说，在复制构造的时候，如果默认值有意义，就接受默认值；否则就必须实现析构函数、operator=和复制构造函数。
一般来说，如果说析构函数是释放内存所必须的，那么复制赋值和复制构造函数的默认值就不适用。例子如下所示：
class IntCell
{
public:
explicit IntCell( int initialValue = 0 )
{ storedValue = new int{ initialValue }; }
~IntCell( )
{ delete storedValue; }
IntCell( const IntCell & rhs )
{ storedValue = new int{ *rhs.storedValue }; }
IntCell & operator= ( const IntCell & rhs )
{
if( this != & rhs )
*storedValue = *rhs.storedValue;
return *this;
}
int read( ) const
{ return *storedValue; }
void write( int x )
{ *storedValue = x; }
private:
int *storedValue;
};
1.6. 模板
用模板来些类型无关的算法(泛型算法)，常见的有函数模板和类模板。
1.6.1. 函数模板
在使用任何模板前，需要了解对特定的类型所需要的构造函数、操作函数的要求。 模板的实参应该定义为非基本数据类型，这也是采用常量引用的原因。
1.6.2. 类模板
同样的，类模板也对特定的类型有要求，例如这里举例的MemoryCell类模板，就要求需要零参数构造函数、复制构造函数和复制赋值运算符
1.6.3. comparable的例子
详见Fig01_21.cpp。
1.6.4. 函数对象
可以看下Fig01_22.cpp。
对应的消除了函数对象的版本：Fig01_23.cpp
1.6.5. 类模板的分离编译
曾经支持分离编译模板的编译器已经越来越弱化并且需要特殊的平台来支持。 所以为了增强跨平台性，整个类模板连同实现都放置在一个单独的头文件中。
1.7. 使用矩阵
详见matrix.h，对operator[]操作符的分析很精彩，对函数返回值的思考需要考虑周全。
2.3 要分析的问题
这里提出了53.maximum-subarray.cpp中的问题作为分析的对象。
2.4 运行时间计算
计算大O运行时间。
2.4.2 一般法则
分析的基本策略是从内部向外展开工作。 介绍运行时间计算的若干一般法则：
- for循环：运行时间*迭代次数
- 嵌套的循环：所有的for循环大小的乘机
- 顺序语句：各语句求和
if-else：max(if-statement, else-statement)- 递归调用：使用归纳法求解
2.4.3 最大子序列和问题的求解
- 序列的左半部分的最大子序列和
- 序列的右半部分的最大子序列和
- 横跨序列左半部分和右半部分得到的最大子序列和：对包含左半部分的最后一个元素的最大子序列和以及包含右半部分第一个元素的最大子序列和二者求和所得到的值
- 比较三者的大小，最大者即为所求的最大子序列和
参考分治策略结合递归思想求最大子序列和，代码如下所示：
int MaxSubSum(const vector<int> &a, int left, int right)
{
if (left == right) /* 递归的基准情形 */
return a[left];
int center = (left + right) / 2; /* 求分界点 */
int maxLeftSum = MaxSubSum(a, left, center); /* 递归，求左半部分子序列的最大子序列和 */
int maxRightSum = MaxSubSum(a, center + 1, right); /* 递归，求右半部分子序列的最大子序列和 */
/* 求横跨左半部分和右半部分的最大子序列和 */
/* 首先是左半部分子序列中包含最后一个元素的最大子序列和 */
int maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; --i) {
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
/* 接着是右半部分子序列中包含第一个元素的最大子序列和 */
int MaxRightBorderSum = a[center + 1], RightBorderSum = a[center + 1];
for (int i = center + 2; i <= right; ++i) {
RightBorderSum += a[i];
if (RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
/* Max3 返回左、右半部分子序列的最大子序列和以及横跨左、右半部分的最大子序列和中的最大者 */
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + MaxRightBorderSum);
}
3. 表、栈和队列
3.3. STL中的向量和表
3.3.1 迭代器
- 获得迭代器
begin()/end() - 迭代器方法
- 需要迭代器的容器操作
- insert
- erase
3.3.3 const_iterator
这种类型的迭代器指向的对象不能被修改。
如果传入的是常量容器，那么在使用迭代器访问该容器的时候就需要对应的使用const_iterator。
4.树
4.8 标准库中的set和map
4.8.1 set
set是一个排序后的容器。 特有的操作是高效的插入、删除和执行基本查找。
4.8.2 map
pair和map的区别是?
pair只是用来存储两个混合的对象，当每次从map中提取一个元素时，会得到一个pair类型的对象。
map是一个排序后的由键值组成的项的集合。
需要注意的是map中的[]操作，如果不存在key，将会在map中插入默认的值——<key, default_val>。
访问的技巧：
map<string, int> m;
map<string, int>::const_iterator itr;
for (itr = m.begin(); itr!=m.end(); ++itr) {
const pair<string, int> &entry = *itr;
int val = entry.second;
}
4.8.4 几个使用map的例子
一个不错的由数据结构来优化的例子。
- 法1: 暴力查找整个字典
- 法2: 将字典中的单词按长度分组查找
- 法3: 见单词分团处理，分而治之
10.2
分治算法由两部分组成：
- 分：递归解决较小的问题
- 治：然后从子问题的解构建原问题的解
传统上，在代码中至少含有两个递归调用的例程叫做分治算法，而代码中只含一个递归调用的例程不是分治算法。 例子：