?

概念

為了性能考慮，嵌入式系統一般使用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) 當前被操作的元素，可能剛操作完，被移除鏈表};

?

結論

在嵌入式開發中，在學習數據結構課程中，在進行OpenHarmony項目開發中，單鏈表都是很重要的，而本文只是其中一個軟件模塊的單鏈表實現。通過對單鏈表的實現的圖示分析，特別是迭代器慣用法的分析，相信讀者對單鏈表以及迭代器的認識都會進一步提升，更詳盡的代碼分析和閱讀留給讀者自己進行，請參考如下代碼文件

https://gitee.com/openharmony/drivers_hdf_core/blob/master/framework/utils/include/hdf_slist.h

https://gitee.com/openharmony/drivers_hdf_core/blob/master/framework/utils/src/hdf_slist.c