[數據結構]用C++實現雙鏈表的各種操作（包括頭刪，尾刪，插入，逆序，摧毀，清空等等）

[數據結構]用C++實現雙鏈表的各種操作（包括頭刪，尾刪，插入，逆序，摧毀，清空等等）

//【數據結構】用C++實現雙鏈表的各種操作（包括頭刪，尾刪，插入，逆序，摧毀，清空等等）

//頭文件

#ifndef _LIST_H
#define _LIST_H


#include
using namespace std;


template
class DList;


template
class ListNode
{
	friend class DList;
public:
	ListNode() :data(Type()), next(NULL), prio(NULL)
	{}
	ListNode(Type d, ListNode *n = NULL,ListNode *m=NULL)
		:data(d), next(n), prio(m)
	{}
	~ListNode()
	{}


private:
	Type data;
	ListNode *next;
	ListNode *prio;
};


template
class DList
{
public:
	DList()
	{
		first = last = Buynode();
	}
	~DList()
	{
		destroy();
	}
public:




	void push_back(const Type &x)            //尾插``
	{
		ListNode *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 *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 *p = last;
		last = last->prio;
		last->next = NULL;
		delete p;
		first->data--;


	}


	void pop_front()                //頭刪``
	{
		if (first->data == 0)
		{
			return;
		}
		else
		{
			ListNode *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  *p = Buynode(x);
		ListNode  *s = first;
		if (first->data == 0)
		{
			push_back(x);
			return;
		}
		while (s->next->datanext->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 *q = first->next;
		while (q != NULL)
		{
			cout << q->data << "->";
			q = q->next;
		}
		cout << "NULL  first->data=" << first->data <<" last->data="<data<< " last->next=" << last->next <<" "<< endl;
	}


	void sort()                     //排序``
	{
		if (first->data == 0)
		{
			return;
		}
		ListNode *p = first->next;
		ListNode *q = p->next;
		p->next = NULL;
		last = p;
		first->data = 1;
		ListNode *r;
		while (q != NULL)
		{
			insert_val(q->data);
			r = q;
			q = q->next;
			delete r;
		}
	}




	ListNode* find(const Type &x)              //查找``
	{
		ListNode *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 *p = find(x);
			if (p == NULL)
			{
				cout << "未找到該數：" << endl;
				return;
			}
			ListNode *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 *p = first->next;
		ListNode *q = p->next;
		p->next = NULL;
		last = p;
		first->data = 1;
		ListNode *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* Buynode(Type x = Type())
	{
		ListNode *p = new ListNode(x);
		return p;
	}
private:
	ListNode *first;
	ListNode *last;
};




//主函數

#endif


#include"DList.h"


void main()
{
	DList 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;
}