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

【（数据结构）— 双向链表的实现】

news 2025/7/28 21:30:26

（数据结构）— 双向链表的实现

  • 一.双向链表的结构
  • 二. 双向链表的实现
    • 2.1 头文件 ——双向链表的创建及功能函数的定义
    • 2.2 源文件 ——双向链表的功能函数的实现
    • 2.3 源文件 ——双向链表功能的测试
    • 2.4 双向链表各项功能测试运行展示
      • 2.4.1 双向链表的初始化 ——（以调试窗口展示）
      • 2.4.2 双向链表的尾插 ——（以打印展示）
      • 2.4.3 双向链表的头插 ——（以打印展示）
      • 2.4.4 双向链表的尾删 ——（以打印展示）
      • 2.4.5 双向链表的头删 ——（以打印展示）
      • 2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——（以打印展示）
      • 2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——（以打印展示）
      • 2.4.8 双向链表的销毁 ——（以调试窗口展示）
  • 三.顺序表和双向链表的优缺点分析

一.双向链表的结构

在这里插入图片描述

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨
的”
“哨兵位”存在的意义：
遍历循环链表避免死循环。

二. 双向链表的实现

2.1 头文件 ——双向链表的创建及功能函数的定义

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDatatype;
//链表的结构创建
typedef struct ListNode
{LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;
//打印
void LTPrint(LTNode* phead);//双链表的初始化//销毁
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁
//void LTDestroy(LTNode** pphead);
void LTDestroy(LTNode* phead);
//头部/尾部/插入/删除
//尾插
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//再pos位置之后插入/删除 
void LTInsrt(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos);
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x);

2.2 源文件 ——双向链表的功能函数的实现

List.c

#include"List.h"//初始化
//二级指针初始化
//前提是我们需要传入一个头节点
//void LTInit(LTNode** pphead)
//{
//	*pphead = (LTNode*)malloc(sizeof(LTNode));
//	if (*pphead == NULL)
//	{
//		perror("malloc error");
//		return;
//	}
//	(*pphead)->data = -1;//哨兵位
//	(*pphead)->next = (*pphead)->prev = *pphead;
//	
//}
//一级指针初始化
//不需要传参，只需要返回一个地址即可
LTNode* LTInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc error");return;}phead->data = -1;phead->next = phead->prev = phead;return phead;
}
//链表的销毁
//参数是二级指针
//void LTDestroy(LTNode** pphead)
//{
//	assert(pphead && *pphead);
//	LTNode* cur = (*pphead)->next;
//	while(cur!=(*pphead))
//	{
//		LTNode* next = cur->next;
//		free(cur);
//		cur = next;
//	}
//	free(*pphead);
//	*pphead = NULL;
//}
//参数是一级指针
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");}
LTNode* LTBuyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));node->data = x;node->next = node->prev = NULL;return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{LTNode* node = LTBuyNode(x);//先处理插入的节点的前驱和后继指针node->next = phead;node->prev = phead->prev;//然后考虑哨兵位的前驱和尾节点的后继指针phead->prev->next = node;phead->prev = node;}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* node = LTBuyNode(x);//先处理插入节点的前驱和后继的指针node->next = phead->next;node->prev = phead;//然后处理phead,phead->nextphead->next->prev = node;phead->next = node;}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//链表不能为空，链表中只有一个哨兵位节点assert(phead->next != phead);LTNode* del = phead->prev;//先处理 del->prevdel->prev->next = phead;//接着处理pheadphead->prev = del->prev;free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//先处理del->nextdel->next->prev = phead;//接着处理pheadphead->next = del->next;free(del);del = NULL;
}
//在pos位置之后插入
void LTInsrt(LTNode* pos, LTDatatype x)
{LTNode* node = LTBuyNode(x);//先处理node的前驱和后继node->next = pos->next;node->prev = pos;//接着处理pos->next,pos->next->prevpos->next = node;pos->next->prev = node;
}
//删除pos位置的数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//查找pos
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.3 源文件 ——双向链表功能的测试

test.c

#include"List.h"void ListTest()
{/*LTNode* plist = NULL;LTInit(&plist);*///初始化LTNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//头插/*LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);*///尾删/*LTPopBack(plist);LTPopBack(plist);*///头删/*LTPopFront(plist);LTPopFront(plist);*/LTNode* find = LTFind(plist, 4);//在pos位置之后插入/*LTInsrt(find, 5);*///删除pos位置的数据LTErase(find);LTPrint(plist);//销毁链表//LTDestroy(&plist);//一级指针销毁需要手动将plist置空LTDestroy(plist);plist = NULL;}int main()
{ListTest();return 0;
}

2.4 双向链表各项功能测试运行展示

2.4.1 双向链表的初始化 ——（以调试窗口展示）

//初始化
LTNode* plist = LTInit();

在这里插入图片描述

2.4.2 双向链表的尾插 ——（以打印展示）

//尾插
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);

在这里插入图片描述

2.4.3 双向链表的头插 ——（以打印展示）

//头插
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);

在这里插入图片描述

2.4.4 双向链表的尾删 ——（以打印展示）

//尾删
LTPopBack(plist);
LTPopBack(plist);

在这里插入图片描述

2.4.5 双向链表的头删 ——（以打印展示）

//头删
LTPopFront(plist);
LTPopFront(plist);

在这里插入图片描述

2.4.6 双向链表的查找指定位置及在指定位置之后插入 ——（以打印展示）

//查找指定位置pos
LTNode* find = LTFind(plist, 4);
//在pos位置之后插入
LTInsrt(find, 5);

在这里插入图片描述

2.4.7 双向链表的查找指定位置及删除指定位置的数据 ——（以打印展示）

// //查找指定位置pos
LTNode* find = LTFind(plist, 4);
//删除pos位置的数据
LTErase(find);

在这里插入图片描述

2.4.8 双向链表的销毁 ——（以调试窗口展示）

//销毁链表
//LTDestroy(&plist);
//一级指针销毁需要手动将plist置空
LTDestroy(plist);
plist = NULL;

在这里插入图片描述

三.顺序表和双向链表的优缺点分析

在这里插入图片描述

http://www.lryc.cn/news/199650.html

相关文章：

  • 酷克数据发布HD-SQL-LLaMA模型，开启数据分析“人人可及”新时代
  • FL Studio21最新中文破解进阶高级完整版安装下载教程
  • MDN--Web性能
  • Vue3.js：自定义组件 v-model
  • AI虚拟主播开发实战(附源码)
  • innoDB如何解决幻读
  • Git - 导出(archive)、忽略(gitignore)、隐藏(Stash)、合并冲突(merge)的解决方法
  • 【Javascript】‘var‘ is used instead of ‘let‘ or ‘const‘
  • 金融统计学方法：神经网络
  • 任何人不知道这款超实用的配音软件，我都会伤心的OK？
  • Linux查看日志文件的常用命令
  • AcWing算法分享系列——二分图
  • 【Excel单元格类型的解析校验】Java使用POI解析excel数据
  • 【运维知识高级篇】超详细的Jenkins教程5（pipeline流水线配置+分布式构建）
  • 为什么要在电影院装监控？有什么作用？
  • 攻防世界题目练习——Web引导模式（三）（持续更新）
  • Python制作PDF转Word工具(Tkinter+pdf2docx)
  • 有哪些手段可以优化 CSS, 提高性能
  • ARM可用的可信固件项目简介
  • 信创办公–基于WPS的Word最佳实践系列 （图文环绕方式）
  • Naive UI数据表格分页pageCount配置没效果
  • Kibana Discover数据查询
  • 笔记 | 编程经验谈：如何正确的使用内存
  • C语言入门-1.1 C语言概述
  • 周记之学习总结
  • 程序设计：C++ 一个可以放入共享内存的string模板
  • 【EI会议征稿】第三届应用力学与先进材料国际学术会议（ICAMAM 2024）
  • Python -- I/O编程
  • langchain入门指南和实战
  • 群晖synology DSM 7.2设置钉钉Webhooks通知