模板实现顺序表、双链表

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++驱动概述