数据结构——单链表专题

目录

    • 1. 链表的概念及结构
    • 2. 实现单链表
      • 初始化
      • 尾插
      • 头插
      • 尾删
      • 头删
      • 查找
      • 在指定位置之前插入数据
      • 在指定位置之后插入数据
      • 删除指定位之前的节点
      • 删除指定位置之后pos节点
      • 销毁链表
    • 3. 完整代码
      • test.c
      • SList.h
    • 4. 链表的分类

1. 链表的概念及结构

在顺序表中存在一定的问题：

  1. 顺序表的中间/头部插入、删除需要挪动数据
  2. 扩容存在性能的消耗
  3. 会有空间的浪费

而链表是独立的节点组成

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

链表、顺序表都是线性表

逻辑结构一定是线性的
物理结构不一定是线性的

在这里插入图片描述

图中指针变量plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希望plist“指向第二个节点时，只需要修改plist保存的内容为0x0012FFA0

为什么还需要指针变量来保存下一个节点的位置？

链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

链表是由一个一个的节点组成的
一个节点由两部分组成：要存储的数据+指针

int a = 1;
int* pa = &a;

节点结构的定义

struct SListNode{
int data;
struct SListNode* next;
}

在这里插入图片描述

链表结构体的打印方式：

在这里插入图片描述

补充说明：

  1. 链式机构在逻辑上是连续的，在物理结构上不一定连续
  2. 节点一般是从堆上申请的
  3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 实现单链表

初始化

typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{SLTDataType data;//节点数据struct SListNode* next;//指针变量保存下一个节点的地址
}SLTNode;

尾插

//公共部分，开辟一个新的节点
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}

在这里插入图片描述

在这里插入图片描述

头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}

在这里插入图片描述

尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}

在这里插入图片描述

头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}

在这里插入图片描述

查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}

在这里插入图片描述

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}

在这里插入图片描述

在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

在这里插入图片描述

删除指定位之前的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}

在这里插入图片描述

删除指定位置之后pos节点

//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}}

在这里插入图片描述

销毁链表

//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

在这里插入图片描述

3. 完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <stdio.h>//void SlistTest1()
//{
//	//一般不会这样去创建链表，这里只是为了给大家展示链表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;//定一个指针指向第一个节点
//	SLTPrint(plist);
//}void SlistTest2()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//SLTPushFront(&plist, 2);//SLTPushFront(&plist, 3);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);
}void SlistTest3()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 0);SLTPrint(plist);//头删SLTPopFront(&plist);SLTPrint(plist);//查找SLTNode* FindRet = SLTFind(&plist, 0);if (FindRet){printf("找到了\n");}else {printf("未找到\n");}SLTInsert(&plist, FindRet, 100);SLTPrint(plist);SLTInsertAfter(FindRet, 200);SLTPrint(plist);//删除指定位置的节点SLTErase(&plist, FindRet);SLTPrint(plist);//销毁节点SListDesTory(&plist);
}int main()
{SlistTest3();//SlistTest2();//SlistTest1();return 0;
}

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <assert.h>//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL){*pphead = newnode;return;}//链表不为空，找尾结点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptril就是尾结点,将尾结点指向newnodeptail->next = newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);//newnode  *ppheadnewnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//指向第一个节点的地址//链表不为空//链表只有一个节点/多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点称为新的头SLTNode* next = (*pphead)->next;//->优先级高于*//把旧的头节点释放掉free(*pphead);*pphead = next;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(*pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到当前数据return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//链表不能为空assert(*pphead);//pos刚好是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* newnode = SLBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//找到了prev->next = newnode;newnode->next = pos;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除指定位之前的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos){//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}//销毁链表
void SListDesTory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

SList.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.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** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除指定位置之前pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);//销毁链表
void SListDesTory(SLTNode** pphead);

4. 链表的分类

链表的结构非常多样，一下情况组合组合起来就有8种链表结构：

在这里插入图片描述
链表说明：

在这里插入图片描述

在单链表中，“头结点”的“头”和“带头”链表是两个概念
单链表中提到的“头结点”指的是第一个有效的节点
“带头”链表里的“头”指的是无效的节点

虽然链表的种类非常之多，但是使用比较多的只有两种：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）

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

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

相关文章

【论文阅读笔记】Contrastive Learning with Stronger Augmentations

【论文阅读笔记】Contrastive Learning with Stronger Augmentations

Contrastive Learning with Stronger Augmentations 摘要 基于提供的摘要&#xff0c;该论文的核心焦点是在对比学习领域提出的一个新框架——利用强数据增强的对比学习&#xff08;Contrastive Learning with Stronger Augmentations&#xff0c;简称CLSA&#xff09;。以下…
阅读更多...
考研高数（导数的定义）

考研高数（导数的定义）

总结&#xff1a; 导数的本质就是极限。 函数在某点可导就必连续&#xff0c;连续就有极限且等于该点的函数值。 例题1&#xff1a;&#xff08;归结原则的条件是函数可导&#xff09; 例题2&#xff1a; 例题3&#xff1a;
阅读更多...
星宸科技SSC369G 双4K高性价比AI IPC方案

星宸科技SSC369G 双4K高性价比AI IPC方案

一、方案描述 SSC369G 双4K高性价比AI IPC方案采用主芯片SSC369G&#xff0c;内核为CA55四核最高主频为1.5Ghz处理器。SOC内置集成一个64位的四核RISC处理器&#xff0c;先进的图像信号处理器&#xff08;ISP&#xff09;&#xff0c;高性能的H.265/H.264/MJPEG视频编解码器&a…
阅读更多...
01.数据结构篇-链表

01.数据结构篇-链表

1.找出两个链表的交点 160. Intersection of Two Linked Lists (Easy) Leetcode / 力扣 例如以下示例中 A 和 B 两个链表相交于 c1&#xff1a; A: a1 → a2↘c1 → c2 → c3↗ B: b1 → b2 → b3 但是不会出现以下相交的情况&#xff0c;因为每个节点只有一个…
阅读更多...
代码随想录算法训练营 DAY20 | 二叉树(7)

代码随想录算法训练营 DAY20 | 二叉树(7)

一、LeetCode 530 二叉搜索树的最小绝对值 题目链接&#xff1a;530.二叉搜索树的最小绝对值https://leetcode.cn/problems/minimum-absolute-difference-in-bst/ 思路一&#xff1a;利用搜索二叉树的中序遍历结果为有序数组的性质&#xff0c;将遍历结果保存到数组中&#xf…
阅读更多...
扭蛋机小程序开发：发展优势

扭蛋机小程序开发：发展优势

商场中精美的扭蛋机一直都是年轻人的心头好&#xff0c;目前&#xff0c;扭蛋机商品也不在局限于各种小型玩具&#xff0c;也逐渐与各类热门IP合作&#xff0c;打造出了各类手办、周边等&#xff0c;深受各个年龄层的喜爱。 如今&#xff0c;扭蛋机在互联网的推动下&#xff0…
阅读更多...
Spring Security基础学习

Spring Security基础学习

一、SpringSecurity框架简介 二、SpringSecurity入门案例 三、SpringSecurity Web权限方案 四、SpringSecurity微服务权限方案 五、SpringSecurity原理总结
阅读更多...
milvus insert api的数据结构源码分析

milvus insert api的数据结构源码分析

insert api的数据结构 一个完整的insert例子: import numpy as np from pymilvus import (connections,FieldSchema, CollectionSchema, DataType,Collection, )num_entities, dim 10, 3print("start connecting to Milvus") connections.connect("default&q…
阅读更多...
【FastAPI】P1 安装与第一个 FastAPI 应用

【FastAPI】P1 安装与第一个 FastAPI 应用

目录 FastAPI 安装第一个 FastAPI 应用代码拆解分析 FastAPI 安装 FastAPI 是用于快速构建 API 的 web 框架&#xff0c;依赖 Python 3.8 及更高版本。使用 pip 命令安装 fastapi&#xff1a; pip install fastapi安装异步处理 ASGI 的服务器 Uvicorn&#xff1a; pip insta…
阅读更多...
设置墙、楼板每层的厚度和材质——群问题整理003

设置墙、楼板每层的厚度和材质——群问题整理003

你好&#xff0c;这里是BIM的乐趣&#xff0c;我是九哥~ 今天分享的是设置墙、楼板等每层的厚度和材质。 我们都知道&#xff0c;Revit中墙、板这类系统族&#xff0c;厚度设置和普通族是不太一样的&#xff0c;他的厚度参数可读&#xff0c;但是并不可设置&#xff0c;因为我…
阅读更多...
【数据仓库】主题域和数据域

【数据仓库】主题域和数据域

数据域与主题域区别 https://www.cnblogs.com/datadance/p/16898254.html 数据域是自下而上&#xff0c;以业务数据视角来划分数据&#xff0c;一般进行完业务系统数据调研之后就可以进行数据域的划分。针对公共明细层&#xff08;DWD&#xff09;进行主题划分。主题域则自上而…
阅读更多...
LabVIEW智能监测系统

LabVIEW智能监测系统

LabVIEW智能监测系统 设计与实现一个基于LabVIEW的智能监测系统&#xff0c;通过高效的数据采集和处理能力&#xff0c;提高监测精度和响应速度。系统通过集成传感器技术与虚拟仪器软件&#xff0c;实现对环境参数的实时监测与分析&#xff0c;进而优化监控过程&#xff0c;提…
阅读更多...
后端开发怎么学？

后端开发怎么学？

后端开发怎么学&#xff1f; 后端开发可以简单地理解为与前端开发相对应的开发方向。前端开发主要负责构建用户界面、维护用户体验等方面的工作&#xff0c;而后端开发则主要负责处理数据、逻辑和算法等方面的工作。后端开发旨在为前端应用程序提供支持&#xff0c;以帮助实现可…
阅读更多...
前端vue金额用逗号分隔

前端vue金额用逗号分隔

实现效果 代码 template部分 <el-input v-model"state.val"></el-input><div>{{ priceFor(state.val) }}</div> js部分 const state reactive({ val: });const priceFor (val)> {if(!val){return }else if(val.length<4){return…
阅读更多...
简单介绍数据结构的基本概念

简单介绍数据结构的基本概念

数据结构的基本概念 常用术语 数据 数据&#xff08;Data&#xff09;是客观事物的符号表示&#xff0c;是所有能输入到计算机中并被计算机程序处理的符号的总称。例如&#xff1a;整数、字符串、图形、图像、声音和动画等 数据元素 数据元素&#xff08;Data Element&…
阅读更多...
RocketMQ（四）：功能特性——备份

RocketMQ（四）：功能特性——备份

1 消息发送重试和流控机制 本节介绍Apache RocketMQ的消息发送重试机制和消息流控机制 1.1 消息发送重试机制 1.1.1 重试基本概念 Apache RocketMQ 客户端连接服务端发起消息发送请求时&#xff0c;可能会因为网络故障、服务异常等原因导致调用失败。为保证消息的可靠性&…
阅读更多...
华为配置旁挂二层组网直接转发示例

华为配置旁挂二层组网直接转发示例

配置旁挂二层组网直接转发示例 组网图形 图1 配置旁挂二层组网直接转发示例组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件扩展阅读 业务需求 企业用户通过WLAN接入网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff…
阅读更多...
关于Sora的一些紧迫问题...

关于Sora的一些紧迫问题...

OpenAI Sora 概述 OpenAI最新的创新&#xff0c;Sora&#xff0c;在人工智能领域开辟了新的天地。Sora是一个文本到视频的扩散模型&#xff0c;可以将文本描述转化为逼真的视频内容。它解决了一个重大的技术挑战&#xff0c;即在视频中保持主体的一致性&#xff0c;即使它们暂…
阅读更多...
Vue3快速上手（八） toRefs和toRef的用法

Vue3快速上手（八） toRefs和toRef的用法

顾名思义&#xff0c;toRef 就是将其转换为ref的一种实现。详细请看&#xff1a; 一、toRef 1.1 示例 <script langts setup name"toRefsAndtoRef"> // 引入reactive,toRef import { reactive, toRef } from vue // reactive包裹的数据即为响应式对象 let p…
阅读更多...
SNAT和DNAT

SNAT和DNAT

1.SNAT SNAT原理与应用: SNAT 应用环境:局域网主机共享单个公网IP地址接入Internet (私有IP不能在Internet中正常路由) SNAT原理:源地址转换&#xff0c;根据指定条件修改数据包的源IP地址&#xff0c;通常被叫做源映谢 SNAT转换前提条件: 1.局域网各主机已正确设置IP地址、子…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023