devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构：详解【链表】的实现（单向链表+双向链表）

作者：凡人多烦事01 | 2024-03-26 02:06:56

赞

踩

数据结构：详解【链表】的实现（单向链表+双向链表）

目录

一，前言

1.顺序表的问题和思考

问题：

  1. 中间/头部的插入删除，时间复杂度为O(N)。
  2. 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：
如何解决以上问题呢？下面给出了链表的结构来看看。

二 ，有关链表的概念，结构和分类

1. 链表的概念和结构

链表是一种物理存储结构上非连续、非顺序的存储构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

1.1 逻辑结构（就是我们想象的，数据元素依次链接）：
在这里插入图片描述

1.2 物理结构（实实在在的在内存中真实存储的结构，数据元素不一定是连续存储的）：
在这里插入图片描述

1. 每个结点（一块空间）都是随机在内存中动态开辟（malloc)出来的,都有它们的地址（第一个字节的地址），这些地址也是随机的。
2. 每个新结点都包含两个区域——数据域和指针域。数据域存放我们要操作的数据，指针域存放着下一个结点的地址。我们就是通过这个地址和下一个结点建立联系。
3. 最后一个结点的指针域中存放的是NULL。

2. 链表的分类

实际中的链表种类非常多，以下情况组合起来就有8种链表构：
在这里插入图片描述
比如：
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构，下面也只对这两种结构进行代码实现：
在这里插入图片描述

  1. 无头单向非循环链表： 结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表： 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三，无头单向非循环链表（单链表）

1.单链表的功能

单链表的功能一般有如下几个：

  • 打印数据
  • 动态申请新结点
  • 尾部插入数据
  • 头部插入数据
  • 尾部删除数据
  • 头部删除数据
  • 查找指定数据的位置
  • 在pos位置前插入数据
  • 删除pos处的数据

2.单链表功能的实现

2.1 建立单链表

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//要操作的数据
	struct SListNode * next;//指向下一个结点的指针
}SLNode;

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

2.2 打印数据

首先定义一个指针cur指向第一个结点（头指针phead)，使用循环进行遍历，当cur != NULL时，打印数据，再让cur指向下一个结点，直至跳出循环。

在这里插入图片描述

代码实现如下：

void SListPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

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

2.3 动态申请新结点
由于链表在内存中不是一块连续的空间，所以每次进行插入（增加）数据的操作时，都要在内存中创建新结点，即动态开辟（malloc)一块空间。

//这个函数是每次在增加数据时进行调用的

SLNode* BuySListNode(SLTDataType x)
{
     //随机开辟一块空间（结点）
	SLNode* newnode =(SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;//存入要插入的数据
	newnode->next = NULL;//把最后一个结点指向空

	return newnode;
}

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

2.4 尾部插入数据
尾插分为两种情况：
1.如果链表中没有结点时，直接让新结点指向头指针；
2.链表中至少有一个结点时，需要循环找到链表的尾结点的指针，再链接上新结点。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/7893ddd6c9f941a2a741c18a5911ad15.png
代码实现如下：

void SListPushBack(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	
	//1.如果表中没有一个节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//2.有两个节点以上，找尾，
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//链接新节点
		tail->next = newnode;
	}
}

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

2.5 头部插入数据
头插，首先在内存中开辟一个结点，把链表内原来第一个结点的地址存入新结点中，使两者建立联系，再把新结点的地址存入头指针即可。
在这里插入图片描述

代码实现如下：

void SListPushFront(SLNode** pphead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

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

2.6 尾部删除数据
尾删分为三种情况：
1.如果链表中没有数据（链表为空），则不需要删除，略作提示终止程序即可；
2.如果表中只有一个结点，直接free释放，再置空即可；
3.如果表中多于一个结点，不能直接循环找到尾结点删除，这样前一个结点会形成野指针，而是要先保存倒数第二个结点的地址，再把尾结点释放置空。

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/675e1b58c8ee47aa96ec789bdf037d70.png

代码实现如下：

void SListPopBack(SLNode** pphead)
{
	//1.链表内无数据
	if (*pphead == NULL)
	{
		printf("链表为空!\n");
		return;
	}
	//2.如果只有一个结点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		//3.记住前一个位置
		while (tail->next != NULL)
		{
			prev= tail;
			tail = tail->next;
		}
		
		free(tail);
		prev->next = NULL;
	}
}

  • 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

2.7 头部删除数据
头删，相同的道理，不能直接把第一个结点free释放，这样就找不到后面的数据了，而是先要定义一个指针变量保存第二个结点的地址，再把第一个结点free释放，置空。最后让头指针指向这个变量。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/1a80381988754e858dad4ca8ec3412b4.png

代码实现如下：

void SListPopFront(SLNode** pphead)
{
		SLNode* cur = NULL;
		cur = (*pphead)->next;
		free(*pphead);
		*pphead = cur;
}

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

2.8 查找指定数据的位置
循环遍历链表，查找出指定数字的位置，用指针pos保存，这个函数一般配合下面两个函数一起使用。

代码实现如下：

SLNode* SListFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data == x)
		{
		   //找到了发回地址
			return cur;
		}
		cur = cur->next;
	}
   //没有找到，返回空
	return NULL;
}

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

2.9 在pos位置前插入数据
这个函数包含两种情况：
1.当在第一个结点前插入时（pos指向第一个结点，pos是通过查找函数找到的），相当于头插；
2.当在其余结点前插入时，需要一个变量prev保存pos的前一个结点的地址，再把prev，pos，newnode这三个结点链接起来。
在这里插入图片描述
代码实现如下：

void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);

	//当在第一个结点前插入时，相当于头插
	if ((*pphead)->next == NULL)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = NULL;
		SLNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		prev = cur;//保存到了pos前一个结点的地址
		prev->next = newnode;
		newnode->next = pos;
	}
}

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

2.10 删除pos处的数据
相同的，这个函数也包含两种情况：
1.当要删除第一个结点时（此时pos指向第一个结点），相当于头删；
2.当pos指向其他位置时，不能直接free释放掉pos，而是要先找到pos前一个结点的位置，把它与pos的后一个结点进行链接，最后free释放掉pos。

在这里插入图片描述
代码实现如下：

void SListErase(SLNode** pphead, SLNode* pos)
{
	//当要删除第一个结点时，相当于头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

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

3.完整代码

SList.h

#define _CRT_SECURE_NO_WARNINGS 

#include <stdio.h>
#include <stdlib.h>

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);

//打印数据
void SListPrint(SLTNode* phead);

//尾删
void SListPopBack(SLTNode** pphead);

//头删
void SListPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* pphead, SLTDataType x);

//在pos位置前插入数据
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos位置处删除数据
void SListEarse(SLTNode** pphead, SLTNode* pos);


  • 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

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include "SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur =phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
	//开辟新节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//判断刚开始是否有节点,若没有，则直接开辟
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//若已经存在节点 则找到尾结点，链接新节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		printf("链表无数据！\n");
	}
	//注意不能直接free，要先记住第二个节点的地址，再释放第一个节点
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

void SListPopBack(SLTNode** pphead)
{
	//1.当链表为空时
	if (*pphead == NULL)
	{
		printf("链表无数据!\n");
		return;
	}
	//2.只有一个节点时,直接释放掉，再置空
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		//让prev记住倒数第二个节点，此时tail指向最后一个节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		//释放最后一个空间
		free(tail);
		//这时prev是最后一个节点，要置空，避免野指针
		prev->next = NULL;
	}
	
}

SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
	SLTNode* cur = pphead;
	//遍历链表，找数
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	return NULL;
}

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//要在第一个节点前插入数据时，相当于头插
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = newnode;
		newnode->next = pos;
	}
}

void SListEarse(SLTNode** pphead, SLTNode* pos)
{
	//1.当pos为第一个节点时，没有前一个节点，删除时相当于头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	 }
	else
	{
		//2.Pos不是第一个节点，找到pos的前一个位置，再释放空间
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}

}

  • 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

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SList.h"

 //在这里对那些函数接口进行测试，例如：
void SListTest()
{
   //定义一个头指针，置空
	SLTNode* plist = NULL;
	
	//这里传地址的原因是我们要对链表中的数据进行修改，
	//由于形参是实参的一份临时拷贝，改变形参不影响实参
	//所以只有传地址，对内存进行修改
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	//在3前面插入有一个30，先找到3的前一个的位置，再插入
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist,pos，30);
	}
	SListPrint(plist);

}

int main()
{
	SListTest();

	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

四，带头双向循环链表（双链表）

虽然单链表是我们要掌握基础链表之一，但是它并不完美，比如它不能从后往前操作，不容易找到前驱，每次尾插，尾删都要进行遍历，使得时间复杂度为O（N）等，使用起来其实并不是那么方便。

下面介绍的双链表虽然结构更复杂，但是它完美解决了单链表的缺陷，使用起来十分方便，丝滑。

1.单链表与双链表的结构区别

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/723a6c3b744648d2b956ee6594b89ae7.png

  • 双链表的"带头"是指需要在链表的最前端动态申请一个特殊的结点，这第一个结点不存储有效数据，这种结点也称为带哨兵位的头结点。 它的好处是在进行增删查改等操作时，不需要改变传过来的指针了，也就意味着不需要传二级指针了。
    而且，与单链表相比，它不仅有存放下一个结点地址的next指针（也可叫后驱指针），还会增加一个前驱指针prev，用来存放上一个节点的地址。这样就使得每个节点都能快速找到自己的前一个结点，也能找到自己的下一个结点。 最终会形成"循环"。
    双链表的这两点结构对我们增删查改的实现有极大的方便，使它能够完美解决单链表的缺陷。
  • 单链表的结构就更简单了，它没有带头，也没有循环，只能从头到尾前一个结点指向后一个结点。

2.双链表的功能

双链表的功能一般有如下几个：

  • 初始化链表
  • 打印数据
  • 动态申请新结点
  • 尾部插入数据
  • 头部插入数据
  • 尾部删除数据
  • 头部删除数据
  • 查找指定数据的位置
  • 在pos位置前插入数据
  • 删除pos处的数据
  • 销毁链表

3.双链表功能的实现

3.1 建立双链表

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;//要操作的数据
	struct ListNode* next;//后驱指针
	struct ListNode* prev;//前驱指针

}ListNode;

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

3.2 初始化链表
首先要申请一个带哨兵位的头结点，并且让它的前驱和后驱都指向自己。
在这里插入图片描述
代码实现如下：

//注意：这个函数并没有进行传参，而是通过返回值的方式
//把申请空间的地址返回。这就避免了使用二级指针。
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

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

3.3 动态申请新结点
在初始化链表和插入数据时，都需要在内存中动态申请新结点。

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

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

3.4 打印数据
首先定义一个指针cur指向第二个结点（头节点不存放数据），由于是循环链表，所以通过循环，当cur != phead时，打印出数据即可。

在这里插入图片描述
代码实现如下：

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("链表为空!\n");
		return;
	}

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

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

3.5 尾部插入数据
尾插，申请新结点newnode，定义变量tail指向最后一个结点（其实就是phead的前驱，这就避免了要向单链表那样通过遍历找到尾节点，体现出了双链表的优越性。），再链接起phead，newnode，tail

在这里插入图片描述
代码实现如下：

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);//断言
	ListNode* newnode = BuyListNode(x);

	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	
	phead->prev = newnode;
	newnode->next = phead；
	
}

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

3.6 头部插入数据
头插，就是在头结点phead和和第二个结点之间插入，申请新结点newnode，再定义变量first指向第二个结点，再链接起三者即可。
在这里插入图片描述
代码实现如下：

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

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

3.7 尾部删除数据
尾删，与单链表类似，不能直接把最后一个结点free释放。定义一个变量tail指向尾结点（其实就是phead->prev)，再定义一个变量prev保存倒数第二个结点的地址（其实就是tail->prev)，再进行三者链接，最后释放，置空。

在这里插入图片描述
代码实现如下：

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	phead->prev = prev;
	prev->next = phead;

	free(tail);
	tail = NULL;

}

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

3.8 头部删除数据
头删，是删除第二个结点，不能直接释放第二个结点。定义变量first指向第二个结点（就是phead->next)，再定义变量second指向第三个结点（就是first->next)，再进行三者链接，最后释放，置空。

在这里插入图片描述
代码实现如下：

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}

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

3.9 查找指定数据的位置
定义变量cur指向第二个结点，直接循环遍历，直至cur指向phead。若找到了，则直接返回该结点的地址，用pos接收，否则返回NULL。这个函数一般与下面两个函数配合使用。

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

3.10 在pos位置前插入数据
pos是查找函数找到的位置，申请新结点newnode，定义变量prev指向pos的前一个结点，再链接三者即可。

在这里插入图片描述
代码实现如下：

void ListInsert(ListNode* pos, SLTDataType x)
{
	assert(pos);//断言，pos不能为空

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

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

3.11 删除pos处的数据
与前面类似，不能直接free释放pos处的空间。定义变量prev指向（保存）pos前一个结点的（地址），定义变量next指向（保存）pos后一个结点（地址），再把两者进行链接，最后释放，置空。
在这里插入图片描述
代码实现如下：

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);//释放
	pos = NULL;
}

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

3.12 销毁链表
销毁链表是从第二个结点开始，循环依次释放。定义变量cur指向第二个结点，与前面类似，不能直接释放cur处的空间，而是要先保存到下一个结点的空间，再把当前节点空间释放。最后再释放头结点（phead)，置空。

在这里插入图片描述

代码实现如下：

void ListDestory(ListNode* phead)
{
	assert(phead);
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;//保存下一个结点的地址
		free(cur);//先释放有数据的结点
		cur = next;
	}

	free(phead);//释放哨兵位头结点
	phead = NULL;
}

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

4. 完整代码

List.h

#define _CRT_SECURE_NO_WARNINGS 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

typedef struct ListNode
{
	SLTDataType data;
	struct ListNode* next;
	struct ListNode* prev;

}ListNode;


//初始化链表
ListNode* ListInit();

//销毁链表
void ListDestory(ListNode* phead);

//打印数据
void ListPrint(ListNode* phead);

//尾插
void ListPushBcck(ListNode* phead, SLTDataType x);

//头插
void ListPushFront(ListNode* phead, SLTDataType x);

//尾删
void ListPopBcck(ListNode* phead);

//头删
void ListPopFront(ListNode* phead);

//查找
ListNode*  ListFind(ListNode* phead, SLTDataType x);

//在pos前插入数据
void ListInsert( ListNode* pos, SLTDataType x);

//删除pos处的数据
void ListEarse( ListNode* pos);


  • 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

List.c

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

ListNode* BuyListNode(SLTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;

	if (cur == phead)
	{
		printf("链表为空!\n");
		return;
	}

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	phead = NULL;
}

void ListPushBcck(ListNode* phead, SLTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);

	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	
	phead->prev = newnode;
	newnode->next = phead;

}

void ListPushFront(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);
	
	phead->next = newnode;
	newnode->prev = phead;
	
	newnode->next = first;
	first->prev = newnode;

}

void ListPopFront(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;
	
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;

}

void ListPopBcck(ListNode* phead)
{
	assert(phead);
	
	//此时链表一个结点都没有
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	phead->prev = prev;
	prev->next = phead;

	free(tail);
	tail = NULL;

}

ListNode* ListFind(ListNode* phead, SLTDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void ListInsert(ListNode* pos, SLTDataType x)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	
	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

void ListEarse(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
	pos = NULL;
}


  • 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

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "List.h"

//在这个函数中进行各函数接口的测试：
ListNode* ListTest()
{
	ListNode* plist = ListInit();

	ListPushBcck(plist, 1);
	ListPushBcck(plist, 2);
	ListPushBcck(plist, 3);
	ListPushBcck(plist, 4);
	ListPrint(plist);


	ListDestory(plist);

	return 0;
}

int main()
{
	ListTest();

	return;
}

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/313954
推荐阅读
相关标签

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

  

闽ICP备14008679号