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

【数据结构初阶】单链表

web 2025/6/26 3:55:52

在这里插入图片描述

文章目录

  • 单链表
    • 1. 链表的概念及结构
    • 2. 单链表的实现
      • 1.定义结点
      • 2.打印数据
      • 3.申请新的节点
      • 4.尾插
      • 5.头插
      • 6.尾删
      • 7.头删
      • 8.查找
      • 9.指点位置之前插入
      • 10.指定位置后插入
      • 11.指定位置前删除
      • 12.指定位置后删除
      • 13.链表的销毁
    • 3.程序源码

单链表

1. 链表的概念及结构

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

在这里插入图片描述

链表的结构跟火车厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？
最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。
在链表⾥，每节“⻋厢”是什么样的呢？

在这里插入图片描述

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点”
节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：

struct SListNode
{int data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数
据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。
给定的链表结构中，如何实现节点从头到尾的打印？

在这里插入图片描述

2. 单链表的实现

1.定义结点

typedef int SLTDataType;typedef struct SListNode //s single
{SLTDataType data;struct SListNode* next;
}SLTNode;

2.打印数据

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

3.申请新的节点

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;
}

4.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向尾节点ptail->next = newnode;}
}

5.头插

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

6.尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead&&*pphead);if ((*pphead)->next == NULL)//->的优先级高于*  所以要加括号{free(*pphead);*pphead = NULL;}else{//找尾SLTNode* prev = *pphead;//要删除的前一个SLTNode* ptail = *pphead;//要删除的while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptaifree(ptail);ptail = NULL;prev->next = NULL;}
}

7.头删

void SLTPopFront(SLTNode** pphead)
{//链表不能为空assert(pphead && *pphead);SLTNode* next= (*pphead)->next;//记得加括号free(*pphead);*pphead = next;
}

8.查找

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

9.指点位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);//若*pphead为空 则pos也为空assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;//找pos前一个节点while (prev->next != pos){prev = prev->next;}//prev newnode posprev->next = newnode;newnode->next = pos;}}

10.指定位置后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;//为什么顺序不能交换pos->next = newnode;
}

11.指定位置前删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);SLTNode* prev = *pphead;//找pos前一个节点if (pos == *pphead){//头删SLTPopFront(pphead);}while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}

12.指定位置后删除

void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del->next = NULL;}

13.链表的销毁

void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = (*pphead)->next;free(pcur);pcur = next;}//pcur 为空*pphead = NULL;
}

3.程序源码

共分三个文件

SLTist.h 函数的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义节点结构
//数据+指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode //s single
{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* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

SList.c 函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf("%d->", pcur->data);pcur = pcur->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)
{assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向尾节点ptail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead&&*pphead);if ((*pphead)->next == NULL)//->的优先级高于*  所以要加括号{free(*pphead);*pphead = NULL;}else{//找尾SLTNode* prev = *pphead;//要删除的前一个SLTNode* ptail = *pphead;//要删除的while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptaifree(ptail);ptail = NULL;prev->next = 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)//pcur != NULL{if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur == NULLreturn NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);//若*pphead为空 则pos也为空assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;//找pos前一个节点while (prev->next != pos){prev = prev->next;}//prev newnode posprev->next = newnode;newnode->next = pos;}}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;//为什么顺序不能交换pos->next = newnode;
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);SLTNode* prev = *pphead;//找pos前一个节点if (pos == *pphead){//头删SLTPopFront(pphead);}while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del->next = NULL;}
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = (*pphead)->next;free(pcur);pcur = next;}//pcur 为空*pphead = NULL;
}

test.c 用来测试

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void SListTest01()
{//链表是由一个一个的节点组成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 Test02()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 5);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTNode* find = SLTFind(plist,3);/*if (find == NULL){printf("没有找到\n");}else{printf("找到了！\n");}*///SLTInsert(&plist, find,11);SLTInsertAfter(find,9);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTEraseAfter(find);SLTDestroy(&plist);SLTPrint(plist);}
int main()
{//SListTest01();Test02();return 0;
}
http://www.xdnf.cn/news/12626.html

相关文章：

  • Harmony核心：动态方法修补与.NET游戏Mod开发
  • Java实现飞机射击游戏：从设计到完整源代码
  • 【小红书拥抱开源】小红书开源大规模混合专家模型——dots.llm1
  • 使用WPF的Microsoft.Xaml.Behaviors.Wpf中通用 UI 元素事件
  • 从代码学习深度强化学习 - 初探强化学习 PyTorch版
  • 怎么解决cesium加载模型太黑，程序崩溃，不显示，位置不对模型太大，Cesium加载gltf/glb模型后变暗
  • 开心农场日记之~ 一颗向日葵的成长记录~
  • 基恩士X520 MC通信寄存器转换
  • 如何在软件著作权补正时查看已提交的程序鉴别材料和文档鉴别材料
  • 项目课题——功耗蓝牙（BLE）室内定位系统
  • python queue
  • Python｜GIF 解析与构建（5）：手搓截屏和帧率控制
  • 摆脱硬件依赖：SkyEye在轨道交通中的仿真应用
  • Python训练day40
  • 33 C 语言字符串转数值函数详解：atoi、atol、atoll、atof
  • D3.js与vue3力导向图开发全流程
  • 【机械视觉】Halcon—【八、形态学调整和生成棋盘格】
  • AI智能编码工具：阿里通义灵码使用个人版
  • 拆钢琴清理，装导电橡胶从电路板背后装好装
  • MySQL 索引优化（Explain执行计划） 详细讲解
  • 8天Python从入门到精通【itheima】-73~74（数据容器“集合”+案例练习）
  • 《前端面试题：JavaScript 变量》
  • 关于DSP数据类型长度的思考
  • openlayers实现可拖拽的节点（类似知识图谱）
  • 地震勘探——地震波速度、地震子波、合成地震记录、影响地震振幅的因素
  • 巨控GRM550系列，西门子 S7-1200 PLC 远程上下载与调试技术方案
  • SM560-S (1SAP280000R0001) AC500 CPU Firmware SM560-S-FD-4
  • python学习打卡day45
  • 深入Kubernetes源码阅读指南核心概念-代码目录-pkg/kubeapiserver
  • 信息检索与利用