【Weiss】【第03章】双链表例程

双链表因为多了个前向指针，需要考虑的特殊因素多了一倍

所以中间插入（这儿没写）和中间删除会比较复杂。

其它倒没什么特别的，代码如下。

测试代码

 #include <iostream>

 #include "double_linklist.h"

 using namespace std;

 using namespace doublelinklist;

 template class DList<int>;

 int main(void)

 {

     DList<int> number;

     //测试插入

     cout << "/*additem()*/" << endl;

     number.additem();

     number.additem();

     number.additem();

     number.additem();

     number.additem();

     number.additem();

     number.additem();

     number.traverse();

     cout << "\n" << flush;

     number.reverse();

     cout << "\n/*end*/\n\n" << flush;

     //测试获取长度

     cout << "/*length()*/" << endl;

     cout << number.size() << endl;

     cout << "/*end*/\n\n" << flush;

     //测试获得头元素

     cout << "/*getfirst()*/" << endl;

     cout << number.getfirst() << endl;

     cout << "/*end*/\n\n" << flush;

     //测试删除存在的元素（头尾及中间元素各一）

     cout << "/*remove()*/" << endl;

     number.remove();

     number.remove();

     number.remove();

     number.traverse();

     cout << "\n" << flush;;

     number.reverse();

     cout << "\n/*end*/\n\n" << flush;

     //测试删除不存在的元素

     cout << "/*remove()*/" << endl;

     number.remove();

     cout << "/*end*/\n\n" << flush;

     //测试清空，并测试从空表中删除元素

     cout << "/*clear(),remove()*/" << endl;

     number.clear();

     number.remove();

     cout << "/*end*/\n\n" << flush;

     system("pause");

 }

 double_linklist_driver

实现代码

 #ifndef DOUBLELINKLIST

 #define DOUBLELINKLIST

 #include <iostream> using namespace std;

 namespace doublelinklist

 {

 //链表节点模板

 template <typename T> struct Node

 {

     Node<T>() : next(nullptr),prev(nullptr){}

     Node<T>(const T &item, Node<T>* ptrn = nullptr, Node<T>* ptrp = nullptr) : data(item), next(ptrn), prev(ptrp){}

     T data;

     Node<T>* next;

     Node<T>* prev;

 };

 //头节点及链表主体操作

 template <typename T> class DList

 {

 //构造函数

 public:

     DList<T>() : length(), front(nullptr){}

 //接口

 public:

     //返回长度

     unsigned int size()const{ return length; }

     //返回头指针

     Node<T>* begin()const{ return front; }

     //判断是否为空

     bool empty()const{ return length == ; }

     //获得头元素

     T getfirst()const{ return front->data; }

     //获得尾元素

     T getlast()const{ return rear->data; }

     //#查找元素所在地址

     Node<T>* find(const T &item)const;

     //#尾部加入新元素

     bool additem(const T &item);

     //#删除指定元素

     bool remove(const T &item);

     //#遍历顺序输出链表元素

     void traverse()const;

     //#遍历倒序输出链表元素

     void reverse()const;

     //清空链表

     void clear();

 //辅助函数

 private:

     //#查找元素前驱

     Node<T>* find_prev(const T& item)const;

 //数据

 private:

     unsigned int length;

     Node<T>* front;

     Node<T>* rear;

 };

 //如果元素为头元素或元素不存在则返回nullptr，否则返回前驱

 template <typename T> Node<T>* DList<T>::find_prev(const T& item)const

 {

     if (length == )

         return nullptr;

     if (front->data == item)

         return nullptr;

     for (Node<T>* iter = front; iter->next != nullptr; iter = iter->next)

     {

         if (iter->next->data == item)

             return iter;

     }

     return nullptr;

 }

 //调用find_prev，如果元素存在则返回地址，不存在则返回nullptr

 template <typename T> Node<T>* DList<T>::find(const T &item)const

 {

     Node<T>* iter = find_prev(item);

     if (length == )

         return nullptr;

     if (front->data == item)

         return front;

     return iter->next;

 }

 template <typename T> bool DList<T>::additem(const T &item)

 {

     Node<T>* pnew = new Node<T>(item);

     //原链表无元素

     //头尾指针均指向新节点，且新节点前后指针默认为nullptr

     if (length == )

         front = rear = pnew;

     else

     {

         rear->next = pnew;

         pnew->prev = rear;

         rear = pnew;

     }

     ++length;

     return true;

 }

 //删除操作相对复杂

 template <typename T> bool DList<T>::remove(const T &item)

 {

     //先判断链表是否空避免front->data未定义

     if (length == )

     {

         cout << "No data!" << endl;

         return false;

     }

     Node<T>* iter = find_prev(item);

     //find_prev返回nullptr，且首元素不等，说明链表中无此元素

     if (iter == nullptr && front->data != item)

     {

         cout << "Can not find!" << endl;

         return false;

     }

     Node<T>* save;

     //如果元素是首元素

     //则仅需将save后继（如果存在）的前向指针改为nullptr

     //如果save无后继，说明链表删除后为空，将rear置空

     if (front->data == item)

     {

         save = front;

         front = front->next;

         if (save != rear)

             save->next->prev = nullptr;

         else

             rear = nullptr;

     }

     //如果元素不是首元素

     //则save的前驱iter的后向指针需改指向save后继

     //同时，save后继（如果存在）的前向指针改为指向save的前驱iter

     //如果save无后继，则rear要指向新的尾节点

     else

     {

         save = iter->next;

         iter->next = save->next;

         if (save != rear)

             save->next->prev = iter;

         else

             rear = iter;

     }

     delete save;

     --length;

     return true;

 }

 template <typename T> void DList<T>::traverse()const

 {

     if (length != )

     {

         for (Node<T>* iter = front; iter != nullptr; iter = iter->next)

             cout << iter->data << ends;

     }

 }

 template <typename T> void DList<T>::reverse()const

 {

     if (length != )

     {

         for (Node<T>* iter = rear; iter != nullptr; iter = iter->prev)

             cout << iter->data << ends;

     }

 }

 template <typename T> void DList<T>::clear()

 {

     Node<T>* iter;

     while (front != nullptr)

     {

         iter = front;

         front = front->next;

         delete iter;

     }

     front = rear = nullptr;

     length = ;

 }

 }

 #endif

巴特西

【Weiss】【第03章】双链表例程

最新文章

热门文章