当前位置：首页 > article >正文

数据结构-单链表-详解-2

article 2024/11/15 20:29:12

数据结构-单链表-详解-2

1.前言
2.创建新结点
3.头插与尾插
- 3.1头插
- 3.2尾插
- - 空链表
  - 找尾
4.头删与尾删
- 4.1头删
- 4.2尾删

1.前言

在数据结构-单链表-详解-1中，我们不仅了解了单链表的基本概念，还掌握了如何创建和打印单链表。
今天，我将详细讲解如何对单链表进行头尾部的插入、删除。

2.创建新结点

在后续插入的过程中，都需要创建新的结点，因此直接将该过程封装为一个函数，便于操作。
SList.c：

SListNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("BuySListNode::malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

这段代码定义了一个名为BuySListNode的函数，它接受一个数据值作为参数，并返回一个新的链表结点。函数首先使用malloc来分配内存，然后初始化结点的数据成员和指向下一个结点的指针。

3.头插与尾插

链表的一个重要特性是可以在任意位置插入新元素，这使得链表非常适合动态数据集合的处理。
下面我将分别介绍如何实现头插和尾插操作。

3.1头插

链表不为空：

链表为空：

可以发现，头插时，链表为不为空操作相同。
SList.h：

void SListPushFront(SListNode** pphead, SLTDataType x);

SList.c：

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

这段代码定义了一个名为SListPushFront的函数，它接受指向链表头结点的二级指针和一个数据值作为参数。
首先，调用CreateSLTNode来创建一个新结点，并将其next指针设置为原来的头结点。
最后，更新头指针使其指向新结点。
现在可以测试一下：
test.c:

void TestSList1()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
}
int main()
{
	TestSList1();
	return 0;
}

运行结果：
在这里插入图片描述

3.2尾插

空链表

在尾插中，如果链表为空，则需改变头指针，因此，我们传入二级指针。
SList.h：

void SListPushBack(SListNode** pphead, SLTDataType x);

SList.c：

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = BuySlistNode(x);
	*pphead = newnode;
}

找尾

SListNode* tail = *pphead;

尾插的实现比头插更复杂，想要在尾部插入数据，首先得找到尾部。
错误写法：

while (tail != NULL)
{
	tail = tail->next;
}
tail = newnode;

分析一下，循环的结束条件是tail等于NULL，而下一步则把新结点赋值给了NULL，因此错误。
链表的链接是让上一个结点有下一个结点的地址，因此，尾插的本质是：原尾结点中要存储新尾结点的地址。
完整写法：
SList.c：

void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newnode = BuySlistNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	SListNode* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newnode;
}

这段代码首先创建一个新结点。
如果链表为空，则直接插入新结点并更新头指针。
否则，初始化一个指针tail从头结点开始，并遍历链表直到找到最后一个结点。
最后，将新结点插入到链表的尾部。

4.头删与尾删

删除的条件是链表不为空，因此该处的函数开头应该assert断言。

4.1头删

两个以上的结点：

一个结点：

SList.h：

void SListPopFront(SListNode** pphead);

SList.c：

void SListPopFront(SListNode** pphead)
{
	assert(*pphead);
	SListNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

这段代码定义了一个名为SListPopFront的函数，它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空，然后保存当前的头结点，并更新头指针使其指向下一个结点。
最后，释放原来头结点占用的内存，并将指针设为NULL以避免野指针。

4.2尾删

单个结点：
同头删
多个结点：
由于需要删除的是最后一个结点，因此，找尾时应该找倒数第二个结点。
SList.h：

void SListPopBack(SListNode** pphead);

SList.c：

void SListPopBack(SListNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

这段代码定义了一个名为SListPopBack的函数，它接受指向链表头结点的二级指针作为参数。
函数首先使用assert来确保链表不为空。
如果链表只有一个结点，则直接释放该结点并更新头指针。
否则，初始化一个指针tail从头结点开始，并遍历链表直到找到倒数第二个结点。
最后，释放尾结点占用的内存，并更新倒数第二个结点的next指针使其指向NULL。
现在可以测试一下：
test.c:

void TestSList3()
{
	SListNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
}