【代码】模板实现双向链表的去重、拼接、合并、排序
/*
模板实现双向链表的去重、拼接、合并、排序
*/
#pragma once
#include<iostream>
template <class T>
struct Node
{
T _data;
Node<T> *_next;
Node<T> *prev;
};
template <class T>
class SeqList
{
public:
SeqList()
:_head(NULL),
_tail(NULL)
{
}
SeqList(const SeqList & l)
{
}
SeqList& operator = (const SeqList & l)
{
}
~SeqList()
{
_Clear();
}
void PushBack(const T &x)
{
Node<T>* tmp = new Node<T>;
InitNode(tmp, x);
if (_head == NULL)
{
_head = _tail = tmp;
}
else
{
_tail->_next = tmp;
tmp->prev = _tail;
_tail = _tail->_next;
}
}
void Unique()//去重
{
Node<T>*cur = _head;
while (cur)
{
Node<T>*tmp = cur->_next;
while (tmp)
{
Node<T>*DelTmp = tmp;
if (cur->_data == tmp->_data)
{
if (tmp->_next)
{
cur->_next = tmp->_next;
tmp->_next->prev = cur;
}
else
{
cur->_next = NULL;
}
tmp = tmp->_next;
DelTmp->_next = NULL;
DelTmp->prev = NULL;
delete DelTmp;
}
else
tmp = tmp->_next;
}
cur = cur->_next;
}
}
void Sort()//排序
{
Node<T>*Cur = _head;
while (Cur)
{
Node<T>*CurNext = Cur->_next;
while (CurNext)
{
if (Cur->_data > CurNext->_data)
{
swap(Cur->_data, CurNext->_data);
}
CurNext = CurNext->_next;
}
Cur = Cur->_next;
}
}
void Splice(Node<T>*pos, Node<T>*begin, size_t size)//拼接
{
Node<T>*end = begin;
while (--size)
{
end = end->_next;
}
if (end->_next)
{
end->_next->prev = NULL;
}
end->_next = pos->_next;
begin->prev = pos;
if (pos->_next)
{
pos->_next->prev = end;
}
pos->_next = begin;
}
void Splice(Node<T>*pos, SeqList &l)
{
Node<T>*begin = l.Gethead();
Node<T>*end = l.Gettail();
end->_next = pos->_next;
begin->prev = pos;
if (pos->_next)
{
pos->_next->prev = end;
}
pos->_next = begin;
}
void Merge(SeqList &l)//合并
{
Splice(_tail, l);
Sort();
l._head = NULL;
l._tail = NULL;
}
void InitNode(Node<T>*_node,const T &x)
{
_node->prev = NULL;
_node->_next = NULL;
_node->_data = x;
}
Node<T>* Gettail()
{
return _tail;
}
Node<T>*Gethead()
{
return _head;
}
protected:
void _Clear()
{
Node<T>*cur = _head;
while (cur)
{
Node<T>*tmp = cur;
cur = cur->_next;
tmp->prev = NULL;
tmp->_next = NULL;
delete tmp;
}
}
Node<T> *_head;
Node<T> *_tail;
};
电脑没电了,如有不足希望批评指正,如有疑问也可以提问。
转载于:https://blog.51cto.com/10743407/1751104