雙向鏈表（C++實現）

雙向鏈表（C++實現）

List.h

//////////////////////////////////////////////////////////////////////////////////////
///////  這裡建立兩個類，一個節點類和一個List類，與單鏈表不同的是雙向鏈表的節點要多一
//////  個前驅指針,相應的，雙向鏈表函數實現要與單鏈表實現有所差異
 
    typedef int DataType;
 
    //struct LinkNode    //節點類（復合形態）
    //{
    //  friend class SList;
                  //將SList設為友元，便於SList類可以訪問節點類的私有成員
    //public:
    //  LinkNode(const DataType x); 
    //private:
    //  DataType _data;    //節點的數據
    //  LinkNode* _next;    //指向該節點的下一個節點
    //      LinkNode* _prev;    //指向該節點的前一個節點
    //};
 
    //直接用struct定義LinkNode類，因為struct的成員默認為公有數據成員，所以可直接訪問
    struct LinkNode      //節點類(建議寫法)
    {
        LinkNode(const DataType x);
        DataType _data;    //節點的數據
        LinkNode* _next;    //後繼指針
        LinkNode* _prev;      //前驅指針
    };
 
    class List    //鏈表類
    {
    public:
        List();        //構造函數
        List(const List& s);        //拷貝構造
        List &operator=(List& s);    //賦值運算符的重載
        ~List();
 
    public:
        void Reverse();
        void Swap(List& s);
        void PrintSList();  //打印鏈表
        void PushBack(const DataType& x);    //在尾部插入一個節點
        void Clear();        //鏈表置空
        void PopBack();
        void PushFront(DataType x);  //頭插
        void PopFront();    //刪除首節點
        void Insert(LinkNode* pos, DataType x);//固定位置插入一個節點
        void Erase(LinkNode* pos);        //刪除某一節點
        LinkNode* Find(DataType x);      //查找節點並返回這個節點的地址
        int Amount();  //計算鏈表節點的數目
        void Remove(DataType x);    //查找某節點並刪除
 
    private:
        LinkNode* _head;    //指向頭結點
        LinkNode* _tail;    //指向尾節點
    };

List.cpp

#include<iostream>
    using namespace std;
    #include<assert.h>
    #include"List.h"
 
    //節點類構造函數*
    LinkNode::LinkNode(const DataType x)
    :_data(x)
    , _next(NULL)
    , _prev(NULL)
    {}
 
    //鏈表類*
    List::List()        //構造函數
    : _head(NULL)
    , _tail(NULL)
    {}
   
    List::List(const List& s)          //拷貝構造
    : _head(NULL)
    , _tail(NULL)
    {
        if (s._head == NULL)
        {
            return;
        }
        LinkNode* tmp = s._head;
        while (tmp)
        {
            PushBack(tmp->_data);
            tmp = tmp->_next;
        }
 
    }
   
    //賦值運算符的重載（傳統方法）
    //SList & SList::operator=(const SList& s)   
    //{
    //  if (this != &s)
    //  {
    //      _head = NULL;
    //      _tail = NULL;
    //      LinkNode* tmp = s._head;
    //  do{
    //      PushBack(tmp->_data);
    //      tmp = tmp->_next;
    //      } while (tmp != s._head);
    //  }
    //  return *this;
    //}
 
    //賦值運算符的重載（高效寫法）*
    /*void SList::Swap(SList& s)
    {
    swap(_head, s._head);
    swap(_tail, s._tail);
 
    }
    SList&  SList::operator=(SList &s)
    {
    if (this != &s)
    {
    SList tmp(s);
    Swap(tmp);
    }
    return *this;
    }*/
 
    List&  List::operator=(List &s)    //賦值運算符的重載再優化(推薦寫法)
    {
        if (this != &s)
        {
            swap(_head, s._head);
            swap(_tail, s._tail);
        }
        return *this;
    }
    List::~List()    //析構
    {
        Clear();
    }
 
    void List::Reverse()  //鏈表逆置（利用頭插新節點的方法）
    {
        if (_head == NULL || _head== _tail)
        {
            return;
        }
        int ret = Amount();
 
    /*  //  方法一（相當於用頭插的方式重新建立鏈表）
    _tail = new LinkNode(_head->_data);
        LinkNode* begin = NULL;
        LinkNode* tmp = _tail;
        while (--ret)
        {
            LinkNode* del = _head;
            _head = _head->_next;
            delete del;         
            begin = new LinkNode(_head->_data);
            begin->_next = tmp;
            tmp->_prev = begin;
            tmp = begin;
        }
        _head = begin;*/
 
    //////  方法二（只是交換對稱位置節點的數據）**（高效）
        LinkNode* begin = _head;
        LinkNode* end = _tail;
        while (ret)
        {
            if (end->_next == begin)
                break;
            ret /= 2;
            swap(begin->_data, end->_data);
            begin = begin->_next;
            end = end->_prev;
        }
   
        /*// 方法三  交換前驅和後繼指針
          swap(_head, _tail);
          LinkNode* cur = _head;
          while (cur)
          {
              swap(cur->_prev,cur->_next);
              cur = cur->_next;
          }
          */
       
    }
 
    //打印鏈表*
    void List::PrintSList()
    {
        //頭結點為空時，無需打印鏈表
        if (_head == NULL)
        {
            cout << "This SList is Empty !" << endl;
            return;
        }
        else
        {
            LinkNode* tmp = _head; 
          while (tmp)
          {
                cout << tmp->_data << "-->";
                tmp = tmp->_next;
            }
            cout <<"NULL"<< endl;
        }
    }
   
    void List::PushBack(const DataType& x)    //在尾部插入一個節點*
    {
        //如果鏈表為空，插入節點後只有一個節點，此時_head=_tail
        if (_head == NULL)
        {
            _head = new LinkNode(x);
            _tail = _head;
        }
        else
        {
            _tail->_next = new LinkNode(x);
            _tail->_next->_prev=_tail;
            _tail = _tail->_next;
        }
    }
   
    void List::Clear()        //鏈表置空*
    {
        LinkNode* begin = _head;
        while (begin != _tail)
        {
            _head = _head->_next;
            delete begin;
            begin = _head;
        }
        _head = NULL;
        _tail = NULL;
    }
   
    void List::PopBack()    //尾刪
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else if (_head == _tail)
        {
            delete _head;
            _head = NULL;
            _tail = NULL;
        }
        else
        {
            LinkNode* cur = _head;
            while (cur->_next != _tail)
            {
                cur = cur->_next;
            }
            delete _tail;
            _tail = cur;
            _tail->_prev = cur->_prev;
            _tail->_next = NULL;
        }
    }
   
    void List::PushFront(DataType x)  //頭插*
    {
        if (_head == NULL)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = _head;
            _head = new LinkNode(x);
            _head->_next = tmp;
            tmp->_prev = _head;
        }
    }
   
    void List::PopFront()    //刪除首節點
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return;
        }
        LinkNode* tmp = _head;
        _head = _head->_next;
        _head->_prev = NULL;
        delete tmp;
    }
 
    //固定位置插入一個節點（這個函數需和Find函數搭配使用）
    //先用Find函數找到新節點需要插入的位置
    //（將Find函數的返回值傳給Insert函數的參數pos），再在pos節點後面插入新節點x
    void List::Insert(LinkNode* pos, DataType x)  //*
    {
        assert(pos);
        if (pos == _tail)
        {
            PushBack(x);
        }
        else
        {
            LinkNode* tmp = new LinkNode(x);
            tmp->_next = pos->_next;
            pos->_next = tmp;
            tmp->_next->_prev = tmp;
            tmp->_prev = pos;
        }
    }
   
        //刪除某一節點，同樣，要先找到該節點並傳參給Erase函數
    void List::Erase(LinkNode* pos)       
    {
        assert(pos);
        if (pos == _tail)
        {
            PopBack();
        }
        else if (pos == _head)
        {
            PopFront();
        }
        else
        {
            pos->_prev->_next = pos->_next;
            pos->_next->_prev = pos->_prev;
            delete pos;
        }
    }
   
    //查找節點並返回這個節點的地址
    LinkNode* List::Find(DataType x)     
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
            return NULL;
        }
        else
        {
            LinkNode* tmp = _head;
            while (tmp != NULL)
            {
                if (tmp->_data == x)
                {
                    return tmp;
                }
                tmp = tmp->_next;
            }
            return NULL;
        }
    }
   
    int List::Amount()  //計算鏈表節點的數目
    {
        if (_head == NULL)
        {
            return 0;
        }
        else
        {
            int count = 0;
            LinkNode* cur = _head;
            while (cur != _tail)
            {
                count++;
                cur = cur->_next;
            }
            return ++count;
        }
    }
   
    void List::Remove(DataType x)      //查找某節點並刪除
    {
        if (_head == NULL)
        {
            cout << "This SList is empty !" << endl;
        }
        else
        {
            LinkNode* tmp = Find(x);
            if (tmp != NULL)
            {
                Erase(tmp);
            }
        }
    }

Test.cpp

#include"List.h"
#include<stdlib.h>
#include<iostream>
using namespace std;
 
    void Test1()
    {
        List list1;
        list1.PushBack(1);
        list1.PushBack(2);
        list1.PushBack(3);
        list1.PushBack(4);
        list1.PushBack(5);
        list1.PushBack(6);
        list1.PrintSList();
 
    /*  List list2(list1);
        list2.PrintSList();*/
 
        List list2=list1;
        list2.PrintSList();
        //list2.PopBack();
        //list2.Clear();
        //list2.PushFront(0);
        //list2.PopFront();
 
        //////檢驗Find函數
        ////LinkNode* ret=list2.Find(4);
        ////if (ret != NULL)
        ////{
        ////    cout << "ret:" << ret << " " << ret->_data << endl;
        ////}
        ////else
        ////{
        ////    cout << "Not exit !" << endl;
        ////}
       
    /*  int ret=list2.Amount();
        cout << ret << endl;*/
 
        //list2.Erase(list2.Find(5));
        //list2.Insert(list2.Find(2), 0);
        //list2.Remove(3);
        list2.Reverse();
        list2.PrintSList();
    }
 
    int main()
    {
        Test1();
        system("pause");
    }