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

【数据结构实战】从零开始打造你的专属链表

news 2024/11/15 5:53:53

    

🏝️专栏：【数据结构实战篇】

🌅主页：f狐o狸x

目录

一、链表的概念及结构

二、链表的分类

        2.1 单向的或双向的

        2.2 带头的或不带头的

        2.3 循环或非循环

        三、链表的实现

        3.1 打印和动态申请一个结点

        3.2 尾插一个数

        3.3 头插一个数

        3.4 尾删一个数

 3.5 头删一个数

        3.6 查找数据

        3.7 pos位置插入数据

        3.8 pos位置删除数据

         3.9 销毁链表

四、链表代码

        本期我们接着上期的来，开始我们的链表环节

一、链表的概念及结构

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

        我们可以看出：

        1. 链表结构在逻辑上是连续的，在物理上不一定连续

        2. 现实中 ，每一个节点都需要用malloc向堆栈申请

        3. 申请出来的空间可能连续，也有可能是不连续的

二、链表的分类

        实际中链表的结构非常多样，这里介绍几种类别

        2.1 单向的或双向的

        

        2.2 带头的或不带头的

        带头的链表也被称为哨兵位

        2.3 循环或非循环

        无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
         带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

        三、链表的实现

        我们先实现单链表

typedef int SLDataType;typedef struct SListNode
{SLDataType data;struct SList* next;
}SListNode;

        先在头文件中声明好单链表

        3.1 打印和动态申请一个结点

// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur){printf("%d->",cur->data);cur = cur->next;}printf("\n");
}// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));if (newcode == NULL){perror("SListPushBack::malloc");return NULL;}newcode->next = NULL;newcode->data = x;return newcode;
}

        3.2 尾插一个数

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{SListNode* newcode = BuySListNode(x);//检查单链表是否为空if (*pplist == NULL){*pplist = newcode;}else{SListNode* tail = *pplist;//找尾while (tail->next){tail = tail->next;}tail->next = newcode;}
}

        3.3 头插一个数

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{SListNode* NewCode = BuySListNode(x);NewCode->next = *pplist;*pplist = NewCode;
}

        3.4 尾删一个数

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);//只有一个节点if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{//找尾	SListNode* tail = *pplist;SListNode* prev = NULL;;while (tail->next){prev = tail;tail = tail->next;}//删除节点free(tail);tail = NULL;prev->next = NULL;}}

        也可以这样尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);//只有一个节点if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{找尾	//SListNode* tail = *pplist;//SListNode* prev = NULL;;//while (tail->next)//{//	prev = tail;//	tail = tail->next;//}删除节点//free(tail);//tail = NULL;//prev->next = NULL;SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}//删除节点free(tail->next);tail->next = NULL;}}

 3.5 头删一个数

// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(*pplist);SListNode* del = *pplist;*pplist = (*pplist)->next;free(del);del = NULL;
}

        3.6 查找数据

        找到数据返回该节点的地址，找不到则返回null

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

        3.7 pos位置插入数据

        利用查找函数找到数据的地址之后，在该节点前面插入数据

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{assert(pplist);assert(pos);//申请一个节点SListNode* NewNode = BuySListNode(x);//找到pos前的位置SListNode* prev = NULL;SListNode* cur = *pplist;//第一个位置插入if (pos == *pplist){//直接头插SListPushFront(pplist, x);}//其他位置插入else{while (cur){if (cur == pos){prev->next = NewNode;NewNode->next = cur;}prev = cur;cur = cur->next;}}
}

        3.8 pos位置删除数据

        同理，先找到数据节点的位置，再删除

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);//pos是第一个节点if (pos == *pplist){//直接头删SListPopFront(pplist);}//其他位置删除else{//找到pos前的位置SListNode* prev = *pplist;SListNode* cur = *pplist;while (cur != pos){prev = cur;cur = cur->next;}prev->next = cur->next;free(cur);cur = NULL;}
}

         3.9 销毁链表

        每次申请一个节点我们都用到了malloc开辟了一块空间，记得归还，有借有还，再借不难~

void DestorySList(SListNode** pplist)
{SListNode* del = NULL;while (*pplist){del = *pplist;*pplist = (*pplist)->next;free(del);del = NULL;}pplist = NULL;
}

四、链表代码

#define  _CRT_SECURE_NO_WARNINGS 1;#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SListNode;// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos);#define  _CRT_SECURE_NO_WARNINGS 1;#include "SList.h"// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur){printf("%d->",cur->data);cur = cur->next;}printf("\n");
}// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));if (newcode == NULL){perror("SListPushBack::malloc");return NULL;}newcode->next = NULL;newcode->data = x;return newcode;
}// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{SListNode* newcode = BuySListNode(x);//检查单链表是否为空if (*pplist == NULL){*pplist = newcode;}else{SListNode* tail = *pplist;//找尾while (tail->next){tail = tail->next;}tail->next = newcode;}
}// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{SListNode* NewCode = BuySListNode(x);NewCode->next = *pplist;*pplist = NewCode;}// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);//只有一个节点if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}//多个节点else{找尾	//SListNode* tail = *pplist;//SListNode* prev = NULL;;//while (tail->next)//{//	prev = tail;//	tail = tail->next;//}删除节点//free(tail);//tail = NULL;//prev->next = NULL;SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}//删除节点free(tail->next);tail->next = NULL;}}// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(*pplist);SListNode* del = *pplist;*pplist = (*pplist)->next;free(del);del = NULL;
}// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{SListNode* cur = plist;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{assert(pplist);assert(pos);//申请一个节点SListNode* NewNode = BuySListNode(x);//找到pos前的位置SListNode* prev = *pplist;SListNode* cur = *pplist;//第一个位置插入if (pos == *pplist){//直接头插SListPushFront(pplist, x);}//其他位置插入else{while (cur!=pos){prev = cur;cur = cur->next;}prev->next = NewNode;NewNode->next = cur;}
}// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);//pos是第一个节点if (pos == *pplist){//直接头删SListPopFront(pplist);}//其他位置删除else{//找到pos前的位置SListNode* prev = *pplist;SListNode* cur = *pplist;while (cur != pos){prev = cur;cur = cur->next;}prev->next = cur->next;free(cur);cur = NULL;}
}// 销毁链表
void DestorySList(SListNode** pplist)
{SListNode* del = NULL;while (*pplist){del = *pplist;*pplist = (*pplist)->next;free(del);del = NULL;}pplist = NULL;
}

        坚持学习！当你快扛不住的时候，困难也快扛不住了！

        留下你宝贵的三连叭~ QAQ


http://www.mrgr.cn/news/69727.html

相关文章：

  • 蓝桥杯竞赛单片机组备赛【经验帖】
  • 7.4、实验四：RIPv2 认证和触发式更新
  • 【Golang】Go语言环境安装
  • 关于 3D Engine Design for Virtual Globes（三维数字地球引擎设计）
  • 2024 年Postman 如何安装汉化中文版？
  • UniApp 应用、页面与组件的生命周期详解
  • FPGA 第5讲 点亮你的LED灯
  • AI重塑软件开发流程
  • A025-基于SpringBoot的售楼管理系统的设计与实现
  • 【网络安全】Nginx功能快速入门
  • 05_docker 安装常用软件
  • 【GPTs】EmojiAI：轻松生成趣味表情翻译
  • Linux服务器进程的控制与进程之间的关系
  • ReentrantLock【复习】
  • 微服务(二)
  • AI背后的“思考者“：LLM大语言模型是什么？
  • 使用热冻结数据层生命周期优化在 Elastic Cloud 中存储日志的成本
  • 一定要chatgpt吗？
  • 十八：Spring Boot 依赖（3）-- spring-boot-starter-data-jpa 依赖详解
  • 对静态资源加载失败的场景做降级处理
  • 防倒灌电路【手电钻工作日志】
  • 素数筛选法
  • 说说HDD老将的那些事儿
  • 这是我见过讲解大模型最详细的一本书！学习大模型的建议都去读！
  • 拓扑学与DNA双螺旋结构的奇妙连接：从算法到分子模拟
  • 大模型入门自学资源汇总，很难找到比这还全的大模型学习资源总结了！