一、內核鏈表基礎
1. 什么是 Linux 內核鏈表？
Linux 內核鏈表是一種高效的 雙向循環鏈表，廣泛應用于內核模塊開發中，用于管理數據結構。每個節點通過指針連接前一個和后一個元素，實現插入和刪除的高性能。
2. 鏈表的定義與初始化
在 Linux 內核中，鏈表的實現依賴于 struct list_head 結構體，定義在頭文件 <linux/list.h> 中：
struct list_head {
struct list_head *next, *prev;
};
為了在自定義結構體中集成鏈表，只需在結構體中包含 list_head 成員即可：
struct my_data {
int value;
struct list_head list;
}
鏈表初始化使用如下宏：
LIST_HEAD(my_list); // 靜態初始化
// 或者
INIT_LIST_HEAD(&my_list); // 動態初始化
這兩種方式都將 list.next 和 list.prev 指向自身，構成一個空的循環鏈表。
注意：內核鏈表已經將增刪查改封裝好了，開發者只需要聚焦于數據部分。
3. 內核鏈表設計思想
普通鏈表將數據和節點結構緊耦合。
內核鏈表則通過將鏈表節點作為結構體中的一個字段，從而實現結構體與鏈表解耦。
常用宏如下：
offsetof()：用于計算某個成員在結構體中的偏移量。container_of()：用于通過結構體成員地址獲取整個結構體指針。
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
4. 常用鏈表操作宏與函數
| 功能 | 宏 / 函數名稱 | 說明 |
|---|---|---|
| 添加節點 | list_add / list_add_tail | 添加到鏈表頭/尾 |
| 刪除節點 | list_del | 將節點從鏈表中移除 |
| 遍歷鏈表 | list_for_each | 遍歷每一個節點（通用） |
| 遍歷鏈表 | list_for_each_entry | 遍歷包含結構體的鏈表 |
5. 使用鏈表需注意的要點
內存管理：新增節點前需手動分配內存；刪除節點后應釋放。
線程安全：多線程環境下需加鎖。
性能考量：鏈表適合插入/刪除頻繁場景，但查找效率低。
二、棧（Stack）
1. 基本定義
棧是一種 只允許在一端（棧頂）進行插入和刪除操作 的線性結構，遵循 后進先出（LIFO） 原則。
在 C 語言中，我們通常用動態內存（堆區）來實現線性棧結構。
2. 結構特點
棧頂（top）：允許插入/刪除的一端。
棧底（bottom）：固定不動的一端。
空棧：棧中無任何數據元素。
3. 棧的類型
滿增棧：棧滿時從低地址向高地址增長。
空減棧：從高地址向低地址擴展。
實際實現時通常選擇一種邏輯來處理棧頂移動。
📌 示例說明：
棧空間從底部開始增長，壓棧操作使 top++，出棧使 top--。如果 top 達到容量限制，表示棧已滿。
4. 棧的應用場景
遞歸求解 / 回溯問題
表達式求值（符號優先級）
函數調用管理（程序棧幀）
5. 棧的基本操作代碼
#include <stdio.h>
#include "stack.h"
#include <stdlib.h>Stack *creatStack()
{Stack *pstack = malloc(sizeof(Stack));if(pstack == NULL){printf("malloc error\n");return NULL;}pstack->ptop = NULL;pstack->clen = 0;return pstack;
}int IsEmptyStack(Stack *pstack)
{return NULL == pstack->ptop;
}
int pushStack(Stack *pstack, DataType data)
{StNode *pnode = malloc(sizeof(StNode));if(NULL == pnode){printf("malloc error\n");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = pstack->ptop;pstack->ptop = pnode;pstack->clen++;return 1;
}/*** @brief 出棧，且出棧之前保存棧頂的元素，通過主函數定義的dadatype類型返回改后的數值* * @param pstack 棧頭指針* @param data 返回的棧頂元素的值* @return int 成功出棧返回1，失敗為0*/
int popStack(Stack *pstack, DataType *data)
{if(IsEmptyStack(pstack)){return -1;}StNode *temp = pstack->ptop;*data = temp->data;pstack->ptop = temp->pnext;free(temp);pstack->clen--;return 1;
}/*** @brief Get the Stack Top object* * @param pstack * @param data * @return int */
int getStackTop(Stack *pstack, DataType *data)
{if(IsEmptyStack(pstack)){return -1;}*data = pstack->ptop->data;return 1;
}void printStack(Stack *pstack)
{if(IsEmptyStack(pstack)){return ;}StNode *temp = pstack->ptop;while(temp){printf("%d ", temp->data);temp = temp->pnext;}puts("");return ;
}void destroyStack(Stack **pstack)
{StNode *temp = (*pstack)->ptop;while(temp){(*pstack)->ptop = temp->pnext;free(temp);temp = (*pstack)->ptop;}free(*pstack);*pstack = NULL;
}三、隊列（Queue）
1. 基本定義
隊列是一種**先進先出（FIFO）**的數據結構，特點是：
從 隊尾（tail） 進入數據
從 隊頭（head） 移除數據
2. 隊列的應用場景
緩沖區管理
數據包調度
多任務之間的通信機制
3. 循環隊列（環形隊列）
為避免頻繁移動數據，可將隊列邏輯設計為循環結構。即：利用數組，頭尾指針移動時利用求余操作形成環形效果。
next = (tail + 1) % MAX_LEN;
判斷條件：
| 隊列狀態 | 條件 |
|---|---|
| 隊空 | head == tail |
| 隊滿 | (tail + 1) % MAX == head |
4. 隊列的類型
順序隊列（數組實現）
鏈式隊列（鏈表實現，擴展性強）
5. 鏈表型隊列的代碼
#include <stdio.h>
#include "linkqueue.h"
#include <stdlib.h>LQueue *creatQLink()
{LQueue *plink = malloc(sizeof(LQueue));if(NULL == plink){fprintf(stderr, "malloc error\n");return NULL;}plink->phead = NULL;plink->ptail = NULL;plink->clen = 0;return plink;
}int isEmptyLQueue(LQueue *plink)
{return NULL == plink->phead;
}int pushLQueue(LQueue *plink, DataType data)
{LQNode *pnode = malloc(sizeof(LQNode));if(pnode == NULL){fprintf(stderr, "malloc error\n");return -1;}pnode->data = data;pnode->pnext = NULL;if(isEmptyLQueue(plink)){plink->phead = pnode;plink->ptail = pnode;plink->clen++;}else{plink->ptail->pnext = pnode;plink->ptail = pnode;plink->clen++;}return 0;
}int popLQueue(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr,"is empty lqueue\n");return -1;}LQNode *temp = plink->phead;plink->phead = temp->pnext;if(NULL == temp->pnext){plink->ptail = NULL;}free(temp);plink->clen--;return 0;
}LQNode* getLQueueHeadNode(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr, "empty Lqueue\n");return NULL;}return plink->phead;
}void printLQueue(LQueue *plink)
{if(isEmptyLQueue(plink)){fprintf(stderr, "empty lqueue\n");return ;}LQNode *temp = plink->phead;while(temp){printf("%d ", temp->data);temp = temp->pnext;}puts("");return ;
}void destroyLQueue(LQueue **plink)
{LQNode *temp = (*plink)->phead;while(temp){(*plink)->phead = temp->pnext;free(temp);temp = (*plink)->phead;}free(*plink);*plink = NULL;return ;
}
