数据结构、算法与应用 习题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;
}

- 阅读剩余部分 -