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

【数据结构】双向链表专题

news 2025/7/19 0:20:44

目录

1.双向链表的结构

2.双向链表的实现

2.1初始化

以参数的形式初始化链表： 

以返回值的形式初始化链表：

2.2尾插

2.3打印

2.4头插

2.5尾删

2.6头删

2.7查找

2.8在指定位置之后插入数据​编辑

2.9删除pos节点

2.10销毁

3.整理代码

3.1 List.h

3.2 List.c

3.3 Test.c

1.双向链表的结构

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

“哨兵位”存在的意义： 遍历循环链表避免死循环。

2.双向链表的实现

不带头节点的单链表为空链表的判条件：head=NULL，因为head本来指向链表的第一个节点，如果head为NULL，说明链表没有节点，为空链表。

而带头结点的单链表为空链表的判定条件：head->next=NULL;

双向链表为空链表的判定条件：链表中只剩下一个头结点。

2.1初始化

申请节点函数

LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;//自己指向自己return node;
}

以参数的形式初始化链表： 

开始的时候创建一个空链表，LTNode* plist = NULL;我们要对空链表进行初始化，保证让链表只有一个头结点（哨兵位），为我们后续插入操作做准备。由于要改变plist的指向，所以传二级指针。

void LTInit(LTNode** pphead)
{//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);//哨兵位里面不需要有值，为了调用申请节点函数，传一个值-1好了
}

以返回值的形式初始化链表：

初始化可以不传递二级指针，以返回值的形式返回哨兵位，调用完LTInit函数后，plist指针接收其返回值：LTNode* plist = LTInit();

LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}

2.2尾插

void LTPushBack(LTNode* phead, LTDataType x)//不改变哨兵位的地址，传一级指针即可
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;//注意：这两行代码不能颠倒位置
}

2.3打印

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.4头插

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;newnode->next->prev = newnode;phead->next = newnode;//注意：这两行代码不能颠倒位置
}

2.5尾删

void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next!=phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}

2.6头删

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

2.7查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

2.8在指定位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

2.9删除pos节点

为了保持接口的一致性，这里传的是一级指针，对形参的修改不影响实参，pos置为空不影响find , find此时是野指针，所以调用完 LTERase 函数后要手动将find置为空（find=NULL;）

void LTErase(LTNode* pos)
{assert(pos);// pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;//删除pos节点free(pos);pos = NULL;
}

2.10销毁

同样为了保持接口的一致性，这里也传一级指针，对形参的修改不影响实参，phead置为空不影响实参plist，所以调用完 LTDesTroy 函数后要手动将plist置为空（plist=NULL;）

void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}

3.整理代码

3.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
//void LTInit(LTNode** pphead);//以二级指针形式初始化
LTNode* LTInit();//以返回值形式初始化
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁
void LTDesTroy(LTNode* phead);

3.2 List.c

#include"List.h"
//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;//自己指向自己return node;
}//初始化
//以返回值形式初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//以二级指针形式初始化
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}//打印
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 = LTBuyNode(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);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;newnode->next->prev = newnode;phead->next = newnode;//注意：这两行代码不能颠倒位置
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next!=phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = 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);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}//删除pos节点
void LTErase(LTNode* pos)
{	assert(pos);// pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;//删除pos节点free(pos);pos = NULL;
}//销毁
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}

3.3 Test.c

#include"List.h"
void ListTest01()
{  	//传二级指针形式初始化/*LTNode* plist = NULL;LTInit(&plist); *///以返回值形式初始化LTNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);	LTPushBack(plist, 3);LTPrint(plist);//打印//头插LTPushFront(plist,4);	LTPushFront(plist,5);			LTPrint(plist);//打印//尾删LTPopBack(plist);LTPrint(plist);//打印//头删LTPopFront(plist);LTPrint(plist);//打印//查找LTNode* find = LTFind(plist,4);//删除pos节点LTErase(find);LTPrint(plist);//打印find = NULL;//手动置空//销毁		LTDesTroy(plist);plist = NULL;//手动置空
}
int main()
{ListTest01();return 0;
}
http://www.lryc.cn/news/436977.html

相关文章：

  • 大二上学期计划安排
  • HarmonyOS开发实战（ Beta5.0）图片编辑实现马赛克效果详解
  • 【新书介绍】《JavaScript前端开发与实例教程（微课视频版）（第2版）》
  • 什么是GWAS全基因组关联分析？
  • k8s dashboard token 生成/获取
  • windows@openssh免密登陆配置@基于powershell快速配置脚本
  • 【深度学习】【图像分类】【OnnxRuntime】【Python】VggNet模型部署
  • 手写排班日历
  • SpringBoot多数据源配置
  • 影响画布微信小程序canvas及skyline和webview用户界面布局的关键流程
  • MATLAB图像处理
  • 【编程底层思考】性能监控和优化：JVM参数调优，诊断工具的使用等。JVM 调优和线上问题排查实战经验总结
  • 数据库的实施过程分析
  • 【Kubernetes】常见面试题汇总（十二）
  • 基于SpringBoot+Vue+MySQL的美术馆管理系统
  • golang面试
  • 基于＂WT2605C的智能血压计：AI对话引领个性化健康管理新时代，健康守护随时在线
  • redis高级教程
  • prfm命令初探
  • AI大模型需要学什么？怎么学？从零基础入门大模型（保姆级），从这开始出发！
  • python自述3
  • Redis常见的数据结构
  • 批量插入insert到SQLServer数据库，BigDecimal精度丢失解决办法，不动代码，从驱动层面解决
  • 随手记：uniapp小程序登录方式和小程序使用验证码登录
  • 【Hadoop|HDFS篇】DataNode概述
  • Vue2 VueRouter学习笔记
  • 3D培训大师，化工企业安全教育与应急演练的新助力
  • 斯坦福大学论文润色chat-gpt指令
  • 简单硬件在环搭建（ROS+Prescan+Carsim+simulink)
  • 【Python 数据分析学习】Pandas基础与应用（1）