网站 服务器选择,网页设计网站期末作业,高效简便的网站开发,wordpress 菜单 导出文章目录 1链表的再次介绍2为什么选择双向循环链表#xff1f;3代码实现#xff1a;从初始化到销毁1. 定义链表节点2. 初始化链表3. 插入和删除节点4. 链表的其他操作5. 打印链表和判断链表是否为空6. 销毁链表 4测试代码5链表种类介绍6链表与顺序表的区别7存储金字塔L0: 寄存… 文章目录 1链表的再次介绍2为什么选择双向循环链表3代码实现从初始化到销毁1. 定义链表节点2. 初始化链表3. 插入和删除节点4. 链表的其他操作5. 打印链表和判断链表是否为空6. 销毁链表 4测试代码5链表种类介绍6链表与顺序表的区别7存储金字塔L0: 寄存器L1: 高速缓存SRAML2: 高速缓存SRAML3: 高速缓存SRAML4: 主存DRAML5: 本地二级存储本地磁盘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新年快乐代码相伴
在这个充满希望的新年里愿你的代码之旅充满乐趣和挑战。无论是探索数据结构的奥秘还是深入理解计算机系统的运行机制都希望你能收获满满。让我们一起在代码的世界里继续探索、学习和成长用代码书写属于自己的精彩篇章。
