如何使用模板函数实现双链表

这篇文章给大家分享的是有关如何使用模板函数实现双链表的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

#include <iostream>

#include <string>

using namespace std;

template<typename T>

struct Node

{

T _data;

Node<T> * _next;

Node<T> * _prev;

Node(const T&d)

:_next(NULL)

, _prev(NULL)

, _data(d)

{}

};

template<typename T>

class Dlist

{

public:

Node<T> *_head;

Node<T> *_tail;

public:

Dlist();

~Dlist();

Dlist(const Dlist<T>& list);

Dlist<T> & operator=(const Dlist<T>& list);

void PushBack(const T&d);

void Insert(int pos, const T&d);

void PopBack();

void PushFront(const T&d);

void PopFront();

void Remove(const T&d);

void RemoveAll(const T&d);

void Reverse();

void Sort();

void BubbleSort();

void print();

void DelKNode(int k);

Dlist& Merge(Dlist& l1, Dlist& l2);

void EraseNotTail(Node<T>* pos);

void InsertFrontNode(Node<T>* pos, const T& d);

Node <T>*Find(const T&d);

ostream &operator<<(ostream &os)

{

Node<T> *cur = _head;

while (cur)

{

os << cur->_data << " ";

cur = cur->_next;

}

return os;

}

};

template <typename T>

Dlist<T>::~Dlist()

{

Node<T>* cur = _head;

while (cur)

{

Node<T> *del = cur;

cur = cur->_next;

delete cur;

cur = NULL;

}

}

template <typename T>

void Dlist<T>::DelKNode(int k)

{

Node <T>*fast = _head;

Node <T>*slow = _head;

while (--k)

fast = fast->_next;

while(fast->_next)

{

fast = fast->_next;

slow = slow->_next;

}

slow->_prev->_next = slow->_next;

slow->_next->_prev = slow->_prev;

delete slow;

}

template <typename T>

void Dlist<T>::Sort()

{

Node <T> *cur = _head;

Node <T> *end = NULL;

T tmp = 0;

if (_head == NULL || _head == _tail)

return;

else

{

while (cur != end)

{

cur = _head;

while (cur->_next && cur->_next != end)

{

if (cur->_data > cur->_next->_data)

{

tmp = cur->_data;

cur->_data = cur->_next->_data;

cur->_next->_data = tmp;

}

cur = cur->_next;

}

end = cur;

}

}

}

template <typename T>

void Dlist<T>::BubbleSort()

{

Node <T>*cur = _head;

Node <T>*end = NULL;

while (cur != end)

{

cur = _head;

while (cur->_next && cur->_next != end)

{

if (cur->_data > cur->_next->_data)

{

T tem = cur->_data;

cur->_data = cur->_next->_data;

cur->_next->_data = tem;

}

cur = cur->_next;

}

end = cur;

}

}

template <typename T>

void Dlist<T>::EraseNotTail(Node<T>* pos)

{

pos->_prev->_next = pos->_next;

pos->_next->_prev = pos->_prev;

delete pos;

pos = NULL;

}

template <typename T>

void Dlist<T>::Remove(const T&d)

{

Node <T>*cur = _head;

while (cur)

{

if (cur->_data == d)

{

if (cur == _head)

{

PopFront();

return;

}

else

if (cur == _tail)

{

PopBack();

return;

}

else

{

cur->_next->_prev = cur->_prev;

cur->_prev->_next = cur->_next;

delete cur;

return;

}

}

cur = cur->_next;

}

}

template <typename T>

Node <T>*Dlist<T>::Find(const T&d)

{

Node <T>*cur = _head;

while (cur)

{

if (cur->_data == d)

return cur;

cur = cur->_next;

}

return NULL;

}

template <typename T>

void Dlist<T>::RemoveAll(const T&d)

{

Node <T>*cur = _head;

Node <T>*del = NULL;

while (cur)

{

if (cur->_data == d)

{

del = cur;

if (cur == _head)

{

PopFront();

cur = _head;

}

else if (cur == _tail)

{

PopBack();

cur = _head;

}

else

{

cur->_prev->_next = cur->_next;

cur->_next->_prev = cur->_prev;

cur = cur->_prev->_next;

}

delete del;

}

else

{

cur = cur->_next;

}

}

}

template <typename T>

void Dlist<T>::print()

{

Node<T>* cur = _head;

while (cur)

{

cout << cur->_data << "->";

cur = cur->_next;

}

cout << "over" << endl;

}

template <typename T>

Dlist<T>&Dlist<T>::Merge(Dlist& l1, Dlist& l2)

{

Node <T>*cur = NULL;

Node <T>*p1 = l1._head;

Node <T>*NewNode = p1;

Node <T>*p2 = l2._head;

if (p1 == p2)

return l1;

if (p1 == NULL && p2 != NULL)

return l2;

if(p1 != NULL && p2 == NULL)

return l1;

else

if (p1->_data < p2->_data)

{

p1 = p1->_next;

}

else

{

NewNode->_data = p2->_data;

p2 = p2->_next;

}

cur = NewNode;

while (p1&&p2)

{

if (p1->_data < p2->_data)

{

cur->_next = p1;

p1->_prev = cur;

p1 = p1->_next;

cur = cur->_next;

}

else

{

cur->_next = p2;

p2->_prev = cur;

cur = cur->_next;

p2 = p2->_next;

}

}

if (p1)

{

cur->_next = p1;

p1->_prev = cur;

}

else

{

cur->_next= p2;

p2 = p2->_next;

}b

return l1;

}

template <typename T>

Dlist<T> & Dlist<T>::operator =(const Dlist<T>&list)

{

Node <T> *del = _head;

Node <T>* tem = _tail;

if (this != &list)

{

delete _head;

_head = NULL;

delete _tail;

_tail = NULL;

Node<T> *cur = list._head;

while (cur)

{

Dlist<T>::PushBack(cur->_data);

cur = cur->_next;

}

}

return *this;

}

template <typename T>

void Dlist<T>::Insert(int pos, const T&d)

{

Node <T>*NewNode = new Node<T>(d);

Node <T>*cur = _head;

while (cur && (--pos))

{

cur = cur->_next;

}

NewNode->_next = cur->_next;

NewNode->_prev = cur;

cur->_next = NewNode;

}

template <typename T>

Dlist<T>::Dlist()

{

_head = NULL;

_tail = NULL;

}

template <typename T>

void Dlist<T>::PushFront(const T&d)

{

Node<T>* NewNode = new Node<T>(d);

if (_head == NULL)

{

_head = NewNode;

_tail = _head;

}

else

{

_head->_prev = NewNode;

NewNode->_next = _head;

_head = NewNode;

}

}

template <typename T>

void Dlist<T>::PushBack(const T&d)

{

Node<T>* NewNode = new Node<T>(d);

if (_head == NULL)

{

_head = NewNode;

_tail = _head;

}

else

{

_tail->_next = NewNode;

NewNode->_prev = _tail;

_tail = NewNode;

}

}

template <typename T>

void Dlist<T>::PopBack()

{

if (_head == NULL)

return;

else if (_head == _tail)

{

delete _head;

_head = NULL;

_tail = _head;

}

else

{

_tail = _tail->_prev;

_tail->_next = NULL;

}

}

template <typename T>

void Dlist<T>::Reverse()

{

Node<T>* NewNode = NULL;

Node <T> *cur = _head;

Node<T> *prev = NULL;

while (cur->_next)

{

prev = cur;

cur = cur->_next;

prev->_next = NewNode;

prev->_prev = cur;

NewNode = prev;

}

_tail = _head;

_tail->_next = NULL;

_head = cur;

_head->_prev = NULL;

_head->_next = NewNode;

}

template <typename T>

void Dlist<T>::PopFront()

{

if (_head == NULL)

return;

else if (_head == _tail)

{

delete _head;

_head = NULL;

_tail = _head;

}

else

{

_head = _head->_next;

_head->_prev = NULL;

}

}

template <typename T>

Dlist<T>::Dlist(const Dlist<T>& list)

{

Node<T> *cur = list._head;

while (cur)

{

Dlist<T>::PushBack(cur->_data);

cur = cur->_next;

}

}

int main()

{

Dlist<int> list1;

Dlist <int>list2;

Node <int>*tem = NULL;

Node <int>*cur = NULL;

list1.PushBack(1);

list1.PushBack(2);

list1.PushBack(3);

list1.PushBack(2);

/*list2.PushBack(5);

list2.PushBack(6);

list2.PushBack(7);

list2.PushBack(8);

list2.Merge(list1, list2)<<cout;*/

list1.Insert(2, 5);

///*list1.Reverse();

//list1.PushFront(5);

//list1.PopBack();*/

///*Dlist <int> list2;

//list2 = list1;*/

list1.RemoveAll(2);

/*list1.BubbleSort();*/

list1.print();

getchar();

return 0;

}

感谢各位的阅读！关于“如何使用模板函数实现双链表”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！