双向链表冒泡排序c语言,【C++】模版实现双向链表的各种操作(如：逆置、去重Unique、分类（冒泡）、合并)...

在cplusplus.com里，我们可以搜索list来查看库是如何实现双向链表的。当然，我们也可以在平时使用时包上头文件list来调用C++里的list库。在这里，我今天就不再赘述用C语言或者C++未引入模版这两种场景来向大家分享双向链表了，而是注重多类型都可以使用双向链表。也就是我们今天的主题：模版实现双向链表。

我主要实现了尾插、尾删、打印、去重、逆置等等一系列操作，而关于像Insert()、Erase()之类的操作我并没有在这里全部实现，一方面是因为之前我们反复实现过，如果你感兴趣的话，可以查看我之前的博客。另一方面，我出于较为低效不常见的原因。希望大家理解。

另外，需要说明的一点是，今天我使用的均是类内声明，类外定义的方式。

代码如下：#include

using namespace std;

template

struct ListNode

{

ListNode(const T& x)

:_next(NULL)

, _prev(NULL)

, _data(x)

{}

ListNode* _next;

ListNode* _prev;

T _data;

};

template

class List

{

public:

List()

:_head(NULL)

, _tail(NULL)

{}

List(const List& l)

{

ListNode* cur = l._head;

while (cur)

{

this->PushBack(cur->_data);

cur = cur->_next;

}

}

List& operator=(const List& l)

{

//先删除节点，再插入节点

if (&s != this)

{

ListNode* pcur = _head;

while (pcur)

{

ListNode* del = pcur;

pcur = pcur->_next;

delete del;

del = NULL;

}

ListNode* cur = _head;

while (cur)

{

this->PushBack(cur->_data);

cur = cur->_next;

}

}

return *this;

}

~List()//一个节点一个节点的删除

{

ListNode* cur = _head;

while (cur)

{

ListNode* del = cur;

cur = cur->_next;

delete del;

del = NULL;

}

}

void PushBack(const T& x);

void PopBack();

void Unique();

void PrintList();

void Reverse();

int Length();

void Sort();

void Merge(List& l2);

protected:

ListNode* _head;

ListNode* _tail;

};

//尾插

template

void List::PushBack(const T& x)

{

//分析：分为两种情况：无节点、有节点

if (_head == NULL)

{

_head = _tail = new ListNode(x);

}

else

{

ListNode* cur = new ListNode(x);

_tail->_next = cur;

cur->_prev = _tail;

_tail = cur;

_tail->_next = NULL;

}

}

//尾删

template

void List::PopBack()

{

//分析：分为三种情况：无节点、一个节点、多个节点

if (_head == _tail)

{

if (_head == NULL)

{

return;

}

else

{

delete _head;

_head = _tail = NULL;

}

}

else

{

ListNode* prev = _tail->_prev;

delete _tail;

_tail = NULL;

_tail = prev;

_tail->_next = NULL;

}

}

//去重:前提是针对已排序的有重复数据的链表

//template

//void List::Unique()

//{

//    //分析：分为三种情况：无节点一个节点(无需删除节点)、两个节点、两个以上节点

//    if (_head == _tail)

//    {

//        return;

//    }

//    else

//    {

//        ListNode* pcur = _head;

//        ListNode* pnext = _head->_next;

//        if (pnext->_next == NULL)    //两个节点

//        {

//            if (pcur->_data == pnext->_data)

//            {

//                delete pnext;

//                pnext = NULL;

//                _tail = _head = pcur;

//                return;

//            }

//            else

//            {

//                return;

//            }

//        }

//        else

//        {

//            //两个以上节点

//            ListNode* cur = _head;

//            while (cur->_next)

//            {

//                ListNode* next = cur->_next;

//                ListNode* nextnext = next->_next;

//                if (cur->_data == next->_data)

//                {

//                    cur->_next = nextnext;

//                     nextnext->_prev = cur;

//                    delete next;

//                    next = NULL;

//                }

//                cur = cur->_next;

//            }

//        }

//    }

//}

//逆置

template

void List::Reverse()

{

//分析：从两头开始走,交换数据(分奇数个数据和偶数个数据)

ListNode* begin = _head;

ListNode* end = _tail;

while (!((begin == end) || end->_next == begin))

{

swap(begin->_data, end->_data);

begin = begin->_next;

end = end->_prev;

}

}

//长度

template

int List::Length()

{

ListNode* cur = _head;

int count = 0;

while (cur)

{

count++;

cur = cur->_next;

}

return count;

}

//分类

template

void List::Sort()

{

//使用冒泡排序,实现升序或者降序

ListNode* i = _head;

while (i != _tail)

{

ListNode* j = _head;

ListNode* end = _tail;

while (j != end)

{

if (j->_data >(j->_next)->_data)

{

swap(j->_data, (j->_next)->_data);

}

j = j->_next;

}

end = end->_prev;

i = i->_next;

}

}

//合并

template

void List::Merge(List& l2)

{

ListNode* cur1 = _head;

ListNode* cur2 = l2._head;

if (cur1->_data > cur2->_data)

{

swap(cur1->_data, cur2->_data);

}

while (cur1 && cur2)

{

if (cur1->_data <= cur2->_data)

{

cur1 = cur1->_next;

}

else

{

ListNode* tmp = cur2;

cur2 = cur2->_next;

ListNode* prev = cur1->_prev;

cur1->_prev = tmp;

tmp->_next = cur1;

prev->_next = tmp;

tmp->_prev = prev;

}

}

if (cur1 == NULL)

{

_tail->_next = cur2;

cur2->_prev = _tail;

_tail = l2._tail;

}

}

//打印

template

void List::PrintList()

{

ListNode* cur = _head;

while (cur)

{

cout <_data <";

cur = cur->_next;

}

cout <

}

void Test()

{

List l1;

l1.PushBack(1);

l1.PushBack(3);

l1.PushBack(5);

l1.PushBack(7);

l1.PrintList();

l1.PopBack();

l1.PrintList();

/*l1.Unique();

l1.PrintList();*/

List l2;

l2.PushBack(2);

l2.PushBack(4);

l2.PushBack(6);

l1.Merge(l2);

l1.PrintList();

l1.Reverse();

l1.PrintList();

l1.Sort();

l1.PrintList();

}

int main()

{

Test();

system("pause");

return 0;

}