Site Overlay

算法入门笔记:1. 预备知识

模板函数(template function)

C++ 的模板是通过编译时懒加载生成类/函数实现的。
使用范例:

template<class T>
T Abc(T a, T b, T c){
    return a+b+c
}

引用传参(pass by ref)

template<class T>
T Abc(T& a, T& b, T& c){
    return a+b+c
}

常量引用(const ref)

template<class T>
T Abc(const T& a, const T& b, const T& c){
    return a+b+c
}

作用是约束上面的 Abc 函数,使得函数内部不得修改参数值。

引用返回

上面的函数是复制返回。返回值被复制到 caller 那儿。可以如此进行引用返回

T& funcXX(int i, T& z){
    // do somthing...
    return z;
}

递归函数

递归函数就是自己调用自己的函数。

例子 生成排列(permutation)的递归函数。

设集合 $E = \{e_1, e_2, ...\}$

设集合 $E_i$ 表示 $E$ 中排除 $e_i$ 后得到的集合。

设函数 $\operatorname{perm} (X)$ 返回集合 $X$ 中元素的排列方式。

则:

$$
\operatorname{perm}(E) = e_1 \cdot \operatorname{perm}(E_1)+e_2 \cdot \operatorname{perm} + \cdots
$$

示例程序如下:

#include <stdio.h>
#include <string>
#include <iostream>
#include <list>

using namespace std;

void batchPushBack(list<string> &toWhere, list<string> &fromWhere, char prefix);

list<string> perm(string str);

int main()
{
    string str1 = "abcdefg";
    list<string> ret = perm(str1);
    printStrings(ret);
    return 0;
}

list<string> perm(string str)
{
    // 存放返回值
    list<string> ret;

    // 如果只有一个字符,直接返回
    if (str.size() == 1)
    {
        ret.push_back(str);
        return ret;
    }
    if (str.size() > 8)
    {
        cout << "emm" << endl;
        return ret;
    }

    // 遍历 str,对每个 char:
    string::iterator strIt = str.begin();
    while (strIt != str.end())
    {
        // 获取抽走 chr 之后的字符串,对其进行 perm 操作。
        char chr = *strIt;
        std::string cpy = str;
        cpy.erase(strIt - str.begin(), 1);
        list<string> perms = perm(cpy);
        // 将 perms 批量添加到返回链表中
        batchPushBack(ret, perms, chr);

        strIt++;
    }
    return ret;
}

void batchPushBack(list<string> &toWhere, list<string> &fromWhere, char prefix)
{
    list<string>::iterator stringsIt = fromWhere.begin();
    while (stringsIt != fromWhere.end())
    {
        cout << "str: " << *stringsIt << endl;
        toWhere.push_back(prefix + *stringsIt);
        stringsIt++;
    }
}

void printStrings(const list<string> &strings)
{
    list<string>::const_iterator stringsIt = strings.begin();
    while (stringsIt != strings.end())
    {
        cout << *stringsIt << endl;

        stringsIt++;
    }
}

异常处理


try {
    /* code */
}
catch(const std::exception& e) {
    std::cerr << e.what() << '\n';
}

动态内存分配

分配

int *y = new int(10);
float *x = new float[n];

释放

delete y;
delete []x;

例如定义 Currency 类。头文件:

class Currency{
// 公有函数
public:
    // 构造函数
    Currency(sign s = plus, unsigned long d = 0, unsigned int c = 0);
    // 析构函数
    ~Currency(){}
    // 普通方法
    bool Set(sign s, unsigned long d, unsigned int c);
    // 重载方法
    bool Set(float a);
    sign getSign() const { return sign;}
    // ...

}

实现:必须在函数开头加上 Currency:: 指明函数所属类。

Currency::Currency(sign s, unsigned long d, unsigned int c){
    // 创建一个Currency对象
    if(c > 99){ 
        //美分数目过多
        cerr << "Cents should be < 100" << endl;
        exit(1); 
    }
    sgn = s;
    dollars = d;
    cents = c;
}

运算符重载

例子:

Currency Currency::operator+(const Currency& x) const{
    // 把 x 累加至
    *this.Currency y;
    y.amount = amount + x.amount;
    return y;
}

自定义异常

自定义的异常和定义普通类是一样的。使用 throw ExceptionClassName() 抛出。不需要 new

友元

类的友元能够直接访问类的私有成员。代价是破坏了封装。

友元不可传递。

发表评论

电子邮件地址不会被公开。 必填项已用*标注