朝花夕拾-鏈表（二）

来源:https://www.cnblogs.com/mylibs/archive/2022/12/07/c-generic-linked-list-2.html
-Advertisement-
Play Games

"Good code is its own best documentation." - Steve McConnell “好代碼本身就是最好的文檔。” —— 史蒂夫·麥克康奈爾 0x00 大綱 0x01 前言 數據與結構的解耦 在上篇文章，我們通過將鏈表的節點放在具體數據類型的結構體內，這樣，抽象 ...


"Good code is its own best documentation." - Steve McConnell

“好代碼本身就是最好的文檔。” —— 史蒂夫·麥克康奈爾

0x00 大綱

目錄

0x01 前言

數據與結構的解耦

在上篇文章，我們通過將鏈表的節點放在具體數據類型的結構體內，這樣，抽象（鏈表結構）不再依賴於細節（數據類型），細節（數據類型）依賴於抽象（鏈表結構），利用依賴倒置的思想，完成了數據與結構的解耦，進而實現了通用的鏈表。

offsetof

offsetof 是定義在C標準庫頭文件<stddef.h>中的一個巨集，它會生成一個類型為size_t的無符號整型，代表一個結構成員相對於結構體起始的位元組偏移量（offset）。

container_of

cotainer_of返回的是結構體成員所在結構體的起始地址（指針）,它的原理是用成員變數的起始地址減去成員變數在結構體內的偏移量（用offsetof求得）。

通用鏈表

有了上面三個理論基礎，我們就具備了創建通用鏈表的條件。下麵將通過具體的代碼來演示如何構造和使用這樣的鏈表結構，全程圖解，包你學會。

0x02 鏈表節點

我們的通用鏈表是一個雙向迴圈鏈表，它由一個鏈表頭節點list_head和若幹個位於結構體中的中間節點list_node（註意不包括數據域部分）構成。

我們定義了一個名為struct list_head的結構體類型作為我們的鏈表節點，它包含一個指向前驅節點的指針*prev和一個指向後繼節點的指針*next。同時，為了方便後續的編碼和增強代碼的可讀性，又定義了list_head和list_node兩個結構體類型別名，它們是同一種數據類型的不同名稱。

typedef struct list_head
{
    struct list_head *next, *prev;
} list_head, list_node;

下麵的代碼簡單說明瞭這種方法給我們帶來的語義上的便利，後面的代碼示例將延續這樣的風格。

list_head head;// 等價於 struct list_head head;
list_node node;// 等價於 struct list_head node;

0x03 創建鏈表

/**
 * 初始化一個鏈表（頭）節點，它的前驅和後繼指針都指向自己
 * @param list: 需要初始化的節點的指針
 * @return void
**/
static inline void list_init(list_head *list)
{
    list->next = list;
    list->prev = list;
}

創建鏈表

0x04 插入節點

任意位置的插入

/**
 * 將節點entry插入到prev和next之間
 * @param entry: 新節點的指針
 * @param prev: 指向插入位置前驅節點的指針
 * @param next: 指向插入位置後繼節點的指針
 * @return void
**/
static inline void __list_add(list_node *entry,
                              list_node *prev,
                              list_node *next)
{
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
}

插入到最前

/**
 * 將節點entry插入到頭節點之後
 * 頭插，新節點成為第一個節點
 * @param entry: 指向新節點的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
static inline void list_add_head(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head, head->next);
}

插入節點（頭）

插入到最後

/**
 * 將節點entry插入到頭節點之前
 * 尾插，新節點成為最後一個節點
 * @param entry: 指向新節點的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
static inline void list_add_tail(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head->prev, head);
}

插入節點（尾）

0x05 刪除節點

/**
 * 刪除節點
 * @param prev: 被刪除節點的前驅指針
 * @param head: 被刪除節點的後繼指針
 * @return void
**/
static inline void __list_del(list_node * prev,
                              list_node * next)
{
    next->prev = prev;
    prev->next = next;
}
/**
 * 刪除節點，並將其前驅指針和後繼指針指向NULL
 * @param prev: 指向被刪除節點的指針
 * @return void
**/
static inline void list_del(list_node *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = entry->next = NULL;
}

刪除節點

可以看到，由於節點本身並不存儲數據，所以，在刪除鏈表節點的時候，也就不用考慮對數據域進行記憶體釋放的操作。

0x06 替換節點

/**
 * 替換節點
 * @param old: 指向被替換節點的指針
 * @param entry: 指向新節點的指針
 * @return void
**/
static inline void list_replace(list_node *old,
                                list_node *entry)
{
    entry->next = old->next;
    entry->next->prev = entry;
    entry->prev = old->prev;
    entry->prev->next = entry;
}

替換節點

0x07 遍歷和獲取節點數據

遍歷鏈表

/**
 * 快速遍歷鏈表（不可進行刪除操作）
 * @param pos: 指向當前節點位置的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
/**
 * 遍歷鏈表（可進行刪除操作）
 * @param pos: 指向當前節點位置的指針
 * @param n: 指向下一節點位置的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)

遍歷鏈表

獲取節點數據

/**
 * 獲得節點所在數據結構體的起始地址（指針）
 * @param ptr: 指向節點的指針
 * @param type: 數據結構體類型
 * @param member: 節點在數據結構體中被定義的變數名稱
 * @return void
**/
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

0x08 小結

將上述的所有基本操作彙總後，得到我們的通用鏈表定義文件list.h（你可以在Linux內核的源碼中找到它，這裡的代碼稍微作了一點修改）：

#ifndef LIST_H
#define LIST_H
#include <stddef.h>
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr)-offsetof(type,member)))
typedef struct list_head
{
    struct list_head *next, *prev;
} list_head, list_node;
/**
 * 初始化一個鏈表（頭）節點，它的前驅和後繼指針都指向自己
 * @param list: 需要初始化的節點的指針
 * @return void
**/
static inline void list_init(list_head *list)
{
    list->next = list;
    list->prev = list;
}
/**
 * 將節點entry插入到prev和next之間
 * @param entry: 新節點的指針
 * @param prev: 指向插入位置前驅節點的指針
 * @param next: 指向插入位置後繼節點的指針
 * @return void
**/
static inline void __list_add(list_node *entry,
                              list_node *prev,
                              list_node *next)
{
    next->prev = entry;
    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
}
/**
 * 將節點entry插入到頭節點之後
 * 頭插，新節點成為第一個節點
 * @param entry: 指向新節點的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
static inline void list_add_head(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head, head->next);
}
/**
 * 將節點entry插入到頭節點之前
 * 尾插，新節點成為最後一個節點
 * @param entry: 指向新節點的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
static inline void list_add_tail(list_node *entry,
                                 list_head *head)
{
    __list_add(entry, head->prev, head);
}
/**
 * 刪除節點
 * @param prev: 被刪除節點的前驅指針
 * @param head: 被刪除節點的後繼指針
 * @return void
**/
static inline void __list_del(list_node * prev,
                              list_node * next)
{
    next->prev = prev;
    prev->next = next;
}
/**
 * 刪除節點，並將其前驅指針和後繼指針指向NULL
 * @param prev: 指向被刪除節點的指針
 * @return void
**/
static inline void list_del(list_node *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = entry->next = NULL;
}
/**
 * 替換節點
 * @param old: 指向被替換節點的指針
 * @param entry: 指向新節點的指針
 * @return void
**/
static inline void list_replace(list_node *old,
                                list_node *entry)
{
    entry->next = old->next;
    entry->next->prev = entry;
    entry->prev = old->prev;
    entry->prev->next = entry;
}
/**
 * 判斷迴圈雙鏈表是否為空（只有頭節點）
 * @param head: 指向頭節點的指針
 * @return void
**/
static inline int list_empty(const list_head *head)
{
    return head->next == head;
}
/**
 * 快速遍歷鏈表（不可進行刪除操作）
 * @param pos: 指向當前節點位置的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)
/**
 * 遍歷鏈表（可進行刪除操作）
 * @param pos: 指向當前節點位置的指針
 * @param n: 指向下一節點位置的指針
 * @param head: 指向頭節點的指針
 * @return void
**/
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
        pos = n, n = pos->next)
/**
 * 獲得節點所在數據結構體的起始地址（指針）
 * @param ptr: 指向節點的指針
 * @param type: 數據結構體類型
 * @param member: 節點在數據結構體中被定義的變數名稱
 * @return void
**/
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)
#endif // LIST_H

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • CSS Margin中5個經典佈局解決方案，重難點知識，記得收藏複習
    前幾天我在面試前端開發同學的時候，有問到關於margin基礎佈局相關內容的過程中，發現很多同學基本解釋不清楚，今天剛好有點時間就整理了一篇筆記出來。就以下5點在CSS佈局經常會用到的經典佈局解決方案。 css中margin外邊距（重疊）合併現象 css中margin外邊距穿透現象 css中margi ...
  • 記錄--微信小程式獲取用戶信息的最新方法記錄
    這裡給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 微信小程式獲取用戶信息的幾種方式 以下三種方式都無法獲取到用戶的openID 1. 開放組件獲取用戶信息<open-data></open-data>該功能已無效 該組件的type屬性根據不同的屬性值可以展示用戶不同的信息 該方式不需要授 ...
  • echart繪製中國地圖及各省份地圖
    示例： 地圖文件下載地址：https://gitcode.net/mirrors/fuhang-lm/echarts?utm_source=csdn_github_accelerator&from_codechina=yes 這裡以北京市地圖為例，如果是其他省份或者全國，下載對應的js文件並引入系統 ...
  • 跨端開發浪潮中的變與不變
    自 90 年代初開啟 PC 時代以來，隨著移動網路的快速普及，在 2010 年左右，進入移動時代、IOT 時代，各種移動互聯設備不斷涌現，除了最常見的 PC、Pad、智能手機外，它還可能是小小的一塊智能手錶，也可以是一個大屏終端。智能設備層出不窮，填滿了人們生活的各個角落，設備的系統類型、屏幕大小等... ...
  • 力扣14 尋找字元串數組中最長公共首碼
    力扣14 尋找字元串數組中最長公共首碼 題目： 編寫一個函數來查找字元串數組中的最長公共首碼。 如果不存在公共首碼，返回空字元串 ""。 示例 1： 輸入：strs = ["flower","flow","flight"] 輸出："fl" 示例 2： 輸入：strs = ["dog","raceca ...
  • C++入門級基礎知識彙總
    知識來源：https://www.imooc.com/learn/1304 https://www.runoob.com/cplusplus/cpp-tutorial.html 編程第一步導入頭文件： #include <stdio.h> std=standard io= into out #inc ...
  • python中的函數進階
    1.局部變數和全局變數 在函數外定義的不可變數據類型，在函數裡面是可讀不可寫在函數外定義的可變數據類型，在函數裡面可讀可寫不可變類型傳入函數，進行的操作不會影響到外面的變數但是當我們聲明一個變數為全局變數後，進行的操作會影響到函數外的變數 可變數據類型，傳入和直接使用都會改變原本的數據不可變數據類型 ...
  • OpenGL 透明度
    目錄 一.OpenGL 透明度 1.IOS Object-C 版本 1.Windows OpenGL ES 版本 2.Windows OpenGL 版本 二.OpenGL 透明度 GLSL Shader 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類