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

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

news 来源：原创 2025/5/9 7:51:17

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

在这里插入图片描述

单链表实现逻辑

0. 前言
1. 概念及结构
2. 实现逻辑
- 2.1 相关函数的声明
- 2.2 函数代码实现
- - 2.2.1 打印
  - 2.2.2 创建新节点
  - 2.2.3 尾插
  - 2.2.4 头插
  - 2.2.5 尾删
  - 2.2.6 头删
  - 2.2.7 查找
  - 2.2.8 pos位置前插入
  - 2.2.9 pos位置的删除
  - 2.2.10 pos位置后插入
  - 2.2.11 pos位置后删除
3. 测试逻辑

0. 前言

单链表的结构简单而精妙，每个节点仅包含一个数据元素和一个指向下一个节点的指针。这种结构使得单链表在处理动态数据时游刃有余，无论是数据的增删改查，都能以一种优雅的方式实现。与顺序表相比，单链表在内存使用上更加灵活，无需预先分配固定大小的空间，能够根据实际需求动态扩展，这使得它在处理大量数据时更具优势。

本篇文章将带你走进单链表的世界，从它的基本概念、结构特点，到各种常见操作的实现逻辑，我们将一一深入剖析。通过详细的代码示例和生动的解释，你将能够清晰地理解单链表的每一个细节，掌握其在实际编程中的应用技巧。无论你是数据结构的初学者，还是希望在编程中运用更高效数据结构的开发者，这篇文章都将为你提供宝贵的指导，帮助你在编程的道路上更进一步。

1. 概念及结构

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

链表特点：

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

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

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

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

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的那个结点*2SLTNode* 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;
}

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