鏈表-雙向非通用鏈表
- 2020 年 10 月 10 日
- 筆記
- /label/dataStructure, /label/lzm, C語言, 數據結構
前言
- 20201010
- 在閱讀 RTOS LiteOS 內核源碼時發現該內核使用的鏈表時通用鏈表，而 FreeRTOS 內核使用的時非通用鏈表，所以，有必要發布一下關於鏈表實現的筆記。
- 以下內容為個人筆記，涉及一些非專業辭彙，敬請諒解，謝謝。
鏈接
參考
- 上面鏈接
- FreeRTOS 內核源碼
- 野火
概念
-
正常表達
- 鏈表：
- 鏈表為 C 中一種基礎的數據結構。
- 看成環形晾衣架即可。
- 節點：
- 節點組成鏈表
- 鏈表：
-
自理解概念
- 鏈表：圓形的晾衣架
- 節點：掛鉤
- 包含上一個
- 下一個
- 鉤子等其它需要的資訊
- 襪子：掛在到 鉤子 的東西
- 包含被鉤子
- 襪子攜帶的資訊
-
通用鏈表與非通用鏈表的區別
- 通用鏈表節點內容很少一般只有 上一個 和 下一個。
- 通用鏈表節點被放到資訊結構體中，通過偏移找到所在的結構體（即是通過偏移找到襪子頭）
- 而非通用鏈表是在節點中攜帶資訊結構體的指針的（即是節點就攜帶資訊）。
- 別人通俗理解，讀者不必理會本小點
- 通用鏈表是把襪子放到晾衣架的圓形圈上，襪子與圓形圈接觸部分為襪子接待的節點。（資訊攜帶節點）
- 非通用鏈表是。（節點攜帶資訊）
筆錄草稿
雙向鏈表
-
雙向鏈表理解圖
-
原理：鏈表包括 根節點 和 普通節點
-
根節點 主要管理鏈表的，一般包括
- 上一個
- 下一個
- 存在多少個等資訊
-
普通節點 主要用於鉤住襪子（即是攜帶資訊）
-
節點及節點結構體程式碼
- 普通節點
- 存放節點資訊
- 掛載東西（掛鉤），如掛載襪子等等
/*
* The linked list node
*/
struct LIST_ITEM_LSS_T
{
struct LIST_ITEM_LSS_T * pxNext; // 下一個
struct LIST_ITEM_LSS_T * pxPrevious; // 上一個
/* 節點屬性，（根據個人需求增減以下內容） */
uint32_t xItemValue; // 記號值，一般用於排序
void * pvOwner; // 掛鉤，即攜帶的資訊
void * pvContainer; // 歸屬，即屬於哪一個鏈表
};
typedef struct LIST_ITEM_LSS_T listItem_t;
- root節點（鏈表點）
- 存放鏈表的資訊
- 有一個mini節點，用於駁接和定位（相當於位置校準點），不掛載如何東西，且簡潔為妙
- mini節點的記號值在雙向鏈表中為最大值，因為最大是尾也是頭。
- mini節點的記號值在雙向鏈表中為最大值，因為最大是尾也是頭。
/* mini 節點結構體 */
struct LIST_MINI_ITEM_LSS_T
{
/* 指向，（根據單、雙鏈表刪減以下內容） */
struct node *pxPrevious; // 上一個節點
struct node *pxNext; // 下一個節點
/* 節點屬性，（根據個人需求增減以下內容） */
uint32_t xItemValue; // 記號值，在雙向鏈表中為最大值
};
typedef struct LIST_MINI_ITEM_LSS_T ListMiniItem_t;
/* 鏈表結構體，即根節點 */
struct LIST_LSS_T
{
/* 節點屬性，（根據個人需求增減以下內容） \*/
uint32_t uxNumberOfItems; // 節點數，統計粘附在本鏈表上的節點數
struct LIST_ITEM_LSS_T * pxIndex; // 索引，鏈表索引，指向鏈表中的某個節點
struct LIST_MINI_ITEM_LSS_T xListEnd; // 鏈表根節點
};
typedef struct LIST_LSS_T List_t;
鏈表操作的函數程式碼
鏈表初始化函數
- 鏈表索引指向該鏈表的尾節點（尾節點，即也是頭節點）
- 鏈表尾節點記號值賦值為最大值（根節點包含尾節點）
- 初始化尾節點的上一個及下一個，分別都指向**尾節點
- 初始化節點總數為 0。
/**
* @brief 鏈表初始化
* @param
* @retval
* @author lzm
*/
void listInit(list_t * const list)
{
/* 索引指向最後：尾就是頭 */
list->pxIndex = (listItem_t *) &(list->xListEnd);
/* 鏈表最大值 */
list->xListEnd.xItemValue = lssLIST_MAX_VALUE;
list->xListEnd.pxNext = ( listItem_t * ) &( list->xListEnd );
list->xListEnd.pxPrevious = ( listItem_t * ) &( list->xListEnd );
list->uxNumberOfItems = (lssLIST_BASE_TYPE)0U;
}
節點初始化函數
- 初始化節點攜帶的資訊為空
/**
* @brief 節點初始化
* @param
* @retval
* @author lzm
*/
void listItemInit(listItem_t * const item)
{
item->pvContainer = NULL;
}
節點插入鏈表尾部函數
注意：需要插入的節點以下稱為節點A
- 獲取索引（索引即游標，也就是該鏈表當前指向的節點）
- 節點A的下一個指向索引節點，
- 節點A的前一個指向索引節點的前一個
- 索引節點前一個的下一個指向節點A
- 索引節點的前一個指向節點A
- 設置節點A歸屬於哪個鏈表
- 鏈表節點計數值 +1
/**
* @brief 插入鏈表尾部（*雙向鏈表沒有絕對的頭尾，此處是以游標為參考物*）
* @param
* @retval
* @author lzm
*/
void listInsertEnd( list_t * const pxList, listItem_t * const pxNewListItem )
{
listItem_t * const pxIndex = pxList->pxIndex;
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
/* Remember which list the item is in. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
節點有序插入鏈表函數
注意：需要插入的節點以下稱為節點A
- 獲取新節點記號值
2.找出需要插入的位置- 如果記號值為鏈表中最大值（即和尾節點的記號值相等），則取出尾節點的前一個節點作為參考節點
- 如果記號值不為鏈表中最大值，則從尾節點開始找，直至找到當前節點的下一個節點的記號值為大於 節點A的記號值（即是在鏈表中找出紅框節點B）
- 插入節點
- 節點A（節點A 為需要插入的節點）的下一個指向索引節點，
- 節點A的前一個指向節點B的前一個
- 節點B的前一個的下一個指向節點A
- 節點B的前一個指向節點A
- 設置節點A歸屬於哪個鏈表
- 鏈表節點計數值 +1
/**
* @brief 按記號值值插入
* @param
* @retval
* @author lzm
*/
void listInsert( list_t * const pxList, listItem_t * const pxNewListItem )
{
listItem_t *pxIterator;
const lssLIST_BASE_TYPE xValueOfInsertion = pxNewListItem->xItemValue; // 獲取新節點記號值
/* 按順序尋找 */
if( xValueOfInsertion == lssLIST_MAX_VALUE )
{
pxIterator = pxList->xListEnd.pxPrevious;
}
else
{
for( pxIterator = ( listItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */
{
/* There is nothing to do here, just iterating to the wanted insertion position. */
}
}
pxNewListItem->pxNext = pxIterator->pxNext;
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
/* Remember which list the item is in. This allows fast removal of the
item later. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
從鏈表中刪除函數
注意：被刪除的節點以下稱為節點A
- 獲取鏈表
- 節點A下一個節點的前一個指向節點A的前一個節點
- 節點A前一個節點的下一個指向節點A的下一個節點
- 檢查鏈表索引是否指向了節點A
- 是：索引更新為指向節點A的前一個節點
- 否：跳過
- 清空節點A的鏈表歸屬
- 鏈表節點計數值 -1
- 返回鏈表節點數
/**
* @brief 從鏈表中刪除節點
* @param
* @retval
* @author lzm
*/
uint32_t listRemove( listItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list
item. */
list_t * const pxList = ( list_t * ) pxItemToRemove->pvContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/* Make sure the index is left pointing to a valid item. */
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
源碼集合
- 內含
- 節點及鏈表結構體
- 節點初始化函數
- 鏈表初始化函數
- 節點插入函數
- 刪除節點函數
- 配對掛鉤與襪子函數
- 獲取節點資訊函數
- 獲取記號值函數
- 獲取第一個節點的節點值函數
- 獲取鏈表的入口節點函數
- 獲取下一個節點函數
- 獲取鏈表最後一個節點（尾節點）函數
- 判斷鏈表是否為空函數
- 獲取鏈表當前節點總數函數
- 獲取鏈表索引指向的下一個節點函數
- 跳轉到非通用鏈表完整C語言源碼即可
