数据结构线性表之双链表

双链表和循环列表

一、什么是双链表

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域$\Rightarrow$双链表

二、单链表和双链表的区别

1.单链表是在元素的结点中只能包含一个后继结点指针，不能包含多个指针，双链表则是包含前驱结点和后继结点两个指针。
2.单链表要求建好后返回一个结点的指针，只能朝后运行，双链表建好后可以给任意一个结点的指针，前后两个方向都可以走。

三、双链表的优点

• 从任意一个结点出发可以快速找到前驱结点和后继结点；
• 从任意一个结点出发可以访问其他结点。
  

四、定义一个双链表

定义如下：

typedef struct DNode	//双链表结点类型
{
	ElemType data;
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;	//指向后继结点
}DLinkNode;
1
2
3
4
5
6

1.插入和删除结点的操作

在p结点之后插入结点s。

代码如下：

s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
1
2
3
4

2.双链表删除结点

删除p结点之后的一个节点

p->next->next-prior=p;
p->next=p->next-next;
1
2

五、建立双链表

整体建立双链表：
1.头插法
2，尾插法

a.头插法建立双链表

void CreateListF(DLinkNode *&L,ElemType a[],int n)//由·含n个元素的数组a创建带头结点的双链表L
{
	DLinkNode *s;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));//创建头结点
	L->prior=L->next=NULL;//前后指针域置为NULL
	for(int i=0;i<n;i++)
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode);
		s->data=a[i];	//创建数据结点s
		s-next=L->next;	//将s结点插入到头结点之后
		if(L->next=NULL)	//如果L非空，修改L->next的前驱指针
		L-next-prior=s;
		L->next=s;
		s->prior=L;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

b.尾插法建立双链表

void CreatListR(DLinkNode *&L,ElemType a[],int n)
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建头结点
	r=L;	//r始终指向尾结点，开始时指向头结点
	for(int i=0;i<n;i++)	//循环建立数据结点
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=a[i];	//创建数据结点s
		r->next=s;
		s->prior=r;
		r=s;	//r指向尾结点
		}
		r-next=NULL;	//尾结点next域置为NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六、补充：头插法与尾插法的区别

头插法核心：
利用头指针控制链表结点的增加。

newNode->next=head->next;
head-next=newNode;
1
2

尾插法创建链表需要借助一个辅助指针，指向当前列表的最后一个结点。

尾插法建立链表的核心：

newNode->next=rear->next;
rear->next=newNode;
rear=rear->next;
1
2
3

七、线性表基本运算在双链表中的实现

1.双链表的插入运算

bool ListInsert(DLinkNode *&L,ElemType e,int i)
{
	int j=0;
	DLinkNode *p=L,*s;	//p指向头结点，j设置为0
	while(j<i-1&&p!=NULL)	//查找第i-1个结点
{
	j++;
	p=p->next;
}	
if(p==NULL)	//未找到第1个结点
return false;
else
{
	s=(DLinkNode *)malloc(sizeof(DLinkNode));
	s->data=e;	//创建新结点s
	s-next=p->next;	//在p结点之后插入s结点
	if(p->next!=NULL)	//若存在后继结点，则修改其前驱指针
	p->next->prior=s;
	s->prior=p;
	p->next=s;
	return ture;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.双链表的删除算法

bool ListDelete(DLinkNode *&L,Elemtype &e,int i)
{
	int j=0;DLinkNode *p=L,*q;	//p指向头结点，j设置为0
	while(j<i-1&&p!=NULL)
	{
		j++;
		p=p->next;
	}
if(p==NULL)	//未找到第i-1个结点
return false;
else
{
	e=q->data;	
	p->next=q->next;
	if(q-next!!=NULL)
	q->next->prior=p;
	free(p);
	return ture;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20