模闆實作順序表、雙連結清單

1 模闆實作順序表–考慮深層次的深淺拷貝問題

1）順序表模闆實作如下：

//SeqList.h
#pragma once
#include<iostream>
#include<assert.h>
#include"string.h"
template<class T>
class SeqList
{
public:
    SeqList()
        :_a(NULL)
        , _size(0)
        , _capacity(0)
    {}
        SeqList(const SeqList& s)
            :_a(new T[s._size])
        {
            for (size_t i = 0; i < s._size; ++i)
            {
                _a[i] = s._a[i];
            }
            _size = s._size;
            _capacity = s._capacity;
        }
        SeqList& operator=(SeqList s)
        {
            if (_a != s._a)
            {
                swap(_a, s._a);
                swap(_size, s._size);
                swap(_capacity, s._capacity);
            }
            return *this;
        }
    ~SeqList()
    {
        if (_a == NULL)
        {
            delete _a;
            _size = 0;
            _capacity = 0;
        }
    }
    void PushBack(const T& x)
    {
        if (_size >= _capacity)
        {
            CheckCapacity();
        }
        _a[_size++] = x;
    }
    void PopBack()
    {
        assert(_size > 0);
        _a[_size] = NULL;
        _size--;
    }
    void Insert(size_t pos, const T& x)//插入到pos前
    {
        assert(pos < _size);
        if (_size >= _capacity)
        {
            CheckCapacity();
        }
        for (int i = _size; i > (int)pos; --i)
        {
            _a[i] = _a[i-1];
        }
        _a[pos] = x;
        _size++;
    }
    void Erase(size_t pos)
    {
        assert(pos < _size);
        if (pos == _size - 1)
        {
            PopBack();
        }
        else
        {
            for (size_t i = pos; i < _size-1; ++i)
            {
                _a[i] = _a[i+1];
            }
            _size--;
        }
    }
    T& operator[](size_t pos)
    {
        return _a[pos];
    }
    void Print()
    {
        for (size_t i = 0; i<_size; ++i)
        {
            cout << _a[i] << " ";
        }
        cout << endl;
    }
 void CheckCapacity()
    {       
        _capacity = _capacity>0 ? _capacity * 2 : 3;
        T* tmp = new T[_capacity];
        if (_a)//深拷貝
        {
            for (size_t i = 0; i < _size; ++i)
            {
                tmp[i] = _a[i];
            }
            delete _a;
        }       
        _a = tmp;
    }
private:
    T* _a;
    size_t _size;
    size_t _capacity;
};
void TestSeqList1()
{
    SeqList<int> s2;
    s2.PushBack(1);
    s2.PushBack(2);
    s2.PushBack(3);
    s2.PushBack(4);
    s2.PushBack(1);
    s2.PushBack(2);
    s2.PushBack(3);
    s2.PushBack(4);
    s2.Print();
    s2.PopBack();
    s2.PopBack();
    s2.Print();
    SeqList<int> s3(s2);
    s3.Print();
    SeqList<int> s4;
    s4 = s3;
    s4.Print();
    s4.Insert(0, 100);
    s4.Insert(6, 100);
    s4.Insert(4, 100);
    s4.Print();
    s4.Erase(0);
    s4.Erase(6);
    s4.Erase(4);
    s4.Erase(5);
    s4.Print();
}
void TestSeqList2()
{
    SeqList<char> s2;
    s2.PushBack('a');
    s2.PushBack('b');
    s2.PushBack('c');
    s2.PushBack('d');
    s2.Print();
}

//test.cpp
using namespace std;
#include"SeqList.h"
int main()
{
    //TestSeqList1();
    TestSeqList2();
    system("pause");
    return ;
}

運作結果如下：

模闆實作順序表、雙連結清單

2）考慮深層次的深淺拷貝問題

若上面CheckCapacity()函數不是深拷貝，而是淺拷貝如下時：

void CheckCapacity()
    {       
        _capacity = _capacity> ? _capacity *  : ;
        T* tmp = new T[_capacity];
        if (_a)//深拷貝
        {
            memcpy(tmp,_a,_size*sizeof(T));
            delete[] _a;
        }       
        _a = tmp;
    }

再運作一下測試，程式會崩潰

void TestSeqList()
{
SeqList s2;
s2.PushBack("aaaaaaaaaaaaaaaaaaa");
s2.PushBack("bbb");
s2.PushBack("ccc");
s2.PushBack("ddd");
s2.Print();
}

分析原因：

由于string類成員函數包含了以下：

模闆實作順序表、雙連結清單

private：
char _Buf[16];
char* _ptr;//當Buf存儲不下，_ptr指向新開的空間
size_t _Mysize;//Buf存入的個數
size_t _Myres;//Buf容量

模闆實作順序表、雙連結清單

string類調用CheckCapacity()時，擴容前有ptr指針，當delete _a;會釋放ptr指向的空間，而memcpy進行淺拷貝。擴容後的ptr為野指針，之後在調用析構函數，則會對同一空間析構兩次。

當T為自定義類且有指針指向另一個空間時，不可用淺拷貝memcpy。

解決此淺拷貝帶來的問題可以用深拷貝的方法消除:

void CheckCapacity()
    {       
        _capacity = _capacity> ? _capacity *  : ;
        T* tmp = new T[_capacity];
        if (_a)//深拷貝
        {
            for (size_t i = ; i < _size; ++i)
            {
                tmp[i] = _a[i];
            }
            delete[] _a;
        }       
        _a = tmp;
    }

但是SeqList是模闆函數當類型為内置類且沒有指針時，用深拷貝浪費空間和時間，此問題解決方法可用類型萃取方法

2 帶頭節點的雙向循環連結清單–思考結構的優勢

1）帶頭節點的雙向循環連結清單實作

//ListNode.h
#include<iostream>
#include"assert.h"
template<class T>
struct ListNode
{
    T _data;
    ListNode* _next;
    ListNode* _prev;
    ListNode(const T x=T())
        :_data(x)
        , _next(NULL)
        , _prev(NULL)
    {}
};

template<class T>
class List
{
    typedef ListNode<T>  Node;
public:
    List()//構造函數
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    List(const List& l)//拷貝構造函數
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        Node* cur = l._head->_next;
        while (cur !=l. _head)
        {
            this->PushBack(cur->_data);
            cur = cur->_next;
        }       
    }
    List<T>& operator=(const List l)//指派運算符重載
    {
        if (this != &l)
        {
            clear();
            Node* cur = l._head->_next;
            while (cur != l._head)
            {
                this->PushBack(cur->_data);
                cur = cur->_next;
            }
        }       
        return *this;
    }
    ~List()
    {
        clear();
        delete _head;
        _head = NULL;
    }
    void clear()
    {
        Node* cur = _head->_next;
        while (cur != _head)
        {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        _head->_next = _head;
        _head->_prev = _head;
    }
    /*void PushBack(const T& x)
    {
        Node* tmp = new Node(x);
        Node* tail = _head->_prev;
        tail->_next = tmp;
        tmp->_prev = tail;
        _head->_prev = tmp;
        tmp->_next = _head;
    }*/
    void PushBack(const T& x)
    {
        Insert(_head->_prev, x);
    }
    /*void PopBack()
    {
        assert(!Empty());
        Node* tail = _head->_prev;
        Node* prev = tail->_prev;
        delete tail;
        prev->_next = _head;
        _head->_prev = prev;
    }*/
    void PopBack()
    {
        Erase(_head->_prev);
    }
    /*void PushFront(const T& x)
    {
        Node* tmp = new Node(x);
        Node* next = _head->_next;
        _head->_next = tmp;
        tmp->_next = next;
        next->_prev = tmp;
        tmp->_prev = _head;
    }*/
    void PushFront(const T& x)
    {
        Insert(_head->_next, x);
    }
    bool Empty()
    {
        if (_head->_next == _head->_prev)
        {
            return true;
        }
        return false;
    }
    /*void PopFront()
    {
        assert(!Empty());
        Node* cur = _head->_next;
        Node* next = cur->_next;
        delete cur;
        _head->_next = next;
        next->_prev = _head;
    }*/
    void PopFront()
    {
        Erase(_head->_next);
    }
    void Insert(Node* pos, const T& x)
    {
        Node* tmp = new Node(x);
        Node* prev = pos->_prev;
        prev->_next = tmp;
        tmp->_next = pos;
        pos->_prev = tmp;
        tmp->_prev = prev;
    }
    void Erase(Node* pos)
    {
        assert(!Empty());
        Node* prev = pos->_prev;
        Node* next = pos->_next;
        delete pos;
        prev->_next = next;
        next->_prev = prev;
    }
    Node* Find(const T x)
    {
        Node* cur = _head->_next;
        while (cur != _head)
        {
            if (cur->_data == x)
            {
                return cur;
            }
            cur = cur->_next;
        }
        return NULL;
    }
    void Print()
    {
        Node* cur = _head->_next;
        while (cur != _head)
        {
            cout << cur->_data << " ";
            cur = cur->_next;
        }
        cout << endl;
    }
private:
    Node* _head;
};
void TestListNode()
{
    List<int> l1;
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.Print();
    List<char> c1;
    c1.PushFront('a');
    c1.PushFront('b');
    c1.PushFront('c');
    c1.PushFront('d');
    c1.Print();
    List<int> l2 = l1;
    l2.Print();
    List<char> c2;
    c2 = c1;
    c1.Print();
    l1.PushFront();
    l1.PushFront();
    l1.PushFront();
    l1.Print();
    l1.PopBack();
    l1.PopBack();
    l1.PopFront();
    l1.Print(); 
    c1.Insert(c1.Find('a'), 'z');
    c1.Insert(c1.Find('c'), 'x');
    c1.Insert(c1.Find('d'), 'r');
    c1.Print();
    l1.Erase(l1.Find());
    l1.Erase(l1.Find());
    l1.Erase(l1.Find());
    l1.Print();
}

//test.cpp
using namespace std;
#include"ListNode.h"
int main()
{
    TestListNode();
    system("pause");
    return ;
}

運作結果如下：

模闆實作順序表、雙連結清單

2）帶頭節點的雙向循環鍊的結構優勢

模闆實作順序表、雙連結清單

單連結清單的缺點是隻能往前，不能後退，雖然有循環單連結清單，但後退的成本還是很高的，需要跑一圈。在這個時候呢，雙向連結清單就應運而生了，再加上循環即雙向循環連結清單就更加不錯了。所謂雙向連結清單隻不過是添加了一個指向前驅結點的指針，雙向循環連結清單是将最後一個結點的後繼指針指向頭結點。上圖為帶頭結點的雙向循環連結清單的結構。

關于查找插入删除操作，多出的那個前驅指針并沒有起多大作用，在時間性能上仍然是和單連結清單一樣，雙向循環連結清單的時間複雜度是O(n)。添加前驅指針後是給某個結點的前後結點操作帶來了友善，可以有效提高算法的時間性能，但是因為每個結點都多了一個前驅指針，會增加一些空間消耗，是以空間換時間！

模闆實作順序表、雙連結清單

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述