C++《数据结构与算法》-->双向链表

#include<iostream>
using namespace std;

typedef struct _DoubleList
{
	int Data;   //双向链表的数据域
	struct _DoubleList * perv;//指向前一个节点的指针域
	struct _DoubleList * next;//指向后一个节点的指针域
}DoubleList, DoubleListNode;

//初始化双向链表
bool initDoubleList(DoubleList* &L){
	L = new DoubleList;
	if (!L)
	{
		cout<<"初始化失败！"<<endl;
		return false;
	}
	L->Data = -1;
	L->perv = NULL;
	L->next = NULL;
	return true;
}

//头部添加节点
bool addDoubleListNode(DoubleList* &L,DoubleListNode* &node){
	if (!L)
	{
		cout<<"插入失败！"<<endl;
		return false;
	}
	if (!L->next)//首节点插入
	{
		node->next = NULL;
		L->next = node;
		node->perv = L;
	}else
	{
		node->next = L->next;
		node->perv = L;
		L->next->perv = node;
		L->next = node;
	}
	return true;
}

//尾部添加节点
bool addDoubleListNode_back(DoubleList* &L,DoubleListNode* &node){
	if (!L)
	{
		cout<<"链表不存在，插入失败！"<<endl;
		return false;
	}

	DoubleList *p;
	p = L->next;
	while (p)
	{
		p = p->next; //找到尾节点
	}
	node = p->next;
	p->next = node;
	node->perv = p;
	return true;
}

//指定位置插入指定数值的节点
bool insterDoubleListNodeByIndex(DoubleList* &L, int i, int value){
	if (!L)
	{
		cout<<"链表不存在！"<<endl;
		return false;
	}
	int j = 0;
	DoubleList *p=NULL,*pPre;
	if (i<=0)
	{
		//链表为空或者要插入的位置<=0
		cout<<"你插入位置太靠前了！"<<endl;
		return false;
	}

	pPre = L;
	while (pPre && j < i)
	{
		pPre = pPre->next;
		j++;
	}

	if (!pPre)
	{
		cout<<"插入失败！"<<endl;
		return false;
	}
	p = new DoubleListNode;
	p->Data = value;
	p->next = pPre;

	pPre->perv->next = p;
	p->perv = pPre->perv;
	pPre->perv = p;
	return true;
}

void printDoubleList(DoubleList* &L){
	if (!L || !L->next)
	{
		cout<<"要打印的链表不存在或者链表为空！"<<endl;
		return;
	}
	DoubleList *p;
	p = L->next;

	while (p)
	{
		cout<<p->Data<<" ";
		p = p->next;
	}
	cout<<endl;
}

//双向链表的清空
void destroyDoubleList(DoubleList* &L){
	if (!L || !L->next)
	{
		cout<<"要清空的双向链表不存在，或者为空！"<<endl;
		return;
	}

	DoubleList *p;
	p = L->next;
	while (p)
	{
		L->next = p->next;
		delete p;
		p = L->next;
	}
	cout<<"链表已清空"<<endl;
}


int main(void){
	DoubleList *L = NULL;
	DoubleListNode *p;
	int n = 0,m = 0, h=0;
	if (initDoubleList(L))
	{
		cout<<"初始化双向链表成功！"<<endl;
	}

	cout<<"头部插入节点数量："<<endl;
	cin>>n;
	while (n > 0)
	{
		cout<<"第"<<(h+1)<<"个节点："<<endl;
		cin>>m;
		p = new DoubleListNode;
		p->Data = m;
		if (!addDoubleListNode(L,p))
		{
			cout<<"插入失败！释放指针！"<<endl;
			delete p;
			p = NULL;
			break;
		}
		n--;
		h++;
	}
	printDoubleList(L);

	cout<<"尾部插入节点数量："<<endl;
	cin>>n;
	while (n > 0)
	{
		cout<<"第"<<(h+1)<<"个节点："<<endl;
		cin>>m;
		p = new DoubleListNode;
		p->Data = m;
		if (!addDoubleListNode(L,p))
		{
			cout<<"插入失败！释放指针！"<<endl;
			delete p;
			p = NULL;
			break;
		}
		n--;
		h++;
	}
	printDoubleList(L);
	cout<<"指定插入节点数量："<<endl;
	cin>>n;
	while (n > 0)
	{
		int index;
		cout<<"输入要插入的位置："<<endl;
		cin>>index;
		cout<<"在第"<<index<<"位置插入节点："<<endl;
		cin>>m;

		if (!insterDoubleListNodeByIndex(L,index,m))
		{
			cout<<"插入第"<<index<<"位置失败！"<<endl;
			n--;
			continue;
		}
		n--;
		printDoubleList(L);
	}
	destroyDoubleList(L);
	printDoubleList(L);
	delete L;
	system("pause");
	return 0;
}