课程出处

P16 常用求导公式 -《高等数学》同济版 全程教学视频（宋浩老师）

视频中 22分钟处有一个关于 x的u次幂求导公式，其中证明步骤跳过了后面的步骤，当时看的时候有些疑问，经过一些尝试总算得出有效递推过程。

当时的疑问主要是 第二行的部分 h/x 既然趋向于0 那么 (1+0)的u次方 - 1 也趋向于零，所以结果应该是0

幂函数求导

谭浩强 C++程序设计（第三版）P189 第16题

输入一个字符串，内有数字和非数字字符，如

a123x456_17960?302tab5876

将其中连续的数字作为一个整数，依次存放到一个数组a中。统计总共有多少个整数，并输出这些数。

这个问题是比较好解决的，主要是三步

  1. 开辟一个 int a[(n+1)/2]; 大小的整数数组a，(n+1)/2 是字符串中能够包含的至多个整数了。 初始化一个数字统计 int total = 0;，用来累计出现过的数字总数。

  2. 遍历字符串，比对是否是数字，如果是 压入栈中，如果不是，将栈逐步清空并将取出的若干个数字计算为十进制数，其中每次出栈，将进制+1，则可以顺利求出。 每次得出一个新整数，total++。

  3. 以total为终，遍历a并输出。

#include <iostream>
#include <stack>

using namespacing std;

int getNumberFromStack( stack &s ){ // 传递引用

    int level = 1;
    int number= 0;

    while( !stack.empty() ){

        number += stack.top() * level;

        stack.pop();
        level *= 10;
    }
    return number;
}

int main(){

    string s;
    cout << "请输入一个字符串,如a123x456_17960?302tab5876。\n";
    cin >> s;

    int a[ (s.size() + 1)/2 ];
    int total = 0;
    stack<int> numberStack;

    for( unsigned int i =0; i< s.size(); i++ ){

        if( s[i]<='9' && s[i]>='0' ){

            numberStack.push( s[i]-0 );
        }else if( !numberStack.empty() ){

            a[total++] = getNumberFromStack( numberStack );
        }
    }

    // 输出全部数字
    for( int k=0; k < total; k++ ){

        cout << a[k] << "\n";
    }

    return 0;
}

数据结构、算法与应用 习题6.1 70题 p144

多项式

一个阶数为d的一元多项式( univariate polynomial ) 形式如下：

···

设计一个c++polynomial类，包含数据成员degree等等...

在设计多项式类之前，当然是要设计好 链表节点的结构。 节点应该包括多项式的指数，系数，以及下一项的地址。

struct polynomialNode{
    friend class polynomial; // 声明友元
    int exp;    // 指数
    int coeff;  // 系数
    polynomialNode* next;   // 下一项
public:
    polynomiaNode(int exp, int coeff, polynomiaNode* next):exp( exp),coeff(coeff),next(next){}
}

class polynomia{
    polynomialNode* _head;
    int _size;
public:
    polynomia(){
        _head = new polynomialNode(0,-1,NULL);
    }
    int degree(){};
    void input( istream input ){};
    void output( ostream output ){};
    polynomia add( polynomia b ){};
    polynomia operator+( polynomia b ){};
    polynomia subtract( polynomia b ){};
    polynomia operator-( polynomia b ){};
}

数据结构、算法与应用 习题6.1 69题 p143

给出一种整数表示法，用于对任意大小的整数进行数学运算(加减乘除),且不能有精度损失。

这里应该能支持两种表示法，1链表，2数组。

使用链表比较符合我们直观上对于数字的印象，其中将 rear链接到最后一位数，那么使用prev就可以陆续的取出每一个数字。 并且在进行数学运算时，我们无需关注最终的位数，只需要将结果insert进入结果链表中即可。

由于没有规定一定是正整数，所以需要给一个符号。 （在网上也搜索了一些大数运算的参考，没有提供有符号运算的版本） 带符号的时候，逻辑会变复杂不少。

这里我给出一个带符号的方式 其中isNegative true为负数，false为正数

为了表示符号对于运算的影响，我会写两个版本的 加法

链表表示:


class BigInt: public Chain<int>{
public:
    bool isNegative = false;

    BigInt( int* a, int size ){ // 基于数组构造
        for( int i=0; i<size; i++ ){
            insert( a[i] );
        }
    }

    // 最基本的 正正 相加
    BigInt& operator+( BigInt& bigInt ){
        int plus = 0;  // 进位
        int res  = 0;  // 单次计算结果
        BigInt result = new BigInt; // 结果
        ChainNode<int>* cursor = last();
        ChainNode<int>* targetCursor = bigInt.last();

        // 使用倒序的方式取出元素并计算
        while( cursor->prev() && targetCursor->prev() ){
            res = cursor->element + targetCursor->element + plus;
            plus = res > 9 ? 1 : 0;

            result->prepend( res ); // prepend即为 addAfter( head )
            cursor = cursor->prev();
            targetCursor = targetCursor->prev();
        }
        while( cursor->prev() ){
            result->prepend( cursor->element );
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element );
            targetCursor = targetCursor->prev();
        }
        return result;
    }

    // 完整版 带符号运算的加法 （不是重载!!!）
    BigInt& operator+( BigInt& bigInt ){

        BigInt result = new BigInt; // 结果
        result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同，根据最后一次计算结果修正。

        int plus = 0;   // 进位或借位
        int res;        // 单次计算结果
        ChainNode<int>* cursor = last();                // 当前游标
        ChainNode<int>* targetCursor = bigInt.last();   // 目标游标

        while( cursor->prev() && targetCursor->prev() ){

            res = isNegative ? -cursor->element : cursor->element
                + bigInt.isNegative ? -targetCursor->element : targetCursor->element
                + plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
            // 绝对值超过>9的都需要向上进一位(一定是同符号)
            // 不同符号 结果小于0的 需要借位
            // 同符号小于0，不同符号大于0小于10的都可以忽略
            // 小于0的时候 res需要取绝对值，保持元素的非负

            if( res >9 || res<-9 ){
                plus = 1;
            }else if( res < 0 ){
                plus = isNegative == bigInt.isNegative ? 0 : -1;
                res  = -res;
            }

            result.prepend(res);
        }

        if( size() == bigInt.size()  ){ // 修复位数相同的问题
            if( plus>0 ){
                result.prepend(1); // 一定是同符号的，直接+1
            }else if( plus<0 ){
                result.isNegative = true; // 此时已经无法借位了，确认最终结果为负数
            }
        }

        // 任意链表仍有元素未计算，继续补齐
        while( cursor->prev() ){
            result->prepend( cursor->element + plus );
            plus = 0;
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element + plus );
            plus = 0;
            targetCursor = targetCursor->prev();
        }

        // 修复首位为0的情况 // 全部删除则为空 即0
        while( result.first().element == 0 ){
            result.remove( result.first() );
        }

        return result;
    }

    // 在有符号加法的前提下，减法运算就简单多了
    BigInt& operator-( BigInt& bigInt ){

        bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
        BigInt result = *this + bigInt;

        bigInt.isNegative = !bigInt.isNegative; // 恢复
        return result;
    }
}

本页的练习在无特殊说明时一律按照 单右向循环 链表为准。

1. L=(a,b,c,d,e) 作图 pass

2. setSize

复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
    chainNode<T> current = firstNode();
    int i=0, max = _size < n ? _size : n;

    // 由于不是双向链表，所以需要先到达n的极点
    while( i < max ){
        current = current->next();
        i++;
    }

    chainNode<T> tmp;
    // 如果有多余的
    while( _size > n ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size = n;
}

3. set()

复杂度O(n) 在实际使用的时候，链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。

template <class T>
void chain<T>::checkIndex( int theIndex ){

    if( theIndex <0 || theIndex >= _size ){
        throw illegalIndex("Out of range");
    }
}

template <class T>
void chain<T>::set( int theIndex, T& theElement ){
    checkIndex(theIndex);
    chainNode<T>* current = firstNode();
    int i = 0;
    while( i < _size ){
        current = current->next();
    }
    current->element.~T(); // 析构
    current->element = theElement;
}

4. removeRange

复杂度O(n) 和上面的setSize类似，做一次遍历，之后将切割掉的部分接起来即可。

template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
    checkIndex(fromIndex);
    checkIndex(toIndex);

    chainNode<T>* current = firstNode();
    int i=0;

    // fromIndex的极点
    while( i < fromIndex ){
        current = current->next();
        i++;
    }

    chainNode<T>* tmp;

    while( i < toIndex ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size -= toIndex-fromIndex +1; // 考虑左右闭区间
}

5. lastIndex()

复杂度O(n) 遍历元素并比对，不即时返回。

template <class T>
int chain<T>::lastIndex( T& theElement ) const{

    if( empty() ) return -1;

    chainNode<T>* current = firstNode();
    int i = 0, lastIndex = -1;

    while( i< _size ){
        if( current->element == theElement ){
            lastIndex = i;
        }
        current = current->next();
        i++;
    }
    return lastIndex;
}

6. 重载[]

复杂度O(n) 实际上重载应该包含两种，分别是提供左值，右值返回。

template <class T>
const T& chain<T>::operator[](int n) const{  } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
    int i = 0;
    chainNode<T>* current = firstNode();

    while( i < n ){
        current = current->next();
    }
    return current->element;
}

7. 重载==

复杂度O(n) 同步遍历两个链表元素，一旦发现不同元素返回false。

template <class T>
bool chain<T>::operator==( chain<T>& c) const{

    if( size() != c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element !== target->element ) return false;
        current = current->next();
        target  = target->next();
    }
    return true;
}

8. 重载!=

复杂度O(n)

template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
    return !*this == c;
}

9. 重载<

复杂度O(n) 略微需要注意的是，除了最后一项的值完全相等以外，其他的相等 都不能判断非<。 所以在遍历的靠前阶段，== 都应该算成功，只有最后一项相等判断非小于。

template <class T>
bool chain<T>::operator<( chain<T>& c) const{

    if( size() > c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element > target->element ){
            return false;
        }else{
            current = current->next();
            target  = target->next();
        }
    }
    if( current->element == target->element ) return false;
    return true;
}

- 阅读剩余部分 -

1### 2. L = (a,b,c,d,e) ... 做图

初始状态:

0 1 2 3 4 5 6 7 8 9
a b c d e  

insert(0,f)

0 1 2 3 4 5 6 7 8 9
f a b c d e  

insert(3,g)

0 1 2 3 4 5 6 7 8 9
f a b g c d e  

insert(7,h)

0 1 2 3 4 5 6 7 8 9
f a b g c d e h  

earse(0)

0 1 2 3 4 5 6 7 8 9
a b g c d e h  

erase(4)

0 1 2 3 4 5 6 7 8 9
a b g c e h  

3. changeLength2D

二维数组的话要基于Array设计一个矩阵类，其中的每一行都是一个Array对象。

template <class T>
class ArrayMatrix: public Array{
    void changeLength2D( int x, int len );
}

template <class T>
void ArrayMatrix::changeLength2D( int rowIndex, int len ){
    checkIndex(x);
    get(rowIndex).changeLength(len);
}

3. 构造函数

好像题目描述有问题。 我自己写的是提供一个是否自动扩容的参数。如果配置为不自动扩容则在超出的时候抛出异常。

enum class ARRAY_AUTO_CAPACITY
{
    DISABLED = 0,ENABLED = 1
};

template <class T>
class Array{
public:
    Array(int initCapacity = ARRAY_DEFAULT_CAPACITY, ARRAY_AUTO_CAPACITY autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED);
    void checkMax();
private:
    ARRAY_AUTO_CAPACITY _autoCapacity =  ARRAY_AUTO_CAPACITY::DISABLED;
}


template<class T>
inline void Array<T>::checkMax()
{
    if (_size >= _capacity) {

        switch (_autoCapcity)
        {
        case ARRAY_AUTO_CAPACITY::ENABLED:
            changeCapacityTo(_capacity << 1);
            break;
        case ARRAY_AUTO_CAPACITY::DISABLED:
            throw illegalInputData("Array is full.");
            break;
        default:
            break;
        }
    }
}

5. trimToSize()

实际上就是改变数组长度， 长度为size或1。 这里我基于我改写的 changeCapacityTo()来实现，实际上是一回事。

复杂度是O(n)

void trimToSize(){
    changeCapacityTo( _size>0 ? _size : 1 );
}

template<class T>
inline void Array<T>::changeCapacityTo(int newCapacity)
{
    T* newElements = new T[newCapacity];
    _capacity = newCapacity;
    _size = newCapacity < _size ? newCapacity : _size;

    for (int i = 0; i < _size; i++)
    {
        newElements[i] = _elements[i];
    }
    delete[] _elements;

    _elements = newElements;
}

6. setSize

这一题，同样题目描述是有问题的。 见上一题changeCapacityTo()

7. 重载[]

T& operator[]( int n){
    checkIndex(n);
    return _elements[n];
}

8. 重载==

template<class T>
bool operator==( const Array<T>& targetArray ) const{
    if( size()!= targetArray.size() ){
        return false;
    }
    for( int i=0; i<size();i++ ){
        if( get(i) != target.get(i) ){
            return false;
        }
    }
    return true;
}

9. 重载!=

template<class T>
bool operator!=( const Array<T>& targetArray ){
    return !*this == targetArray;
}

10. 重载<

见8 . 其中!= 替换为>

- 阅读剩余部分 -

C++在使用的时候莫名的会出一些编译错误，有时候只是语法的特定写法不一致，所以记录一下。

1. 不允许使用默认参数

默认参数需要写在定义部分，不能写在实现部分。

const ARRAY_DEFAULT_CAPACITY = 8;

template <class T>
class Array{
    Array( int capacity ); // 有效
    Array( int capacity = ARRAY_DEFAULT_CAPACITY ); // 有效
}

// 错误， 不允许使用默认参数
template<class T>
Array<T>::Array( int initCapacity = ARRAY_DEFAULT_CAPACITY ){
    ...
}

2. 空参数实例化错误

使用空参数实例化的时候，不能使用()，会被编译器识别为函数定义

// 使用上述定义

Array<float> arr(10) // 正确 容量为10
Array<float> arr();  // 错误 容量为默认长度 无法实例化
Array<float> arr;    // 正确 容量为默认长度 可以实例化

字符串匹配： KMP算法， BM_BC, BM_GS算法

字符串匹配是搜索算法的基础，也是数据结构中一个十分有用的算法分支，我在学习KMP和BMBC算法的时候就觉得听的云里雾里，但经过一些实操和分析不难发现，这几个算法都是很好理解，并且对算法有很务实启发的。

以下我从零开始梳理以下如何建立一个清晰，并且有一定模式的理解这两个算法的思路。

1. 什么是字符串匹配

从一个字符串中查询是否完全包含另一个字符串的过程。如果有则返回起始位置，无则匹配失败。 例： 在 "这是一个多美丽又遗憾的世界" 匹配 "美丽" 应该返回5. 匹配"太美丽" 失败。

前菜开始：

2. 直观解法 循环遍历

令 字符串 S = "这是一个多美丽又遗憾的世界" 模式串(待匹配子串) s = "美丽" 循环遍历S并且在每一次S[i]与 s[j=0]匹配时，依次比较 S[i++] 与 s[j++]， 若成功则可以返回当前的 i-j 即为第一个字符所在的位置，失败则 i = i-j，再右移1位继续比较。

* 边界情况，当 i> m-n 时，宣告失败。 也就是说剩余可以配的元素已经不足够了，无需比较即告失败。 另外，约定查找失败时，返回-1；

算法示例:

int matchStr( char * S, char * s )
{
    size_t m = strlen(S), n = strlen(s);
    int i =0, j = 0;
    while( i < m-n+1 && j<n ){
        if( S[i] == s[j] ){
            i++;j++;
        }else{
            i -= j-1; // i = i-j+1
            j = 0;
        }
    }
    return j==n ? i-j : -1;
    // 当且仅当j与n相等时，模式串最后一位匹配成功
}
循环遍历的方式有什么问题呢？ 那就是机械，无论如何都需要完整遍历S，并且每一次至少需要比对1次，而从渐进角度来说总体来说复杂度是达到O(m*n)。

接下来才是正餐：

3. 优化方向/算法策略

优化的可能性仔细分析一下，就是如何减少没必要的匹配。 首先我们看一下，模式串都有哪些可能性呢？ （这里只需要考虑前缀，因为如果不是前缀重复，发生失配的时候一定是要从第一位开始比较的）

1 . 真前缀永不重复

a b c d e f g

2 . 单元素真前缀重复 / 真·一元前缀字串 重复

a a a a b c a a e

3 . 真·多元前缀字串重复

a b c a b c a b c a a b

那么接下来，分别看一下这几种不同的模式串，分别有怎样的优化方式。

- 阅读剩余部分 -

C++ 几乎可以重载全部的运算符，而且只能够重载C++中已经有的。

· 不能重载的运算符：“.”、“.*”、“::”、“?:” · 重载之后运算符的优先级和结合性都不会改变。

可以重载为类的非静态成员函数； 可以重载为非成员函数。

重载单目运算符，前置的单目运算符不需要提供形参。如 ++ -- *= +=...

而后置的单目运算符是需要提供参数来区别前置（为了重载）的。

class Even{
    int number=0;
    public:
    A & operator ++ (){
        number +=2;
        return *this;
    }
    A operator ++ ( int ){
        int old = number;
        ++(number);
        return old;
    }
}

前置++ 返回的是左值，而后置++ 返回的只是一个右值。

重载双目运算符，需要提供一个形参。如 + - * % /...

class Matrix{
    int ** elements;
    int sizeX;
    int sizeY;
    public:
    Matrix & operator + ( const Matrix & m ) const{
        int newX = m.getX() > this.sizeX ? m.getX() : this.sizeX;
        int newY = m.getY() > this.sizeY ? m.getY() : this.sizeY;
        Matrix _new(newX,newY);
        for( int i = 0; i< newX; i++ ){
            for( int j =0; j< newY; j++ ){
                _new[i][j] = m[i][j] + elements[i][j];
            }
        }
        return _new;
    }
}

重载为非成员函数

当需要对当前程序没有权限的类型进行操作符重载的时候，或是将不同类型重载到一起运算，都需要进行非成员函数重载。

重载时需要从左至右依次声明参与预算的各个参数

这个时候可以理解为以重载的形式写的常规函数。

非成员函数的重载操作符参数，不能全为普通类型。

构造函数

c++在进行实例化的时候通常需要使用构造函数，没有显示构造函数的时候，系统会默认一个所有参数为空的默认构造函数。

C++中的构造函数有很多细节，其中从语法上来说，定义在函数声明的部分，是会优先于构造函数本身执行。 譬如说以下的两种方式，会有不同的效果。

class A{
    int X;int Y;
    public:
    A( int x, int y ){
        std::cout << X << std::endl;
        X = x; Y = y;
    }
}
class B{
    int X;int Y;
    public:
    B( int x, int y ): X(x),Y(y){
        std::cout << X << std::endl;
    }
}

A,B都能分别完成对象的构造，区别在于B由于是在声明阶段定义了两个形式参数将要被放置到的对象属性中，所以A的构造函数不能在函数体内的第一行输出我们期望的值。而B中，X属性已经完成了初始化，可以顺利的输出我们的期望值。 另外由于省略了建立、销毁局部参数的过程，这种声明式的构造函数效率更好。

派生类中的构造函数

在派生类中使用构造函数时，需要同时构造基类的构造函数，如果同时继承多个基类，则需要依次构造基类。 在没有进行基类构造的时候，c++会默认使用基类的默认构造函数进行构造，但如果不满足这样的条件，就会报错。

class A{
    int a;
    public:
    A( int a ):a(a){}
}
class B{
    char b;
    public:
    B( char b ):b(b){}
}

class C : public A, public B{
    bool c;
    C( int a, char b, bool c ):A(a),B(b),c(c){}
}

这是一个最基本的多继承构造函数的形式。

有些时候我们可能会需要一些变种构造函数，也就是重载。譬如说当我们基于Matrix设计一个九宫格类的时候，实际上matrix的行和列都是固定的3x3.我们并不需要这两个参数来初始化。 这样的话，我们就可以使用单参数的形式重载九宫格类的构造函数：

template <typename T>
class sMatrix : public Matrix<T>{
private:
    int _sign;
public:
    sMatrix( int sign ): Matrix<T>(3,3), _sign(sign){ cout<< _sign << endl; }
    sMatrix( int x, int y, int s ):Matrix<T>( x, y ){
        cout << _sign << endl;
        _sign = s;    
        cout << _sign << endl;
    }
};

在C++中创建数组的时候需要声明数组的长度，在声明一个二维数组的参数时，则至少需要确认第二维的长度，否则就无法完成编译。 为什么呢，我们可以用一张图来表示c++二维数组在内存中的表示就理解了。

实际上在创建数组的时候，c++是根据最低维，也就是最靠后的那个维度最大值来分配连续内存空间的。譬如int[2][5]就会分配10*4个字节空间出来，如果不知道最后一个维度，c++就不知道如何开辟内存空间了。

二维数组返回的就是整个数组的首元素地址。 而访问则是根据最后维的长度进行运算后得出：

/*
 * c++ 二维数组
 * 
 * hello@shezw.com 2020.07.03
 */

#include <iostream>
#include <string>

using namespace std;

int main()
{
   int a[2][5] = {1,2,3,4,5,6,7,8,9,10};

    for( auto e:a ){
        printf( "%p : %d \n",e,*e );
    }
    printf( "%p : %d \n",&a[1][3],a[1][3] );
    printf( "%p : %d \n",&a[0][8],a[0][8] );

}

输出:

0x7fffa508a870 : 1 
0x7fffa508a884 : 6 
0x7fffa508a890 : 9 
0x7fffa508a890 : 9

可以看到 a[0][8] 其实是完全等价于 a[1][3] 的,实际上a[1][3] 就是从第一个空间开始往后数第3+1*5 = 8个。

在数据结构、算法与应用一书中约定了一种动态创建二维数组的方式。

这种方式的核心是 先构造一维指针数组，再将每个指针指向对应列的首元素。

为了调用和使用方便，我这里设计一个Matrix模板类，专门用于这样的动态二维数组的使用。

/*
 * c++ 二维数组
 * 
 * hello@shezw.com 2020.07.03
 */

#include <iostream>
#include <string>

using namespace std;

template <typename T>
class Matrix{
private:
    T ** _elements;
    int _colSize;
    int _rowSize;

public:
    Matrix( int rows, int cols ){
        _colSize = cols;
        _rowSize = rows;
        _elements = new T * [rows];
        for( int i=0;i<rows;i++ ){
            _elements[i] = new T [cols]();
        }
    }

    ~Matrix(){
        for( int i=0;i<_rowSize;i++ ){
            delete [] _elements[i];
        }
        delete [] _elements;
    }

    int getSize(){ return _colSize * _rowSize; };
    int colSize(){ return _colSize; };
    int rowSize(){ return _rowSize; };

    // 函数形式
    const T & get( int row, int col ){
        return _elements[row][col];
    }
    // 重载操作符形式
    T* & operator[]( int row ){
        return _elements[row];
    }
    // 重载操作符形式 只读
    const T* & operator[]( int row) const{
        return _elements[row];
    }
    void print(){

        for( int i=0; i< _rowSize; i++ ){

            printf( "\n row %p: \n", _elements[i] );

            for( int j=0; j< _colSize; j++ ){
                printf( "  col %p - %d\n", &_elements[i][j], _elements[i][j] );
            }

        }

    }
};

int main()
{
   Matrix<int> m(3,5);
    m[2][1] = 15;
   m.print();
}

* 指针运算符 可作为左值。表示查询到指针所对应的内存空间这样的操作。

& 地址运算符，可以概括为 取址运算符，从变量或对象等获取到该元素所在的内存空间中对应的地址。

指针定义

int i = 0;
int * pt = &i;

/* 
 未定义类型指针
 void类型指针可以存入任何类型的变量地址，但是不能直接被使用。使用的时候需要强制转换类型。
*/
int  i = 10;
bool b = false;
void * tentativePointer;
tentativePointer = & i;
i += static_cast<int *>(tentativePointer);
tentativePointer = & b;
b = !static_cast<bool *>(tentativePointer);

// 常量指针  指针所对应的地址的值被保护
int a;
a = 10; // √ a是变量 可以修改
const int *p1 = &a; // 指针
*p1 = 5; // × 不能通过p1 给a赋值

int b = 5;
p1 = &b; // √ 可以将p1转向其他变量

// 常指针  指针的地址被保护，即确定地址之后 不能修改，但对应的值可以修改。
int a;
a = 10;
int * const p2 = &a;
*p2 = 5; // √

int b = 5;
p2 = &b; // ×

指向对象的指针

指向对象的指针和其他类型的区别在于，访问对象的属性或方法不能通过.操作符。需要使用->。

实际上这里的object->method()等价于 (* object).method()，这是c++提供的一种语法糖。

另外，每个对象的方法内，默认隐含了一个this属性，实际上是指向该对象本身的。

指针的运算

算数运算

对指针的运算并非对地址进行修改，而是对于指针所指向的内存空间进行偏移定位。 而每一次移动的单位，取决于指针所表示的类型，例如 char 占用一个字节，那么 p++则会从010A0000前往010A0001，而如果是 int 类型，那么每次会移动4个字节，如从010A00B0前往010A00B4。 由于数组在内存中是紧密相连排列的，所以我们也就可以通过第一个元素的地址和[n]下标来查询对应的元素。

int a[] = {1,2,3,4,5};
cout << *(a+3) << endl;
// 会输出4 
// *(a+3) 等价于 a[ 0 + 3 ]

关系运算

一般来说同类型的指针可以进行比较操作。 另外可以将指针与0做比较，判断指针是否为空。(如果是新标准 可能不行)

指针传参

指针传参是十分重要的一个特性了，失去了指针，C++也就失去了他最大的性能优势。 传递指针本身是很容易的，即使用 * type param_name这样的形式定义参数即可。外部调用时，将对应的实参地址进行填入即可。

这时，如果为了保护数据的可靠性，可以用const修饰参数类型。

普通参数

// 批量打印
void printArray( const int * arr, int len ){
    for( int i=0; i<len; i++ ){
        cout << arr[i] << endl;
    }
}
int a[] = {1,2,3,4,5};
printArray( a,5 );

// 批量修改
void batchIncrease( int * arr, int len, int n ){
    for( int i=0; i<len; i++ ){
        arr[i] += n;
    }
}
int b[] = {1,2,3,4,5};
batchIncrease( b, 5, 2 );
printArray( b );

// 输出 3,4,5,6,7

当实参不是数组类型的时候，我们无法通过[]操作符进行寻秩操作，这个时候需要使用 * 运算符来获取地址对应的值。

void splitFloat(float x, int *intPart, float *fracPart) {
   *intPart = static_cast<int>(x); //取x的整数部分
   *fracPart = x - *intPart; //取x的小数部分
}

函数参数

需要实现传递函数作为回调函数的时候，我们可以将函数名作为 函数指针参数传递进去。比较典型的用法是，遍历回调。 例如我们对一系列的对象进行遍历的时候，我们设计的遍历函数是一个通用 或者说一个接口，它能够支持调用者用各式各样的方式来处理遍历时的元素，那么这个时候函数指针是非常有用的。

函数指针参数的格式为:return_type( * function_name )( function_params )

template <typename T>
void forEach( T * elements, int len , void(* callback)( const T el ) ){

    for( int i=0; i<len; i++ ){
        callback( T )
    }
}

// 可以再考虑一下传递的T 采用引用的类型如何编写

除此之外，函数指针不仅限于传参，和普通类型一样，函数指针一样可以先定义，后赋值为各个具体的函数。

void (*pf)(int,char*);
void fun(int n,char *s) {......}
pf=fun;

指针类型函数

指针类型函数就是返回一个指针（内存地址）的函数。定义十分简单，在返回类型后增加 * 标识符即可。 但是需要注意，返回的指针应当是一个返回后依然有效的指针，否则会产生越界，野指针或是更多错误。

这个问题很好理解，如果你在网上购物，给了一个地址，千万不要给酒店门牌号，因为快递送过来的时候，你已经不在酒店了。无论是租房还是买房，只要你收货的时候，你这个地址还是有效的，那就可以~

所以无论是返回外部变量中的有效地址，还是通过new 进行动态分配的空间地址，都是可以顺利返回给调用者。 而动态分配的地址，永恒的点就是不要忘了delete。

其他补充

基于范围循环

for( type & e : array ){} 基于范围循环是类似于很多其他语言中提供的in循环,比如Javascript中的for( var k in arr ){}。

SLT版本 string,queue


/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>
#include <queue>

using namespace std;

struct opr{
    int t;
    char c;
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

由于清华judge是不允许使用SLT的，所以使用自建QUEUE来完成。

非SLT版

/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>

using namespace std;


struct opr{
    int t;
    char c;
    opr(){}
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

template <typename T>
struct qe{
    qe<T>* prev;
    qe<T>* next;
    T data;
    qe(){}
    qe( T d, qe<T>* p = NULL, qe<T>* n = NULL ){
        data = d; prev = p; next = n;
    }
}; 

template <typename T>
class queue{ // 专为本算法特别定制队列,简化版
private:
    int _size = 0;
public:
    qe<T>* _head;
    qe<T>* _tail;

    queue(){
        _size = 0;
        _head = new qe<T>;
        _tail = new qe<T>;
        _head->next = _tail; _head->prev = NULL;
        _tail->prev = _head; _tail->next = NULL;
    }
    ~queue(){
    }
    int size(){return _size;}

    void push( T data ){

        qe<T>* newQe = new qe<T>( data, _tail->prev, _tail );
        _tail->prev->next = newQe;
        _tail->prev = newQe;
        _size++;
    }

    void pop(){

        if( empty() ) return;

        _head->next = _head->next->next;
        delete _head->next->prev;
        _head->next->prev = _head;
        _size--;
    }

    bool empty(){
        return _size == 0;
    }

    const T & front(){
        return _head->next->data;
    }

};



void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时，原右侧必不为空，右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

编译结果 95/100 最坏结果 204ms 14388KB。

这样看来还需要进一步优化。 20200629

格雷码

数据结构、算法与应用 第一张练习 26

两个代码之间的 海明距离 (Hamming distance) 是对应位不等的数量。 例如：100和010的海明距离是2。 一个（二进制）格雷码是一个代码序列，其中任意相邻的两个代码之间的海明距离是1。 子集生成的序列 000，100，010，001...111 不是格雷码，因为100，010海明距离是2。 而三位代码序列 000，100，110，010，011，111，101，001是格雷码。

在代码序列的一些应用中，从一个代码到下一个代码的代价取决于它们的海明距离。因此我们希望这个代码序列是格雷码。格雷码可以用代码变化的位置序列简洁地表示。 对于上面的格雷码，位置序列是1，2，1，3，1，2，1.

令g(n)是一个n元素的格雷码的位置变化序列。以下是g的递归定义：

    1                   n=1
    g(n-1),n,g(n-1)     n>1

注意这个是位置变化序列，并不是格雷码生成。

以下为算法

递归版：

#include <iostream>
#include <cmath>
/*
 *  格雷码序列数量是 2^n，相应的变化序列数量是 2^n - 1
 */
int * GrayCodeChangeSequence( int n ){
    int len   = pow(2,n)-1;
    int * arr = new int[len];
    if( n<2 ){ arr[0]=1; return arr; }

    int half  = (len-1)>>1;
    int * half_arr = GrayCodeChangeSequence( n-1 );

    for( int i=0; i<half; i ++ ){
        arr[i] = half_arr[i];
    }
    arr[half] = n;
    for( int i=0; i<half; i ++ ){
        arr[i+half+1] = half_arr[i];
    }

    return arr;
}

void testGCCS( int n ){

    int * b = GrayCodeChangeSequence(n);
    for( int i = 0; i< pow(2,n)-1 ; i++ ){
        std::cout << b[i] << ' ';
    }
    std::cout << endl;
    delete[] b;
}

int main()
{
    testGCCS(1);
    testGCCS(2);
    testGCCS(3);
    testGCCS(4);
    testGCCS(5);
}

测试分别输出：

1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

优化

实际上格雷码修改序列生成和斐波那契数列的生成效率是需要进一步优化的，原因在于每一次收到递归结果，都需要遍历一次结果并且覆盖到当前的序列中。从渐进意义上来说，复杂度是O(n2) 而且相对于序列的长度增长渐进意义上远大于n，这个时候如果能够在一次遍历的情况下配合少量计算那么可以将复杂度降低至O(n)

- 阅读剩余部分 -

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. ...
  9. 10