devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之双链表（c语言附完整代码)_c语言双向链表的代码

作者：IT小白 | 2024-07-05 07:31:11

赞

踩

c语言双向链表的代码

文章目录

一、定义

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
示意图：
在这里插入图片描述

声明双链表

typedef struct DNode		//定义双链表结点类型
{
	ElemType data;           //数据域
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;		//指向后继结点
} DLinkNode;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

注意：本文章讨论的双链表是带头结点的双链表。
增加头结点的优点如下：
1.双链表中首结点的插入和删除操作与其他结点一致，无需进行特殊处理。
2.无论双链表是否为空都有一个头结点，因此统一了空表和非空表的处理过程。

二、基本运算

在双链表中除了(建立双链表，插入元素，删除元素)，其余运算和单链表完全相同。

头插法建立双链表

void CreateListF(DLinkNode *&L,ElemType a[],int n)
//头插法建双链表
{
	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->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		if (L->next!=NULL)
	        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
  • 17

该运算依次从数组a中读取数据，生成一个新的结点，将该数据储放到新结点的数据域，然后将其插入到当前链表的表头（即头结点之后），直到所有的数据读完为止。
例如：数组 a={ 1,2,3,4 }，使用头插法得到的链表顺序为 4，3，2，1。
插入操作如下：

s->next=L->next;
if(L->next!=NULL)
    L->next->prior=s;
L->next=s;
s->prior=L;

  • 1
  • 2
  • 3
  • 4
  • 5

首先修改s结点的后继指针next，使其指向头节点L的后继指针next所指结点，接着判断头结点L的后继指针next是否为NULL(此处等价于判断s结点的后继指针next是否为NULL),如果不为NULL,则修改s结点后继指针next所指结点的前驱指针prior，使其指向s，然后修改头结点的后继指针next，使其指向s结点，最后修改s结点的前驱指针prior，使其指向L。

本算法的时间复杂度为O（n）

尾插法建立双链表

void CreateListR(DLinkNode *&L,ElemType a[],int n)
//尾插法建双链表
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

该运算依次从数组a中读取数据，生成一个新的结点，将该数据储放到新结点的数据域，然后将其插入到当前链表的表尾，直到所有的数据读完为止。其过程是设置一个指针r，让它始终指向当前链表的尾结点，每次插入一个新结点后，让r指向这个新结点，所有元素插入完后，将r所指结点(尾结点)的next域设置为NULL。

例如：数组 a={ 1,2,3,4 }，使用尾插法得到的链表顺序为 1，2，3，4。
插入操作如下：

r->next=s;
s->prior=r;
r=s;

  • 1
  • 2
  • 3

首先修改r结点的后继指针next，使其指向s结点，然后再修改s结点的前驱指针prior，使其指向r结点，最后让r指向s结点。

本算法的时间复杂度为O（n）

初始化双链表

void InitList(DLinkNode *&L)
{
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
}

  • 1
  • 2
  • 3
  • 4
  • 5

该运算建立一个空的双链表，其过程是创建一个头结点，并将其next域和prior域置为NULL。

本算法的时间复杂度为O（1）

销毁双链表

void DestroyList(DLinkNode *&L)
{
	DLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

该运算释放双链表L占用的内存空间，即逐一释放全部结点存储空间。设置p,pre两个指针指向两个相邻的结点，初始时pre指向头节点，p指向首结点(链表第一个元素)，当p不为NULL执行循环:先释放pre，然后pre，p同步后移一个结点。循环结束时，pre指向尾结点，再将其释放。

本算法的时间复杂度为O（n）

判断双链表是否为空表

bool ListEmpty(DLinkNode *L)
{
	return(L->next==NULL);
}

  • 1
  • 2
  • 3
  • 4

该运算判断双链表是否为空表，当头结点的next域为NULL时，表示链表为空，返回1，否则返回0。
本算法的时间复杂度为O（1）

求双链表的长度

int ListLength(DLinkNode *L)
{
	DLinkNode *p=L;
	int i=0;
	while (p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	return(i);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

该运算返回链表L中数据元素的个数，设置指针p(初始指向头节点)，i(初始值为0）用来记录链表中结点的个数，遍历链表，当p不为NULL时执行循环:i加1，p指向下一个结点。循环结束后返回i。
本算法的时间复杂度为O（n）

输出双链表

void DispList(DLinkNode *L)
{
	DLinkNode *p=L->next;
	while (p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

该运算逐一输出各结点的data域值，设置指针p(初始指向首结点)，p不为NULL执行循环:输出当前结点的数据域，p指向下一个结点。
本算法的时间复杂度为O（n）

求双链表中某个位置数据元素的值

bool GetElem(DLinkNode *L,int i,ElemType &e)
{
	int j=0;
	DLinkNode *p=L;
	if (i<=0) return false;		//i错误返回假
	while (j<i && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)
		return false;
	else
	{
		e=p->data;
		return true;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

该运算在双链表L中从开始找到第i个结点，如果存在第i个结点则将其data域值赋给e。设置指针p(初始指向头结点)，j(初始值为0)用来记录遍历过的结点个数，当j<i且p不为空时循环:j+1，p指向下一个结点。循环结束时有两种情况:如果p为NULL，表示单链表L中没有第i个结点(参数错误)，返回false;如果p不为NULL，表示找到第i个结点，将其data域值赋给e并返回true。
本算法的时间复杂度为O（n）

按元素的值查找

int LocateElem(DLinkNode *L,ElemType e)
{
	int n=1;
	DLinkNode *p=L->next;
	while (p!=NULL && p->data!=e)
	{
		n++;
		p=p->next;
	}
	if (p==NULL)
		return(0);
	else
		return(n);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

该运算在双链表中从头开始找到第一个data域值与e相等的结点，如果存在这样的结点，则返回逻辑序号，否则返回0。设置指针p(初始指向首结点)，i(初始值为1)，当p不为NULL且p结点的data域值不等于e时执行循环:p指向下一个结点，i加1。循环结束时有两种情况:如果p=NULL,表示不存在值为e的结点，返回0;否则表示存在值为e的结点，返回其逻辑序号i。
本算法的时间复杂度为O（n）

插入数据元素

bool ListInsert(DLinkNode *&L,int i,ElemType e)
{
	int j=0;
	DLinkNode *p=L,*s;
	if (i<=0) 
	    return false;		//i错误返回假
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
		s->data=e;	
		s->next=p->next;		//将结点s插入到结点p之后
		if (p->next!=NULL) 
			p->next->prior=s;
		s->prior=p;
		p->next=s;
		return true;
	}
}

  • 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

该运算在双链表第i个结点前插入值为e的结点。
实现过程是先在双链表L中找到第i-1个结点，用p指向它。如果存在这样的结点，将值为e的结点(指针s所指结点)插入到p结点的后面。设置指针p(初始指向头结点)，i(初始值为0)，当j<i-1且p为NULL时执行循环:j加1，p指向下一个结点。循环结束时有两种情况:如果p为NULL，表示未找到第i-1个元素(参数错误)，返回false;否则表示找到第i-1个结点，创建新结点s并将其data域值置为e，将结点s插入到结点p之后，最后返回true。
插入操作如下：

s->next=p->next;
if(p->next!=NULL)
    p->next->prior=s;
s->prior=p;
p->next=s;

  • 1
  • 2
  • 3
  • 4
  • 5

此处插入操作与头插法建立双链表的插入操作相同(头插法建立双链表时的插入操作相当于把s结点插入到头结点L之后),此处是把s结点插入到p结点之后。
本算法的时间复杂度为O（n）
动画演示：
在这里插入图片描述

删除数据元素

bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{
	int j=0;
	DLinkNode *p=L,*q;
	if (i<=0) return false;		//i错误返回假
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		q=p->next;				//q指向要删除的结点
		if (q==NULL) 
			return false;		//不存在第i个结点
		e=q->data;
		p->next=q->next;		//从单链表中删除*q结点
		if (p->next!=NULL)
		    p->next->prior=p;
		free(q);				//释放q结点
		return true;
	}
}


  • 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

该运算删除双链表L中第i个结点，并将其data域值赋给e。实现过程是先在双链表中找到第i-1个结点，用p指向它。如果存在这样的结点，且存在后继结点(q所指结点)，则删除q所指结点。设置指针p(初始指向头结点)，j(初始值为0)，当j<i-1执行循环:j加1，p指向下一个结点。当循环结束时有两种情况:如果p为NULL,表示未找到第i-1个结点(参数错误)，返回false;否则表示找到第i-1个结点，用q指向第i个结点，如果q为NULL,则表示不存在第i个结点(参数错误)返回false，如果q不为NULL,则表示存在第i个结点，删除q结点，返回true。
删除操作如下：

p->next=q->next;
if(q->next!=NULL)
     q->next->prior=p;

  • 1
  • 2
  • 3

首先修改p结点的后继指针next，使其指向q结点的后继指针next所指的结点，然后判断q结点的后继指针next是否为NULL(此处等价于判断s结点的后继指针next是否为NULL),如果不为NULL,则修改q结点的后继指针next所指结点的前驱指针prior，使其指向p结点。
本算法的时间复杂度为O（n）
动画演示：
在这里插入图片描述

三、完整代码

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode		//定义双链表结点类型
{
	ElemType data;
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;		//指向后继结点
} DLinkNode;
void CreateListF(DLinkNode *&L,ElemType a[],int n)
//头插法建双链表
{
	DLinkNode *s;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		if (L->next!=NULL) 
		   L->next->prior=s;
		L->next=s;
		s->prior=L;
	}
}
void CreateListR(DLinkNode *&L,ElemType a[],int n)
//尾插法建双链表
{
	DLinkNode *s,*r;
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;i<n;i++)
	{	
		s=(DLinkNode *)malloc(sizeof(DLinkNode));//创建新结点
		s->data=a[i];
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}
void InitList(DLinkNode *&L)
{
	L=(DLinkNode *)malloc(sizeof(DLinkNode));  	//创建头结点
	L->prior=L->next=NULL;
}
void DestroyList(DLinkNode *&L)
{
	DLinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}
bool ListEmpty(DLinkNode *L)
{
	return(L->next==NULL);
}
int ListLength(DLinkNode *L)
{
	DLinkNode *p=L;
	int i=0;
	while (p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	return(i);
}
void DispList(DLinkNode *L)
{
	DLinkNode *p=L->next;
	while (p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
bool GetElem(DLinkNode *L,int i,ElemType &e)
{
	int j=0;
	DLinkNode *p=L;
	if (i<=0) 
	   return false;		//i错误返回假
	while (j<i && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)
		return false;
	else
	{
		e=p->data;
		return true;
	}
}
int LocateElem(DLinkNode *L,ElemType e)
{
	int n=1;
	DLinkNode *p=L->next;
	while (p!=NULL && p->data!=e)
	{
		n++;
		p=p->next;
	}
	if (p==NULL)
		return(0);
	else
		return(n);
}
bool ListInsert(DLinkNode *&L,int i,ElemType e)
{
	int j=0;
	DLinkNode *p=L,*s;
	if (i<=0) 
	   return false;		//i错误返回假
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));	//创建新结点s
		s->data=e;	
		s->next=p->next;		//将结点s插入到结点p之后
		if (p->next!=NULL) 
			p->next->prior=s;
		s->prior=p;
		p->next=s;
		return true;
	}
}
bool ListDelete(DLinkNode *&L,int i,ElemType &e)
{
	int j=0;
	DLinkNode *p=L,*q;
	if (i<=0) 
	   return false;		//i错误返回假
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		q=p->next;				//q指向要删除的结点
		if (q==NULL) 
			return false;		//不存在第i个结点
		e=q->data;
		p->next=q->next;		//从单链表中删除*q结点
		if (p->next!=NULL) p->next->prior=p;
		free(q);				//释放q结点
		return true;
	}
}
int main()
{
	DLinkNode *L;
	ElemType e;
	ElemType a[]={1,2,3,4};
	CreateListF(L,a,4);        //尾插法建立链表 
	printf("尾插法所得顺序为: ");
	DispList(L);
	DestroyList(L);
	CreateListR(L,a,4);        //头插法建立链表 
	printf("头插法所得顺序为：");
	DispList(L);
	printf("链表的长度为:%d\n",ListLength(L));
	ListInsert(L,4,5);          //在链表第四个元素前插入5 
	printf("插入一个元素后链表的元素为:");
	DispList(L);
	ListDelete(L,1,e);          //删除链表中第一个元素，并将它的值赋给e 
	printf("删除的元素为:%d\n",e);
	printf("删除一个元素后链表的元素为:");
	DispList(L);
	printf("当前链表是否为空:%d\n",ListEmpty(L));
	GetElem(L,1,e);
	printf("链表第一个元素为:%d\n",e);
	printf("值为2的元素在链表中的位置为:%d\n",LocateElem(L,2));
	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
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193

参考资料：
李春葆《数据结构教程》（第五版）

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号