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

数据结构双向链表和循环链表

目录

  • 一、循环链表
  • 二、双向链表
  • 三、循环双向链表

一、循环链表

循环链表就是首尾相接的的链表,就是尾节点的指针域指向头节点使整个链表形成一个循环,这就弥补了以前单链表无法在后面某个节点找到前面的节点,可以从任意一个节点找到目标节点,但是现在我们就不能像以前那样停止循环时的判断条件是否为NULL了,而是判断是否指向头指针
在这里插入图片描述
在这里插入图片描述
由于我们的操作经常是在链表的首位进行操作,所以我们引进尾指针的概念,这样以后就可以直接找到操作尾节点
在这里插入图片描述
下面是循环单链表的相关代码:

typedef struct
{int data;Lnode* next;
}*CirList,Lnode;//初始化一个循环单链表
bool init_list(CirList& l)
{l = new Lnode;//开辟空间作为头节点if (l == NULL)return false;l->next = l;//头指针的指针域指向自己return true;
}//判断循环单链表是否为空表
bool isEmpty(CirList& l)
{if (l->next == l)return true;return false;
}

二、双向链表

由于单链表无法逆向检索,循环链表逆向寻找元素时间复杂度也是O(n),所以这里提出双向链表的概念,就是给每个元素一个前驱指针,这样我们就可以直接逆向检索上一个元素了,而且时间复杂度为O(1);双向链表的空表里面两个指针装的都是空指针
在这里插入图片描述

#include<iostream>
using namespace std;
typedef struct Lnode
{int data;Lnode* next,*prior;
}*DoubList,Lnode;//初始化一个双向链表
bool init_list(DoubList& l)
{l = new Lnode;if (l == NULL)return false;l->next = NULL;l->prior = NULL;return true;
}//双向链表建立(前插法)
bool insert_list(DoubList& l)
{init_list(l);int x;while (cin >> x && x != 0){Lnode* p = new Lnode{x,l->next,l};if (p == NULL)return false;if (l->next)l->next->prior = p;l->next = p;}return true;
}//双链表建立(后插法)
bool insert_tail_list(DoubList& l)
{init_list(l);int x;Lnode* r =l;while (cin >> x && x != 0){Lnode* p = new Lnode{ x,NULL,r };if (p == NULL)return false;r->next = p;r = p;}return true;
}//按位插入:在i位插入元素e
bool insertElem(DoubList& l, int i, int e)
{if (i < 1)return false;int j=0;Lnode* r = l;while (j < i - 1 && r->next != NULL){r = r->next;j++;}if (j != i - 1)return false;Lnode* p = new Lnode{ e,r->next,r };if (r->next)r->next->prior = p;r->next = p;return true;
}//按值删除元素e
void deleteElem(DoubList&l,int e)
{if (!l->next)cout << "删除失败:链表为空" << endl;Lnode* r = l->next;while (r){if (r->data == e){r->prior->next = r->next;if (r->next)r->next->prior = r->prior;delete r;r = NULL;return;}r = r->next;}
}//打印双链表
void print(DoubList l)
{Lnode* p=l;while (p->next){p = p->next;cout << p->data << "\t";}cout << endl;
}int main()
{DoubList l;insert_list(l);print(l);deleteElem(l, 3);print(l);return 0;
}

三、循环双向链表

即使我们有了双向链表,但是当我们想要在尾节点找到头节点附近某个节点仍然不够快捷,所以就引进了循环双向链表的概念,不过判断条件这些就需要改变:判断结束条件从NULL变为链表名L

#include<iostream>
using namespace std;
typedef struct Lnode
{int data;Lnode* next,*prior;
}*DoubCirList,Lnode;//初始化一个循环双向链表
bool init_list(DoubCirList& l)
{l = new Lnode;if (l == NULL)return false;//指针域都指向自身l->next = l;l->prior = l;return true;
}//双向循环链表建立(前插法)
bool insert_list(DoubCirList& l)
{init_list(l);int x;while (cin >> x && x != 0){Lnode* p = new Lnode{x,l->next,l};if (p == NULL)return false;l->next->prior = p;l->next = p;}return true;
}//双链表建立(后插法)
bool insert_tail_list(DoubCirList& l)
{init_list(l);int x;Lnode* r =l;while (cin >> x && x != 0){Lnode* p = new Lnode{ x,l,r };if (p == NULL)return false;r->next = p;r = p;}return true;
}//按位插入:在i位插入元素e
bool insertElem(DoubCirList& l, int i, int e)
{if (i < 1)return false;int j=0;Lnode* r = l;while (j < i - 1 && r->next != l){r = r->next;j++;}if (j != i - 1)return false;Lnode* p = new Lnode{ e,r->next,r };r->next->prior = p;r->next = p;return true;
}//按值删除元素e
void deleteElem(DoubCirList&l,int e)
{if (l->next==l)cout << "删除失败:链表为空" << endl;Lnode* r = l->next;while (r!=l){if (r->data == e){r->next->prior = r->prior;r->prior->next = r->next;delete r;r = NULL;return;}r = r->next;}
}//打印双链表
void print(DoubCirList l)
{Lnode* p=l;while (p->next!=l){p = p->next;cout << p->data << "\t";}cout << endl;
}int main()
{DoubCirList l;insert_tail_list(l);print(l);return 0;
}

相关文章:

数据结构双向链表和循环链表

目录 一、循环链表二、双向链表三、循环双向链表 一、循环链表 循环链表就是首尾相接的的链表&#xff0c;就是尾节点的指针域指向头节点使整个链表形成一个循环&#xff0c;这就弥补了以前单链表无法在后面某个节点找到前面的节点&#xff0c;可以从任意一个节点找到目标节点…...

go基础面试题汇总第一弹

init函数是什么时候执行的? init的函数的作用是什么&#xff1f; 通常作为程序执行前包的初始化&#xff0c;例如mysql redis 等中间件的初始化 init函数的执行顺序是怎样的&#xff1f; 分不同情况来回答&#xff1a; 在同一个go文件里面如果有多个init方法&#xff0c;它们…...

Redis 实现分布式锁时需要考虑的问题

引言 分布式系统中的多个节点经常需要对共享资源进行并发访问&#xff0c;若没有有效的协调机制&#xff0c;可能会导致数据竞争、资源冲突等问题。分布式锁应运而生&#xff0c;它是一种保证在分布式环境中多个节点可以安全地访问共享资源的机制。而在Redis中&#xff0c;使用…...

百年极限论一直存在百年糊涂话:有正数小于所有正数

百年极限论一直存在百年糊涂话&#xff1a;有正数小于所有&#xff08;任何、任意&#xff09;正数。 “对于每个大于0的ε[ε>0]&#xff0c;都有非0距离数小于ε”显然是病句&#xff1a;有正数小于每个&#xff08;所有&#xff09;正数ε。其中任意&#xff08;任何&am…...

红日靶场1学习笔记

一、准备工作 1、靶场搭建 靶场地址 靶场描述 靶场拓扑图 其他相关靶场搭建详情见靶场地址相关说明 2、靶场相关主机信息 后续打靶场的过程中&#xff0c;如果不是短时间内完成&#xff0c;可能ip会有变化 主机ip密码角色win7192.168.122.131hongrisec2019!边界服务器win…...

【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)

文章目录 从零实现 list 容器&#xff1a;细粒度剖析与代码实现前言1. list 的核心数据结构1.1节点结构分析&#xff1a; 2. 迭代器设计与实现2.1 为什么 list 需要迭代器&#xff1f;2.2 实现一个简单的迭代器2.2.1 迭代器代码实现&#xff1a;2.2.2 解释&#xff1a; 2.3 测试…...

【C#生态园】打造现代化跨平台应用:深度解析.NET桌面应用工具

选择最适合你的.NET UI框架&#xff1a;全面解析六种热门选择 前言 在现代软件开发中&#xff0c;选择合适的桌面应用框架和UI库对于开发人员来说至关重要。本文将介绍几种流行的.NET桌面应用框架和UI库&#xff0c;包括Eto.Forms、Avalonia、ReactiveUI、MahApps.Metro、Mat…...

第二十一章 (动态内存管理)

1. 为什么要有动态内存分配 2. malloc和free 3. calloc和realloc 4. 常⻅的动态内存的错误 5. 动态内存经典笔试题分析 6. 总结C/C中程序内存区域划分 1.为什么要有动态内存管理 我们目前已经掌握的内存开辟方式有 int main() {int num 0; //开辟4个字节int arr[10] …...

机器学习框架总结

机器学习框架是用于构建、训练、评估和部署机器学习模型的工具和库的集合。它们简化了模型开发过程&#xff0c;并提供了预构建的功能、优化的计算性能和对深度学习、监督学习、无监督学习等技术的支持。下面是一些主要的机器学习框架的详细介绍&#xff1a; 1. TensorFlow 1…...

docker pull 超时的问题如何解决

docker不能使用&#xff0c;使用之前的阿里云镜像失败。。。 搜了各种解决方法&#xff0c;感谢B站UP主 <iframe src"//player.bilibili.com/player.html?isOutsidetrue&aid113173361331402&bvidBV1KstBeEEQR&cid25942297878&p1" scrolling"…...

【数学分析笔记】第4章第3节 导数四则运算和反函数求导法则(2)

4. 微分 4.3 导数四则运算与反函数求导法则 双曲正弦函数 sh ⁡ x e x − e − x 2 \sh x\frac{e^x-e^{-x}}{2} shx2ex−e−x​ 双曲余弦函数 ch ⁡ x e x e − x 2 \ch x\frac{e^xe^{-x}}{2} chx2exe−x​ ch ⁡ 2 x − sh ⁡ 2 x 1 \ch^2 x-\sh^2 x1 ch2x−sh2x1 ( e…...

【2024】基于mysqldump的数据备份与恢复

基于mysqldump备份与恢复 mysqldump是一个用于备份 MySQL 数据库的实用工具。 它可以将数据库的结构&#xff08;如数据库、表、视图、存储过程等的定义&#xff09;和数据&#xff08;表中的记录&#xff09;导出为文本文件&#xff0c;这些文本文件可以包含 SQL 语句&#…...

家用无线路由器配置

一.首先进行线路连接。如下图&#xff1a;"光猫LAN口"—网线—"路由器WAN口"。 注意&#xff1a;家用光纤宽带一般选择使用200兆宽带到1000兆&#xff0c;如果网速不达标请查看路由器是否是千兆路由器。千兆路由器通常是双频的&#xff0c;支持两个信号一个…...

模拟算法(4)_外观数列

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 模拟算法(4)_外观数列 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 1. 题目链…...

vsomeip用到的socket

概述&#xff1a; ​ vsomeip用到的socket的代码全部都在implementation\endpoints目录下面&#xff0c;主要分布在下面六个endpoint类中&#xff1a; local_client_endpoint_impl // 本地客户端socket&#xff08;UDS Socket或者127.0.0.1的socket&#xff09;local_server…...

MFC有三个选项:MFC ActiveX控件、MFC应用程序、MFC DLL,如何选择?

深耕AI&#xff1a;互联网行业 算法研发工程师 ​ 目录 MFC ActiveX 控件 控件的类型 标准控件 自定义控件 ActiveX控件 MFC ActiveX控件 标准/自定义控件 MFC ActiveX控件分类 3种MFC如何选择&#xff1f; MFC ActiveX控件 MFC 应用程序 MFC DLL 总结 举例说明…...

边缘概率 | 条件概率

关于什么是边缘概率分布和条件概率分布&#xff0c;在理论上&#xff0c;我自己也还没有理解&#xff0c;那么现在就根据我学习到的理解方式来记录一下&#xff0c;有错误指出&#xff0c;请大家指正&#xff01;&#xff01;&#xff01; 例如&#xff0c;一个箱子里有十个乒乓…...

深入浅出:现代JavaScript开发者必知必会的Web性能优化技巧

亲爱的读者们&#xff0c;欢迎来到本期博客。今天&#xff0c;我们将深入探讨JavaScript开发者在日常工作中如何提升Web性能。在快节奏的Web开发世界中&#xff0c;性能优化至关重要。本文将分享一些实用技巧&#xff0c;帮助你构建快速、高效的Web应用。 1. 使用CDN加速资源加…...

【S32K3 RTD LLD篇5】K344 ADC SW+HW trigger

【S32K3 RTD LLD篇5】K344 ADC SWHW trigger 一&#xff0c;文档简介二&#xff0c;ADC SW HW 触发2.1 软硬件平台2.2 SWADC 软件触发2.3 SWBCTUADC 软件BCTU触发2.4 PITTRIGMUXADC 硬件PIT TRIGUMX触发2.5 EMIOSBCTUHWADC硬件EMIOS BCTU触发2.6 EMIOSBCTUHW LISTADC硬件EMIOS …...

TransFormer 视频笔记

TransFormer BasicsAttention单头注意力 single head attentionQ&#xff1a; query 查寻矩阵 128*12288K key matrix 128*12288SoftMax 归一 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/19e3cf1ea28442eca60d5fc1303921f4.png)Value matrix 12288*12288 MLP Bas…...

英雄联盟智能工具League Akari:从效率提升到战术优化的全方位解决方案

英雄联盟智能工具League Akari&#xff1a;从效率提升到战术优化的全方位解决方案 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾在英…...

[C语言]控制台扫雷游戏

用精简的代码&#xff0c;回顾数组、函数和游戏逻辑的核心应用。还记得Windows自带的扫雷吗&#xff1f;这次我们用C语言实现一个9x9的简易版&#xff0c;适合用来巩固函数封装、二维数组和随机数等知识点。1. 整体思路 扫雷的核心功能可以拆成几块&#xff1a; 打印菜单&#…...

intv_ai_mk11详细步骤:24GB单卡部署Llama模型并启用Web UI全流程

24GB单卡部署Llama模型并启用Web UI全流程指南 1. 环境准备与快速部署 在开始部署intv_ai_mk11模型前&#xff0c;我们需要确保硬件和软件环境满足基本要求。这个中等规模的Llama架构模型可以在单张24GB显存的GPU上流畅运行&#xff0c;非常适合个人开发者和小型团队使用。 …...

数学动画音频同步:让几何图形随音乐起舞的技术实现

数学动画音频同步&#xff1a;让几何图形随音乐起舞的技术实现 【免费下载链接】manim A community-maintained Python framework for creating mathematical animations. 项目地址: https://gitcode.com/GitHub_Trending/man/manim 在数学可视化领域&#xff0c;Manim…...

Splunk Enterprise 10.2.2 (macOS, Linux, Windows) - 搜索、分析和可视化,数据全面洞察平台

Splunk Enterprise 10.2.2 (macOS, Linux, Windows) - 搜索、分析和可视化&#xff0c;数据全面洞察平台 Search, analysis, and visualization for actionable insights from all of your data 请访问原文链接&#xff1a;https://sysin.org/blog/splunk-10/ 查看最新版。原…...

对 OS:TEP 的 MLFQ 策略的一点思考

1.SJF 调度算法SJF 没啥好说的, 书上讲的很清楚了, SJF 就是最短任务优先原则, 其设计初衷是想解决 FIFO 的糟糕的周转时间的问题.但是, 正如书上所说, 这玩意主打一个秩序井然, 只能处理所有任务同时到队列的情况, 要是某堆进程不按这套路出牌, 那 SJF 立马完蛋, 书上就有一个…...

CentOS7下KingbaseES V9与MySQL性能对比实测:从安装到查询优化的全流程体验

CentOS7下KingbaseES V9与MySQL性能对比实测&#xff1a;从安装到查询优化的全流程体验 在国产数据库技术快速发展的今天&#xff0c;越来越多的企业开始关注从传统数据库向国产化解决方案的迁移。作为国产数据库中的佼佼者&#xff0c;KingbaseES V9凭借其出色的MySQL兼容性和…...

FSearch:Linux系统上如何用这款革命性工具实现毫秒级文件搜索

FSearch&#xff1a;Linux系统上如何用这款革命性工具实现毫秒级文件搜索 【免费下载链接】fsearch A fast file search utility for Unix-like systems based on GTK3 项目地址: https://gitcode.com/gh_mirrors/fs/fsearch 你是否曾在Linux系统中为寻找一个文件而花费…...

资源提取高效解析与跨设备管理:猫抓浏览器扩展的技术实践

资源提取高效解析与跨设备管理&#xff1a;猫抓浏览器扩展的技术实践 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 在数字化内容爆炸的今天&…...

Univer全栈框架实战指南:3步构建企业级AI原生表格应用

Univer全栈框架实战指南&#xff1a;3步构建企业级AI原生表格应用 【免费下载链接】univer Build AI-native spreadsheets. Univer is a full-stack framework for creating and editing spreadsheets on both web and server. With Univer Platform, Univer Spreadsheets is d…...