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

【数据结构】双向链表的接口实现(附图解和源码)

双向链表的接口实现(附图解和源码)


文章目录

  • 双向链表的接口实现(附图解和源码)
  • 前言
  • 一、定义结构体
  • 二、接口实现(附图解+源码)
    • 1.初始化双向链表
    • 2.开辟新空间
    • 3.尾插数据
    • 4.尾删数据
    • 5.打印双向链表中数据
    • 6.头插数据
    • 7.头删数据
    • 8.查找结点位置
    • 9.在pos位置之前插入
    • 10.删除pos位置
    • 11.销毁双向链表
  • 三、源代码展示
    • 1.test.c(测试+主函数)
    • 2.List.h(接口函数的声明)
    • 3.List.c(接口函数的实现)
  • 总结


前言

本文主要介绍双向链表中增删查改等接口实现,结尾附总源码


一、定义结构体

在这里插入图片描述

代码如下(示例):

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;

二、接口实现(附图解+源码)

在这里插入图片描述

这里一共10个接口,我会我都会一 一为大家讲解(图解+源码


1.初始化双向链表

初始化出一个哨兵位的头结点(用malloc开辟),next和prev都指向自己。具体如下图!
在这里插入图片描述
在这里插入图片描述

代码如下(示例):

ListNode* ListInit()
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* phead = p;phead->next = phead;phead->prev = phead;return phead;
}

2.开辟新空间

(1)开辟一个链表类型的动态空间,将地址给newnode;
(2)将值放入 newnode 的 data 数据内;
(3)将 newnode 的 next 和 prev 都置为NULL;
注意:1.将malloc开辟空间存到 newnode 里面时,参数为结构体所占的字节大小!2.对 newnode 进行 NULL 判断!

代码如下(示例):

ListNode* BuyListNode(LTDataType x)
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* newNode = p;newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}

3.尾插数据

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListPushBack(ListNode* phead, LTDataType x)//尾插数据
{ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//第一个链接tail->next = newnode;newnode->prev = tail;//第二个链接phead->prev = newnode;newnode->next = phead;
}

4.尾删数据

这里需要两次进行断言:
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListPopBack(ListNode* phead)//尾删
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;free(tail);//连接tailprev->next = phead;phead->prev = tailprev;
}

5.打印双向链表中数据

在这里插入图片描述


代码如下(示例):

void ListPrint(ListNode* phead)//打印数据
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

6.头插数据

头插数据也是很简单的一个接口,链接两次即可,如下图
在这里插入图片描述


代码如下(示例):

void ListPushFront(ListNode* phead, LTDataType x)//头插
{assert(phead);ListNode* newNode = BuyListNode(x);ListNode* next = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = next;next->prev = newNode;
}

7.头删数据

在头删数据时和尾删数据一样都需要进行两次断言如下图!
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListPopFront(ListNode* phead)//头删
{assert(phead);assert(phead->next != phead);ListNode* next = phead->next;ListNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);
}

8.查找结点位置

这个比较简单,和单链表一样,直接用cur遍历即可,直接上代码

代码如下(示例):

ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

9.在pos位置之前插入

在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListInsert(ListNode* pos, LTDataType x)//pos位置之前插入
{assert(pos);ListNode* newNode = BuyListNode(x);ListNode* posPrev = pos->prev;// posPrev  newnode posposPrev->next = newNode;newNode->prev = posPrev;newNode->next = pos;pos->prev = newNode;
}

根据ListInsert接口我们可以把头插和尾插进行改版,如下图!
在这里插入图片描述


在这里插入图片描述


10.删除pos位置

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListErase(ListNode* pos)//删除pos位置
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}

11.销毁双向链表

在这里插入图片描述


在这里插入图片描述


代码如下(示例):

void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

三、源代码展示

1.test.c(测试+主函数)

代码如下(示例):

#include "list.h"
void Testlist1()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插//ListPushBack(n1, 3);//尾插//ListPushBack(n1, 4);//尾插//ListPushBack(n1, 5);//尾插//ListPopFront(n1);//头删//ListPopBack(n1);//尾删//ListPushFront(n1, 0);//头插ListPrint(n1);
}
void Testlist2()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插ListPushBack(n1, 3);//尾插ListPushBack(n1, 4);//尾插ListPushBack(n1, 5);//尾插ListNode* p = ListFind(n1, 5);printf("%d \n", p->data);
}
void Testlist3()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插ListPushBack(n1, 3);//尾插ListPushBack(n1, 4);//尾插ListPushBack(n1, 5);//尾插//ListNode* p = ListFind(n1, 5);//ListInsert(p, 0);ListDestory(n1);ListPrint(n1);
}
int main()
{//Testlist1();//Testlist2();Testlist3();return 0;
}

2.List.h(接口函数的声明)

代码如下(示例):

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;
ListNode* ListInit();//初始化双向链表
void ListPushBack(ListNode* phead, LTDataType x);//尾插
void ListPopBack(ListNode* phead);//尾删
void ListPushFront(ListNode* phead, LTDataType x);//头插
void ListPopFront(ListNode* phead);//头删
void ListPrint(ListNode* phead);//打印
ListNode* ListFind(ListNode* phead, LTDataType x);//查找数据
void ListInsert(ListNode* pos, LTDataType x);//pos位置之前插入
void ListErase(ListNode* pos);//删除pos位置
void ListDestory(ListNode* phead);//销毁双向链表

3.List.c(接口函数的实现)

代码如下(示例):

#include "list.h"
ListNode* ListInit()
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* phead = p;phead->next = phead;phead->prev = phead;return phead;
}
ListNode* BuyListNode(LTDataType x)
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* newNode = p;newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}
void ListPushBack(ListNode* phead, LTDataType x)//尾插数据
{ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//第一个链接tail->next = newnode;newnode->prev = tail;//第二个链接phead->prev = newnode;newnode->next = phead;//ListInsert(phead, x);
}
void ListPrint(ListNode* phead)//打印数据
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
void ListPopBack(ListNode* phead)//尾删
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;free(tail);//连接tailprev->next = phead;phead->prev = tailprev;
}
void ListPushFront(ListNode* phead, LTDataType x)//头插
{assert(phead);ListNode* newNode = BuyListNode(x);ListNode* next = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = next;next->prev = newNode;//ListInsert(phead->next, x);
}
void ListPopFront(ListNode* phead)//头删
{assert(phead);assert(phead->next != phead);ListNode* next = phead->next;ListNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)//pos位置之前插入
{assert(pos);ListNode* newNode = BuyListNode(x);ListNode* posPrev = pos->prev;// posPrev  newnode posposPrev->next = newNode;newNode->prev = posPrev;newNode->next = pos;pos->prev = newNode;
}
void ListErase(ListNode* pos)//删除pos位置
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

总结

以上就是今天要讲的内容,本文介绍双向链表的接口实现(附图解和源码)。
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
在这里插入图片描述

相关文章:

【数据结构】双向链表的接口实现(附图解和源码)

双向链表的接口实现&#xff08;附图解和源码&#xff09; 文章目录双向链表的接口实现&#xff08;附图解和源码&#xff09;前言一、定义结构体二、接口实现&#xff08;附图解源码&#xff09;1.初始化双向链表2.开辟新空间3.尾插数据4.尾删数据5.打印双向链表中数据6.头插数…...

数据结构与算法之[把数字翻译成字符串]动态规划

前言&#xff1a;最近在刷动态规划的算法题目&#xff0c;感觉这一类题目还是有一点难度的&#xff0c;但是不放弃也还是能学好的&#xff0c;今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串]&#xff0c;这是一道经典的面试题目&#xff0c;快手&#xff0c;字节跳…...

java 面向对象三大特性之多态 万字详解(超详细)

目录 前言 : 一、为什么需要多态 : 1.白璧微瑕 : 2.举栗&#xff08;请甘雨,刻晴,钟离吃饭&#xff09;: 3.代码 : 4.问题 : 二、什么是多态 : 1.定义 : 2.多态的实现步骤&#xff08;重要&#xff09; : 三、多态的使用 : 1.多态中成员方法的使用&#xff08;重要…...

git push origin master 情况

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3;哈喽&#xff01;大家好&#xff0c;我是「奇点」&#xff0c;江湖人称 singularity。刚工作几年&#xff0c;想和大家一同进步&#x1f91d;&#x1f91d;一位上进心十足的【Java ToB端大厂领…...

ElasticSearch查询优化routing

如果一个索引分片多达一百,再加上每个分片数据量大的情况下ES查询速度会慢,这种情况可以根据业务情况考虑使用_routing优化。 _routing 路由 当索引一个文档的时候,文档会被存储在一个主分片上。在存储时一般都会有多个主分片。Elasticsearch 如何知道一个文档应该放置在哪…...

【HashMap 1.7和1.8】

Java中的HashMap是一种常用的数据结构&#xff0c;用于存储键值对。在Java 1.7和1.8中&#xff0c;HashMap的实现有一些不同。 Java 1.7中的HashMap实现是基于“拉链法”的哈希表。每个哈希桶(bucket)是一个链表&#xff0c;存储了散列值相同的键值对。当键值对数量过多时&…...

【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法

【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法 一、问题展现1.查看Zabbix仪表盘2.问题分析二、检查Zabbix环境1.检查Zabbix监控主机2.检查Zabbix各组件状态三、在宿主机安装中文字体库1.安装中文字体2.查看字体文件四、安装中文字库1.查看Zabbix所有组件容器2.拷贝…...

学习(mianshi)必备-ClickHouse高性能查询/写入和常见注意事项(五)

目录 一、ClickHouse高性能查询原因-稀疏索引 二、ClickHouse高性能写入-LSM-Tree存储结构 什么是LSM-Tree 三、ClickHouse的常见注意事项和异常问题排查 一、ClickHouse高性能查询原因-稀疏索引 密集索引: 在密集索引中&#xff0c;数据库中的每个键值都有一个索引记录&…...

在Kotlin中探索 Activity Results API 极简的解决方案

Activity Results APIActivity Result API提供了用于注册结果、启动结果以及在系统分派结果后对其进行处理的组件。—Google官方文档https://developer.android.google.cn/training/basics/intents/result?hlzh-cn一句话解释&#xff1a;官方Jetpack组件用于代替startActivity…...

样式冲突太多,记一次前端CSS升级

目前平台前端使用的是原生CSSBEM命名&#xff0c;在多人协作的模式下&#xff0c;容易出现样式冲突。为了减少这一类的问题&#xff0c;提升研效&#xff0c;我调研了业界上主流的7种CSS解决方案&#xff0c;并将最终升级方案落地到了工程中。 样式冲突的原因 目前遇到的样式…...

如何解决报考PMP的那些问题?

关于PMP的报考条件&#xff0c;报考PMP都需要什么条件呢&#xff1f;【学历条件】&#xff1a;需要满足23周岁/高中毕业5年以上/大专以上学历&#xff0c;三个满足一个即可&#xff1b;【PDU条件】&#xff1a;报考PMP需要PDU证明&#xff08;学习项目管理课程的学时证明&#…...

数据结构栈的经典OJ题【leetcode最小栈问题大剖析】【leetcode有效的括号问题大剖析】

目录 0.前言 1.最小栈 1.1 原题展示 1.2 思路分析 1.2.1 场景引入 1.2.2 思路 1.3 代码实现 1.3.1 最小栈的删除 1.3.2 最小栈的插入 1.3.3 获取栈顶元素 1.3.4 获取当前栈的最小值 2. 有效的括号 0.前言 本篇博客已经把两个关于栈的OJ题分块&#xff0c;可以根据目…...

数据结构与算法之打家劫舍(一)动态规划思想

动态规划里面一部题目打家劫舍是一类经典的算法题目之一&#xff0c;他有各种各样的变式&#xff0c;这一篇文章和大家分享一下打家劫舍最基础的一道题目&#xff0c;掌握这一道题目&#xff0c;为下一道题目打下基础。我们直接进入正题。一.题目大家如果刚接触这样的题目&…...

无人驾驶路径规划论文简要

A Review of Motion Planning Techniques for Automated Vehicles综述和分类0Motion Planning for Autonomous Driving with a Conformal Spatiotemporal Lattice从unstructured环境向structured环境的拓展&#xff0c;同时还从state lattice拓展到了spatiotemporal lattice从而…...

C++ sort()函数和priority_queue容器中比较函数的区别

普通的queue是一种先进先出的数据结构&#xff0c;元素在队列尾追加&#xff0c;而从队列头删除。priority_queue中元素被赋予优先级。在创建的时候根据优先级进行了按照从大到小或者从小到大进行了自动排列&#xff08;大顶堆or小顶堆&#xff09;。可以以O(log n) 的效率查找…...

STM32开发(14)----CubeMX配置ADC

CubeMX配置ADC前言一、什么是ADC&#xff1f;二、实验过程1.单通道ADC采集STM32CubeMX配置代码实现2.多通道ADC采样(非DMA)STM32CubeMX配置代码实现3.多通道ADC采样&#xff08;DMA&#xff09;STM32CubeMX配置代码实现总结前言 本章介绍使用STM32CubeMX对ADC进行配置的方法&a…...

Simple RNN、LSTM、GRU序列模型原理

一。循环神经网络RNN 用于处理序列数据的神经网络就叫循环神经网络。序列数据说直白点就是随时间变化的数据&#xff0c;循环神经网络它能够根据这种数据推出下文结果。RNN是通过嵌含前一时刻的状态信息实行训练的。 RNN神经网络有3个变种&#xff0c;分别为Simple RNN、LSTM、…...

【原创】java+swing+mysql生肖星座查询系统设计与实现

今天我们来开发一个比较有趣的系统&#xff0c;根据生日查询生肖星座&#xff0c;输入生日&#xff0c;系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析&#xff1a; 生肖星座查询系统&#xff0c;顾名思义…...

CentOS 环境 OpneSIPS 3.1 版本安装及使用

文章目录1. OpenSIPS 源码下载2. 工具准备3. 编译安装4. opensips-cli 工具安装5. 启动 OpenSIPS 实例1. OpenSIPS 源码下载 使用以下命令即可下载 OpenSIPS 的源码&#xff0c;笔者下载的是比较稳定的 3.1 版本&#xff0c;读者有兴趣也可前往 官方传送门 sudo git clone htt…...

SQL95 从 Products 表中检索所有的产品名称以及对应的销售总数

描述 Products 表中检索所有的产品名称&#xff1a;prod_name、产品id&#xff1a;prod_idprod_idprod_namea0001egga0002socketsa0013coffeea0003colaOrderItems代表订单商品表&#xff0c;订单产品&#xff1a;prod_id、售出数量&#xff1a;quantityprod_idquantitya0001105…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...