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

（数据结构）链表

ds 2025/8/13 11:49:36

1.单向链表

1.1单链表的认识

#pragma once
#include<stdio.h>
//SList.h
typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;void SListPrint(SLTNode* phead);

定义一个struct SListNode类型的结构体，这个结构体的变量名是SLTNode，这个结构体（节点）有两个成员，一个用来存放SLTDateType（这里是int类型，可以根据实际需求更改）类型的数据，另一个成员是一个struct SListNode类型的指针，存放下一个节点的地址，就是指向下一个struct SListNode类型的结构体，下一个结构体也有一个指向下下个结构体的指针。

打印链表：

首先定义一个STList类型的指针cur存放头节点（链表第一个结构体）的地址，通过cur指针可以找到头节点存放的数据以及下一个节点的地址，这样就可以打印出链表的数据，最后一个节点的地址为空。

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//SList.c
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}
}

1.2尾插

在链表尾部插入一个节点：

1.首先找到要插入链表的最后一个节点，此时tail->next=NULL

2.新开辟一个节点，初始化这个节点，这个新节点的指针域指向NULL

3.令原先的最后一个节点指向这个新节点

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode* phead, SLTDateType x)
{SLTNode* tail = phead;while (tail->next != NULL){tail=tail->next;}SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;tail->next = newnode;
}

需要注意

plist的值拷贝给phead，但是phead的改变不会影响plist，他们不是同一块空间，phead出了函数之后被销毁，plist还是空指针

要改变int*，要传int**。

通俗一点来说就是，如果我有一个int类型的变量a，我想通过函数传参的方式改变a的值，因为形参是实参的临时拷贝,如果形参直接传int类型，形参相当于是内存新开一块空间拷贝实参的内容，你所定义的函数操作的实际上是操作这块新空间；

所以我们如果想改变实参，需要传实参的地址，现在形参相当于是内存新开一块空间存放实参的地址，我们在函数中对这个地址进行解引用就能找到实参；

使用实例：

//在链表的尾部插入一个新的节点
void SListPushBack(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;if (*pphead == NULL){*pphead = newnode;}else{//找到最后一个节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}        tail->next = newnode;}
}void test1()
{SLTNode* plist=NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushBack(&plist, 3);SListPushBack(&plist, 4);SListPrint(plist);
}int main()
{test1();return 0;
}

下面我再举一个例子加深一下对这个问题的理解：

情况1：这相当于把p存的地址的值传给形参，形参相当于实参的临时拷贝，会再开一块空间存形参，函数相当于把形参的值改为NULL但是不影响实参

情况2：

//情况2
void x(int* j)
{*j = NULL;
}int main()
{int* p = 0x1234;x(p);
}

而对形参j解引用就找到了这块空间，而*j=NULL相当于把j指向这块空间的值置为0

情况3：

//情况3
void x(int** j)
{*j = NULL;
}int main()
{int* p = 0x1234;x(&p);
}

地址是假设的）这次传的是p的地址，对j解引用 就可以找到p，从而改变p

1.3头插

新建一个节点，这个节点的指针指向这个链表的头节点

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{//新建一个节点SLTNode* newnode = BuySTLNode(x);//这个是新建节点的函数if (newnode == NULL){exit(-1);}newnode->next = *pphead;*pphead = newnode;        
}

1.4尾删

先看一下存在问题的写法

//尾删
void SListPopBack(SLTNode** pphead)
{SLTNode* tail = *pphead;//while(tail->next) 两种写法是等价的while (tail->next != NULL){tail = tail->next;} free(tail);tail = NULL;
}

没有把前一个节点的指针置空，造成野指针问题

除此之外，我们还要考虑如果链表为空，或者只有一个节点的情况

//尾删
void SListPopBack(SLTNode** pphead)
{assert(*pphead != NULL);//满足括号中的条件才可以继续往下执行if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;SLTNode* prev = NULL;//再定义一个指针//while(tail->next) 两种写法是等价的while (tail->next != NULL){prev = tail;//tail指向下一个节点之前，存放上一个节点的地址tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//把前一个节点的指针置空}//这样写就可以少定义一个变量/*SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;*/
}

1.6寻找节点

//寻找数据x的节点
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}elsecur = cur->next;}return NULL;
}

1.7在pos位置之前插入一个节点

//在pos位置之前插入一个节点
void SListInsert_Front(SLTNode** pphead, SLTDateType* pos, SLTDateType x)
{SLTNode* newnode = BuySTLNode(x);SLTNode* posPrev = *pphead;if (*pphead == pos)//单独分析pos是头节点的情况{newnode->next = *pphead;*pphead = newnode;}else{//找到pos的前一个位置while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;}        
}

1.8在pos位置之后插入一个节点

//在pos位置之后插入一个节点
void SListInsert_Afert(SLTNode* pos, SLTDateType x)
{SLTNode* newnode = BuySTLNode(x);newnode->next = pos->next;pos->next = newnode;}

2.双向链表

链表的结构

哨兵位的头节点不存储有效数据

1.无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

LTNode* ListInit()
{//哨兵位头节点，单单改变形参不能让plist拿到头节点，可以用二级指针，也可以返回地址LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->next = phead;phead->prev = phead;return phead;
}void ListPushBack(LTNode* phead, LTDateType x)
{assert(phead);LTNode* tail = phead->prev;//画图理解LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;tail->next = newnode; //前一个节点的尾指向新节点newnode->prev = tail; //新节点的头指向前一个节点的尾newnode->next = phead; //新节点的尾指针指向哨兵位phead->prev = newnode; //哨兵位的头指针指向新节点
}

这里指针指向的都是结构体（即节点），不是结构体的某个成员，如tail->next = newnode; 意思是前一个节点的尾指向新节点，而不是新节点的前节点指针域newnode->prev；

不改变phead，不用传二级指针

以下是双向链表的尾插，头插，尾删，头删等操作，和单向链表相差无几，重要的是学会画图分析

//List.h
typedef int LTDateType;typedef struct ListNode
{LTDateType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
//双向链表初始化
LTNode* ListInit();
//打印双向链表，从哨兵位的下一个节点开始打印，到哨兵位结束打印
void ListPrint(LTNode* phead);//尾插
void ListPushBack(LTNode* phead, LTDateType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDateType x);
//头删
void ListPopFront(LTNode* phead);
//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x);
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);
//删除pos位置
void ListErase(LTNode* pos);
void ListDestroy(LTNode* phead)；
//尾删
void ListPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailnode = tail;tail = tail->prev;phead->prev = tail;tail->next = phead;free(tailnode);
}
//头插
void ListPushFront(LTNode* phead, LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}
//头删
void ListPopFront(LTNode* phead)
{//记录头节点地址LTNode* headnode = phead->next;headnode->next->prev = phead;phead->next = headnode->next;free(headnode);
}//寻找x的节点
LTNode* ListFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}}return NULL;
}
//pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;pos->prev->next = newnode;newnode->prev = pos->prev;pos->prev = newnode;newnode->next = pos;
}
//删除pos位置
void ListErase(LTNode* pos)
{LTNode* prevnode = pos->prev;prevnode->next = pos->next;pos->next->prev = prevnode;free(pos);
}
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

有错误欢迎在评论区指出。

上一篇：

（数据结构）顺序表实现-增删查改-CSDN博客

http://www.xdnf.cn/news/17451.html

相关文章：

  • 快切装置与备自投装置的区别
  • Node.js 》》数据验证 Joi 、express-joi
  • 汽车电子：现代汽车的“神经中枢“
  • 【优选算法】多源BFS
  • 三方相机问题分析七：【datespace导致GPU异常】facebook 黑块和Instagram花图问题
  • C++程序库选择：权衡与取舍的艺术——以iostream和stdio为例
  • 借助Rclone快速从阿里云OSS迁移到AWS S3
  • 使用 C# 通过 .NET 框架开发应用程序的安装与环境配置
  • 省市县人口密度(2000-2023)
  • 嵌入式 - 数据结构：哈希表和排序与查找算法
  • 基于Jeecgboot3.8.1的flowable流程审批人为空的设置-后端部分
  • 若以微服务部署踩坑点
  • 【C#】掌握并发利器：深入理解 .NET 中的 Task.WhenAll
  • 跟着尚硅谷学vue-day7
  • 【MongoDB学习笔记2】MongoDB的索引介绍
  • 宁商平台税务新政再升级：精准施策，共筑金融投资新生态
  • 塑料可回收物检测数据集-10,000 张图片 智能垃圾分类系统 环保回收自动化 智慧城市环卫管理 企业环保合规检测 教育环保宣传 供应链包装优化
  • UE5太空射击游戏入门（一）：项目创建与飞船控制
  • 5.0.9 C# wpf通过WindowsFormsHost嵌入winform控件
  • 网络基础浅谈
  • 僵尸进程、孤儿进程、进程优先级、/proc 文件系统、CRC 与网络溢出问题处理（实战 + 原理）
  • Docker搭建Jenkins实现自动部署：快速高效的持续集成之道！
  • 进程管理、系统高负载、cpu超过800%等实战问题处理
  • Android 中解决 Button 按钮背景色设置无效的问题
  • Numpy科学计算与数据分析：Numpy广播机制入门与实践
  • conda pip uv与pixi
  • react的form.resetFields()
  • 论文阅读：User Behavior Simulation with Large Language Model-based Agents
  • 五十五、【Linux系统nginx服务】nginx安装、用户认证、https实现
  • MySQL 配置性能优化赛：核心策略与实战技巧