数据结构(C语言)中双向链表的定义及基本操作_双向链表中有两个指针域prior和next,分别指向前驱及后继,设p指向链表中的一个结点

作者：Gausst松鼠会 | 2024-05-31 05:36:12

踩

双向链表中有两个指针域prior和next,分别指向前驱及后继,设p指向链表中的一个结点

一、双向链表的定义及基本操作
单链表中的结点只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，而双向链表的话可以直接访问结点的后继结点和前驱结点。
双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

定义双向链表

 //定义双链表 
typedef struct DoubleLNode{
	Elem data;//数据域
	struct DoubleLNode *prior;//前驱指针 
	struct DoubleLNode *next;//后继指针 
}DLN;
1
2
3
4
5
6

初始化双向链表

 //初始化链表 
void InitLNode(DLN *&L){
	L=(DLN *)malloc(sizeof(DLN));//带头节点的链表
	L->prior=NULL;
	L->next=NULL;
}
1
2
3
4
5
6

创建双向链表
创建链表：头插法和尾插法

//尾插法 	 
void CreateLNodeW(DLN *&L,Elem a[],int n){
	DLN *s,*p=L;
	for(int i=0;i<n;i++){
		s=(DLN *)malloc(sizeof(DLN));
		s->data=a[i];
		if(p->next==NULL){//头结点的后继结点为空的时侯 
			s->next = L;// s的后继结点为头结点H 
            s->prior = L;//s的前驱结点为头结点H 
            L->next = s;//头结点H的后继结点为s 
            L->prior=s;//头结点H的前驱结点为s 
		}
		else{//在最后插入 
			//最后一个结点为p->prior（头结点的前驱） 
			p->prior->next=s; // 
			s->prior=p->prior;
			s->next=p;
			p->prior=s;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//头插法
void CreateLNodeH(DLN *&L,Elem a[],int n){ 
	DLN *s;
	for(int i=0;i<n;i++){
		s=(DLN *)malloc(sizeof(DLN));
		s->data=a[i];
		if(L->next == NULL){//头结点的后继结点为空的时侯 
            s->next = L;//s的后继结点为头结点H 
            s->prior = L;//s的前驱结点为头结点H 
            L->next = s;//头结点H的后继结点为s 
            L->prior=s;//头结点H的前驱结点为s 
        }else{
            s->next =L->next;
            L->next->prior = s;
            s->prior = L;
            L->next = s;
        }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

判空（判断双向链表是否为空）

	//判空        
bool EmpyLNod(DLN *L){
	if(L->next==NULL || L->prior==NULL) return 1;
	return 0;
}
1
2
3
4
5

插入操作
插入操作分为：结点之前和结点之后插入。
结点之后插入：

//在p结点之后插入s结点 
bool InsertDNodeH(DLN *&L,Elem a,Elem b){// a是要插入的前一个结点,b 是我们想插入的值 。插入在 p之后 
	DLN *s,*p=L->next;
	s=(DLN *)malloc(sizeof(DLN));
	while(p->next!=L){//先找到a值的 结点，才好插入b值 
		if(p->data==a){
			break;//此时p指向所插入结点的前一个结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所删除的结点 
	s->data=b;	//   s结点 为插入的结点 
	s->next=p->next;	// s后继结点 为 p->next(p的后继结点)。
	p->next->prior=s;	//p的后继结点 的前驱为 s 结点 
	s->prior=p;	//s结点的前驱为p结点 
	p->next=s;	//p的后继结点为s 
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

结点之前插入：

//在p结点之前插入s结点
bool InsertDNodeQ(DLN *&L,Elem a,Elem b){// a是要插入的前一个结点,b 是我们想插入结点的值 。插入在 p之前 
	DLN *s,*p=L->next;
	s=(DLN *)malloc(sizeof(DLN));
	while(p->next!=L){	//先找到a值的 结点，才好插入b值 
		if(p->data==a){
			break;	//此时p指向所插入结点的后一个结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;	//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所插入结点的前一个结点 
	s->data=b;	//   s结点 为插入的结点 
	p->prior->next=s;	//p->prior(p结点的前驱结点) 的后继结点为 s 结点 
	s->prior=p->prior;	//s的前驱为 p->prior 
	s->next=p;	// s后继结点 为 p结点
	p->prior=s;// p的前驱为s 
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除操作
删除成功返回true，删除失败返回flase。

 //删除p结点
bool DelDNode(DLN *&L,Elem a){// a 是我们想删除的值 
	DLN *p=L->next;
	if(L->next==NULL || L->prior==NULL) return 0;
	while(p->next!=L){
		if(p->data==a){
			break;//此时p指向所删除的结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所删除的结点 
	p->prior->next=p->next;
	free(p);  
	return 1;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出链表所有元素

 //输出链表所有的元素 
void DispLNode(DLN *L){//输出链表所有的元素 
	DLN *p=L->next;
	while(p->next!=L){
		printf("%c ",p->data);
		p=p->next;
	}
	printf("%c ",p->data);
	printf("\n");	
}
1
2
3
4
5
6
7
8
9
10

全部代码（包含主函数main() ）:


```c
#include<stdio.h>
#include<malloc.h> 
typedef char Elem;
//定义双链表 
typedef struct DoubleLNode{
	Elem data;//数据域
	struct DoubleLNode *prior;//前驱指针 
	struct DoubleLNode *next;//后继指针 
}DLN;
//初始化链表 
void InitLNode(DLN *&L){
	L=(DLN *)malloc(sizeof(DLN));//带头节点的链表
	L->prior=NULL;
	L->next=NULL;
}
//创建链表 
void CreateLNodeW(DLN *&L,Elem a[],int n){//尾插法 
	DLN *s,*p=L;
	for(int i=0;i<n;i++){
		s=(DLN *)malloc(sizeof(DLN));
		s->data=a[i];
		if(p->next==NULL){//头结点的后继结点为空的时侯 
			s->next = L;// s的后继结点为头结点H 
            s->prior = L;//s的前驱结点为头结点H 
            L->next = s;//头结点H的后继结点为s 
            L->prior=s;//头结点H的前驱结点为s 
		}
		else{//在最后插入 
			//最后一个结点为p->prior（头结点的前驱） 
			p->prior->next=s; // 
			s->prior=p->prior;
			s->next=p;
			p->prior=s;
		}
	}
}
void CreateLNodeH(DLN *&L,Elem a[],int n){//头插法 
	DLN *s;
	for(int i=0;i<n;i++){
		s=(DLN *)malloc(sizeof(DLN));
		s->data=a[i];
		if(L->next == NULL){//头结点的后继结点为空的时侯 
            s->next = L;//s的后继结点为头结点H 
            s->prior = L;//s的前驱结点为头结点H 
            L->next = s;//头结点H的后继结点为s 
            L->prior=s;//头结点H的前驱结点为s 
        }else{
            s->next =L->next;
            L->next->prior = s;
            s->prior = L;
            L->next = s;
        }
	}
}
//判空        
bool EmpyLNod(DLN *L){
	if(L->next==NULL || L->prior==NULL) return 1;
	return 0;
}
//输出链表所有的元素 
void DispLNode(DLN *L){//输出链表所有的元素 
	DLN *p=L->next;
	while(p->next!=L){
		printf("%c ",p->data);
		p=p->next;
	}
	printf("%c ",p->data);
	printf("\n");	
}
//删除p结点
bool DelDNode(DLN *&L,Elem a){// a 是我们想删除的值 
	DLN *p=L->next;
	if(L->next==NULL || L->prior==NULL) return 0;
	while(p->next!=L){
		if(p->data==a){
			break;//此时p指向所删除的结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所删除的结点 
	p->prior->next=p->next;
	free(p);  
	return 1;
 } 
//在p结点之后插入s结点 
bool InsertDNodeH(DLN *&L,Elem a,Elem b){// a是要插入的前一个结点,b 是我们想插入的值 。插入在 p之后 
	DLN *s,*p=L->next;
	s=(DLN *)malloc(sizeof(DLN));
	while(p->next!=L){//先找到a值的 结点，才好插入b值 
		if(p->data==a){
			break;//此时p指向所插入结点的前一个结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所删除的结点 
	s->data=b;	//   s结点 为插入的结点 
	s->next=p->next;	// s后继结点 为 p->next(p的后继结点)。
	p->next->prior=s;	//p的后继结点 的前驱为 s 结点 
	s->prior=p;	//s结点的前驱为p结点 
	p->next=s;	//p的后继结点为s 
	return 1;
}
//在p结点之前插入s结点 
bool InsertDNodeQ(DLN *&L,Elem a,Elem b){// a是要插入的前一个结点,b 是我们想插入结点的值 。插入在 p之前 
	DLN *s,*p=L->next;
	s=(DLN *)malloc(sizeof(DLN));
	while(p->next!=L){	//先找到a值的 结点，才好插入b值 
		if(p->data==a){
			break;	//此时p指向所插入结点的后一个结点 
		}
		p=p->next;
	}
	if(p->next==L) return 0;	//表示删除元素不在链表当中，返回 0 (false) 
	//break 之后：此时p指向所插入结点的前一个结点 
	s->data=b;	//   s结点 为插入的结点 
	p->prior->next=s;	//p->prior(p结点的前驱结点) 的后继结点为 s 结点 
	s->prior=p->prior;	//s的前驱为 p->prior 
	s->next=p;	// s后继结点 为 p结点
	p->prior=s;// p的前驱为s 
	return 1;
}
int main(){
	DLN *L;
	InitLNode(L);
	Elem a[]={'a','b','c','d'};
	CreateLNodeW(L,a,4); DispLNode(L);
	DelDNode(L,'a'); DispLNode(L);
	printf("输出1 表示插入成功 输出0 表示插入失败：%d\n",InsertDNodeH(L,'b','e'));  DispLNode(L);
	printf("输出1 表示插入成功 输出0 表示插入失败：%d\n",InsertDNodeH(L,'b','f'));  DispLNode(L);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

二、总结反思：

双链表与单链表在某些操作上大同小异

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/650597