07|静态链表:用一维数组表达的链表
王健伟
你好,我是王健伟。
前面已经聊了很多种链表,今天我们再来聊一聊最后一种链表——“静态链表”。
有些早期的高级语言,并没有指针这种概念,之前我们探讨的链表实现方法在这些高级语言中并不适用。于是,用一维数组代替指针来描述单链表的想法应运而生,这种用一维数组描述的链表,就称为静态链表。
之前我们说过,单链表节点之间在内存中并不需要紧密相连地存放,而采用数组存储数据时则需要数据在内存中紧密相连。所以不难想象,静态链表在内存中也需要分配一整块连续的内存空间,如图 8 所示:
图8 用静态链表存储数据(需要分配一整块连续的内存空间)
你会发现,说是内存空间紧密相连,但是链表中的各个节点却是并不需要紧密地连在一起的。
每个数组元素都是由两个数据域组成:data 和 cur。其中 data 用来存储链表中每个节点的数据,cur 用来存储链表中后继节点所属的数组元素的下标(cur 也称为游标,用来模拟指针)。比如图 8 中存储数据 a2 的区域就是 data 域,存储数字 6 的区域就是 cur 域。
注意,如果 cur 域的值为“末尾(一个负数作为标记)”,则表示该 cur 所代表的数组元素是链表中的最后一个节点,比如图 8 中存储数据 a5 的节点。下标为 0 的数组元素可以看成是链表的头节点,其 cur 域的值(数字 2)用于指示链表第一个数据节点对应的数组下标。所以,数据 a1 所在的节点,其实就是静态链表的第一个数据节点。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
静态链表是一种用一维数组表达的链表结构,适用于早期高级语言中缺乏指针概念的情况。本文详细介绍了静态链表的类定义、初始化操作、元素插入和删除操作的实现方式,以及在main函数中的测试代码。通过清晰的语言和示意图展示了静态链表的结构和操作,为读者提供了深入理解静态链表的基础知识。文章还提到了静态链表的特点,包括无法进行随机存取、无法扩容等,以及不同的静态链表实现方式。总体而言,本文通过详细的代码实现和图示,使读者能够快速了解静态链表的特点和实现方式,为其提供了深入理解静态链表的基础知识。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》,新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
- RIVER老师可不可以把一些关键词的定义带上(英文),便于后续阅读英文资料
作者回复: 你指的关键词的定义带上(英文)是指哪个,可以举一个例子让老师看看。另外代码中也有一些英文名字、拼写之类的你可以参考。提到阅读英文资料,除非你有明确的任务需求,不然没必要阅读英文资料,因为我们有太多新知识需要学,学每样知识适度就是最好的。
2023-03-06归属地:湖北1
收起评论