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

ops/2024/11/14 4:33:37/

    

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

🌅主页：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.ppmy.cn/ops/132543.html

相关文章

ArrayList扩容机制

ArrayList扩容机制

ArrayList的扩容机制是Java集合框架中的一个重要特性&#xff0c;它允许ArrayList在需要时自动增加其容量以容纳更多的元素。以下是关于ArrayList扩容机制的详细解释&#xff1a; 一、扩容触发条件 ArrayList的扩容通常发生在以下两种情况下&#xff1a; 添加元素时容量不足…
阅读更多...
数字化转型实践：金蝶云星空与钉钉集成提升企业运营效率

数字化转型实践：金蝶云星空与钉钉集成提升企业运营效率

数字化转型实践&#xff1a;金蝶云星空与钉钉集成提升企业运营效率 本文介绍了深圳一家电子设备制造企业在数字化转型过程中&#xff0c;如何通过金蝶云星空与钉钉的高效集成应对挑战、实施解决方案&#xff0c;并取得显著成果。集成项目在提高沟通效率、自动化审批流程和监控异…
阅读更多...
lua入门教程：数字

lua入门教程：数字

在Lua中&#xff0c;数字&#xff08;number&#xff09;是一种基本数据类型&#xff0c;用于表示数值。以下是对Lua中数字的详细教程&#xff1a; 一、数字类型概述 Lua中的数字遵循IEEE 754双精度浮点标准&#xff0c;可以表示非常大的正数和负数&#xff0c;以及非常小的正…
阅读更多...
Rust闭包（能够捕获周围作用域变量的匿名函数，广泛应用于迭代、过滤和映射）闭包变量三种捕获方式：通过引用（不可变引用）、通过可变引用和通过值（取得所有权）

Rust闭包（能够捕获周围作用域变量的匿名函数，广泛应用于迭代、过滤和映射）闭包变量三种捕获方式：通过引用（不可变引用）、通过可变引用和通过值（取得所有权）

文章目录 Rust 闭包详解闭包的定义与语法基本语法 闭包的特性- 环境捕获&#xff08;三种捕获方式&#xff1a;通过引用、通过可变引用和通过值&#xff08;取得所有权&#xff09;&#xff09;示例代码 - 内存安全与生命周期示例代码1 示例代码2&#xff1a;闭包所有权转移示例…
阅读更多...
bert-base-uncased处理文档

bert-base-uncased处理文档

1.安装必要的库 确保安装 transformers 和 torch 库&#xff1a; pip install transformers torch 2.加载本地 BERT 模型和分词器 由于已将模型和分词器下载到本地&#xff0c;可以指定文件路径加载。确保路径与本地文件结构一致。 from transformers import BertTokenizer…
阅读更多...
【Python】轻松实现机器翻译：Transformers库使用教程

【Python】轻松实现机器翻译：Transformers库使用教程

轻松实现机器翻译&#xff1a;Transformers库使用教程 近年来&#xff0c;机器翻译技术飞速发展&#xff0c;从传统的基于规则的翻译到统计机器翻译&#xff0c;再到如今流行的神经网络翻译模型&#xff0c;尤其是基于Transformer架构的模型&#xff0c;翻译效果已经有了质的飞…
阅读更多...
EasyExcel 学习之 导出 “提示问题”

EasyExcel 学习之 导出 “提示问题”

EasyExcel 学习之 导出 “提示问题” 现象分析解决&#xff08;伪代码&#xff09;前端 POST 实现后端实现 现象 EasyExcel 支持导出 xlsx、xls、csv 三种文件格式。在导出过程中可能发生各种异常&#xff0c;当发生异常时应该提示错误信息而非导出一个错误的文件。 分析 首…
阅读更多...
Hive操作库、操作表及数据仓库的简单介绍

Hive操作库、操作表及数据仓库的简单介绍

数据仓库和数据库 数据库和数仓区别 数据库与数据仓库的区别实际讲的是OLTP与OLAP的区别 操作型处理(数据库)&#xff0c;叫联机事务处理OLTP&#xff08;On-Line Transaction Processing&#xff09;&#xff0c;也可以称面向用户交易的处理系统&#xff0c;它是针对具体业务…
阅读更多...
最新文章

Copyright @ 2022~2023