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

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

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;
}

10. swap

复杂度O(1) 这个swap实际上交换的是两个链表的元素。我们知道链表的元素并非是内存连续的，其每个元素的地址都是系统动态生成的，所以对于单项链表来说，只需要将首元素进行交换，即完成了链表的元素交换。同时，size也需要交换。

* 考虑到我这里都是写的循环列表，所以如果修改末节点的引用，那复杂度会变为O(n) * 如果将单向列表改成双向列表，即头header 以及尾rear 两个的时候，那么复杂度又回归O(1)

在学堂在线邓俊辉教授的课程中，链表也是使用非循环双向链表来表示，实际应用中，比较推荐这种方式。既可以规避掉 while循环时每次判断的复杂度，同时也方便从后往前遍历。代价是每个元素多一个prev指针。

template <class T>
void chain<T>::swap<( chain<T>& c) const{

    int s = _size;
    chainNode<T>* fn = firstNode();

    _size = c.size();
    firstNode() = c.firstNode();

    c.firstNode() = fn;
    c.size() = s;
}

11. 独立函数 Array 转 Chain

比较简单，遍历并插入到chain。一般来说我会重载insert方法，使用一个只有数据类型，没有index的方法，默认添加到最后。

template <class T>
Chain<T>& convertArrayToChain( Array<T>& a ){

    Chain<T> c = new Chain();
    for( int i=0; i<a.size(); i++ ){
        c.insert( a[i] );
    }
    return c;
}

12. 独立函数 Chain 转 Array convertChainToArray

template <class T>
Array<T>& convertChainToArray( Chain<T>& c ){

    Array<T> a = new Array( c.size() );
    chainNode<T>* current = c.firstNode();

    for( int i=0; i<a.size(); i++ ){
        a[i] = c.get(i); // 不推荐 这种写法，渐进复杂度高达n² ( 1+2+3+...+n = n(n+1)/2 )
        a[i] = current->element; // 推荐 复杂度O(n)
        current = current->next();
    }
    return a;
}

13. 成员函数 fromArray, toArray Pass

template <class T>
void chain<T>::fromArray( Array<T>& a ){}

template <class T>
Array<T>& chain<T>::toArray() const {}

具体逻辑参考11,12

14. 左移元素 leftShift

对于链表来说，左移实际上就是从左侧开始删除n个元素。并将首元素链接到最后删除位置的下一个元素。当n大于size()时候，应该是空链表。或者抛出索引错误。

template <class T>
void chain<T>::leftShift( int n ){

    checkIndex(n);
    chainNode<T>* current = firstNode();
    chainNode<T>* tmp;

    for( int i=0; i<size(); i++ ){ // 遍历删除元素

        tmp = current->next();
        delete current;
        current = tmp;
    }
    firstNode() = tmp;
    _size -= n;
}

15. reverse 元素倒转

如果使用单向链表，原地完成则需要每次获取到两端的并交换元素。这里会有高达O(n²)的复杂度，因为每一次都需要查询到与当前i所对应的尾部元素。这个操作复杂度是O(n), 虽然复杂度随着n接近n/2而降低，但是总体复杂度量级不变。

推荐的做法是使用双向链表，双指针分别从两端往中间移动，当指针大于 size/2 下整的时候结束。这样的复杂度是O(n)。

template <class T>
void chain<T>::reverse(){

    chainNode<T>* front = firstNode();
    chainNode<T>* back = lastNode();

    for( int i=0; i<size()/2; i++){
        swap( front->element, back->element ); // 交换元素的swap
        front = front->next();
        back = back->prev();
    }
}

这里的复杂度从理论来说是可以接受的，但是交换的是元素。如果元素本身体积庞大，那么在实际运行的时候，系统挪移元素的开销是很大的。所以考虑另一种实现方式，即 交换指针。这种方式在单向链表中，实现依然是比较复杂的，因为我们可以比较容易的获取前列的元素，但是难以链式的改变每一个node的反向连接。当我们使用双向链表的时候，相对来说就简单很多了。

我们需要一个暂存指针，从任一端开始，将元素的next设为prev,prev设为next，用暂存指针用来跳转到原来的next。直到末元素，将末元素的prev设置为header，或者首元素的next设置为rear。

template <class T>
void chain<T>::reverse(){

    chainNode<T>* current = firstNode();
    chainNode<T>* tmp;

    _header->next = lastNode();
    _rear->prev = firstNode();

    while( tmp = current->next() ){
        current->prev = tmp;
        current->next = current->prev(); // 第一次时将header设为了first的下一个，后面要修复。因为header并不参与交换。 rear同理
        current = tmp;
    }
    // 一轮循环结束，修复first,last
    _header->next->prev = _header;
    _rear->prev->next = _rear;
}

这里可以看到复杂度是O(n)，并且所需要进行处理的仅仅是指针类型，对于元素本身没有任何影响，不会造成额外的开销。

16. 独立函数 reverse PASS

17. 复制合并方法 copyMeld

复制方法不改变原链表，所以需要依次取出元素并合并。这时候就需要维护两个指针分别用来转向下一个位置。

template <class T>
Chain<T>& copyMeld( const Chain<T>& a, const Chain<T>& b ){

    ChainNode<T>* currentA = a->first();
    ChainNode<T>* currentB = b->first();
    Chain<T> c;

    while( currentA->next() && currentB->next() ){
        c.insert( currentA->element );
        c.insert( currentB->element );
        currentA = currentA->next();
        currentB = currentB->next();
    }
    while( currentA->next() ){
        c.insert( currentA->element );
        currentA = currentA->next();
    }
    while( currentB->next() ){
        c.insert( currentB->element );
        currentB = currentB->next();
    }
    return c;
}

18. 剪切合并方法 cutMeld

这里需要使用remove方法，其中remove方法删除该node并返回元素。删除元素满足单调性递减，经过n次迭代一定转为空。所以复杂度是O(n)。

template <class T>
Chain<T>& copyMeld( Chain<T>& a, Chain<T>& b ){

    Chain<T> c;

    while( a.first() && b.first() ){
        c.insert( a.remove(a.first()) );
        c.insert( b.remove(b.first()) );
    }
    while( a.first() ){
        c.insert( a.remove(a.first()) );
    }
    while( b.first() ){
        c.insert( b.remove(b.first()) );
    }
    return c;
}

19. 非成员复制merge

与17类似，多了一个比较大小的过程。

Chain<T> merge( const Chain<T>& a, Chain<T>& b ){

    ChainNode<T>* currentA = a->first();
    ChainNode<T>* currentB = b->first();
    Chain<T> c;

    while( currentA->next() && currentB->next() ){
        c.insert( currentA->element );
        if( currentA->element > currentB->element ){
            c.insert( currentB->element );
            currentB = currentB->next();
        }else{
            c.insert( currentA->element );
            currentA = currentA->next();
        }
    }
    while( currentA->next() ){
        c.insert( currentA->element );
        currentA = currentA->next();
    }
    while( currentB->next() ){
        c.insert( currentB->element );
        currentB = currentB->next();
    }
    return c;
}

20. 非成员剪切merge PASS 结合 18,19

21. split奇偶切割

遍历链表，每次走2步。

void extendedChain<T>::split( Chain<T> a, Chain<T> b ){

    ChainNode<T>* currentNode = first();
    while( currentNode->next()->next() ){
        b.insert(currentNode->element); // 0 为非奇数
        a.insert(currentNode->next()->element);
        currentNode = currentNode->next()->next();
    }
    while( currentNode->next() ){ // 当元素个数非偶数时，最后一个元素的秩一定为偶数
        b.insert(currentNode->next()->element); // 此时currentNode尚未跳转
    }
}

22. 循环移动 circularShift

链表循环移动的关键在于将首元素与末元素拼接，从第i-1个位置截断，i-1与尾部拼接，i与头部拼接。 i取决于 i%size。如果i%size==0 ，则无需移动。

void extendedChain<T>::circularShift( int i ){

    i = i%size();
    if(i==0) return;

    ChainNode<T>* currentNode = first();

    while( i>0 ){
        currentNode = currentNode->next();
        i--;
    }
    // 此时currentNode刚好处于i-1的位置

    // 头尾拼接  如果不移动切割节点，此时正好构成一个双向循环列表
    first()->prev = last();
    last()->next = first();

    // 重新链接切割节点
    currentNode->next = rear;
    currentNode->next()->prev = head;

    // 修复头尾链接
    head->next = currentNode->next();
    rear->prev = currentNode;
}

24. 逆转切分 PASS 因为看不懂题目说什么

25. PASS

26. insertSort 链表插入排序

插入排序的基本方法是迭代元素，并且在该元素之前的位置中找到一个合适的位置并将该元素挪移到该位置。插入排序遍历的复杂度是O(n)，而每一次取到一个元素，都需要在前置序列中找到一个合适的位置，这个查找过程的复杂度渐进来说也是O(n)，所以最坏复杂度是O(n²) n²/2 最好情况复杂度实际上刚好是逆序，而最坏复杂度是有序数组。因为每次取到的元素都会是前置序列中最大的那个，所以也会导致完整遍历前置序列。

void Chain<T>::insertSort(){

    int c = 0,; // 当前待排序元素的秩
    ChainNode<T>* currentNode = first();
    ChainNode<T>* compareNode;

    while( currentNode->next() ){
        currentNode = currentNode->next();
        compareNode = firstNode();
        for( int i=0; i<c; i++ ){
            if( compareNode->element > currentNode->element ){
                insertBefore(compareNode,currentNode->element);
                remove(currentNode);
            }else{
                compareNode = compareNode->next();
            }
        }
        c++;
    }
}

27. 冒泡排序选择排序计数排序/排列排序

在进行这几个排序之前需要先写一个 swap方法，用于交换两个元素的的位置。

void chain<T>::swap( ChainNode<T>* a, ChainNode<T>* b ){

    ChainNode<T> tmp = new ChainNode( *a ); // 复制构造

    a->next = b->next();
    a->prev = b->prev();
    b->next()->prev = a;
    b->prev()->next = a;

    b->next = tmp->next();
    b->prev = tmp->prev();
    a->next()->prev = b;
    a->prev()->next = b;

    tmp~ChainNode();
}

有了交换，对应的算法就简洁很多

冒泡排序

冒泡排序就是每一轮将一个最大元素推送到最后一位。正常来说每次比较相邻的两个元素，如果左侧较大则交换位置，一直到最后一个元素。就可以保证每一轮都会归为1个元素到n-i序列之后。这里的每一轮交换复杂度也是高达O(n)，更优的方法是记录当前序列中，最大且靠右的那个，并将其和队末元素交换，这样可以保证每一趟遍历至多一次交换。

选择排序

实际上和上面已经重复了，在我自己的理解中，冒泡排序和和选择排序没有什么本质区别。因为本质上他们都是每一轮将最后一个元素归位，属于减而治之。

而且在很多阐释中讲到冒泡排序的稳定性，选择排序不稳定，实际上细节上略作调整就可以满足。譬如说我在上面提到的，每次选择最大，且靠右的元素和队尾进行交换。这样就可以保证多轮交换后，相同大小的元素，从顺序上来说依然是保持了稳定的。

而冒泡排序。。。不管怎么想我都觉得就是选择排序。不多说了

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

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

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

2. setSize

3. set()

4. removeRange

5. lastIndex()

6. 重载[]

7. 重载==

8. 重载!=

9. 重载<

10. swap

11. 独立函数 Array 转 Chain

12. 独立函数 Chain 转 Array convertChainToArray

13. 成员函数 fromArray, toArray Pass

14. 左移元素 leftShift

15. reverse 元素倒转

16. 独立函数 reverse PASS

17. 复制合并方法 copyMeld

18. 剪切合并方法 cutMeld

19. 非成员复制merge

20. 非成员剪切merge PASS 结合 18,19

21. split奇偶切割

22. 循环移动 circularShift

24. 逆转切分 PASS 因为看不懂题目说什么

25. PASS

26. insertSort 链表插入排序

27. 冒泡排序选择排序计数排序/排列排序

冒泡排序

选择排序

添加新评论

最新文章

最近回复

友情链接

标签云

归档

其它

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

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

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

2. setSize

3. set()

4. removeRange

5. lastIndex()

6. 重载[]

7. 重载==

8. 重载!=

9. 重载<

10. swap

11. 独立函数 Array 转 Chain

12. 独立函数 Chain 转 Array convertChainToArray

13. 成员函数 fromArray, toArray Pass

14. 左移元素 leftShift

15. reverse 元素倒转

16. 独立函数 reverse PASS

17. 复制合并方法 copyMeld

18. 剪切合并方法 cutMeld

19. 非成员复制merge

20. 非成员剪切merge PASS 结合 18,19

21. split奇偶切割

22. 循环移动 circularShift

24. 逆转切分 PASS 因为看不懂题目说什么

25. PASS

26. insertSort 链表插入排序

27. 冒泡排序 选择排序 计数排序/排列排序

冒泡排序

选择排序

添加新评论

最新文章

最近回复

友情链接

标签云

归档

其它

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

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

27. 冒泡排序选择排序计数排序/排列排序