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

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

#include

#include

using namespace std;

template

struct Node

{

T _data;

Node * _next;

Node * _prev;

Node(const T&d)

:_next(NULL)

, _prev(NULL)

, _data(d)

{}

};

template

class Dlist

{

public:

Node *_head;

Node *_tail;

public:

Dlist();

~Dlist();

Dlist(const Dlist& list);

Dlist & operator=(const Dlist& 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* pos);

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

Node *Find(const T&d);

ostream &operator<<(ostream &os)

{

Node *cur = _head;

while (cur)

{

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

cur = cur->_next;

}

return os;

}

};

template

Dlist::~Dlist()

{

Node* cur = _head;

while (cur)

{

Node *del = cur;

cur = cur->_next;

delete cur;

cur = NULL;

}

}

template

void Dlist::DelKNode(int k)

{

Node *fast = _head;

Node *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

void Dlist::Sort()

{

Node *cur = _head;

Node *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

void Dlist::BubbleSort()

{

Node *cur = _head;

Node *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

void Dlist::EraseNotTail(Node* pos)

{

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

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

delete pos;

pos = NULL;

}

template

void Dlist::Remove(const T&d)

{

Node *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

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

{

Node *cur = _head;

while (cur)

{

if (cur->_data == d)

return cur;

cur = cur->_next;

}

return NULL;

}

template

void Dlist::RemoveAll(const T&d)

{

Node *cur = _head;

Node *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

void Dlist::print()

{

Node* cur = _head;

while (cur)

{

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

cur = cur->_next;

}

cout << "over" << endl;

}

template

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

{

Node *cur = NULL;

Node *p1 = l1._head;

Node *NewNode = p1;

Node *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

Dlist & Dlist::operator =(const Dlist&list)

{

Node *del = _head;

Node * tem = _tail;

if (this != &list)

{

delete _head;

_head = NULL;

delete _tail;

_tail = NULL;

Node *cur = list._head;

while (cur)

{

Dlist::PushBack(cur->_data);

cur = cur->_next;

}

}

return *this;

}

template

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

{

Node *NewNode = new Node(d);

Node *cur = _head;

while (cur && (--pos))

{

cur = cur->_next;

}

NewNode->_next = cur->_next;

NewNode->_prev = cur;

cur->_next = NewNode;

}

template

Dlist::Dlist()

{

_head = NULL;

_tail = NULL;

}

template

void Dlist::PushFront(const T&d)

{

Node* NewNode = new Node(d);

if (_head == NULL)

{

_head = NewNode;

_tail = _head;

}

else

{

_head->_prev = NewNode;

NewNode->_next = _head;

_head = NewNode;

}

}

template

void Dlist::PushBack(const T&d)

{

Node* NewNode = new Node(d);

if (_head == NULL)

{

_head = NewNode;

_tail = _head;

}

else

{

_tail->_next = NewNode;

NewNode->_prev = _tail;

_tail = NewNode;

}

}

template

void Dlist::PopBack()

{

if (_head == NULL)

return;

else if (_head == _tail)

{

delete _head;

_head = NULL;

_tail = _head;

}

else

{

_tail = _tail->_prev;

_tail->_next = NULL;

}

}

template

void Dlist::Reverse()

{

Node* NewNode = NULL;

Node *cur = _head;

Node *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

void Dlist::PopFront()

{

if (_head == NULL)

return;

else if (_head == _tail)

{

delete _head;

_head = NULL;

_tail = _head;

}

else

{

_head = _head->_next;

_head->_prev = NULL;

}

}

template

Dlist::Dlist(const Dlist& list)

{

Node *cur = list._head;

while (cur)

{

Dlist::PushBack(cur->_data);

cur = cur->_next;

}

}

int main()

{

Dlist list1;

Dlist list2;

Node *tem = NULL;

Node *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)<

list1.Insert(2, 5);

///*list1.Reverse();

//list1.PushFront(5);

//list1.PopBack();*/

///*Dlist list2;

//list2 = list1;*/

list1.RemoveAll(2);

/*list1.BubbleSort();*/

list1.print();

getchar();

return 0;

}

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