《数据结构与STL》笔记和习题（2）

大致浏览了一下chapter3和chapter4，直接到chapter5

这一章简单介绍了一下vector和deque，以及他们各自的实现原理。

vector和deque，主要特点是向后插入和随机访问是常数级别复杂度，deque比vector

强悍的地方，就是在前端插入也是常数级别的，但是代价就是deque比vector要难实现。

deque用一个辅助索引数组，实现两端插入都是常数，感觉还是巧妙的。

vector貌似是只扩大空间，而deque还会回收空间。

这两个顺序容器，对于随机位置的插入、删除，开销是线性级别，这个比list要差很多。

#########################

课后project

1. 扩展very_long_int类

简单描述：实现非大整数之间的基本运算：加法、减法、乘法、除法和幂运算。

算法：

加法，减法，乘法，直接用手工计算的方法；除法，用减法实现；幂运算,将指数转为二进制后，累乘即可。

类定义：

#ifndef VERY_LONG_INT_H
#define VERY_LONG_INT_H

#include <vector>
#include <string>
#include <iostream>

class very_long_int {
public:
    very_long_int() {}
    very_long_int(const very_long_int &another) {
        digits = another.digits;
    }
    very_long_int(const std::string &str);

    very_long_int operator+(const very_long_int &another) const;
    very_long_int operator-(const very_long_int &another) const;
    very_long_int operator*(const very_long_int &another) const;
    very_long_int operator/(const very_long_int &another) const;

    /*
     * if *this > another, return 1
     * else if *this == another, return 0
     * else return -1
     */
    int compare(const very_long_int &another) const;

    /* transform the digits into a readable sequence */
    std::string toString() const;

    very_long_int pow(unsigned int exp) const;

    friend std::ostream& operator<<(std::ostream &out, const very_long_int &very_long);
private:
    std::vector<char> digits; // digits stored in reverse order

    bool isZero() const;
};

#endif // VERY_LONG_INT_H

除法：

very_long_int very_long_int::operator/(const very_long_int &another) const {
    assert(!another.isZero()); // check zero
    very_long_int result;
    int sign = compare(another);
    if (sign < 0) {
        result.digits.push_back(0);
        return result;
    } else if (sign == 0) {
        result.digits.push_back(1);
        return result;
    }

    very_long_int left = *this;
    very_long_int right = another;
    right.digits.insert(right.digits.begin(),
            digits.size()-right.digits.size(), 0);
    while ( left.compare(another) >= 0 ) {
        char carry = 0;
        while ( left.compare(right) >= 0 ) {
            carry++;
            left = left - right;
        }
        right.digits.erase(right.digits.begin());
        result.digits.push_back(carry);
    }
    reverse(result.digits.begin(), result.digits.end());
    if (result.digits[result.digits.size()-1] == 0)
        result.digits.pop_back();
    return result;
}

幂运算：

very_long_int very_long_int::pow(unsigned int exp) const {
    assert(!isZero());
    very_long_int result;
    result.digits.push_back(1);
    very_long_int base = *this;

    while (exp) {
        if (exp & 0x1)
            result = result * base;
        exp = exp >> 1;
        base = base * base;
    }
    return result;
}

测试数据：

我是用python生成的，每中25组测试。

源码：

 pj_1.zip