第五章:C语言数据结构与算法之双向带头循环链表
创始人
2024-05-31 09:06:48
0

系列文章目录


文章目录

  • 系列文章目录
  • 前言
  • 一、哨兵位的头节点
  • 二、双向链表的结点
  • 三、接口函数的实现
    • 1、创建结点
    • 2、初始化
    • 3、尾插与尾删
    • 4、头插与头删
    • 5、打印
    • 6、查找
    • 7、随机插入与随机删除
    • 8、判空、长度与销毁
  • 四、顺序表和链表的对比
    • 1. 不同点
    • 2. 优缺点
  • 五、缓存命中
    • 1、缓存
    • 2、缓存命中
  • 总结


前言

一般题目给的单链表是无头单向非循环链表,但是我们可以升级成双向带头循环链表,这个链表比起单链表更有优势。


一、哨兵位的头节点

在这里插入图片描述

上面带有head头结点的链表就是带头的链表,题目中的链表一般没有头节点,phead指针直接指向第一个结点,而带头的链表phead指针指向头结点,头节点指向第一个结点,一般称为 哨兵位的头节点

二、双向链表的结点

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

比起单链表的结点,多了指向前一个结点的指针——prev。

三、接口函数的实现

1、创建结点

LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));assert(newnode);newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;}

2、初始化

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

初始化即开辟一个头节点,然后让这个头节点的前后指针域都指向自己。

3、尾插与尾删

在这里插入图片描述

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);	newnode->prev = phead->prev;phead->prev->next = newnode;newnode->next = phead;phead->prev = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//空phead->prev = phead->prev->prev;free(phead->prev->next);phead->prev->next = phead;}

双向带头循环链表并没有单独讨论空链表的情况,这就是头节点的好处,之所以不用讨论就是因为节点的个数不可能为0,最少也包括一个头节点。

4、头插与头删

在这里插入图片描述

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->next;newnode->next = phead->next;newnode->prev = phead;tail->prev = newnode;phead->next = newnode;}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->next->next;LTNode* tailPrev = phead->next;phead->next = tail;tail->prev = phead;free(tailPrev);}	

5、打印

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("[%p | %d | %p]", cur->prev, cur->data, cur->next);if(cur->next != phead)printf("<->");cur = cur->next;}printf("\n");
}

就是从头遍历一遍即可,但是需要注意的是,这是一个循环链表,如果我们不加限制条件的话,他会一直循环下去。所以,我们这里需要加上判断条件。

6、查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);assert(phead->next != phead);LTNode* cur = phead->next;while (cur->data != x && cur != phead)cur = cur->next;if (cur == phead)return NULL;else return cur;
}

也要加限制条件。

7、随机插入与随机删除

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

实现方式之前的头尾操作一样,也可以复用到头尾操作中。

8、判空、长度与销毁

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next != phead;
}size_t LTSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;size_t size = 0;while (cur != phead){size++;cur = cur->next;}return size;
}void LTDestory(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead)LTErase(cur);free(phead);
}

逐个释放就行。

四、顺序表和链表的对比

1. 不同点

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持:O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

2. 优缺点

顺序表:
优点:尾插尾删效率高,下标的随机访问。
缺点:空间不够需要扩容(扩容的代价大);头部或者中间插入删除效率低,需要挪动数据。

链表:
优点:需要扩容,按需申请释放小块结点内存;任意位置插入效率很高–O(1)。
缺点:不支持下标随机访问;

五、缓存命中

1、缓存

CPU与内存经常有数据的访问与存储,但两者运行速度不同,就导致了CPU会“等待”内存传输数据的情况,我们在二者之间搭建一片缓冲区域,即缓存,来解决这个问题。
在这里插入图片描述
从下到上,各种存储器的内存逐渐降低,数据传输速度逐级增高。

2、缓存命中

那么每次CPU会从寄存器中读取数据,这二者的速度差距已经大大缩小了。我们以一个数组为例,我们想对第一个元素进行计算,我们不仅会把第一个元素所对的内存传输到寄存器,还会把其相邻的内存空间传输到寄存器中作为备用,每次传输到寄存器中的数据的大小取决于电脑的相应配置。
这样,我们在CPU访问完第一元素后,假设我们还需要计算第二个元素,我们又恰好在寄存器中存储了第二个元素的内存信息。CPU便可直接调用,而无需寄存器再去读取。这就叫缓存命中。


总结

链表和顺序表各有优势,带头双向链表比起单链表更加方便操作。

深窥自己的心,而后发觉一切的奇迹在你自己。——培根

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...