快速上手 C++ 数据结构与算法
王健伟
《C++ 新经典》系列作者,资深 C++ 讲师
3224 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 55 讲
结束语 (1讲)
快速上手 C++ 数据结构与算法
15
15
1.0x
00:00/00:00
登录|注册

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
立即购买
登录 后留言

全部留言(1)

  • 最新
  • 精选
  • RIVER
    老师可不可以把一些关键词的定义带上(英文),便于后续阅读英文资料

    作者回复: 你指的关键词的定义带上(英文)是指哪个,可以举一个例子让老师看看。另外代码中也有一些英文名字、拼写之类的你可以参考。提到阅读英文资料,除非你有明确的任务需求,不然没必要阅读英文资料,因为我们有太多新知识需要学,学每样知识适度就是最好的。

    2023-03-06归属地:湖北
    1
收起评论
显示
设置
留言
1
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部