数据结构与算法分析(c++描述)-01-引论

本文最后更新于：2021年7月2日

1.2 数学知识基础

todo…

1.3 递归的简单介绍

1. 递归的四条基本原则

（1）基准情形。必总有某些基准情形不用递归就能求解。

（2）不断推进。对于那些需要递归求解的情形，递归调用必须总能够朝着基准情形的方向推进。

（3）设计法则。假设所有的递归调用都能运行。

（4）合成效益法则（compound interest rule）。在求解一个问题的同一实例时，切勿在不同的

递归调用中做重复性的工作。

1.4 C++类

1.4.1 基础class语法

  1. c++中类由成员(member)构成
  2. 成员包括数据成员和成员函数(member funciton)
  3. 成员函数作用于对象，被称为方法(method)
  4. public和private，类中所有数据成员的默认属性都为privete

1.4.2 特别的构造函数语法与访问函数

1
2
3
4
5
6
7
8
class IntCell{
public:
    explict IntCell(int initialValue = 0) : storedValue(initialValue) { }
    int read() const {return storedValue;}
    int write(int x) {storedValue = x;}
private:
    int storedValue;
}
  1. 默认参数(default parameter)
  2. 初始化列表(initializer list)：
    • 在数据成员是具有复杂初始化过程的类类型的时候，使用初始化列表代替代码体中的赋值语句可以节省很多时间
    • 如果一个数据成员是const的，数据成员的值只能在初始化列表里进行初始化
  3. 所有的单参数的构造函数都是explicit的
  4. 访问函数(accessor)和修改函数(mutator)

1.4.3 接口与实现的分离

1. 预处理命令

  • 接口通常放在以.h结尾的文件中
  • 一个复杂的项目中有包含其他文件的文件，这样在编译一个文件时就存在一个接口被读两次的危险，这是非法的。为避免这种情况，每个头文件在读类接口时都定义一个预处理器来定义一个符号。
  • 符号名不应该再出现在其他文件中，通常该符号都是文件名。
1
2
3
4
#ifndef IntCell_H
#define IntCell_H

#endif

2. 作用域运算符

  • 实现文件通常以.cpp、.cc或.c结尾
  • ::称为作用域运算符

3. 签名必须精确匹配

4. 如基本类型一样申明对象

1
2
3
4
IntCell obj1;
IntCell obj2(12);
//IntCell obj3 = 37;	//构造函数是explicit的
//IntCell ibj4();	//函数声明

1.4.4 vector和string

在STL中，vector和string类将数组和字符串作为基本类来处理。

1.5 C++细节

1.5.1 指针

指针变量是用来存储其他对象的存储地址的变量。

1. 动态对象创建

1
2
m = new IntCell();	//ok
m = new Intcell;	//Preferred in this text
  • 内存泄漏(memory leak)
  • 本书中始终使用lhs和rhs定义二元操作符的左手侧和右手侧
  • 取地址运算符(&)
  • ->操作符

1.5.2 参数传递

  • 按值调用(call by value)
  • 按常量引用调用(call by constant reference)
  • 引址调用(call by reference)

参数传递选项总结：

（1）按值调用适用于不被函数更改的小对象。

（2）按常量引用调用适用于不被函数更改的大对象。

（3）引址调用适用于所有可以被函数更改的对象。

1.5.3 返回值传递

  • 多数情况下，不要使用引址返回
  • 如果返回的对象是类类型，最好的办法是使用按常量引用返回以节省复制的开销

1.5.4 引用变量

引用变量和常量引用变量常用于参数传递

1.5.5 三大函数：析构函数、拷贝构造函数和operator=

假设类包含一个指针数据成员，指向一个动态分配地址的对象，两个类实例包含的指针都指向同一个对象，称为浅拷贝(shallow copy)。

一般，我们期望得到的是整个对象进行克隆的深拷贝(deep copy)。

1.5.6 C风格的数组和字符串

  • 内置的C风格的字符串是当作字符数组来实现的
  • 终止符\0用以标识字符串逻辑上的结束，以避免传递字符串的长度值
  • 字符串通过strcpy来复制，通过strcmp类比较，通过strlen来确定字符串的长度

1.6 模板

  • 函数模板

  • 类模板

1.6.4 函数对象

函数对象(function object)：定义一个包含零个数据和一个成员函数的类，然后传递给这个类的实例。

函数调用操作符(function call operator)：operator()

1.6.5 类模板的分离编译

在许多情况下，整个的类模板连同其实现都放置在一个单独的头文件中

1.7 使用矩阵

1.7.1 数据成员、构造函数和基本访问函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#ifndef MATRIX_H
#define MATRIX_H

#include <vector>
using namespace std;

template <typename Object>
class matrix{
public:
    matrix(int rows, int cols):array(rows){
        for(int i = 0; i < rows; i++)
            array[i].resize(cols);
    }

    const vector<Object> & operator[](int row) const{
        return array[row];
    }
    vector<Object> & operator[](int row){
        return array[row];
    }
    int numrows() const{
        return array.size();
    }
    int numcols() const{
        return numrows() ? array[0].size() : 0;
    }
private:
    vector<vector<Object>> array;
}

#endif