C++_Seqlist/Linklist

C++下实现顺序表，代码如下：

#include <iostream>
using namespace std;

//实现顺序表的下列接口： 
typedef int DataType; 
class SeqList 
{ 
public: 
    SeqList() 
        : _pData(new DataType[3]) 
        , _capacity(3) 
        , _size(0) 
    {} 

    SeqList(size_t n, DataType value)//构造一个容量为n，成员全是value的顺序表
        :_pData(new DataType[n])
        ,_capacity(n)
        ,_size(0)
    {
        for (;_size<n;++_size)
        {
            _pData[_size] = value;
        }
    }
    SeqList(const SeqList& s) 
    { 
        _pData = new DataType[s._capacity]; 
        _capacity = s._capacity; 

        // 方式一： 
        //memcpy(_pData, s._pData, s._size*sizeof(DataType)); 

        // 方式二： 
        _size = 0; 
        for(; _size < s._size; ++_size) 
            _pData[_size] = s._pData[_size]; 
    } 

    SeqList& operator=(const SeqList& s)
    {
        DataType* p = new DataType[s._capacity];
        for(size_t i=0; i < s._size; ++i) 
        {
            p[i] = s._pData[i];
        }
        delete _pData;
        _pData = p;
        _capacity = s._capacity;
        _size = s._size;

        return *this;
    }
    ~SeqList()
    {
        delete _pData;
        _size = 0;
        _capacity = 0;
    }
    void PushBack(const DataType& data)//顺序表尾部插入一个元素
    {
        _CheckCapacity();
        _pData[_size] = data;
        _size++;
    }
    void PopBack()//释放尾部最后一个元素
    {
        _size--;
    }
    void Insert(size_t pos, const DataType& data)//在下标为pos的位置插入一个元素data
    {
        _CheckCapacity();
        size_t i=_size;
        for (;i>=pos;i--)
        {
            _pData[i] = _pData[i-1];
        }
        _pData[i] = data;
        _size++;
    }
    void Erase(size_t pos)//删除下标为pos的元素
    {
        size_t i = pos-1;
        for (i;i<_size-1;i++)
        {
            _pData[i] = _pData[i+1];
        }
        _size--;
    }
    size_t Find(const DataType& data)//寻找元素data，并返回他的下标
    {
        for (size_t i = 0;i<_size;i++)
        {
            if (_pData[i] == data)
            {
                return i+1;
            }
        }
        return NULL;
    }
    size_t Size()const//返回顺序表的元素个数
    {
        return _size;
    }
    size_t Capacity()const//返回顺序表的容量
    {
        return _capacity;
    }
    bool Empty()const//判断顺序表是否为空
    {
        if (_size == 0)
        {
            return 1;
        }
        return 0;
    }
    void Clear()
    {
        _size = 0;
    }
    // 把顺序表中的有效元素改变到size个 
    void Resize(size_t size, const DataType& data)
    {
        if (size<_size)
        {
            _size = size;
        }
        else if (size > _size)
        {
            for (;_size < size;_size++)
            {
                PushBack(data);
            }
        }
    }
    DataType& operator[](size_t index)//下标运算符[]的重载
    {
        return _pData[index-1];
    }
    const DataType& operator[](size_t index)const
    {
        return _pData[index-1];
    }
    DataType& Front()//返回顺序表的第一个元素
    {
        return _pData[0];
    }
    const DataType& Front()const
    {
        return _pData[0];
    }
    DataType& Back()//返回元素表的最后一个元素
    {
        return _pData[_size-1];
    }
    const DataType& Back()const
    {
        return _pData[_size-1];
    }
    void DisPlay()
    {
        if (_size == 0)
        {
            cout<<"顺序表为空！！！"<<endl;
            return;
        }
        DataType* p = _pData;
        for (size_t i = 0;i<_size;i++)
        {
            cout<<p[i]<<"-->";
        }
        cout<<endl;
    }

private:
    void _CheckCapacity()//容量扩充
    { 
        if(_size == _capacity) 
        { 
            DataType* pTemp = new DataType[_capacity*2]; 
            for(size_t idx = 0; idx < _size; ++idx) 
                pTemp[idx] = _pData[idx]; 

            delete[] _pData; 
            _pData = pTemp; 
            _capacity *= 2; 
        } 
    } 

private: 
    DataType* _pData; 
    size_t _capacity; 
    size_t _size; 
};

测试代码：

void Test1()//测试构造，拷贝构造，赋值运算符重载
{
    cout<<"测试构造，拷贝构造，赋值运算符重载"<<endl;
    SeqList p1;
    p1.DisPlay();
    SeqList p2(5,2);
    p2.DisPlay();
    SeqList p3(p2);
    p3.DisPlay();
    p1 = p3;
    p1.DisPlay();
}

void Test2()//下标运算符[]重载，尾插，尾删，返回大小，返回容量，返回第一个元素，返回最后一个元素
{
    cout<<endl<<"下标运算符[]重载，尾插，尾删，返回大小，返回容量，返回第一个元素，返回最后一个元素"<<endl;
    SeqList p2;
    p2.PushBack(1);
    p2.PushBack(2);
    p2.PushBack(3);
    p2.PushBack(4);
    p2.DisPlay();
    cout<<"p2[3]="<<p2[3]<<endl;
    size_t tmp = p2.Size();
    cout<<"p2.Size()="<<tmp<<endl;
    tmp = p2.Capacity();
    cout<<"p2.Capacity()="<<tmp<<endl;
    DataType d = p2.Front();
    cout<<"p2.Front()="<<d<<endl;
    d = p2.Back();
    cout<<"p2.Back()="<<d<<endl;
}


int main()
{
    Test1();
    Test2();
    return 0;
}

测试结果：

C++实现链表，代码如下：

#include<iostream>
#include <assert.h>
using namespace std;


//链表 
#pragma once 
typedef int DataType; 


struct Node //结点的结构体
{ 
    Node(const DataType& data) 
        : _pNext(NULL) 
        , _pPre(NULL) 
        , _data(data) 
    {} 

    Node* _pNext; 
    Node* _pPre; 
    DataType _data; 
}; 

class List 
{ 
public: 
    List() 
        : _pHead(NULL)
        ,_tail(NULL)
    {} 
    List(size_t n, DataType data)//构造一个有n个结点，且结点的数据全是data的链表
    {
        _pHead = BuyNode(data);
        _tail = _pHead;
        while (--n)
        {
            Node* NewNode = BuyNode(data);
            _tail->_pNext = NewNode;
            NewNode->_pPre = _tail;
            _tail = _tail->_pNext;  
        }
    }
    void PushBack(const DataType& data)//链表尾部插入
    {
        Node* NewNode = BuyNode(data);
        if (_pHead == NULL)
        {
            _pHead = NewNode;
            _tail = _pHead;
        }
        else
        {
            _tail->_pNext = NewNode;
            NewNode->_pPre = _tail;
            _tail = NewNode;
        }
    }
    void PopBack()//释放链表最后一个元素
    {
        if (_pHead == NULL)
        {
            return ;
        }
        if (_pHead->_pNext == NULL)
        {
            _pHead = NULL;
            delete _tail;
            _tail = NULL;
            return ;
        }
        Node* cur = _tail;
        _tail = _tail->_pPre;
        _tail->_pNext = NULL;
        delete cur;
    }
    void PushFront(const DataType& data)//链表头部插入
    {
        Node* NewNode = BuyNode(data);
        if (_pHead == NULL)
        {
            _pHead = NewNode;
            _tail = _pHead;
        }
        else
        {
            _pHead->_pPre = NewNode;
            NewNode->_pNext = _pHead;
            _pHead = NewNode;
        }
    }
    void PopFront()//释放链表第一个结点
    {
        if (_pHead == NULL)
        {
            return ;
        }
        if (_pHead->_pNext == NULL)
        {
            _pHead = NULL;
            delete _tail;
            _tail = NULL;
            return ;
        }
        Node* cur = _pHead;
        _pHead = _pHead->_pNext;
        _pHead->_pPre = NULL;
        delete cur;
    }
    Node* Find(const DataType& data)//链表中寻找结点内元素为data的结点，并返回其地址
    {
        Node* cur = _pHead;
        while ((cur != NULL)&&(cur->_data != data))
        {
            cur = cur->_pNext;
        }
        return cur;
    }
    void Insert(Node* pos, const DataType& data)//指定位置插入一个结点
    {
        assert(pos != NULL);
        Node* NewNode = BuyNode(data);
        pos->_pPre->_pNext = NewNode;
        NewNode->_pPre = pos->_pPre;
        pos->_pPre = NewNode;
        NewNode->_pNext = pos;
    }
    void Erase(Node* pos)//删除指定位置的结点
    {
        assert(pos != NULL);
        pos->_pPre->_pNext = pos->_pNext;
        pos->_pNext->_pPre = pos->_pPre;
        delete pos;
    }
    size_t Size()//返回链表中有多少个结点
    {
        Node* cur = _pHead;
        size_t count = 0;
        while (cur != NULL)
        {
            count++;
            cur = cur->_pNext;
        }
        return count;
    }
    bool Empty()const//判断链表是否为空
    {
        if (_pHead == NULL)
        {
            return 1;
        }
        return 0;
    }
    List(const List& l)
        :_pHead(NULL)
        ,_tail(NULL)
    {
        Node* pl = l._pHead;
        while (pl != NULL)
        {
            PushBack(pl->_data);
            pl = pl->_pNext;
        }
    }
    List& operator=(const List& l)
    {
        Node* pl = l._pHead;
        if (pl == NULL)
        {
            if (_pHead == NULL)
            {
                return *this;
            }
            while (_pHead != NULL)
            {
                Node* cur = _pHead;
                _pHead = _pHead->_pNext;
                delete cur;
            }
            _tail = NULL;
            return *this;
        }
        else
        {
            if (_pHead == NULL)
            {
                while (pl != NULL)
                {
                    PushBack(pl->_data);
                    pl = pl->_pNext;
                }
                return *this;
            }
            Node* p = _pHead;
            while ((p != NULL)&&(pl != NULL))
            {
                p->_data = pl->_data;
                _tail = p;
                p = p->_pNext;
                pl = pl->_pNext;
            }
            if (p == NULL)
            {
                while (pl != NULL)
                {
                    PushBack(pl->_data);
                    pl = pl->_pNext;
                }
                return *this;
            }
            _tail->_pNext = NULL;
            while (p != NULL)
            {
                Node* cur = p;
                p = p->_pNext;
                delete cur;
            }
            return *this;
        }
    }
    ~List()
    {
        while (_pHead != NULL)
        {
            Node* cur = _pHead;
            _pHead = _pHead->_pNext;
            delete cur;
        }
        _tail = NULL;

    }

    void Display()
    {
        Node* p= _pHead;
        if (p == NULL)
        {
            cout<<"链表为空链表！！！"<<endl;
            return ;
        }
        while (p!= NULL)
        {
            cout<<p->_data<<"-->";
            p = p->_pNext;
        }
        cout<<"over"<<endl;
    }
private: 
    Node* BuyNode(const DataType& data)//获得一个结点 
    { 
        return new Node(data); 
    } 
private: 
    Node* _pHead; 
    Node* _tail;
}; 

测试代码：

void FunTest()//测试头插，尾插，头释放，尾释放，指定位置插入，指定位置删除，返回链表长度。
{
    List pLi(5,16);
    pLi.Display();
    pLi.PushBack(12);
    pLi.PushBack(7);
    pLi.PushBack(8);
    pLi.PushBack(4);
    pLi.Display();
    //pLi.PopBack();
    //pLi.Display();

    pLi.PushFront(2);
    pLi.Display();
    //pLi.PopFront();
    //pLi.Display();

    Node* pn = pLi.Find(12);
    if (pn)
    {
        cout<<"pLi.Find(12)"<<pn->_data<<endl;
    }

    pLi.Insert(pn,3);
    cout<<"Insert(pn,3)"<<endl;
    pLi.Display();
    pLi.Erase(pn);
    cout<<"Erase(pn)"<<endl;
    pLi.Display();


    size_t count = pLi.Size();
    cout<<"pLi.Size()"<<count<<endl;

    List pLi1(pLi);
    pLi1.Display();

}

void FunTest1()//赋值运算测试
{
    cout<<endl<<"赋值运算测试:"<<endl<<endl;
    List p1;
    cout<<"p1:"<<endl;
    p1.Display();
    List p2(5,6);
    cout<<"p2:"<<endl;
    p2.Display();
    List p3;
    cout<<"p3:"<<endl;
    p3.Display();
    List p4(2,3);
    cout<<"p4:"<<endl;
    p4.Display();
    List p5(7,8);
    cout<<"p5:"<<endl;
    p5.Display();
    List p6(4,4);
    cout<<"p6:"<<endl;
    p6.Display();

    p1 = p3;
    cout<<"p1 = p3"<<endl;
    p1.Display();

    p6 = p3;
    cout<<"p6 = p3"<<endl;
    p6.Display();

    p3 = p2;
    cout<<"p3 = p2"<<endl;
    p3.Display();

    p4 = p2;
    cout<<"p4 = p2"<<endl;
    p4.Display();

    p5 = p2;
    cout<<"p5 = p2"<<endl;
    p5.Display();


}


int main ()
{
    FunTest();
    FunTest1();
    return 0;
}

测试结果：

顺序表，链表中主要在拷贝构造函数，还有赋值运算符重载时，需要考虑到被赋值对象的大小问题，当被赋值对象大小大于赋值对象时，多余的部分需要手动释放掉，不够的部分可利用尾部插入函数，进行补充。