c++;雙向循環鏈表

c++;雙向循環鏈表

 
#pragma once//頭文件
 
using namespace std;
 
typedef int DataType;
 
class ListNode
{
    friend class DoubleList;
private:
    DataType _data;
    ListNode* _next;
    ListNode* _prev;
public:
    ListNode();
     
};
 
class DoubleList
{
private:
    ListNode* _pHead;
    ListNode* _pTail;
public:
    DoubleList();
    DoubleList(const DoubleList& list);
    ~DoubleList();
    void PushBack(const DataType x);
    void PopBack();
    void Insert( ListNode* pos,const DataType x);
    void Erase(ListNode* pos);
    ListNode* Find(const DataType x);
    void Reverse();
    void GetData();
    void Destroy();
    void operator =(const DoubleList& list);
};
 
#include<iostream>//函數文件
#include"doubleList.h"
#include<assert.h>
 
using namespace std;
ListNode::ListNode()
    :_next(NULL)
    , _prev(NULL)
{}
 
DoubleList::DoubleList()
    :_pHead(new ListNode)
    ,_pTail(_pHead)
{
    _pHead->_next = _pHead;
    _pHead->_prev = _pHead;
}
 
DoubleList::DoubleList(const DoubleList& list)
{
    _pHead = new ListNode;
    ListNode* head = _pHead;
    _pTail = _pHead;
    ListNode *tmp = list._pHead->_next;
    while (tmp != list._pHead)
    {
        head->_next = new ListNode;
        head->_next->_data = tmp->_data;
        _pTail = head->_next;
        _pTail->_prev = head;
        _pTail->_next = _pHead;
        _pHead->_prev = _pTail;
        head = head->_next;
        tmp = tmp->_next;
    }
}
DoubleList::~DoubleList()
{
     
    while (_pTail!=_pHead)
    {
        ListNode* del = _pTail;
        _pTail = _pTail->_prev;
        delete del;
         
         
    }
    delete _pTail;
}
void DoubleList::PushBack(const DataType x)
{
 
     
        ListNode* tmp= new ListNode;
        tmp->_prev = _pTail;
        _pTail->_next= tmp;
        tmp->_data = x;
        _pTail = tmp;
        tmp->_next = _pHead;
        _pHead->_prev = tmp;
     
}
 
void DoubleList::PopBack()
{
     
        ListNode* del = _pTail;
        if (_pTail!=_pHead)
        {
            _pTail = _pTail->_prev;   
            _pTail->_next = _pHead;
        }
         
        delete del;
}
 
void DoubleList::Insert( ListNode* pos, const DataType x)
{
    assert(pos);
    ListNode* tmp = new ListNode;
    tmp->_prev = pos;
    tmp->_next = pos->_next;
    pos->_next = tmp;
    tmp->_next->_prev = tmp;
    tmp->_data = x;
    _pTail = _pHead->_prev;
}
 
void DoubleList::Erase(ListNode* pos)
{
    assert(pos);
    ListNode *del = pos;
    if (_pTail != _pHead)
    {
        pos->_next->_prev = pos->_prev;
        pos->_prev->_next = pos->_next;
    }
    delete del;
}
 
ListNode* DoubleList::Find(const DataType x)
{
    ListNode* tmp = _pHead->_next;
    while (tmp!=_pHead)
    {
        if (tmp->_data == x)
        {
            return tmp;
        }
        tmp = tmp->_next;
    }
    return NULL;
}
 
void DoubleList:: GetData()
{
    ListNode* tmp = _pHead->_next;
    while (tmp!=_pHead)
    {
        cout << tmp->_data << "->";
        tmp = tmp->_next;
    }
    cout << "NULL" << endl;
}
 
void DoubleList::Reverse()
{
    ListNode* tmp = _pHead->_next;
    ListNode* newHead = _pHead;
    do
    {
        newHead->_next = newHead->_prev;
        newHead->_prev = tmp;
        newHead = tmp;
        tmp = newHead->_next;
    } while (newHead != _pHead);
    _pTail = _pHead->_prev;
 
}
 
void DoubleList::Destroy()
{
    this->~DoubleList();
}
 
 
void DoubleList:: operator =(const DoubleList& list)
{
    _pHead = new ListNode;
    ListNode* head = _pHead;
    _pTail = _pHead;
    ListNode *tmp = list._pHead->_next;
    while (tmp != list._pHead)
    {
        head->_next = new ListNode;
        head->_next->_data = tmp->_data;
        _pTail = head->_next;
        _pTail->_prev = head;
        _pTail->_next = _pHead;
        _pHead->_prev = _pTail;
        head = head->_next;
        tmp = tmp->_next;
    }
}
 
#include<iostream>//主函數  測試文件
#include"doubleList.h"
 
using namespace std;
 
void test1()
{
    DoubleList s1;
    s1.PushBack(1);
    s1.PushBack(2);
    s1.PushBack(3);
    s1.PushBack(4);
    s1.GetData();
    cout << (s1.Find(1)) << endl;
    s1.Insert((s1.Find(4)), 5);
    s1.GetData();
    DoubleList s2;
    s2.GetData();
    s1.Reverse();
    s1.GetData();
    s2 = s1;
    s2.GetData();
     
}
 
int main()
{
    test1();
    return 0;
}