//【数据结构】用C++实现双链表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）
//头文件
#ifndef _LIST_H
#define _LIST_H
#include<iostream>
using namespace std;
template<class Type>
class DList;
template<class Type>
class ListNode
{
friend class DList<Type>;
public:
ListNode() :data(Type()),next(NULL),prio(NULL)
{}
ListNode(Type d,ListNode<Type> *n = NULL,ListNode<Type> *m=NULL)
:data(d),next(n),prio(m)
{}
~ListNode()
{}
private:
Type data;
ListNode<Type> *next;
ListNode<Type> *prio;
};
template<class Type>
class DList
{
public:
DList()
{
first = last = Buynode();
}
~DList()
{
destroy();
}
public:
void push_back(const Type &x) //尾插``
{
ListNode<Type> *s = Buynode(x);
last->next = s;
s->prio = last;
last = s;
first->data++;
}
void push_front(const Type &x) //头插``
{
if (first->data == 0)
{
push_back(x);
return;
}
ListNode<Type> *s = Buynode(x);
s->next = first->next;
first->next->prio = s;
first->next = s;
s->prio = first;
last = s;
for (int i = 0; i < first->data; i++)
{
last = last->next;
}
first->data++;
}
void pop_back() //尾删``
{
if (first->data == 0)
return;
ListNode<Type> *p = last;
last = last->prio;
last->next = NULL;
delete p;
first->data--;
}
void pop_front() //头删``
{
if (first->data == 0)
{
return;
}
else
{
ListNode<Type> *s = first->next;
if (first->data == 1)
{
delete s;
last = first;
last->next = NULL;
}
else
{
first->next = s->next;
s->next->prio = first;
delete s;
}
first->data--;
}
}
void insert_val(const Type &x) //按值插入``
{
ListNode <Type> *p = Buynode(x);
ListNode <Type> *s = first;
if (first->data == 0)
{
push_back(x);
return;
}
while (s->next->data<x&&s->next->next != NULL)
{
s = s->next;
}
if (s->next->next == NULL)
{
if (s->next->data>x)
{
p->next = s->next;
s->next->prio = p;
s->next = p;
p->prio = s;
first->data++;
}
else
push_back(x);
}
else
{
p->next = s->next;
s->next->prio = p;
s->next = p;
p->prio = s;
first->data++;
}
}
void show_list() //显示``
{
if (first->data == 0)
{
cout << "NULL" << endl;
return;
}
ListNode<Type> *q = first->next;
while (q != NULL)
{
cout << q->data << "->";
q = q->next;
}
cout << "NULL first->data=" << first->data <<" last->data="<<last->data<< " last->next=" << last->next <<" "<< endl;
}
void sort() //排序``
{
if (first->data == 0)
{
return;
}
ListNode<Type> *p = first->next;
ListNode<Type> *q = p->next;
p->next = NULL;
last = p;
first->data = 1;
ListNode<Type> *r;
while (q != NULL)
{
insert_val(q->data);
r = q;
q = q->next;
delete r;
}
}
ListNode<Type>* find(const Type &x) //查找``
{
ListNode<Type> *s;
for (s = first->next; s != NULL; s = s->next)
{
if (s->data == x)
{
return s;
}
}
return NULL;
}
int length() //求长度``
{
return(first->data);
}
void delete_val(const Type &x) //按值删除``
{
if (first->data == 0)
{
cout << "未找到该数：" << endl;
return;
}
else
{
ListNode<Type> *p = find(x);
if (p == NULL)
{
cout << "未找到该数：" << endl;
return;
}
ListNode<Type> *q = first;
while (q->next != p)
{
q = q->next;
}
if (q->next->next == NULL)
{
pop_back();
}
else
{
q->next = p->next;
p->next->prio = q;
delete p;
first->data--;
}
}
}
void clear() //清除``
{
if (first->data == 0)
return;
while (first->next != NULL)
{
pop_back();
}
}
void resver() //逆序``
{
if (first->data == 0)
{
return;
}
ListNode<Type> *p = first->next;
ListNode<Type> *q = p->next;
p->next = NULL;
last = p;
first->data = 1;
ListNode<Type> *r;
while (q != NULL)
{
push_front(q->data);
r = q;
q = q->next;
delete r;
}
}
void quit_system(int &a) //退出``
{
clear();
a = 0;
}
void destroy() //摧毁``
{
clear();
delete first;
}
protected:
ListNode<Type>* Buynode(Type x = Type())
{
ListNode<Type> *p = new ListNode<Type>(x);
return p;
}
private:
ListNode<Type> *first;
ListNode<Type> *last;
};
//主函数
#endif
#include"DList.h"
void main()
{
DList<int> mylist;
int select = 1;
int Item;
//int pos;
while (select)
{
cout << "**************************************" << endl;
cout << "* [1] show_list [2] push_front *" << endl;
cout << "* [3] push_back [4] pop_front *" << endl;
cout << "* [5] pop_back [6] insert_val *" << endl;
cout << "* [7] find [8] delete_val *" << endl;
cout << "* [9]length [10] clear *" << endl;
cout << "* [11] quit_system [12] destroy *" << endl;
cout << "* [13] resver [14] sort *" << endl;
cout << "**************************************" << endl;
cout << "请选择:>";
cin >> select;
switch (select)
{
case 1:
mylist.show_list();
break;
case 2:
cout << "请输入要插入的值(-1结束):>";
while (cin >> Item,Item != -1)
{
mylist.push_front(Item);
}
break;
case 3:
cout << "请输入要插入的值(-1结束):>";
while (cin >> Item,Item != -1)
{
mylist.push_back(Item);
}
break;
case 4:
mylist.pop_front();
;
break;
case 5:
mylist.pop_back();
break;
case 6:
cout << "请输入要插入的值:>";
cin >> Item;
mylist.insert_val(Item);
break;
case 7:
cout << "请输入要查找的数：";
cin >> Item;
cout << "该数的地址为：";
cout << mylist.find(Item) << endl;
break;
case 8:
cout << "请输入要删除的值:>";
cin >> Item;
mylist.delete_val(Item);
break;
case 9:
cout << "该顺序表长度为：" << mylist.length() << endl;
break;
case 10:
mylist.clear();
break;
case 11:
mylist.quit_system(select);
break;
case 12:
mylist.destroy();
case 13:
mylist.resver();
break;
case 14:
mylist.sort();
break;
default:
break;
}
}
return;
}
<img src="http://img.blog.csdn.net/20150531224355335?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZG91ZG91d2ExMjM0/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />
原文链接：https://www.f2er.com/datastructure/382645.html
