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

带头双向循环链表的实现

1.结构体的创建以及类型重定义

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

2.链表的初始化

这个函数用于创建节点,后面还会用到。

LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

链表的初始化

LTNode* ListInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

3.链表的头插以及尾插

头插

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->next = next;next->prev = newnode;newnode->prev = phead;
}

尾插

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->next = phead;phead->prev = newnode;newnode->prev = tail;
}

4.链表的打印

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

5.链表的头删以及尾删

头删

void ListPopFront(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));LTNode* front = phead->next;LTNode* frontNext = phead->next->next;free(front);phead->next = frontNext;frontNext->prev = phead;
}

尾删

void ListPopBack(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = phead->prev->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}

注意:链表只剩下一个头的时候就不可以再删除了,所以需要多加

assert(ListEmpty(phead));

进行断言判断。

ListEmpty函数如下:

bool ListEmpty(LTNode* phead)
{assert(phead);return phead->next != phead;
}

6.在pos位置之前插入

void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyListNode(x);prev->next = newnode;newnode->next = pos;pos->prev = newnode;newnode->prev = prev;
}

7.删除pos位置的节点

void ListErase(LTNode* pos)
{assert(pos);LTNode* next = pos->next;LTNode* prev = pos->prev;free(pos);prev->next = next;next->prev = prev;
}

8.头插尾插的简化以及头删尾删的简化

由于链表的头节点以及尾节点都可以归类为pos任意位置的节点,所以可以利用6和7的函数来进行简化,如下:

头插

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

尾插

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}

头删

void ListPopFront(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));ListErase(phead->next);
}

尾删

void ListPopBack(LTNode* phead)
{assert(phead);assert(ListEmpty(phead));ListErase(phead->prev);
}

9.链表节点的数量计算

LTDataType ListSize(LTNode* phead)
{assert(phead);LTDataType size = 0;LTNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}

这个链表节点计数量计算的时间复杂度为O(N),如果要实现O(1)的时间复杂度(与链表节点的插入和删除的时间复杂度保持一致)的话,那么可以这么写:

struct List()
{LTNode* phead;int size;
}

这样新定义了一个结构体后,前面的函数都要改一改了,所以可以直接写一个函数来计算链表的节点数量。

注意:不要用头节点来存储链表的节点数量,因为如果链表的节点数据类型不是int而是char的话,那么最高只能存储到127这个数了, 链表的长度可能要远远大于这个数。

10.链表的销毁

void ListDestroy(LTNode* phead)
{assert(phead);while (phead->next != phead){ListErase(phead->next);}free(phead);
}

顺序表与链表的比较:

顺序表的优点:通过下标可以随机访问任意一个数据,cpu高速缓存命中率高

顺序表的缺点:头部或者中间插入数据效率低下,扩容后可能存在一定的空间浪费


链表的优点:数据的插入和删除时间复杂度为O(1), 按需申请释放

链表的缺点:不能通过下标来进行访问,查询任意数据时时间复杂度为O(N)。

相关文章:

带头双向循环链表的实现

1.结构体的创建以及类型重定义 typedef int LTDataType; typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next; }LTNode;2.链表的初始化 这个函数用于创建节点,后面还会用到。 LTNode* BuyListNode(LTDataType x) {LTNode* n…...

大屏使用dv-digital-flop定时刷新显示总人数

本文在基础上进行改进,后端使用若依后端IofTV-Screen: 🔥一个基于 vue、datav、Echart 框架的物联网可视化(大屏展示)模板,提供数据动态刷新渲染、屏幕适应、数据滚动配置,内部图表自由替换、Mixins注入等功…...

Java面向对象部分 个人学习记录

注:此博客是个人学习记录,会有错的地方,面向对象部分我可能会画很多图来加深我的理解 不引出了,直接开始 class Dog{String name;int age;String type;public Dog(String name,int age,String type){this.namename;this.ageage;this.typetyp…...

MySQL数据库——对Linux MySQL软件包的一些说明

Linux 操作系统的发行版很多,不同发行版下的 MySQL 版本也是不同的。MySQL 主要支持的 Linux 版本有 Red Hat Enterprise Linux 和 SUSE Linux Enterprise Server。这里主要介绍不同 Linux 发行版下 MySQL 支持的版本。 Linux 操作系统的 MySQL 软件包一般分为以下…...

【JavaEE进阶】——第二节.Spring核心和设计思想

文章目录 前言 一、Spring是什么? 二、什么是容器? 三、什么是IoC? 3.1 初始loC 3.2 举例解释loC 3.3 Spring IoC思想的体现 四、什么是DI? 4.1DI的概念 4.2 Ioc和DI的区别 总结 前言 今天我们将进入到有关spring的认识当中&…...

twitter开源算法(1)For You推荐系统架构

1 Twitter’s Recommendation Algorithm 我们的推荐系统由许多互相关联的服务(services)和工作(jobs)组成,本节这要是聚焦home timeline的for you feed流。 the-algorithm开源地址:https://github.com/twitter/the-algorithm 本篇博客来源&…...

A General Framework for Uncertainty Estimation in Deep Learning源码阅读(二)

接上文 ResNet定义: 代码使用 def ResNet18ADF(noise_variance1e-3, min_variance1e-3):return ResNet(BasicBlock, [2,2,2,2], num_classes10, noise_variance1e-3, min_variance1e-3, initialize_msraFalse)定义模型,其中ResNet定义为: …...

串行通信协议---HART协议

实际应用中,HART协议是仅次于Modbus协议的最接近统一现场总线的标准,主要是在4~20mA电流信号上面叠加数字信号,物理层采用Bell 202标准的FSK技术成功实现模拟信号和数字信号双向同时通信而互不干扰。HART协议规定了传输的物理形式、消息结构、…...

【独家】华为OD机试 - 寻找密码(C 语言解题)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本期题目:寻找密码 题目 小王在进行游…...

FPGA有哪些优质的带源码的IP开源网站?

这是某乎上的一个问题,我觉得还不错,今天就系统性的总结一下1、fpga4funhttps://www.fpga4fun.com/你能在这个网站上找到什么?您可以找到信息页面,以及使用 FPGA 板构建的 FPGA 项目。注重点:项目。FPGA 项目使用一种称…...

基于模型预测控制(MPC)的微电网调度优化的研究(Matlab代码实现)

💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

Postman接口测试之Mock快速入门

一、Mock简介 1.Mock定义 Mock是一种比较特殊的测试技巧,可以在没有依赖项的情况下进行接口或单元测试。通常情况下,Mock与其他方法的区别是,用于模拟代码依赖对象,并允许设置对应的期望值。简单一点来讲,就是Mock创建…...

分享一个国内可用的免费ChatGPT网站

背景 ChatGPT作为一种基于人工智能技术的自然语言处理工具,近期的热度直接沸腾🌋。 作为一个程序员,我也忍不住做了一个基于ChatGPT的网站,免费!免登陆!!国内可直接对话ChatGPT,也…...

15. 三数之和(Java)

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例 …...

Navicat Premium 16安装教程

1.鼠标右击【Navicat Premium 16(64bit)】压缩包(win11及以上系统需先选择“显示更多选项”)选择【解压到 Navicat Premium 16(64bit)】。 2.打开解压后的文件夹,鼠标右击【setup】选择【以管理员身份运行】。 3.点击【下一步】。 4.选择【我…...

蓝桥杯刷题冲刺 | 倒计时8天

作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 文章目录1.三角形的面积2.图中点的层次1.三角形的面积 题目 链接: 三角形的面积 - 蓝桥云课 …...

四.JAVA基础面试题:重要知识

四.JAVA基础面试题:重要知识 1.为什么JAVA只有值传递 2.JAVA获取运行时类的四种方式 四.JAVA基础面试题:重要知识 1.为什么JAVA只有值传递 实参:传递给形参的实际参数。 形参:接受实参的参数。值传递:方法接受实参…...

某面试官分享经验:看求职者第一眼,开口说第一句话,面试结果就差不多定了,准确率高达90%以上...

我们以前分享过许多经验,但大多是站在打工人的视角上,今天给大家带来一个面试官的经验:1. 看求职者第一眼,开口说第一句话,面试结果就差不多定了,准确率高达90%以上。2. 绝不考八股文,如果问技术…...

Java开发 - 消息队列之RabbitMQ初体验

目录 前言 RabbitMQ 什么是RabbitMQ RabbitMQ特点 安装启动 RabbitMQ和Kafka的消息收发区别 RabbitMQ使用案例 添加依赖 添加配置 创建RabbitMQ配置类 RabbitMQ消息的发送 RabbitMQ消息的接收 测试 结语 前言 前一篇,我们学习了Kafka的基本使用&#…...

蓝桥杯入职项目(HTML + springBoot)

文章目录需要解决npm包安装axioshttp-servedebug开发下个阶段测试运行方式注意清理磁盘缓存问题解决HTML Web项目的结构通常是基于MVC(Model-View-Controller)模式设计的。下面是一般的项目结构:index.html:项目的入口文件&#x…...

【IAR工程】STM8S208RB基于ST标准库下按键检测

【IAR工程】STM8S208RB基于ST标准库下按键检测📍相关篇《【IAR工程】STM8S208RB基于ST标准库下GPIO点灯示例》🎈《【IAR工程】STM8S208RB基于ST标准库下EXTI外部中断》🔖基于ST STM8S/A标准外设库:STSW-STM8069,版本号:2.3.1&…...

【5】深度学习之Pytorch——如何使用张量处理文本数据集(语料库数据集)

在计算机领域,不断崛起的两个领域,一个是CV一个是NLP,下面我们可以探索一下深度学习在NLP的应用和特点。 深度学习在自然语言处理(NLP)领域有广泛的应用。以下是一些主要的应用和特点: 语音识别&#xff1…...

《Spring系列》第5章 refresh()

前言 Spring框架中最重要的肯定是IOC容器,那么其如何进行初始化,就是通过refresh()这个方法,无论是单独使用Spring框架,还是SpringBoot,最终都会通过执行到这个方法,那么下面会介绍一下这个方法 一、IOC容…...

ThreeJS-缩放、旋转(四)

代码&#xff1a; <template> <div id"three_div"> </div> </template> <script> import * as THREE from "three"; import {OrbitControls } from three/examples/jsm/controls/OrbitControls export default { name: &quo…...

数据更新 | CnOpenData法拍房数据

法拍房数据 一、数据简介 法拍房&#xff0c;即“法院拍卖房产”&#xff0c;是被法院强制执行拍卖的房屋 。当债务人&#xff08;业主&#xff09;无力履行借款合约或无法清偿债务时&#xff0c;而被债权人经司法程序向法院申请强制执行&#xff0c;将债务人名下房屋拍卖&…...

【Spring从成神到升仙系列 五】从根上剖析 Spring 循环依赖

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小黄&#xff0c;独角兽企业的Java开发工程师&#xff0c;CSDN博客专家&#xff0c;阿里云专家博主&#x1f4d5;系列专栏&#xff1a;Java设计模式、数据结构和算法、Kafka从入门到成神、Kafka从成神到升仙…...

设计模式之代理模式(C++)

作者&#xff1a;翟天保Steven 版权声明&#xff1a;著作权归作者所有&#xff0c;商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处 一、代理模式是什么&#xff1f; 代理模式是一种结构型的软件设计模式&#xff0c;在不改变原代码前提下&#xff0c;提供一个代理…...

c++11 标准模板(STL)(std::unordered_multimap)(三)

定义于头文件 <unordered_map> template< class Key, class T, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator< std::pair<const Key, T> > > class unordered…...

Linux进程控制-2

紧接着上篇博客出发&#xff0c;我们接着来讲述Linux中进程控制的内容。 目录 1.等待 1.1具体操作 1.等待 进程等待主要的作用在于&#xff1a;父进程创建子进程之后&#xff0c;等待子进程退出&#xff0c;获取子进程的退出码&#xff0c;释放子进程的资源&#xff0c;避…...

快速排序算法

一&#xff1a;快速排序思想 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数&#xff08;不要被这个名词吓到了&#xff0c;就是一个用来参照的数&#xff0c;待会你就知道它用来做啥的了&#xff09;。为了方便&#xff…...