文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >单链表的拓扑本质：节点互联中的线性哲学

单链表的拓扑本质：节点互联中的线性哲学

作者头像
胖咕噜的稞达鸭
发布于 2025-10-22 14:50:23
发布于 2025-10-22 14:50:23
1070
举报
文章被收录于专栏：C++初阶高阶C++初阶高阶

1.链表的概念及结构

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

链表的结构跟火车车厢相似，淡季的时候车厢会减少，旺季的时候火车车厢会增加几节，只需要按需去掉车厢节数就可以，每节车厢都是单独存在的。每节车厢都是有车门的。假设如果每节车厢都是上锁的状态，而且都需要不同的钥匙来开启车门，每次只能携带一把钥匙的情况下如何从车头走到车尾？

答案是：每节车厢中都要携带下一节车厢的钥匙。

与顺序表不同的是，链表中的每节车厢都是单独申请下来的空间，我们称之为“节点/结点”。

节点的组成主要有两个：当前节点保存的数据和保存下一个节点的地址（指针变量）。

我们需要通过指针变量来保存下一个节点的位置才能从当前节点走到下一个节点。

2. 单链表的实现

2.1 向操作系统申请一块空间实现单链表的相关操作

代码语言：javascript
复制
//在SList.h中操作
#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>

//定义节点的结构
//数据 + 指向下一个节点的地址

typedef int SLDataType;//假如想保存到数据是浮点型，字符型或者其他自定义类型的数据，用SLDataType
typedef struct SListNode
{
	SLDataType data;//节点存储的数据
	struct SListNode* next;//下一个节点的地址
}SLTNode;

//链表的打印
void SLTPrint(SLTNode* phead);
代码语言：javascript
复制
//在SList.c中操作
#include"SLIST.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;//为什么有phead还要pcur来遍历链表？
	//因为链表遍历的最后会指向NULL，phead如果置为空的话就无法进行及后的操作
	while (pcur)//相当于pcur！=NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
代码语言：javascript
复制
//测试test.c
#include"SLIST.h"

//创建节点和数据
void SListTest01()
{
	//链表就是由一个一个的节点组成的
	//现在需要创建几个节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将几个节点链接在一起
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//打印出来链表
	SLTNode* plist = node1;
	SLTPrint(plist);
}
int main(void)
{
	SListTest01();
	return 0;
}

 2.2 尾插

上代码！

代码语言：javascript
复制
//在SList.h中操作
//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x);
代码语言：javascript
复制
//在SList.c中操作
//申请一个空间用来下面的尾插，头插等操作
SLTNode* SLTBuyNode(SLDataType x)
{
	//申请空间
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//万一申请空间失败了
	if (newnode == NULL)
	{
		perror("malloc failed!\n");
		exit(1);
	}
	newnode->data = x;//申请成功的话插入x
	newnode->next = NULL;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLDataType x)
{
	assert(pphead);//传递的指针不能为空
	SLTNode* newnode = SLTBuyNode(x);//调用申请SLTBuyNode(x)
	//链表为空不为空两种情况都要考虑
	if (*pphead == NULL)
	{
		*pphead = newnode;//如果这个链表本身就为空的话，那么刚刚申请的newnode就是*pphead
	}
	else //链表不为空，找尾
	{
		SLTNode* ptail = *pphead;//把*pphead赋值给ptail遍历链表
		while (ptail->next)//相当于ptail->next!=NULL
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;//这一步ptail->next走出了循环，ptail->next=NULL,在此处赋值newnode，把x插进去
	}
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
}

int main(void)
{
	//SListTest01();
	SListTest02();
	return 0;
}

2.3 头插

代码语言：javascript
复制
//在SList.h中操作
//头插
void SLTPushFront(SLTNode** pphead, SLDataType x);
代码语言：javascript
复制
//在SList.c中操作
//头插
void SLTPushFront(SLTNode** pphead, SLDataType x)
{
	assert(pphead);//传的指针不为空指针
	SLTNode* newnode = SLTBuyNode(x);//申请一个newnode空间，作为头插x的位置
	newnode->next = *pphead;//创建的新的空间newnode下一个节点指向链表的第一个位置*pphead
	*pphead = newnode;//也就是newnode赋值给*pphead
	//以上代码为空的时候也是适用的
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
    SLTPushFront(&plist, 6);
    SLTPushFront(&plist, 5);
    SLTPrint(plist);
}
int main(void)
{
	//SListTest01();
	SListTest02();
	return 0;
}

2.4 尾删 

代码语言：javascript
复制
//在SList.h中操作
//尾删
void SLTPopBack(SLTNode** pphead);
代码语言：javascript
复制
//在SList.c中操作
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//传的指针不能为空指针，而且链表也不能为空
	//这里分为两种情况：链表中有一个节点，或者链表中有多个节点
	//当链表中只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else //链表中有多个节点
	{
		SLTNode* prev = *pphead;//不仅要找到尾节点，而且为节点的前一个指针也要有，prev->next=NULL,不然直接释放掉尾删的代码，会导致prev指向野指针
		SLTNode* ptail = *pphead;//ptail和prev都要指向*pphead，遍历链表
		while (ptail->next)
		{
			prev = ptail;//prev要保存ptail的前一个节点的值
			ptail = ptail->next;//然后ptail继续往下走
		}
		//现在来到了出了循环的一步
		free(ptail);
		ptail = NULL;//释放掉ptail的空间之后将申请的空间置为空
		prev->next = NULL;//prev的下一个指针置为空
	}
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	
	//尾删
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

}

int main(void)
{
	//SListTest01();
	SListTest02();
	return 0;
}

2.5 头删

代码语言：javascript
复制
//在SList.h中操作
//头删
void SLTPopFront(SLTNode** pphead);
代码语言：javascript
复制
//在SList.c中操作
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//头删的时候不能直接把pphead指向的空间free掉，不然会找不到下一个节点的位置，所以要把*pphead存储的节点先赋值给next节点
	SLTNode* next = (*pphead)->next;//->优先级高于（）
	free(*pphead);
	*pphead = next;//头节点释放掉之后，第一个节点已经被释放掉了,但是不可置为空，要衔接给下一个空间作为链表的头节点
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	
	//头删
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}

int main(void)
{
	//SListTest01();
	SListTest02();
	return 0;
}

2.6 查找

代码语言：javascript
复制
//在SList.h中操作
//查找
SLTNode* SLTFind(SLTNode* phead, SLDataType x);//查找数据不会影响第一个节点的指针，所以这里传的是一级指针，查找完之后要返回值为SLTNode*类型
代码语言：javascript
复制
//在SList.c中操作
//查找
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{
	SLTNode* pcur = phead;
	//pcur原因:用phead遍历链表，如果找到链表末尾没有查找到，需要再查找一遍，phead已经置为空，那么就需要定义一个pcur来遍历链表
	while (pcur)//pcur!=NULL
	{
		if (pcur->data==x)//如果pcur指针指向的data刚刚好等于x
		{
			return pcur;//返回这个指针pcur指向的x
		}
		pcur = pcur->next;
	}
	return NULL;//没有找到
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	


	SLTNode* find = SLTFind(plist, 3);//链表中查找3，find来接收
	SLTPrint(plist);
	if (find == NULL)
	{
		printf("没有找到！\n");
	}
	else
	{
		printf("找到了!\n");
	}
}

2.7 在指定位置插入数据

代码语言：javascript
复制
//在SList.h中操作
//在指定位置插入数据、
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
代码语言：javascript
复制
//在SList.c中操作
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead && *pphead);
	assert(pos);//需要查找的数据也不能为空
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	


	SLTNode* find = SLTFind(plist, 3);//链表中查找3，find来接收
	SLTInsert(&plist, find, 99);
	SLTPrint(plist);
}

2.8 在指定位置之后插入数据

代码语言：javascript
复制
//在SList.h中操作
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataType x);
代码语言：javascript
复制
//在SList.c中操作
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{
	assert(pos);
	//申请一个空间存放x
	SLTNode* newnode = SLTBuyNode(x);
	//pos - newnode - pos->next
	newnode->next = pos->next;//pos的下一个节点赋值给newnode
	pos->next = newnode;//然后pos的下一个节点链接newnode

	//pos->next = newnode;//newnode已经赋值给了pos->next
	//newnode->next = pos->next;//这时候pos->next中存放的是newnode的值，所以这样写是不对的
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	


	SLTNode* find = SLTFind(plist, 3);//链表中查找3，find来接收
	SLTInsertAfter( find, 99);
	
	SLTPrint(plist);

2.9 删除指定位置的数据

代码语言：javascript
复制
//在SList.h中操作
//删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);
代码语言：javascript
复制
//在SList.c中操作
//删除指定位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && pos);
	//有两种情况：删除的数据是头节点/不是头节点
	if (*pphead == pos)//if大括号中都是头删代码
	{
		SLTNode* next = (*pphead)->next;//这三行也可以SLTPopFront(pphead);
		free(*pphead);
		*pphead = next;
	}
	else 
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
			{
				prev = prev->next;
			}
		prev->next = pos->next;
		free(pos);
		pos == NULL;
	}
}
代码语言：javascript
复制
//测试test.c
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	


	SLTNode* find = SLTFind(plist, 3);//链表中查找3，find来接收
	SLTErase(&plist, find);
	
	SLTPrint(plist);

2.10 删除指定节点之后的数据

代码语言：javascript
复制
//在SList.h中操作
//删除指定节点之后的数据
void SLTEraseAfter(SLTNode* pos);
代码语言：javascript
复制
//在SList.c中操作
//删除指定节点之后的数据
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;//定义一个del用来存储pos的下一个数据，也就是应该被删掉的数据
	//pos del del->next
	//现在要做的就是让pos->=del->next,然后释放掉del，del置为空
	pos->next=del->next;
	free(del);
	del = NULL;
}
代码语言：javascript
复制
//在test.c中操作
void SListTest02()
{
	//指向链表的头节点为空
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);//指向头结点的指针
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	


	SLTNode* find = SLTFind(plist, 3);//链表中查找3，find来接收
	SLTErase(&plist, find);
	SLTEraseAfter(find);
	//SLTInsertAfter( find, 99);
	//SLTInsert(&plist, find, 99);
	SLTPrint(plist);
}

int main(void)
{
    SListTest02();
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-08-07，如有侵权请联系 cloudcommunity@tencent.com 删除
plist
测试
链表
数据
指针

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

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

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

plist
测试
链表
数据
指针
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 1.链表的概念及结构
    •  2.2 尾插
    • 2.3 头插
    • 2.4 尾删 
    • 2.5 头删
    • 2.6 查找
    • 2.7 在指定位置插入数据
    • 2.8 在指定位置之后插入数据
    • 2.9 删除指定位置的数据
    • 2.10 删除指定节点之后的数据
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论