1.2 实现单链表

在上一篇文章中，单链表的实现只有一少部分，这一篇接着来了解单链表剩下的接口实现。

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义单链表就是定义节点，因为单链表是由节点组成的，所以定义单链表就是定义节点
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);//在指定位置之后插入数据
void* SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos节点
void* SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SLTDesTroy(SLTNode** pphead);//申请新的节点
SLTNode* SLTBuyNode(SLTDataType x);

SList.c
#include"SList.h"//单链表的打印
void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//新节点的申请
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申请新节点这里传的应该是节点类型而不是数据类型//单链表：每次插入一个节点时，需要分配一个节点（结构体）的内存，因此使用 `sizeof(节点类型)`。//顺序表：在扩容时，需要为多个数据元素分配一块连续的内存（即数组），因此使用 `元素个数 * sizeof(数据类型)`。if (node == NULL){perror("malloc fail!\n");exit(1);}node->data = x;node->next = NULL;return node;
}//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {//单链表为空assert(pphead);//SLTNode* Tail = *pphead; 不能在这里定义Tail 因为这里的Tail为空，后面循环中的Tail->next 就会报错，不会进入循环当中SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else {//单链表不为空，找尾节点，插入新节点SLTNode* Tail = *pphead;while (Tail->next != NULL){Tail = Tail->next;}//跳出循环，插入新节点Tail->next = newnode;//newnode->next = NULL; 不需要写是因为，newnode在初始化的时候就已经置为NULL了}
}//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead &&*pphead);//pphead 不能插入空的数据//*pphead 不能对空表进行插入SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;//将新的节点作为插入后链表的头结点
}//单链表尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead&&*pphead);//pphead--空链表不可以进行删除操作// *pphead--不为空的链表--循环遍历 --遍历到尾节点的前一个节点，将此节点的next置为NULL；//只有一个节点的情况，是不能遍历的，因为他的next->next为NULLif ((*pphead)->next == NULL) // -> 的优先级大于 * 的优先级{free(*pphead);*pphead = NULL;}else {SLTNode* Tail = *pphead;SLTNode* prev = NULL;while (Tail->next){prev = Tail;Tail = Tail->next;}//跳出循环prev->next = NULL;free(Tail);Tail = NULL;}}//单链表的头删
void SLTPopFront(SLTNode** pphead) 
{assert(pphead&&*pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) 
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//跳出循环return NULL;}//在指定位置之前插入数据
void* SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead && pos);//下标pos从1开始的if (pos == *pphead){//头插SLTPushFront(pphead,x);}else {SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){//找到prevprev=prev->next;}newnode->next = pos;prev->next = newnode;}}//在指定位置之后插入数据
void* SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;//不用考虑pos->next为不为空的情况，因为assert只限制了pos//所以也不用单独考虑当pos->next=NULL时尾插的情况，上述的//代码包含这种情况}//删除pos节点
void* SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead && pos);//pos为头结点if (pos == *pphead){//头删操作SLTPopFront(pphead);}//pos非头结点else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//销毁链表
void SLTDesTroy(SLTNode** pphead) {SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

1.3 链表的分类

链表的结构多样，有8种链表结构：

链表的具体分类：

虽然链表的种类有很多，但是最常用的就两种：单链表和双链表。

单链表：单向不带头不循环的链表。结构简单，一般不会单独用来存储数据；实际中更多的是作为其他数据结构的子结构。

双链表：双向带头循环的链表 。结构最复杂，一般用在单独存储数据；实际中使用的链表数据结构，都是带头双向循环链表，虽然这个结构复杂，但是在写代码的时候会发现结构会带来很多优势，实现反而会变得更加简单。

2  双链表

2.1 概念与结构

双链表全称：带头双向循环链表

注意：

我们这里提到的 "带头" 跟我们前面说的 "头结点" 是两个概念，前面在单链表中的称呼是不严谨的，是为了更好的理解。

而在带头链表里的头结点，实际是 "哨兵位"，哨兵位节点不存储任何的有效元素，只是站在这里 “放哨的”

2.2 实现双向链表

List.c

#include "List.h"LTNode* buyNode(LTDataType x)
{LTNode* node=(LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = node;return node;
}//初始化双向链表  --- 接口一致性
LTNode* LTInit()
{////创建头结点//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//phead->data = -1;    //头结点是无效的数据，随便存放一数值就ok//phead->next = phead->prev = phead;   //指向自己代表是双向的LTNode* phead = buyNode(-1);return phead;}//void LTInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ->", pcur->data);pcur = pcur->next;}printf("\n");}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//phead newnode phead->nextLTNode* newnode = buyNode(x);phead->next->prev = newnode;newnode->next = phead->next;phead->next = newnode;newnode->prev = phead;}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;//等于     true   为空//不等于   false  不为空}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));//为空    true  ---  ！true=false 报错//不为空  false ---  ！false=true 继续执行LTNode* del = phead->prev;//phead phead->prev->prev phead->prevdel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//头删 删除的是头结点的下一个结点
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));//phead phead->next phead->next->nextLTNode* next = phead->next;next->next->prev = phead;phead->next = next->next;free(next);next = NULL;}//查找指定元素
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);//pos为空就是在双向链表中没有找到x，就不能进行插入操作LTNode* newnode = buyNode(x);//pos newnode pos->nextpos->next->prev = newnode;newnode->next = pos->next;pos->next = newnode;newnode->prev = pos;}
//删除在pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);//pos 为空不可删除 为空找不到该元素//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

3. 顺序表与链表的分析

不同点顺序表链表（单链表）
存储空间物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持：O(1)不支持：O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低：O(N)只需要修改指针指向
插入动态顺序表，空间不够是需要扩容和空间浪费没有容量的概念，按需申请释放，不存在空间浪费
应用场景元素高效存储+频繁访问任意位置高效插入和删除

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/92367.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/92367.shtml
英文地址，请注明出处：http://en.pswp.cn/web/92367.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Windows和Linux应急响应以及IP封堵

Windows和Linux应急响应以及IP封堵

目录 1、Windows入侵排查思路 1.1 检查系统账号安全 1.2 检查异常端口、进程 1.3 检查启动项、计划任务、服务 1.4 检查系统相关信息 1.5 自动化查杀 1.6 日志分析 系统日志分析 Web 访问日志 2、Linux 入侵排查思路 2.1 账号安全 2.1.1、基本使用 2.1.2、入侵排查…
阅读更多...
MIT成果登上Nature！液态神经网络YYDS

MIT成果登上Nature！液态神经网络YYDS

2025深度学习发论文&模型涨点之——液态神经网络液态神经网络&#xff08;Liquid Neural Networks&#xff0c;LNN&#xff09;是一种受生物神经系统启发的连续时间递归神经网络&#xff08;RNN&#xff09;&#xff0c;其核心创新在于将静态神经网络转化为由微分方程驱动的…
阅读更多...
AI 对话高效输入指令攻略（四）：AI+Apache ECharts：生成各种专业图表

AI 对话高效输入指令攻略（四）：AI+Apache ECharts：生成各种专业图表

- **AI与数据可视化的革命性结合**：介绍AI如何降低数据可视化门槛，提升效率。 - **Apache ECharts：专业可视化的利器**：使用表格对比展示ECharts的特点、优势和适用场景。 - **四步实现AI驱动图表生成**：通过分步指南讲解从环境准备到图表优化的全流程，包含多个代码示例及…
阅读更多...
vue2 基础学习 day04 （结构/样式/逻辑、组件通信、进阶语法）下

vue2 基础学习 day04 （结构/样式/逻辑、组件通信、进阶语法）下

一、非父子通信-event bus 事件总线1.作用非父子组件之间&#xff0c;进行简易消息传递。(复杂场景→ Vuex)2.步骤创建一个都能访问的事件总线 &#xff08;空Vue实例&#xff09;import Vue from vue const Bus new Vue() export default BusA组件&#xff08;接受方&#xf…
阅读更多...
ubuntu 20.04 C和C++的标准头文件都放在哪个目录？

ubuntu 20.04 C和C++的标准头文件都放在哪个目录？

在 Ubuntu 20.04 中&#xff0c;C 和 C 标准头文件的存放目录主要由编译器&#xff08;如 GCC&#xff09;的安装路径决定&#xff0c;通常分为以下两类&#xff1a;​1. C 标准头文件​C 语言的标准头文件&#xff08;如 <stdio.h>、<stdlib.h> 等&#xff09;默认…
阅读更多...
change和watch

change和watch

是的&#xff0c;你理解得很对&#xff01; change 与 v-model 的结合&#xff1a;change 事件通常用于监听 表单元素的变化&#xff0c;但它并不一定意味着值发生了变化。它主要是当 用户与输入框交互时&#xff08;如点击选项、选择文本框内容、提交表单等&#xff09;触发的…
阅读更多...
分布式微服务--GateWay(1)

分布式微服务--GateWay(1)

一、什么是微服务网关&#xff08;API Gateway&#xff09; 定义&#xff1a;微服务网关是整个系统请求的统一入口&#xff0c;负责请求转发、过滤处理、安全校验等。 作用&#xff1a; 请求路由 日志记录 权限控制 参数校验 解决跨域问题 黑白名单控制 限流、熔断、降级…
阅读更多...
大文件断点续传（vue+springboot+mysql）

大文件断点续传（vue+springboot+mysql）

断点续传vue前端代码后端代码controller 层service层持久层主表&#xff0c;初始化单次上传文件表&#xff0c;单次上传所有的文件记录文件分块表科普信息参考其他博主 流程图 vue前端代码 这里是只做了demo示例&#xff0c;主线测试没什么问题&#xff0c;前端同学可参考修…
阅读更多...
Nodejs》》MySql

Nodejs》》MySql

Node.js 操作MySQL数据库 文档 # 项目要先安装mysql包npm i mysqlxx // 安装指定版本npm i mysql // 默认安装最新版本 # 连接 mysq// 使用连接池连接const mysql require(mysql)# 建立连接const db mysql.createPool({host:, // 数据库的IP地址user:ro…
阅读更多...
金仓数据库常见问题（持续更新）

金仓数据库常见问题（持续更新）

目录 1.查看大小是否敏感写参数&#xff0c;提示&#xff1a;未认可的配置参数 "case_sensitive" 2.sys_backup.sh init时提示can not connect the primary node 3.设置逻辑备份运行脚本时提示错误are not allowed to use this program (crontab) 4.修改表字段类…
阅读更多...
Docker Buildx最佳实践：多架构镜像构建指南

Docker Buildx最佳实践：多架构镜像构建指南

文章目录为什么需要 Docker Buildx安装与启用 Docker Buildx创建多架构构建器实例构建多架构镜像优化构建性能调试多架构构建实战案例&#xff1a;构建 Go 应用多架构镜像总结Docker Buildx 是 Docker 官方推出的扩展工具&#xff0c;用于支持多平台镜像构建&#xff0c;简化跨…
阅读更多...
你用的是什么键盘？

你用的是什么键盘？

在电竞行业飞速发展的当下&#xff0c;游戏键盘作为玩家操作的核心载体&#xff0c;其性能表现直接影响着游戏体验与竞技结果。而赛卓电子推出的磁轴键盘专用芯片 SC4823&#xff0c;凭借一系列突破性的技术特性&#xff0c;正成为游戏键盘领域的性能革新者。​对于游戏玩家而言…
阅读更多...
Activiti 中各种 startProcessInstance 接口之间的区别

Activiti 中各种 startProcessInstance 接口之间的区别

前言在用 RuntimeService 接口启动流程实例时&#xff0c;总是分不清楚不同 startProcessInstanceXXX 接口之间的区别&#xff0c;这篇文章基于 Activiti 7.0.0.GA 版本&#xff0c;对这一类接口进行一个梳理和归类。详解接口列表RuntimeService 接口中以 startProcessInstance…
阅读更多...
新手BUG：函数中 static 变量的赋值语句只会执行一次

新手BUG：函数中 static 变量的赋值语句只会执行一次

在 C 函数中使用 static 变量时&#xff0c;很多新手会陷入一个认知误区&#xff1a;认为变量的初始化语句会在每次函数调用时执行。比如在bool funcA() { // Q&#xff1a;多次调用funcA&#xff0c;funcB会被执行几次&#xff1f;// A&#xff1a;1次static bool value func…
阅读更多...
Python 基础详解：数据类型（Data Types）—— 程序的“数据基石”

Python 基础详解：数据类型（Data Types）—— 程序的“数据基石”

一、引言&#xff1a;为什么数据类型如此重要&#xff1f;在 Python 编程中&#xff0c;数据类型决定了&#xff1a;数据的存储方式可以对数据执行的操作数据的取值范围不同类型之间的运算规则理解数据类型是编写正确、高效程序的基础。Python 是动态类型语言&#xff0c;虽然你…
阅读更多...
WindowsLinux系统 安装 CUDA 和 cuDNN

WindowsLinux系统 安装 CUDA 和 cuDNN

Windows安装前的准备工作 检查硬件兼容性&#xff1a;确认电脑显卡为 NVIDIA GPU。通过快捷键 Win R 唤出“运行”&#xff0c;输入“control /name Microsoft.DeviceManager”唤出“设备管理器”&#xff0c;点击“显示适配器”查看是否有 NVIDIA 字样。 验证 CUDA 支持性&a…
阅读更多...
工业数采引擎-通信链路SOCKET

工业数采引擎-通信链路SOCKET

通信库&#xff1a;DotNetty 封装实现&#xff1a;TcpServer、TcpClient、Udp TCP协议特性&#xff1a;面向连接协议&#xff1b;每个新连接都会创建独立的ChannelHandler实例&#xff1b;TcpHandler构造函数在每次客户端连接时触发 UDP协议特性&#xff1a;无连接协议&#…
阅读更多...
PHP小白零基础入门（附视频教程）

PHP小白零基础入门（附视频教程）

概述 PHP是一种通用开源脚本语言&#xff0c;常用于服务器端Web开发&#xff0c;具有语法简单、上手快等特点。视频教程&#xff1a;https://pan.quark.cn/s/8f214c23301b 搭建开发环境&#xff1a; 选择集成工具&#xff1a;可选择XAMPP&#xff08;支持Windows/Mac/Linux…
阅读更多...
验证码等待时间技术在酒店自助入住、美容自助与社区场景中的应用必要性研究—仙盟创梦IDE

验证码等待时间技术在酒店自助入住、美容自助与社区场景中的应用必要性研究—仙盟创梦IDE

代码 代码 完整<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>验证码倒计时</title><s…
阅读更多...
Flask从入门到实战：基础、进阶、项目架构与接口测试

Flask从入门到实战：基础、进阶、项目架构与接口测试

本文将带你从零开始掌握Flask框架&#xff0c;涵盖基础使用、进阶技巧、项目架构设计&#xff0c;并提供完整的接口测试客户端代码。 目录一、Flask基础入门1.1 Flask简介与安装1.2 第一个Flask应用1.3 路由与请求处理1.4 请求与响应处理二、Flask进阶使用2.1 模板引擎Jinja22.…
阅读更多...
最新文章

Copyright @ 2022~2023