C语言之旅：探索单链表

embedded/2024/9/25 16:53:39/

目录

一、前言

二、实现链表的功能：

打印

创建节点

尾插

尾删

头插

头删

查找

在指定位置之前插入数据

指定位置删除

在指定位置之后插入数据

打印

销毁

三、全部源码： 

四、结语

一、前言

链表是一个强大且基础的数据结构。对于很多初学者来说，链表可能是一个令人望而生畏的主题，因为它涉及到了动态内存分配和指针操作等较为高级的概念。但是，一旦你掌握了链表的基本概念和操作，你会发现它在很多实际应用中都有着广泛的应用。

今天，我们就从C语言的角度，来探索一下单链表的基本概念和实现方法。在接下来的篇幅中，我将带你逐步构建一个单链表的简单实现，并解释其中的关键概念和代码逻辑。 

首先，我们需要明确什么是单链表。单链表是一种线性数据结构，它的元素（在C语言中通常称为节点）按照线性的顺序排列，但每个节点并不是在内存中连续存储的。相反，每个节点都包含两个部分：一个是数据域（用于存储实际的数据），另一个是指针域（用于指向下一个节点）。通过这种方式，我们可以将多个节点连接起来，形成一个链状的数据结构。

单链表的定义：
 

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* 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* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

打印

void SLTPrint(SLTNode* phead)
{SLTNode* pucr = phead;while (pucr != NULL){printf("%d->", pucr->data);pucr = pucr->next;}printf("NULL\n");
}

创建节点

SLTNode* SLTBuyNode(SLTDataType x) 
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;newNode->next = NULL;return newNode;
}

尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{SLTNode* newNode = SLTBuyNode(x);// 如果链表为空，直接让头指针指向新节点  if (*pphead == NULL) {*pphead = newNode;return;}// 否则，找到链表尾部并插入新节点  SLTNode* current = *pphead;while (current->next != NULL){current = current->next;}current->next = newNode;
}

尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* prev = NULL;SLTNode* current = *pphead;while (current->next != NULL){prev = current;current = current->next;}free(current);if (prev == NULL){*pphead = NULL;}else{prev->next = NULL;}
}

1.  首先，检查传入的二级指针和其指向的头指针是否为空，以确保链表存在。
2.  接着，定义了两个指针prev和current，用于遍历链表并找到尾节点。
在循环中，prev总是指向current的前一个节点，而current则遍历链表直到找到尾节点（即current->next为NULL的节点）。
3.  找到尾节点后，释放其内存。
4.  最后，根据prev是否为空来判断链表是否只有一个节点。如果是，则将头指针置为NULL；否则，将prev的next指针置为NULL，完成尾节点的删除。 

头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = SLTBuyNode(x);newNode->next = *pphead;*pphead = newNode;}

我们首先通过断言确保传入的二级指针pphead不为空。接着，我们调用SLTBuyNode函数来根据给定的数据x创建一个新的节点newNode。然后，我们将新节点的next指针设置为当前的头节点*pphead，这样新节点就连接到了链表的开始位置。最后，我们更新头指针*pphead，使其指向新节点，从而完成了在链表头部插入新节点的操作。 

头删

//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead=tmp;
}

定义一个临时指针tmp，让它指向当前头节点的下一个节点。接着，我们释放当前头节点的内存。最后，我们更新头指针*pphead，使其指向tmp， 从而完成了头节点的删除操作。如果链表原本只有一个节点，那么删除后头指针*pphead将被设置为NULL，表示链表为空。

查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

使用一个指针pcur来遍历链表，从头节点开始，逐个检查每个节点的数据是否与要查找的数据x相等。如果找到了匹配的节点，就返回该节点的指针；如果遍历完整个链表都没有找到匹配的节点，则返回NULL表示未找到。

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead, x);}else{// 找到pos节点的前一个节点  SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 在pos之前插入新节点  newnode->next = pos;prev->next = newnode;}
}

指定位置删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){*pphead = pos->next;}else{SLTNode* prev = *pphead;while (prev->next != pos)// 遍历链表，找到要删除节点的前一个节点{prev = prev->next;}prev->next = pos->next;}}

在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}

设置新节点的next指针指向pos的下一个节点。最后，它将pos的next指针指向新节点，从而将新节点插入到pos之后。 

打印

//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++) {printf("%d ", ps->arr[i]);}printf("\n");
}

销毁

//销毁
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur != NULL){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

三、全部源码： 

// 打印链表
void SLTPrint(SLTNode* phead)
{SLTNode* pucr = phead;while (pucr != NULL){printf("%d->", pucr->data);pucr = pucr->next;}printf("NULL\n");
}
//初始化
SLTNode* SLTBuyNode(SLTDataType x) 
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;newNode->next = NULL;return newNode;
}
// 尾部插入  
void SLTPushBack(SLTNode** pphead, SLTDataType x) 
{SLTNode* newNode = SLTBuyNode(x);// 如果链表为空，直接让头指针指向新节点  if (*pphead == NULL) {*pphead = newNode;return;}// 否则，找到链表尾部并插入新节点  SLTNode* current = *pphead;while (current->next != NULL){current = current->next;}current->next = newNode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* prev = NULL;SLTNode* current = *pphead;while (current->next != NULL){prev = current;current = current->next;}free(current);if (prev == NULL){*pphead = NULL;}else{prev->next = NULL;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newNode = SLTBuyNode(x);newNode->next = *pphead;*pphead = newNode;}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* tmp = (*pphead)->next;free(*pphead);*pphead=tmp;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead, x);}else{// 找到pos节点的前一个节点  SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 在pos之前插入新节点  newnode->next = pos;prev->next = newnode;}
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){*pphead = pos->next;}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;}}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;	}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur != NULL){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

四、结语

总之，C语言中的单链表之旅是一次富有成效的学习经历。它不仅让我们掌握了链表的基本操作，还提高了我们的编程技能和问题解决能力。希望这个旅程能为你在数据结构和算法领域的进一步探索打下坚实的基础。


http://www.ppmy.cn/embedded/45685.html

相关文章

大文件分片【笔记】

大文件分片【笔记】

createChunk.js Spark-md5计算文件各分片MD5生成文件指纹 可以帮助我们更加方便地进行文件哈希计算和文件完整性检测等操作。 import sparkMd5 from ./sparkmd5.jsexport function createChunk(file, index, chunkSize) {return new Promise((resolve, reject) > {const sta…
阅读更多...
系统架构设计师【第1章】: 绪论 (核心总结)

系统架构设计师【第1章】: 绪论 (核心总结)

文章目录 1.1　系统架构概述1.1.1　系统架构的定义及发展历程1.1.2　软件架构的常用分类及建模方法1.1.3　软件架构的应用场景1.1.4　软件架构的发展未来 1.2　系统架构设计师概述1.2.1　架构设计师的定义、职责和任务1.2.2　架构设计师应具备的专业素质1.2.3　架构设计师的知识…
阅读更多...
配置Zabbix自定义监控、自动发现与注册及代理与Windows监控

配置Zabbix自定义监控、自动发现与注册及代理与Windows监控

目录 引言 一、自定义监控内容 &#xff08;一&#xff09;添加监控主机 &#xff08;二&#xff09;添加自定义监控内容 &#xff08;三&#xff09;自定义监控模板 1.创建模板 2.创建应用集 3.创建监控项 4.创建触发器 5.创建图形 6.主机与模板关联 7.设置邮件报…
阅读更多...
iOS hitTest 机制用处之二-----使用pointInside方法

iOS hitTest 机制用处之二-----使用pointInside方法

hittest 机制 下面是伪代码 - (UIView *)hitTest:(CGPoint)point withEvent:(UIEvent *)event{if (self.hidden NO || self.alpha < 0.05 || self.userInteractionEnabled NO) {//1.当满足这几个条件时&#xff0c;直接丢弃touch事件&#xff0c;不再向下分发。return n…
阅读更多...
初识SDN

初识SDN

初识SDN 软件定义网络&#xff08;SDN&#xff0c;Software-Defined Networking&#xff09;是一种网络架构方法&#xff0c;它通过将网络控制平面与数据平面分离来实现网络的集中化控制和管理。 基本概念 以下是SDN的关键概念和组成部分&#xff1a; 1. SDN的基本概念 控制…
阅读更多...
苹果设备mac/Paid/phone 下载使用anki记忆卡

苹果设备mac/Paid/phone 下载使用anki记忆卡

安卓的设备直接可以下 如果你这个&#xff0c;如图。 首先点击下列网址&#xff0c;下载&#xff0c;在里面搜索anki记忆卡 https://www.i4.cn 下载好&#xff0c;打开应用软件爱思助手。搜索anki记忆卡&#xff0c;下载&#xff0c;然后用数据线一端连接电脑一端连接手机或者…
阅读更多...
net/http与gin框架的关系分析

net/http与gin框架的关系分析

要想学好 gin 框架&#xff0c;首先要学习 net/http 服务&#xff0c;而二者的关系又是重中之重。 本文所要做的任务就是将二者“连接” 起来&#xff0c;让读者掌握其中之精髓。 一、Golang HTTP 标准库示例 使用 golang 启动 http 服务非常简单&#xff0c;就是一个标准的 C…
阅读更多...
uniapp实现微信小程序调用云函数【vue3】

uniapp实现微信小程序调用云函数【vue3】

本人是从微信开发者工具写原生微信小程序一步一步走来&#xff0c;由于vue3框架的慢慢的步入前端市场&#xff0c;为了不被前端市场遗弃&#xff0c;果断从vue2开始步入vue3的学习&#xff0c;本人习惯在在HBuilder X写uniapp的项目&#xff0c;过去uniapp默认vue2框架&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023