数据结构——单向链表（C语言实现）

无头链表：以结点为开头的链式结构——————同时也是非循环链表typedef struct SListNode//定义的是结点的结构//存放数据//存放下一个位置的地址}SLTNode;//pos就是节点的指针。

笔记专用号嘎嘎嘎

2066人浏览 · 2024-01-18 22:28:05

笔记专用号嘎嘎嘎 · 2024-01-18 22:28:05 发布

什么是链表？

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

实则可以看做一个一个车厢连接在一起，车厢里的元素可以看做人，也就是节点里存储的数据，元素。

注意：

1. 链式结构在逻辑上是连续的，但是在物理结构上是不连续的

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可能连续，也可能不连续。

此篇文章先介绍无头单向非循环链表

什么是单向链表

无头链表：以结点为开头的链式结构——————同时也是非循环链表

单向链表的声明和定义

typedef int SLTDataType;
typedef struct SListNode//定义的是结点的结构
{
	SLTDataType data;//存放数据
	struct SListNode* next;//存放下一个位置的地址
}SLTNode;

void SLTPrint(SLTNode* phead);
void SLTPopFront(SLTNode** phead);
void SLTPopBack(SLTNode** phead);

SLTNode* STFind(SLTNode* phead, SLTDataType x);

void SLInsert(SLTNode* pphead, SLTNode* pos, SLTDataType x);//pos就是节点的指针
void SLInsertAfter(SLTNode* pos, SLTDataType x);
void SLErase(SLTNode* pphead, SLTNode* pos);
void SLEraseAfter(SLTNode* pos);

void SLDestroy(SLTNode* phead);

单向链表元素的插入（在pos前插入）

我们要知道，链表本质是一个个结点连接起来的，所以可以看做是多个指针连接起来的。

与顺序表不同：顺序表里定义的指针是指向一个动态开辟的数组

链表本身就是由多个指针构成的结点相互连接形成的链式结构。

所以在主函数里定义的时候，顺序表直接定义变量，链表是要定义一个指针变量

void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);//若为初始位置，那么就直接头插
	}
	else 
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;//将newnode后边的接上pos处的数据
	}
}

解惑

1.为什么接收的结构体指针临时变量是用" ** "定义？

——因为我们定义的是一个结构体指针，若是想要改变一个指针本身，那么就需要传入结构体指针的地址，所以我们需要用到二级指针。

2.为什么接收的结构体指针的位置是用" * "定义？

——在顺序表中，我们可以直接用下标来定到要改变元素的位置，但是链表是由指针组成的，因此我们不能用下标来定位。所以需要一个指针来定位，传入，，这里仅是用来定位，所以用一级指针来接收。

3. 插入的具体过程是什么？

——由于链表不能直接用下标定位元素位置，所以我们只能通过指针来定位

——因此要找到插入的位置pos，那我们就需要用一个while循环，直到定位到pos前的一个节点，然后将这个节点定位到新建立的节点上，新建立的节点连接在原pos的节点上。

单向链表元素的插入（在pos后插入）

因为单向链表可以直接定位到下一个节点的位置，所以不需要定位到前一个结点的位置（指针）。因此我们这里不需要传入整个结构体的指针，定位到pos处的指针即可。

void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos); 

	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

单向链表节点的建立

建立一个节点，我们需要给予其一个空间来存放，那怎么建立空间？——malloc函数来建立。

并且节点指向的下一个节点为空

SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    //将这个元素给予一个空间，创建一个结点
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

单向链表元素的打印

我们需要一个接收一个结构体指针来进行遍历。

但是我们不能用原指针来进行遍历，因为这样子遍历到后面，那么头指针就会指向最后一个元素，会导致前面的元素都丢失。

void SLTPrint(SLTNode* phead)//传入的是结构体，所以用一个指针来接收结构体的地址
{
    STNode* cur=phead;//若是*进行了解引用的话，那么就是指向结构体
    while(cur!=NULL)
    {
        printf("%d",cur->data);
        cur=cur->next;
    }
    printf("NULL\n");
}

单向链表元素的删除（后元素）

因为要对链表进行改变，所以我们要传入结构体指针地址，所以需要用一个二级指针来接收地址。

void SLTPopBack(SLTNode** phead)
{
    //因为**phead接收的是地址，所以*phead是结构体的指针
    
	//没有节点（空链表）
	if (*phead == NULL)
	{
		return;
	}
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
			// 找尾部
		while (tail->next->next)//找到倒数第二个,也就是数据中的最后一位数据 
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next=NULL;
	}
}

单向链表元素的删除（前元素）

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);// 链表为空，则pphead也不会为空，所以需要断言——结构体
	assert(*pphead);// 链表为空，不能头删，那么此时需要断言——结构体指针
	SLTNode* del = *pphead;
	*pphead = del->next;//将头指针指向下一个元素的地址
	free(del);
}

单向链表特定位置的删除

void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);//判断结构体不为空
	assert(pos);//判断该位置的指针不为空

	if (pos == *pphead)//若为起始的结点，那么就直接删除第一个结点
	{
		SLTPopFront(pphead);
	}
	else 
	{
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//下一个不是要查找的位置时
		{
			prev = prev->next;//则往下
		}
		prev->next = pos->next;//把下一个元素的地址直接复制为下两位,等于跳过下一个数字
		free(pos);//释放开辟的空间
	}
}

单向链表后一位置的删除

void SLEraseAfter(SLTNode* pos)
{
	assert(pos);
	SLTNode* prve = pos->next;
	pos->next = prve->next;
	free(prve);//释放开辟的内存
}

单向链表元素的查找

同理，不能用下标锁定，所以只能逐一遍历，并且要返回指针

SLTNode* STFind(STNode* phead,SLTDataType x)
{
    assert(phead);
    STNode* cur=phead;
    while(cur)
    {
        if(cur->data==x)
        {
            return cur;//返回此处地方的指针
        }
        cur=cur->next;
    }
    return NULL;
}

单向链表元素的删除

因为链表是由一个个指针连接的，所以我们仅需要删除指针即可。

void SLDestroy(SLTNode* phead)//接受结构体的地址，结构体的地址就是首元素的地址
{
    assert(phead);
    SLTNode* cur=phead;
    while(cur)
    {
        SLTNode* next=cur->next;
        free(cur);
        cur=next;
    }
    phead=NULL;//最后将头指针定义为空指针，置空
}

测试

void TestSList1()
{
	//phead和newnode都是局部变量，该怎么办？
	SLTNode* plist = NULL;//是个结构体指针
	//改变数据要传入数据地址才能同时改变实参的数据
	SLTPushBack(&plist, 1);//拷贝出的是形参，形参改变后不会改变实参
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPushBack(&plist, 4);

	SLTPopBack(&plist);
    SLTPrint(plist);//这里不需要改变内容，故传入指针（指向的起始内容地址）就行

	SLTNode* pos = STFind(plist, 3);//STFind返回的是结构体的指针，故可以通过pos去改变plist
	if (pos)//判断是否为空
	{
		SLInsert(&plist, pos,30);
		//Fine恰好与pos进行协同使用
	}
	SLTPrint(plist);
}

由于此处plist是一个结构体指针，所以

若是想改变结构体的指针，就需要传入结构体指针的地址，所以需要用二级指针来接收

——**pphead

如果只是想进行遍历和结构体的改变，那么就传入结构体的地址即可。

——用一级指针来接收就行了,因为不对指针进行改变，所以不需要用到二级指针。

难点：

主要还是考察了二级指针和一级指针的不同用法，以及在改变链表里的元素时，不同形参的选择

若此处搞懂了，那么单向链表就可以熟练掌握了。

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

uView 2.0 - 通用前端组件库教程

`uView 2.0` 是一个专为 `uni-app` 设计的跨平台 UI 组件库，支持 Vue.js 和 H5 环境。它的设计目标是提供一套简洁、易用且高度自定义的组件，以适应各种应用场景。uView 还提供了丰富的 API 文档以及详细的示例，帮助开发者快速上手并进行定制开发。## 2. 项目快速启动### 安装依赖在你的 uni-app 工程根目录下，通过 npm 或 yarn 安

魔乐社区

【亲测免费】 DeathStarBench：分布式系统性能测试的新星

是一个开源的、云原生的高性能基准测试框架，由希腊雅典国立与卡皮奥理工学院的 George Delimpetrou 教授领导的团队开发。这个项目旨在为现代数据中心和云计算平台提供精确、可扩展的负载测试工具，以评估其在大规模并发场景下的性能和稳定性。## 技术分析DeathStarBench 基于 Rust 和 Go 语言构建，这两个语言以其高效性和内存安全性而闻名。项目采用了模块化设计，包含

魔乐社区

解决Unitree GO2 Edu机器狗SLAM运行中的网络连接问题

在使用Unitree GO2 Edu机器狗进行SLAM(同步定位与地图构建)时，许多开发者可能会遇到网络连接问题。特别是在配置ROS2环境与机器狗通信时，一个常见的错误是获取错误的IP地址导致连接失败。## 错误现象当尝试运行SLAM功能时，系统可能会报出类似以下的错误信息：```ERROR:root:An error occurred: HTTPConnectionPool(hos