从零开始实现一个双向循环链表:C语言实战

文章目录

  • 1链表的再次介绍
  • 2为什么选择双向循环链表?
  • 3代码实现:从初始化到销毁
    • 1. 定义链表节点
    • 2. 初始化链表
    • 3. 插入和删除节点
    • 4. 链表的其他操作
    • 5. 打印链表和判断链表是否为空
    • 6. 销毁链表
  • 4测试代码
  • 5链表种类介绍
  • 6链表与顺序表的区别
  • 7存储金字塔
    • L0: 寄存器
    • L1: 高速缓存(SRAM)
    • L2: 高速缓存(SRAM)
    • L3: 高速缓存(SRAM)
    • L4: 主存(DRAM)
    • L5: 本地二级存储(本地磁盘)
    • L6: 远程二级存储
    • 缓存利用率与局部性原理:
  • 8书籍推荐《深入理解计算机系统》
  • 9新年快乐,代码相伴

1链表的再次介绍

在计算机科学中,链表是一种常见的数据结构,它通过节点之间的指针连接来存储数据。链表有许多变种,其中双向循环链表因其独特的结构而备受关注。今天,我们将通过C语言实现一个双向循环链表,并探讨其核心操作。无论你是数据结构的新手,还是想巩固基础的老手,这篇文章都将为你提供实用的知识和代码示例。
链接: 单链表介绍

2为什么选择双向循环链表?

双向循环链表是一种特殊的链表,它的每个节点都有两个指针:一个指向前一个节点,另一个指向后一个节点。与单向链表不同,双向链表可以从任意一个节点向前或向后遍历。而循环链表的特点是其尾节点指向头节点,形成一个闭环。这种结构在某些场景下非常有用,比如实现高效的队列或缓存机制。

3代码实现:从初始化到销毁

1. 定义链表节点

首先,我们需要定义链表节点的结构。每个节点包含三个部分:

data:存储节点的数据。

next:指向下一个节点的指针。

prev:指向前一个节点的指针。

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

2. 初始化链表

链表的初始化是创建一个头节点,并将其next和prev指针指向自己,形成一个空的双向循环链表。

LTNode* BuyListNode(LTDataType x)
{LTNode* New = (LTNode*)malloc(sizeof(LTNode));if (New == NULL){perror("malloc");exit(-1);}New->next = NULL;New->prev = NULL;New->data = x;return New;
}
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1); // 创建头节点phead->next = phead;phead->prev = phead;return phead;
}

3. 插入和删除节点

在双向循环链表中,插入和删除节点是非常高效的操作。我们可以在任意位置插入或删除节点,只需调整相邻节点的指针即可。

插入节点

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

删除节点

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

4. 链表的其他操作

我们还实现了一些常见的链表操作,如LTPushBack(在链表尾部插入节点)、LTPopBack(删除链表尾部节点)、LTPushFront(在链表头部插入节点)和LTPopFront(删除链表头部节点)。这些操作都依赖于LTInsert和LTErase函数。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}void LTPopBack(LTNode* phead)
{assert(phead);LTErase(phead->prev);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next, x);
}void LTPopFront(LTNode* phead)
{assert(phead);LTErase(phead->next);
}

5. 打印链表和判断链表是否为空

为了方便调试和观察链表的状态,我们实现了LTPrint函数来打印链表中的所有节点数据。此外,LTEmpty函数用于判断链表是否为空。

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<=phead=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}puts("");
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead == phead->next;
}

6. 销毁链表

在使用完链表后,我们需要释放所有节点的内存,避免内存泄漏。

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

4测试代码

为了验证我们的双向循环链表实现是否正确,我们编写了一个简单的测试函数Test1。在这个函数中,我们进行了多次插入、删除操作,并打印链表的状态。

void Test1()
{LTNode* phead = LTInit();LTPushBack(phead, 2);LTPushBack(phead, 1);LTPushFront(phead, 5);LTPrint(phead);LTInsert(phead->next, 6);LTInsert(phead->next, 6);LTPushFront(phead, 6);LTPrint(phead);LTPopBack(phead);LTPopBack(phead);LTPopFront(phead);LTErase(phead->next);LTPrint(phead);LTPushBack(phead, 4);LTPushBack(phead, 3);LTPushBack(phead, 2);LTPushBack(phead, 1);LTPrint(phead);printf("%d\n", LTEmpty(phead));LTDestroy(phead);phead = LTInit();printf("%d\n", LTEmpty(phead));
}int main()
{Test1();return 0;
}

5链表种类介绍

在这里插入图片描述
在这里插入图片描述

6链表与顺序表的区别

在这里插入图片描述

7存储金字塔

在这里插入图片描述
这张图片展示了计算机存储体系的层级结构,通常被称为存储金字塔(Memory Hierarchy)。它描述了不同层级的存储设备从最快速但成本最高到最慢但成本最低的分布情况。每一层级的存储设备都具有不同的访问速度和成本,它们相互配合,以实现性能和成本的最佳平衡。
存储金字塔层级介绍:

L0: 寄存器

位于金字塔的顶端,是CPU内部的寄存器,提供最快的数据访问速度。
寄存器的数量有限,因此它们用于存储最频繁访问的数据。

L1: 高速缓存(SRAM)

位于寄存器下方,是CPU的一级缓存,使用静态随机存取存储器(SRAM)。
L1缓存分为两个部分:L1指令缓存(L1-I)和L1数据缓存(L1-D),分别用于存储指令和数据。

L2: 高速缓存(SRAM)

二级缓存通常集成在CPU芯片上,或者在某些设计中位于CPU芯片附近。
L2缓存比L1缓存大,但访问速度稍慢。

L3: 高速缓存(SRAM)

三级缓存是更大但速度较慢的缓存层级,通常位于CPU芯片外。
L3缓存为多个核心共享,用于减少核心之间的数据访问延迟。

L4: 主存(DRAM)

主存储器,即动态随机存取存储器(DRAM),是计算机的主要内存。
与缓存相比,主存的访问速度较慢,但容量更大,成本更低。

L5: 本地二级存储(本地磁盘)

本地磁盘,如硬盘驱动器(HDD)或固态硬盘(SSD),用于长期存储数据。
访问速度比主存慢得多,但存储容量更大,成本更低。

L6: 远程二级存储

远程存储,如分布式文件系统、网络附加存储(NAS)或Web服务器,提供更大的存储空间。
访问速度最慢,但可以提供几乎无限的存储容量。

缓存利用率与局部性原理:

缓存利用率:指的是缓存中存储的数据被访问的频率。高缓存利用率意味着更多的数据访问可以直接从缓存中获取,从而提高系统性能。
局部性原理:包括时间局部性和空间局部性。时间局部性指的是最近访问过的数据很可能在不久的将来再次被访问;空间局部性指的是如果一个数据被访问,那么它附近的数据也很可能被访问。缓存的设计就是基于这些原理,以提高缓存利用率。

8书籍推荐《深入理解计算机系统》

链接: 书籍介绍

9新年快乐,代码相伴

在这个充满希望的新年里,愿你的代码之旅充满乐趣和挑战。无论是探索数据结构的奥秘,还是深入理解计算机系统的运行机制,都希望你能收获满满。让我们一起在代码的世界里,继续探索、学习和成长,用代码书写属于自己的精彩篇章。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/12780.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

简单本地部署deepseek(软件版)

Download Ollama on Windows 下载 下载安装 winr 输入 cmd 然后输入ollama -v&#xff0c;出现ollama版本&#xff0c;安装成功 deepseek-r1 选择1.5b 输入 cmd 下面代码 ollama run deepseek-r1:1.5b 删除deepseek的代码如下&#xff1a; ollama rm deepseek-r1:1.5b 使用…

21.2.1 基本操作

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 Excel的基本操作步骤&#xff1a; 1、打开Excel&#xff1a;定义了一个Application对象&#xff1a; Microsoft.Office.Interop.E…

SGlang 专为大模型设计的高效服务框架

SGlang 是一种专为大型语言模型&#xff08;LLM&#xff09;和视觉语言模型&#xff08;VLM&#xff09;设计的高效服务框架&#xff0c;旨在提升模型的推理速度和灵活性。以下是关于 SGlang 框架的详细介绍&#xff1a; 1. 框架背景与目标 SGlang 是一种快速服务框架&#x…

基于SpringBoot+vue高效旅游管理系统

Spring Boot后端与Vue前端融合&#xff1a;构建高效旅游管理系统 目录 一、项目简介 二、开发技术与环境配置 2.1 SpringBoot框架 2.2 Java语言简介 2.3 Vue的介绍 2.4 mysql数据库介绍 2.5 B/S架构 三、系统功能实现 四、系统项目截图 登录页面 后台管理页面 用户…

visual studio安装

一、下载Visual Studio 访问Visual Studio官方网站。下载 Visual Studio Tools - 免费安装 Windows、Mac、Linux 在主页上找到并点击“下载 Visual Studio”按钮。 选择适合需求的版本&#xff0c;例如“Visual Studio Community”&#xff08;免费版本&#xff09;&#x…

【HarmonyOS之旅】基于ArkTS开发(三) -> 兼容JS的类Web开发(四) -> 常见组件(一)

目录 1 -> List 1.1 -> 创建List组件 1.2 -> 添加滚动条 1.3 -> 添加侧边索引栏 1.4 -> 实现列表折叠和展开 1.5 -> 场景示例 2 -> dialog 2.1 -> 创建Dialog组件 2.2 -> 设置弹窗响应 2.3 -> 场景示例 3 -> form 3.1 -> 创建…

Java中的object类

1.Object类是什么&#xff1f; &#x1f7ea;Object 是 Java 类库中的一个特殊类&#xff0c;也是所有类的父类(超类),位于类继承层次结构的顶端。也就是说&#xff0c;Java 允许把任何类型的对象赋给 Object 类型的变量。 &#x1f7e6;Java里面除了Object类&#xff0c;所有的…

manimgl安装

一、环境 笔记本 $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.5 LTS Release: 22.04 Codename: jammy二、安装miniconda3 manimgl基于python开发&#xff0c;为了防止将笔记本中已有的python环境破坏&#xff0c;因此…

c++中priority_queue的应用及模拟实现

1.介绍 priority_queue 是一种数据结构&#xff0c;它允许你以特定的顺序存储和访问元素。在 C 标准模板库&#xff08;STL&#xff09;中&#xff0c;priority_queue 是一个基于容器适配器的类模板&#xff0c;它默认使用 std::vector 作为底层容器&#xff0c;并且默认使用最…

【技术追踪】DiffMIC:用于医学图像分类的双引导扩散网络(MICCAI-2024)

似乎是第一个用于医学图像分类的扩散模型嗷~ 论文&#xff1a;DiffMIC: Dual-Guidance Diffusion Network for Medical Image Classification 代码&#xff1a;https://github.com/scott-yjyang/DiffMIC 0、摘要 扩散概率模型最近在生成式图像建模中表现出了显著的性能&#xf…

Deepseek v3R1 学习笔记

o1 o1 模型在训练过程中混合了多种奖励函数的设计方法&#xff0c;并且尝试从结果监督转向过程监督&#xff0c;在中间过程进行打分 使用的搜索策略&#xff1a;基于树的搜索和基于顺序修改的搜索 R1 R1-Zero 是从基础模型开始&#xff0c;完全由强化学习驱动&#xff0c;不…

技术书籍写作与编辑沟通指南

引言 撰写技术书籍不仅仅是知识的输出过程&#xff0c;更是与编辑团队紧密合作的协同工作。优秀的技术书籍不仅依赖作者深厚的技术背景&#xff0c;还需要精准的表达、流畅的结构以及符合出版要求的编辑润色。因此&#xff0c;如何高效地与编辑沟通&#xff0c;确保书籍质量&a…

DeepSeek+Ollama+AnythingLLM 本地部署完全指南,打造专属知识库

DeepSeekOllamaAnythingLLM 本地部署完全指南&#xff0c;打造专属知识库 1 Ollama 本地化部署DeepSeek R1 Ollama 是一个用于本地运行大语言模型&#xff08;LLMs&#xff09;的开源工具&#xff0c;提供简单的界面和优化的推理引擎 &#xff0c;使用户能够在个人设备上高效…

更换IP属地会影响网络连接速度吗

在数字化时代&#xff0c;网络连接速度对于个人用户和企业来说都至关重要。无论是日常浏览网页、观看视频&#xff0c;还是进行在线办公、游戏娱乐&#xff0c;网络速度都直接影响着我们的体验。而IP属地&#xff0c;作为网络连接中的一个重要元素&#xff0c;其变动是否会引发…

2025 持续防范 GitHub 投毒,通过 Sharp4SuoExplorer 分析 Visual Studio 隐藏文件

在2024年底的网络安全事件中&#xff0c;某提权工具被发现植入后门&#xff0c;攻击者利用 .suo 文件作为隐蔽的攻击方式。由于 .suo 文件是 Visual Studio 项目的隐藏配置文件&#xff0c;通常不为安全研究人员所关注&#xff0c;因此为攻击者提供了潜在的攻击渠道。 初步调查…

每日Attention学习19——Convolutional Multi-Focal Attention

每日Attention学习19——Convolutional Multi-Focal Attention 模块出处 [ICLR 25 Submission] [link] UltraLightUNet: Rethinking U-shaped Network with Multi-kernel Lightweight Convolutions for Medical Image Segmentation 模块名称 Convolutional Multi-Focal Atte…

【自然语言处理(NLP)】NLP实战:IMDB影评情感分析项目

文章目录 介绍IMDB影评情感分析项目数据集项目实现1. 导包2. 加载IMDB数据3. 查看部分数据4. 分词5. 加载数据整合6. 构建模型7. 词嵌入8. 初始化模型和权重9. glove词向量10. 训练和评估11. 预测 个人主页&#xff1a;道友老李 欢迎加入社区&#xff1a;道友老李的学习社区 介…

企业高效管理策略中的关键一环:WorkWin 监控上网时间的软件的效能剖析

在企业日常运营体系中&#xff0c;员工工作效率与网络资源的合理配置&#xff0c;始终是企业管理者重点关注的核心议题。伴随互联网的广泛普及&#xff0c;员工在工作时段内的网络使用行为日益常态化。然而&#xff0c;若缺乏行之有效的上网时间管控机制&#xff0c;极易导致员…

Spring AI 智能体通过 MCP 集成本地文件数据

作者&#xff1a;刘军 Model Context Protocol&#xff08;MCP&#xff09;简介 模型上下文协议&#xff08;即 Model Context Protocol&#xff0c;MCP&#xff09; [ 1] 是一个开放协议&#xff0c;它规范了应用程序如何向大型语言模型&#xff08;LLM&#xff09;提供上下…

DIY Shell:探秘进程构建与命令解析的核心原理

个人主页&#xff1a;chian-ocean 文章专栏-Linux 前言&#xff1a; Shell&#xff08;外壳&#xff09;是一个操作系统的用户界面&#xff0c;它提供了一种方式&#xff0c;使得用户能够与操作系统进行交互。Shell 是用户与操作系统之间的桥梁&#xff0c;允许用户通过命令行…