概念
为了性能考虑,嵌入式系统一般使用C语言进行开发,由于C语言标准库没有封装链表,所以嵌入式系统一般自己设计和实现链表这种数据结构。单链表是链表中的一种,本文描述OpenAtom OpenHarmony(以下简称“OpenHarmony”)中HDF软件模块自己定义的单链表,并学习其设计和实现方法。其中包含一些技巧,可以提高读者的软件开发能力。
单链表定义
在OpenHarmony的HDF软件模块中,单链表定义在hdf_slist.h中。
struct HdfSListNode {
struct HdfSListNode *next; // next element in list, or NULL
};
其示意图如下:
如上图所述,每个节点都是HdfSListNode,上图共有5个节点,每个节点内部有一个next成员,其值为下一个节点在内存中的地址。由于可以通过这个地址找到下一个节点,所以在图里面用红色右箭头来描述这个关系。整体来看,从1号节点可以通过next成员依次找到后面4个节点,从图形看,就是一个逻辑上的链关系,我们把这种结构称为链表。
单独看5号节点,5号节点没有下一个节点,所以设计上是需要给一个特定的值来表示,实现上一般把5号节点的next成员填成0值,表明其为最末尾的节点。
接下来我们看下面这个数据结构:
struct HdfSList {
struct HdfSListNode *root;
};
其示意图如下:
如上图所示,圆角矩形表示的是HdfSList,其root成员记录了链表中某节点的地址,为了访问整个链表,需要将root成员的值设置成第1个节点的地址。因为单链表只支持往一个方向查找,不支持往回查找,如上面的错误范例。如果root记录的是第二个节点地址,则第一个节点变得不可访问。
迭代器简介
迭代器是伴随集合概念产生的,意思是依次访问集合中的每一个元素,迭代器提供访问这些元素的方法。对于单链表而言,链表中的每一个节点都是一个元素,所有的节点组成集合。所以可以通过迭代器来访问链表中的元素。
迭代器需要提供的基本能力以及操作范式是:
初始化迭代器
重复判断(集合中还有未被访问的元素)
获取下一个元素的访问方法
读写下一个元素(也可能是删除这个元素)
结束
上述范式展示了迭代器的用法,通过迭代器,遍历元素变得简单直接(将遍历算法封装在迭代器中),不用每次迭代都考虑数据结构细节(数据结构种类繁多,单链表只是其中之一)。
对于本文描述的单链表,其封装了下面3个函数来支持迭代算法。这3个函数分别表示迭代器对象的初始化;集合中是否还有元素没有参与迭代;取出集合中下一个可以参与迭代的元素。
/* * @brief initialize iterator * * @param[in] iterator the point of iterator. * @param[in] list the point of operation list. * * @return None */
void HdfSListIteratorInit(struct HdfSListIterator *iterator, struct HdfSList *list);
/* * @brief check whether list has next node. * * @param[in] iterator the point of iterator. * * @return the result of check next. */
bool HdfSListIteratorHasNext(struct HdfSListIterator *iterator);
/* * @brief get next link in the list and move iterator to next. * * @param[in] iterator the point of iterator. * * @return point to next element of it. */
struct HdfSListNode *HdfSListIteratorNext(struct HdfSListIterator *iterator);
迭代器实现考虑
对于本文所描述的单链表迭代器。直观上看,除了第一个节点,其它节点都可以通过next访问到,第一个节点通过root访问到。那实际上会不会就是这么简单呢?其实不然,因为需要考虑到节点删除的因素。如下图,在链表迭代过程中,如果删除了当前节点,那么怎么找到下一个节点呢?
如上图所示,当在遍历过程中删除了curr节点时,那么通过它找到下一个节点是不可能了。所以这个时候我们必须借助操作curr之前还在链表上的上一个节点,即上图的prev节点,通过其next成员,找到需要迭代处理的下一个节点。所以,迭代过程中需要记录prev、curr这2个节点的位置信息。迭代过程实际就是调整prev和curr的过程,对于不删除的情况,prev和curr依次向后移动,删除操作时,只移动curr。
另外,对于第1个节点的情况需要特殊处理,所以需要一个额外的信息来表示是不是迭代第1个元素,因为本文描述的迭代器对象含有3个信息。如下代码所示:
struct HdfSListIterator {
int stepOnNext; //是否即将开始遍历第二个以及之后的元素
struct HdfSListNode *prev; // points to the item before the current one 当前被操作元素的前一个元素
struct HdfSListNode *curr; // points to the current item (to detect item removal) 当前被操作的元素,可能刚操作完,被移除链表
};
上述代码中prev和curr的作用已经在前面详细描述,而stepOnNext的意思就是是否已经开始取第二个元素。即将第一个元素的获取算法与第二个元素分开。
结论
在嵌入式开发中,在学习数据结构课程中,在进行OpenHarmony项目开发中,单链表都是很重要的,而本文只是其中一个软件模块的单链表实现。
经常有很多小伙伴抱怨说:不知道学习鸿蒙开发哪些技术?不知道需要重点掌握哪些鸿蒙应用开发知识点?
为了能够帮助到大家能够有规划的学习,这里特别整理了一套纯血版鸿蒙(HarmonyOS Next)全栈开发技术的学习路线,包含了鸿蒙开发必掌握的核心知识要点,内容有(ArkTS、ArkUI开发组件、Stage模型、多端部署、分布式应用开发、WebGL、元服务、OpenHarmony多媒体技术、Napi组件、OpenHarmony内核、OpenHarmony驱动开发、系统定制移植等等)鸿蒙(HarmonyOS NEXT)技术知识点。
《鸿蒙 (Harmony OS)开发学习手册》(共计892页)
如何快速入门?
1.基本概念
2.构建第一个ArkTS应用
3.……
开发基础知识:
1.应用基础知识
2.配置文件
3.应用数据管理
4.应用安全管理
5.应用隐私保护
6.三方应用调用管控机制
7.资源分类与访问
8.学习ArkTS语言
9.……
基于ArkTS 开发
1.Ability开发
2.UI开发
3.公共事件与通知
4.窗口管理
5.媒体
6.安全
7.网络与链接
8.电话服务
9.数据管理
10.后台任务(Background Task)管理
11.设备管理
12.设备使用信息统计
13.DFX
14.国际化开发
15.折叠屏系列
16.……
鸿蒙开发面试真题(含参考答案)
OpenHarmony 开发环境搭建
《OpenHarmony源码解析》
- 搭建开发环境
- Windows 开发环境的搭建
- Ubuntu 开发环境搭建
- Linux 与 Windows 之间的文件共享
- ……
- 系统架构分析
- 构建子系统
- 启动流程
- 子系统
- 分布式任务调度子系统
- 分布式通信子系统
- 驱动子系统
- ……
OpenHarmony 设备开发学习手册