穿透单链表的神秘屏障，洞察数据结构的真谛

发布于：2025-04-03 ⋅ 阅读:(18) ⋅ 点赞:(0)

在这里插入图片描述
❤个人主页：折枝寄北的博客
❤专栏位置：数据结构

在这里插入图片描述

单链表实现逻辑

0. 前言

单链表的结构简单而精妙，每个节点仅包含一个数据元素和一个指向下一个节点的指针。这种结构使得单链表在处理动态数据时游刃有余，无论是数据的增删改查，都能以一种优雅的方式实现。与顺序表相比，单链表在内存使用上更加灵活，无需预先分配固定大小的空间，能够根据实际需求动态扩展，这使得它在处理大量数据时更具优势。
本篇文章将带你走进单链表的世界，从它的基本概念、结构特点，到各种常见操作的实现逻辑，我们将一一深入剖析。通过详细的代码示例和生动的解释，你将能够清晰地理解单链表的每一个细节，掌握其在实际编程中的应用技巧。无论你是数据结构的初学者，还是希望在编程中运用更高效数据结构的开发者，这篇文章都将为你提供宝贵的指导，帮助你在编程的道路上更进一步 。

1. 概念及结构

在这里插入图片描述
定义：
链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域用于存储指向下一个节点的指针（或者地址）。链表的节点是动态分配的，不像数组那样在内存中连续存储。链表的这种结构使得它在插入和删除操作时具有较高的灵活性。

链表特点：

  1. 动态性
    链表的长度可以动态改变。在程序运行过程中，可以根据需要随时添加或删除节点。例如，在一个音乐播放器的播放列表中，用户可以随时添加新的歌曲（插入节点）或者删除不想要的歌曲（删除节点），链表能够很好地适应这种动态变化。

  2. 内存分配灵活
    链表的节点不需要在内存中连续存储。它可以在内存的任意位置分配节点空间，通过指针将节点连接起来。这使得链表能够更好地利用内存碎片。相比之下，数组需要连续的内存空间，当内存中没有足够大的连续空间时，数组可能无法分配足够的内存。

  3. 插入和删除操作方便
    在链表中插入和删除节点时，只需要修改相邻节点的指针即可。例如，在单链表中插入一个节点，只需要将前一个节点的指针指向新节点，再将新节点的指针指向原来的下一个节点。删除操作也是类似，只需要将前一个节点的指针直接指向要删除节点的下一个节点。而数组在插入和删除元素时，可能需要移动大量元素来保持数组的连续性，效率较低。

结构示例：
在这里插入图片描述

2. 实现逻辑

2.1 相关函数的声明

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

//重定义类型
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//数据
	struct SListNode* next;//存下一个结构体地址的指针
	//SLTNode* next;  不可以这么写
	//SLTNode* next;  不可以这么写,在重定义前定义会编译报错

}SLTNode;

//打印链表
void SLTPrint(SLTNode* phead);

//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//链表尾删
void SLTPopBack(SLTNode** pphead);

//链表头删
void SLTPopFront(SLTNode** pphead);

//链表查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);

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

//pos位置的删除
void SListErase(SLTNode** pphead, SLTNode* pos);
 
//pos位置后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x); 


//pos位置后删除
void SListInsertAfter(SLTNode* pos);

2.2 函数代码实现

2.2.1 打印

//打印
void SLTPrint(SLTNode* phead)
{
	//不用断言
	SLTNode* cur = phead;
	//while (cur != NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//不可以写成cur++,指针虽然可以++
		//但是地址是连续的增加，而链表的地址不一定是连续的
	}
	printf("NULL\n");
}

2.2.2 创建新节点

//创建新结点
SLTNode* BuySLTNode(SLTDataType x)
{
	//申请新节点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

	//申请失败
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	//初始化新节点
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

2.2.3 尾插

//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	
	//如果链表本身为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//不为空，新结点链接在尾部
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}

}

2.2.4 头插

//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.2.5 尾删

//链表尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表为空
	//暴力检查
	assert(pphead);
	assert(*pphead != NULL);

	//温柔检查
	/*if (*pphead == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}*/

	//1.只有一个节点
	//2.多个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	 }

	找尾
	//SLTNode* prev = NULL;
	//SLTNode* tail = *pphead;
	//while (tail->next != NULL)
	//{
	//	prev = tail;
	//	tail = tail->next;
	//}
	//free(tail);
	//tail = NULL;
	//prev->next = NULL;

	//找尾
	SLTNode* tail = *pphead;
	while (tail->next->next!= NULL) 
	{
		tail = tail->next;
	}
	free(tail->next); 
	tail->next = NULL;
}

2.2.6 头删

//链表头删
void SLTPopFront(SLTNode** pphead)
{
	//链表为空，暴力检查是否可以删除
	assert(*pphead != NULL);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

2.2.7 查找

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

2.2.8 pos位置前插入

//pos位置前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//如果pos为空，进行判断处理
	assert(pos);


	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next!= pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);

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

2.2.9 pos位置的删除

//pos位置的删除
void SListErase(SLTNode** pphead, SLTNode* pos) 
{
	assert(pphead);
	assert(pos);
	//assert(*pphead);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到pos的前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		//删除pos位置结点
		free(pos);
	}

}

2.2.10 pos位置后插入

//pos位置后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.2.11 pos位置后删除

```cpp
//pos位置后删除
void SListInsertAfter(SLTNode* pos) 
{
	assert(pos);
	assert(pos->next);

	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

3. 测试逻辑

对每个函数都进行逻辑测试，检查是否存在运行错误即情况遗漏。

#include"SList.h"

//void TestSList1()
//{
//	SLTNode** plist = NULL;
//	//尾插
//	SLTPushFront(&plist, 1);
//	SLTPushFront(&plist, 2);
//	SLTPushFront(&plist, 3);
//	SLTPushFront(&plist, 4);
//	SLTPrint(plist);
//
//	//SLTPushBack(&plist, 2);
//	//SLTPushBack(&plist, 3);
//	SLTPopBack(&plist);
//	SLTPrint(plist);
//
//	SLTPopBack(&plist);
//	SLTPrint(plist);
//
//	SLTPopBack(&plist);
//	SLTPrint(plist);
//}


//void TestSList2()
//{
//	SLTNode** plist = NULL;
//	//尾插
//	SLTPushFront(&plist, 1);
//	SLTPushFront(&plist, 2);
//	SLTPushFront(&plist, 3);
//	SLTPushFront(&plist, 4);
//	SLTPrint(plist);
//
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//}

//void Func(int y)
//{
//	y = 1;
//}


//void Func(int* p)
//{
//	*p = 1;
//	return p;
//}


//void Func(int** ptr)
//{
//	*ptr = (int*)malloc(sizeof(int));
//}

//void TestSList3()
//{
//	SLTNode* plist = NULL;
//	//尾插
//	SLTPushFront(&plist, 1);
//	SLTPushFront(&plist, 2);
//	SLTPushFront(&plist, 3);
//	SLTPushFront(&plist, 4);
//	SLTPrint(plist);
//
//	//把值为2的那个结点*2
//	SLTNode* ret = SListFind(plist, 2);
//	ret->data *= 2;
//	SLTPrint(plist);
//
//}


void TestSList4()
{
	SLTNode* plist = NULL;
	//尾插
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPushFront(&plist, 5);

	SLTPrint(plist);



	//把值为2的那个结点*2
	SLTNode* ret = SListFind(plist, 2);

	SListInsert(&plist,ret, 20);

	SLTPrint(plist);

	SListErase(&plist, ret);
	ret = NULL;
	SLTPrint(plist);
}
int main()
{
	/*TestSList1();
	TestSList2();*/
	//TestSList3();
	//int* px = NULL;
	//Func(&px);
	//free(px);

	TestSList4();
	return 0;
}

感谢您的阅读支持！！！
后续会持续更新的！！！
文末投票支持一下！！！

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布