数据结构与算法：单链表

用户11029103

发布于 2024-03-19 15:40:11

1260

发布于 2024-03-19 15:40:11

文章被收录于专栏：技术学习

朋友们大家好，本节来到数据结构与算法的新内容：单链表

在上篇文章中，我们知道顺序表通常需要预分配一个固定大小的内存空间，通常以二倍的大小进行增容，可能会造成空间的浪费，本篇文章我们介绍的链表可以解决这个问题

链表的定义和结构

链表是一种在计算机科学中常用的数据结构，用于存储元素的集合。它与数组相比，链表的元素不是在内存中连续存储的。链表由一系列节点组成，每个节点至少包含两个部分：一个是存储的数据，另一个是指向列表中下一个节点的指针（或引用）。通过这种方式，链表中的节点被串联起来

在顺序表中，我们的数据存储在数组中，每个数据在内存中连续存储，意味着可以通过索引直接访问任何元素

我们对顺序表进行数据的插入，物理空间不变，数据依次挪动。

链表中，我们每个节点的地址没有关联，是随机的，但是每个节点都有一个**指针，**让这个指针指向下一个节点的地址

我们设phead指针指向第一个地址，第一个节点的指针指向第二个节点的地址，最后一个节点的指针指向空

如果我们想在2 3节点中间插入新的数据a，并不需要挪动任何数据，只需要将2的指针指向a的地址，a的指针指向3的地址

若要删除3的数据，我们只需将2的指针指向4，并将3的空间释放掉即可

单链表的创建

typedef int SLNDataType;

typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

其中typedef int SLNDataType;在顺序表中我们进行了讲述，为类型抽象

typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

val 用于存储节点中的数据。数据类型由 SLNDataType 定义，当前是 int 类型，表示每个节点可以存储一个整数。
next 是一个指向下一个 SListNode 结构体的指针。它用于链接链表中的节点，使得可以从一个节点遍历到下一个节点。如果 next 为 NULL，则表示当前节点是链表的末尾。

链表的打印

我们定义了一个函数，它的作用是打印出一个单链表的所有节点值

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

我们来解析这个函数：

首先，函数内部定义了一个指针 cur 并将它初始化为指向链表的头节点 phead。这个指针用于遍历链表。
接着，函数进入一个 while 循环，条件是 cur != NULL，即只要 cur 指向的节点不是 NULL，循环就继续执行。这确保了函数能够遍历链表直到最后一个节点。
在循环体内，使用 printf 函数打印当前节点 cur 存储的整数值 cur->val，后面跟着一个箭头 ->，指示链表中的节点是如何连接的。
然后，cur 被更新为指向下一个节点 cur->next，准备打印下一个节点的值。这个步骤使得遍历可以继续进行。
一旦遍历完成（即 cur 为 NULL），循环结束。此时打印 “NULL” 来表示链表的结束

在后续我们会展示出来

创造节点

我们定义一个函数 CreatNode，用于创建一个新的链表节点 SLNode；

SLNode* CreatNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x; 
	newnode->next = NULL;
	return newnode;
}

CreatNode 函数的目的是为了构造一个新的链表节点，并将其初始化。它接收一个参数 x，类型为 SLNDataType，这是链表节点存储数据的类型。函数的返回类型是 SLNode*，即新创建的链表节点的指针。我们来解析这个函数

通过调用 malloc(sizeof(SLNode)) 分配足够的内存来存储一个 SLNode 结构体实- 例。malloc 函数尝试分配指定大小的内存空间，并返回指向这块内存的指针。如果分配成功，这个指针指向的是新分配的内存；如果失败，则返回 NULL。
**初始化节点：**为新节点的 val 成员赋值参数 x，这表示节点存储的数据。将 next 成员设置为 NULL，表示新节点当前没有指向下一个节点
返回新节点：函数返回新创建的节点的指针，允许调用者将该节点添加到链表中的适当位置。

这个 CreatNode 函数用于创建并初始化链表的新节点。通过接收一个数据作为参数，并返回指向新分配和初始化的节点的指针，它为链表构造、数据插入等提供了基础。

单链表的尾插和头插

尾插

首先进行思考，我们能否这样定义函数？

void SLTPushBack(SLNode* pphead, SLNDataType x);

如果链表不为空，我们可以如下找到尾部

SLNode* newnode = CreatNode(x);
SLNode* tail = pphead;
while (tail->next != NULL) {
	tail = tail->next;
}
tail->next = newnode;

这里并没有对头指针进行任何的修改

如果链表为空，意味着我们需要将头指针指向空改为指向newnode，

我们想对一个数值通过函数修改，需要指针，那么对一个指针进行修改，则需要二级指针

所以函数定义如下：

void SLTPushBack(SLNode** pphead, SLNDataType x) {
	SLNode* newnode = CreatNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else 
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

这里，如果链表为空，插入新节点，则头指针发生了改变

我们再test文件中进行测试，创建并初始化头指针plist

尾插三次，插入1 2 3并打印，结果如下

头插

头插我们会改变头指针，也需要二级指针

void SLTPushFront(SLNode** pphead, SLNDataType x)
{

	SLNode* newnode = CreatNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

我们用pphead接收plist

newnode的指针next指向d1，即plist（*pphead）newnode->next = *pphead;，再让plist（*pphead）指向newnode。*pphead = newnode;

在这里，链表为空也无所谓，newnode指向NULL，plist指向newnode

测试如下

单链表的尾删和头删

尾删

void SLTPopBack(SLNode** pphead) 
{
	if (*pphead == NULL) {
		return; 
	}
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLNode* prev = *pphead;
	while (prev->next->next != NULL) { 
		prev = prev->next;
	}
	free(prev->next); 
	prev->next = NULL;
}

如果头指针指向 NULL，即链表没有节点，函数将直接返回，因为没有节点可以删除。
if ((*pphead)->next == NULL) {：这一行检查链表是否只有一个节点。它通过检查头节点的 next 指针是否为 NULL 来实现。如果是这种情况，说明链表中只有一个节点。free(*pphead);：如果链表只有一个节点，这行代码释放这个节点占用的内存。 pphead = NULL;：由于最后一个节点已被删除，链表现在为空。因此，需要将头指针设置为 NULL。
如果有多个节点，这个 while 循环遍历链表，直到 prev 指向倒数第二个节点。条件 prev->next->next != NULL 确保了 prev 停在倒数第二个节点，因为倒数第二个节点的下一个节点（即最后一个节点）的 next 指针是 NULL。 free(prev->next);：释放最后一个节点占用的内存。此时，prev->next 指向最后一个节点。 prev->next = NULL;：将倒数第二个节点的 next 指针设置为 NULL，从而移除对最后一个节点的引用，更新链表的末尾

测试如下，每次尾删后进行打印

头删

void SLTPopFront(SLNode** pphead) {
	if (*pphead == NULL) {
		return; 
	}
	SLNode* temp = *pphead;
	*pphead = (*pphead)->next;
	free(temp);
}

如果链表为空，直接返回，如果不为空，temp和*pphead现在指向同一块空间，我们让头指针指向第二个节点，现在只有temp指向第一个节点，释放第一个节点的空间

测试代码

寻找某个节点

SLNode* SLTFind(SLNode* phead, SLNDataType x) 
{
	SLNode* current = phead; 
	while (current != NULL) {
		if (current->val == x) {
			return current; 
		}
		current = current->next; 
	}
	return NULL; 
}

初始化一个名为 current 的指针，用于遍历链表

在循环体内，if (current->val == x) 检查当前节点的值是否为目标值 x,若当前节点的值不是目标值，则通过 current = current->next; 将 current 更新为下一个节点的指针，继续遍历链表。

在指定位置后面插入节点

void SLTInsertAfter(SLNode* pos, SLNDataType x) {
	if (pos == NULL) {
		return;
	}
	SLNode* newnode =CreatNode(x);
	newnode->next = pos->next; 
	pos->next = newnode; 
}

首先检查pos是否为NULL，如果是，则不进行插入
若不为空，则让newnode指向pos原来指向的节点，pos指向newnode完成插入

测试如下，我们已经有了三个数据1 2 3，在2后面插入4

首先找到2节点的地址，再传入insert函数中即可

在指定位置前面插入节点

要在指定位置之前插入一个新节点，情况就稍微复杂一点，因为单向链表的节点只包含指向下一个节点的指针，没有指向前一个节点的指针。这意味着，要实现这一功能，你需要找到目标位置的前一个节点，然后在这个节点之后插入新节点。以下是实现这一功能的方法

void SLTInsertBefore(SLNode** phead, SLNode* pos, SLNDataType x) {

	if (*phead == NULL || pos == NULL || *phead == pos) {
		SLNode* newnode = CreatNode(x);
		if (*phead == pos) {
			newnode->next = *phead;
			*phead = newnode;
		}
		else {
			free(newnode); 
		}
		return;
	}

	SLNode* current = *phead;
	while (current->next != NULL && current->next != pos) {
		current = current->next;
	}
	if (current->next != pos) {
		return;
	}
	SLNode* newnode = CreatNode(x);
	newnode->next = pos;
	current->next = newnode;
}

首先检查链表是否为空，或者目标位置是否是链表的第一个节点
- 如果是第一个节点，则意味着头插
- 如果pos为NULL，表示在空链表中插入，或者pos不在链表中 将创建的newnode释放掉

if (*phead == NULL || pos == NULL || *phead == pos) {
		SLNode* newnode = CreatNode(x);
		if (*phead == pos) {
			newnode->next = *phead;
			*phead = newnode;
		}
		else {
			free(newnode); 
		}
		return;
	}

寻找pos前的节点

SLNode* current = *phead;
while (current->next != NULL && current->next != pos) {
	current = current->next;
}

如果没有找到pos，则不执行插入

if (current->next != pos) {
        return;
    }

在pos前插入新节点

SLNode* newnode = CreatNode(x);
	newnode->next = pos;
	current->next = newnode;
}

测试代码如下：在1 2 3的2前面插入4

首先找到2节点的地址再传入插入函数

在指定位置后面删除节点

void SLTEraseAfter(SLNode* pos) {
    if (pos == NULL || pos->next == NULL) {
        return;
    }
    SLNode* temp = pos->next;
    pos->next = temp->next;
    free(temp);
}

首先检查pos是否为空或pos之后没有节点，因为如果 pos 是 NULL，则没有任何节点可操作；如果 pos->next 是 NULL，则 pos 是链表中的最后一个节点，没有节点需要被删除。
将**待删除的节点（pos->next）**的地址存储在一个临时变量中。
更新 pos->next 指针，使其指向待删除节点的下一个节点。
释放待删除节点的内存，以防止内存泄漏。

测试代码如下，删除1 2 3中2后面的数据

在指定位置前面删除节点

在单向链表中删除某个指定位置pos之前的节点比删除其之后的节点稍微复杂，因为链表的单向性质意味着不能直接访问前驱节点。为了删除给定pos之前的一个节点，我们首先需要找到这个节点的前两个节点（即要删除的节点的前驱节点和要删除的节点）。然后，通过调整前驱节点的next指针，绕过要删除的节点，最后释放要删除的节点的内存。

void SLTEraseBefore(SLNode** phead, SLNode* pos) {

	if (*phead == NULL || pos == NULL || *phead == pos) return;

	if ((*phead)->next == pos) {
		SLNode* temp = *phead;
		*phead = (*phead)->next; 
		free(temp);
		return;
	}
	SLNode* prev = NULL;
	SLNode* current = *phead;
	while (current != NULL && current->next != pos) {
		prev = current;
		current = current->next;
	}
	if (current == NULL || current->next != pos) return;
	if (prev != NULL) {
		prev->next = current->next;
		free(current);
	}
}

如果链表为空，pos为空，或pos是链表的第一个节点，无法删除前一个节点

if (*phead == NULL || pos == NULL || *phead == pos) return;

if ((*phead)->next == pos) {
		SLNode* temp = *phead;
		*phead = (*phead)->next; // 移动头指针
		free(temp);
		return;
	}

这段代码的目的是处理一个特殊的情况：当我们想要删除位于给定pos节点之前的节点，且该pos恰好是链表的第二个节点时。下面分步解释这个代码块的含义和作用：

条件检查 (if ((*phead)->next == pos)): 这个条件检查链表的头节点（*phead）的下一个节点是否就是我们的目标位置pos。如果是，这意味着我们需要删除链表的第一个节点（即头节点），因为我们想要删除的是位于pos之前的节点，且pos是链表的第二个节点。
删除头节点:
- SLNode* temp = *phead;：首先，我们将头节点（要删除的节点）的地址保存在临时变量temp中，以便之后能够安全地释放该节点占用的内存。
- *phead = (*phead)->next;：接着，我们将头指针（*phead）向前移动到下一个节点，这实际上是在更新链表的头节点为原头节点的下一个节点。简单来说，我们就是把头指针指向了链表的第二个节点，从而在逻辑上“删除”了原来的第一个节点（头节点）。
释放内存 (free(temp);: 最后，使用free(temp);来释放原头节点占用的内存。

SLNode* prev = NULL;
	SLNode* current = *phead;
	while (current != NULL && current->next != pos) {
		prev = current;
		current = current->next;
	}

找到pos之前的节点

if (current == NULL || current->next != pos) return;

无法找到有效的pos位置，pos不在列表中，则返回

if (prev != NULL) {
	prev->next = current->next;
	free(current);
}

删除current的节点，即pos之前的节点；测试代码如下，删除1 2 3中2前面的节点

本节内容到此结束，感谢大家观看！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

函数

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度