[数据结构与算法]数据结构与算法学习笔记(二)-----链表（下）

前言

单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。例如删除结点 p 时，要先找到它的前一个结点 q，然后才能删掉 p 结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？这时，双向链表就应运而生。

一、什么是双向链表？

在单链表的基础上给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表。

二、双向链表基本操作

1.双向链表的初始化

双向链表初始化与单向链表类似，不同点在于双向链表的指针域多了指向前一个结点的 prev 指针。在初始化时，我们需要对这两个指针进行初始化。

代码如下：

typedef struct _DoubleLinkNode
{
	int data;	//数据域
	struct _DoubleLinkNode *next;	//指向下一结点的指针
	struct _DoubleLinkNode *prev;	//指向上一结点的指针
}DbLinkNode,DbLinkList;

bool DbInit_list(DbLinkList* &L)
{
	L=new DbLinkNode;
	if(!L)
		return false;
	else
	{
		L->next=NULL;
		L->prev=NULL;
		L->data=-1;
		return true;
	}
}

2.双向链表前插

前插时，我们要考虑两种情况：
1.该双向链表只有一个头结点；
只有头结点时我们只需要将头结点的 next 指针域赋给 node 结点(插入结点)的指针域，然后再将 node 结点的 prev 的指针域指向头结点，头结点的 next 指针域指向node即可。

2.该双向链表除了头结点外还有其他结点。
这个比较麻烦了。我们先将头结点的下一个结点与 node 结点相连接，再将 node 结点的 next 指针域修改为插入前 L 结点的 next 指针域，接下来是将 node 的 prev 指针指向头结点，最后将头结点与 node 结点连接即可。

代码如下：

bool DbListInsert_front(DbLinkList* &L,DbLinkNode* node)
{
	if(!L||!node)
		return false;
	if(L->next==NULL)	//刚开始只有头结点时前插
	{
		node->next=L->next;	//等同于node->next=NULL;
		node->prev=L;
		L->next=node;
	}
	else	//除了头结点还有其他结点时前插
	{
		L->next->prev=node;	//头结点的下一个结点与插入的结点相连接
		node->next=L->next;	//插入结点 next 指针域指向插入前 L 的 next 结点的指针域
		node->prev=L;	//插入结点的 prev 指针指向头结点
		L->next=node;	//插入结点与头结点相连接
	}
}

3.双向链表尾插

双向链表尾插前，与单向链表和循环链表相同——先找到表尾元素。之后将 node 结点的 next 指针域置空。再将 node 结点插入表尾，最后使 node 结点的 prev 指针域指向插入前表尾结点即可。

代码如下:

bool DbListInsert_back(DbLinkList* &L,DbLinkNode* node)
{
	DbLinkNode *last=NULL;
	if(!L||!node)
		return false;
	last=L;
	while(last->next!=NULL)	//找到表尾元素
	{
		last=last->next;
	}
	node->next=NULL;
	last->next=node;
	node->prev=last;
	return true;
}

4.任意位置插入

注意链表连接时指针域的指向即可，其他与单链表类似。

代码如下：

bool DbList_insert(DbLinkList* &L,int i,int &e)
{
	if(!L||!L->next)
		return false;
	if(i<1)
		return false;
	int j=0;
	DbLinkList *p,*s;
	p=L;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	if(!p||j!=i)
	{
		cout<<"不存在结点"<<i<<endl;
		return false;
	}
	else
	{
		s=new DbLinkNode;	//生成新结点
		s->data = e;	//插入结点 data 域修改为插入值 e 
		s->next = p;	//插入结点与 p 结点相连
		s->prev = p->prev;	//插入结点 prev 指针修改为 p 结点的 prev 指针
		p->prev->next = s;	//p 结点的上一个结点与插入结点相连
		p->prev = s;	//p 结点的 prev 指针指向插入结点
		return true;
	}
}

5.双向链表的遍历

这个与单链表和循环链表操作相比，多了一项逆向打印。因为是双向的，所以支持逆向打印。

代码如下:

void DbLink_print(DbLinkList* &L )
	{
	DbLinkNode *p = NULL;
	if(!L)
	{
		cout<<"链表为空."<<endl;
		return ;
	}
	p = L;
	cout<<"正向打印"<<endl;
	while(p->next!=NULL)
	{
		cout<<p->next->data<<" ";
		p=p->next;
	}
	cout<<endl<<"逆向打印"<<endl;
	while(p&&p!=L)
	{
		cout<<p->data<<" ";
		p=p->prev;
	}
}

6.双向链表获取元素

双向链表获取元素与单向链表完全相同。

代码如下:

bool DbLink_GetElem(DbLinkList* &L,int i,int &e)
{
	int index;
	DbLinkList *p;
	if(!L||!L->next)
		return false;
	p=L->next;
	index=1;
	while(p&&index<i)
	{
		p = p->next; //p 指向下一个结点
		index++; //计数器 index 相应加 1
	}
	if(!p || index>i)
		return false; //i 值不合法,i＞n 或 i<=0
	e=p->data;
	return true;
}

7.双向链表删除元素

双向链表删除元素时，我们只需要注意删除元素的位置：
1.删除元素的位置在表尾。
这种情况，我们只需要将删除结点的上一个节点的 next 指针域指向删除结点的 next 指针域（删除结点的 next 指针域为 NULL）；
2.删除元素的位置不在表尾。
这种情况我们要基于第一种情况再加一步处理:将删除结点的下一节点的 prev 指针域修改为删除结点的 prev 指针域。

代码如下:

bool DbLink_Delete(DbLinkList* &L, int i) //双向链表的删除
{
	DbLinkList *p;
	int index = 0;
	if(!L || !L->next)
	{
		cout<<"双向链表为空!"<<endl;
		return false;
	}
	if(i<1)
		return false; //不能删除头节点
	p=L;
	while(p && index<i)
	{
		p = p->next;
		index++;
	}
	if(!p)	//当节点不存在时，返回失败
		return false;
	p->prev->next=p->next; //改变删除结点前驱结点的 next 指针域(p为尾结点时，只执行这一步操作)
	if(p->next)	//(p不为尾结点时，额外的操作)
	{
		p->next->prev = p->prev; //改变删除节点后继节点的 prev 指针域
	}
	delete p; //释放被删除结点的空间
	return true;
}

8.双向链表销毁

删除数据，释放内存。

代码如下:

void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁
{
	//定义临时节点 p 指向头节点
	DbLinkList *p = L;
	cout<<"销毁链表!"<<endl;
	while(p)
	{
		L=L->next;//L 指向下一个节点
		cout<<"删除元素: "<<p->data<<endl;
		delete p; //删除当前节点
		p = L; //p 移向下一个节点
	}
}

三、完整源码

#include <iostream>

using namespace std;

typedef struct _DoubleLinkNode
{
	int data;	
	struct _DoubleLinkNode *next;
	struct _DoubleLinkNode *prev;
}DbLinkNode,DbLinkList;

bool DbInit_list(DbLinkList* &L)
{
	L=new DbLinkNode;
	if(!L)
		return false;
	else
	{
		L->next=NULL;
		L->prev=NULL;
		L->data=-1;
		return true;
	}
}

bool DbListInsert_front(DbLinkList* &L,DbLinkNode* node)
{
	if(!L||!node)
		return false;
	if(L->next==NULL)	//只有头结点 
	{
		node->next=L->next;
		node->prev=L;
		L->next=node;
	}
	else
	{
		L->next->prev=node;
		node->next=L->next;
		node->prev=L;
		L->next=node;
	}
}

bool DbListInsert_back(DbLinkList* &L,DbLinkNode* node)
{
	DbLinkNode *last=NULL;
	if(!L||!node)
		return false;
	last=L;
	while(last->next!=NULL)
	{
		last=last->next;
	}
	node->next=NULL;
	last->next=node;
	node->prev=last;
	return true;
}

bool DbList_insert(DbLinkList* &L,int i,int &e)
{
	if(!L||!L->next)
		return false;
	if(i<1)
		return false;
	int j=0;
	DbLinkList *p,*s;
	p=L;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	if(!p||j!=i)
	{
		cout<<"不存在结点"<<i<<endl;
		return false;
	}
	else
	{
		s=new DbLinkNode;	//生成新结点
		s->data = e;
		s->next = p;
		s->prev = p->prev;
		p->prev->next = s;
		p->prev = s;
		return true;
	}
}

bool DbLink_GetElem(DbLinkList* &L,int i,int &e)
{
	int index;
	DbLinkList *p;
	if(!L||!L->next)
		return false;
	p=L->next;
	index=1;
	while(p&&index<i)
	{
		p = p->next; //p 指向下一个结点
		index++; //计数器 index 相应加 1
	}
	if(!p || index>i)
		return false; //i 值不合法,i＞n 或 i<=0
	e=p->data;
	return true;
}

bool DbLink_Delete(DbLinkList* &L, int i) //双向链表的删除
{
	DbLinkList *p;
	int index = 0;
	if(!L || !L->next)
	{
		cout<<"双向链表为空!"<<endl;
		return false;
	}
	if(i<1)
		return false; //不能删除头节点
	p=L;
	while(p && index<i)
	{
		p = p->next;
		index++;
	}
	if(!p)	//当节点不存在时，返回失败
		return false;
	p->prev->next=p->next; //改变删除结点前驱结点的 next 指针域
	if(p->next)
	{
		p->next->prev = p->prev; //改变删除节点后继节点的 prev 指针域
	}
	delete p; //释放被删除结点的空间
	return true;
}

void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁
{
	//定义临时节点 p 指向头节点
	DbLinkList *p = L;
	cout<<"销毁链表!"<<endl;
	while(p)
	{
		L=L->next;//L 指向下一个节点
		cout<<"删除元素: "<<p->data<<endl;
		delete p; //删除当前节点
		p = L; //p 移向下一个节点
	}
}

void DbLink_print(DbLinkList* &L )
	{
	DbLinkNode *p = NULL;
	if(!L)
	{
		cout<<"链表为空."<<endl;
		return ;
	}
	p = L;
	cout<<"正向打印"<<endl;
	while(p->next!=NULL)
	{
		cout<<p->next->data<<" ";
		p=p->next;
	}
	cout<<endl<<"逆向打印"<<endl;
	while(p&&p!=L)
	{
		cout<<p->data<<" ";
		p=p->prev;
	}
}

int main()
{
	DbLinkList* L=NULL;
	DbLinkNode* s=NULL;
	if(DbInit_list(L))
	{
		cout<<"初始化成功!"<<endl;
		int n;
		cout<<"请输入插入元素个数(前插法):";
		cin>>n;
		while(n>0)
		{
			s=new DbLinkNode;
			cout<<"请输入元素值:"; 
			cin>>s->data;
			DbListInsert_front(L,s);
			n--;
		}
		DbLink_print(L);
		
		cout<<endl<<"请输入插入元素个数(尾插法):";
		cin>>n;
		while(n>0)
		{
			s=new DbLinkNode;
			cout<<"请输入元素值:";
			cin>>s->data;
			DbListInsert_back(L,s);
			n--;
		}
		DbLink_print(L);
		
		cout<<endl<<"请输入插入元素个数(任意位置插入):";
		cin>>n;
		while(n>0)
		{
			int i,x;
			cout<<"请输入插入的位置和元素(用空格隔开):";
			cin>>i>>x;
			DbList_insert(L,i,x);
			DbLink_print(L);
			n--;
			cout<<endl;
		}
		
		int element = 0;
		if(DbLink_GetElem(L, 2, element))
		{
			cout<<"获取第二个元素成功, 值："<<element<<endl;
		}
		else 
		{
			cout<<"获取第二个元素失败!"<<endl;
		}
		
		if(DbLink_Delete(L, 2))
		{
			cout<<"删除第 2 个元素成功!"<<endl;
			DbLink_print(L);
		}
		else
		{
			cout<<"删除第 2 个元素失败!"<<endl;
		}
		if(DbLink_Delete(L, 1))
		{
			cout<<endl<<"删除第 1 个元素成功!"<<endl;
			DbLink_print(L);
		}
		else
		{
			cout<<"删除第 1 个元素失败!"<<endl;
		}
		
		cout<<endl;
		DbLink_Destroy(L);
	}
	else
	{
		cout<<"初始化失败!"<<endl;
	}
	return 0;
} 

运行结果：

总结

到这里，链表模块就基本上结束了。总结经验是搞会指针会使链表学习更加轻松，对以后队列，树等的学习也有帮助！