1、為何引入鏈表

在程序中經常面臨一個問題，我們需要保存一定數量的對象，但是對象數目是不確定的，或者說是隨時增加或減少的。這時候最簡單的方法是創建一個足夠大的數組，用來存儲這些對象。我最近開發一個項目就遇到類似的問題，下面我把問題簡化一下。

需求：通過PC下發一些矩形的坐標和寬高信息，每個區域有個ID編號，并在這些矩形內填充一定的數據。

通常情況下，最簡單易懂的做法是，限制最多5個區域，每個區域存儲1K數據。因此設置了這樣的一個結構體（類似于面向對象語言里說的成員屬性）。

typedef struct Area_Inf{ uint8_t ID; uint8_t X; uint8_t Y; uint8_t Width; uint8_t Height; uint8_t data_len;}Area_Inf_Typedef;

然后定義結構體的實體。

#define Area_Num 5#define Area_cache 1024

Area_Inf_Typedef Area_Info［Area_Num］;uint8_t Area_Data［Area_Num*Area_cache］;//存儲區域的數據

/*找到ID為5的區域，并將數據拷貝出去*/void main（）{ uint8_t i; uint8_t data［1024］; for（i = 0;i 《 Area_Num;i++） { if（Area_Info［i］.ID == 5） { memcpy（data，&Area_Data［i*Area_cache ］，Area_Info［i］.data_len）; } }}

上面這種做法是最簡單易懂的，但不靈活，比如有客戶要求10個區域，但是每個區域存儲的數據很少，根本用不到1K。雖然上面的程序已經使用了宏定義，只需要修改宏定義就能實現要求。但這意味著不同的客戶，需要編譯不同的固件。

#define Area_Num 10#define Area_cache 512

這樣的程序存在的問題：

1、在內存資源很緊缺的單片機程序中，當區域數據很少時，這種程序的處理方法浪費了大量的內存空間。

2、數值固定，需要存儲更多區域，即使還有內存，還是需要修改宏定義，重新編譯固件，不靈活。

這時需要引入鏈表來解決這個問題。

2、鏈表實現

鏈表實際上是線性表的鏈式存儲結構，與數組不同的是，它是用一組任意的存儲單元來存儲線性表中的數據，存儲單元不一定是連續的，且鏈表的長度不是固定的，鏈表數據的這一特點使其可以非常的方便地實現節點的插入和刪除操作。鏈表的每個元素稱為一個節點，每個節點都可以存儲在內存中的不同的位置，為了表示每個元素與后繼元素的邏輯關系，以便構成“一個節點鏈著一個節點”的鏈式存儲結構，除了存儲元素本身的信息外，還要存儲其直接后繼信息，因此，每個節點都包含兩個部分，第一部分稱為鏈表的數據區域，用于存儲元素本身的數據信息。

對于上面的問題，我們使用鏈表解決，需要配合內存管理才能實現。內存管理這一塊，大家可以自己編寫內存管理驅動，也可以使用C庫的malloc和free函數。如何字節編寫內存管理驅動不是本文的重點，下文將使用C庫的malloc和free函數進行內存管理。

使用鏈表的方式，在原有的成員屬性結構體的前提上，還要再封裝多一層鏈表管理。以單向鏈表為例：

typedef struct Area_Inf{ uint8_t ID; uint8_t X; uint8_t Y; uint8_t Width; uint8_t Height; uint8_t data_len; uint8_t* Area_Data;}Area_Inf_Typedef;

typedef struct Area_List_Inf{ Area_Inf_Typedef *Area_Inf; struct Area_List_Inf *next_Area_Inf; //用于指向下一個}Area_List_Inf_Typedef;

Area_List_Inf_Typedef *Head_Area_List; //鏈表的頭指針

由于在定義的時候，只定義了一個頭指針，那么它也只是個指向了Area_List_Inf_Typedef也就是鏈表結構體的指針，同樣沒有內存空間，在沒有創建新增鏈表之前，它是一個野指針。

所以，在具體應用之前，需要先執行一個初始化操作，也就是申請空間給鏈表管理結構體，然后頭指針指向這個空間。

/*** @brief 動態區鏈表初始化* @return int */int Area_List_Init（void）{ //申請鏈表類型大小的空間，并讓頭指針指向它 Head_Area_List = （Area_List_Inf_Typedef*）malloc（sizeof（Area_List_Inf_Typedef））; if（Head_Area_List == NULL） return false; //同時要標記下一個信息為空 Head_Area_List-》next_Area_Inf = NULL; return true;}

通過PC下發一個新的區域信息后，增加新區域到鏈表末尾。

/*** @brief 在鏈表末尾增加一個區域參數* @param Area_Inf 增加的區域區參數指針* @return int */int Add_Area_ToList（Area_Inf_Typedef *Area_Inf）{ Area_List_Inf_Typedef *p = Head_Area_List; while（p-》next_Area_Inf！=NULL） { p = p-》next_Area_Inf; } //先申請鏈表結構體的空間，因為后續還要繼續增加 p-》next_Area_Inf = （Area_List_Inf_Typedef*）malloc（sizeof（Area_List_Inf_Typedef））; if（p-》next_Area_Inf == NULL） return false;//申請不到內存，返回失敗 //指向剛剛申請的空間，并為需要存放的動態區信息申請對應的內存 p = p-》next_Area_Inf; p-》Area_Inf = （Area_Inf_Typedef*）malloc（sizeof（Area_Inf_Typedef））; if（p-》Area_Inf == NULL） { free（p）;//由于申請失敗，先前申請的鏈表空間也要釋放 return false; } memcpy（p-》Area_Inf，Area_Inf，sizeof（Area_Inf_Typedef））; /*拷貝數據*/ p-》Area_Inf-》Area_Data = （uint8_t*）malloc（Area_Inf-》data_len）; if（p-》Area_Inf-》Area_Data == NULL） { free（p-》Area_Inf）; free（p）; return false; } memcpy（p-》Area_Inf-》Area_Data，Area_Inf-》Area_Data，Area_Inf-》data_len）; //標記這個鏈表的尾部 p-》next_Area_Inf=NULL; //添加成功 return true;}

通過PC下發一個刪除指定ID的區域命令。

/*** @brief 根據區域ID刪除動態區* @param num 區域ID* @return int */int Delete_Area_Accordingn_ID（int num）{ int res = false; Area_List_Inf_Typedef *p = Head_Area_List; while（p-》next_Area_Inf！=NULL） { Area_List_Inf_Typedef *temp = p; p = p-》next_Area_Inf; if（p-》Area_Inf-》ID == num）//匹配到對應的值 { temp-》next_Area_Inf = p-》next_Area_Inf; //釋放內存空間 free（p-》Area_Inf-》Area_Data）; free（p-》Area_Inf）; free（p）; p=temp; res = true; } } return res;}

看了上面的驅動函數，相信大家已經明白，大家可以自行編寫一些驅動，下面我實現的三個簡單函數。

/*** @brief 根據區域ID找到鏈表* @param data_p 鏈表指針* @param num 區域ID編號* @return int */int Find_Area_According_ID（Area_Inf_Typedef **data_p，int num）{ Area_List_Inf_Typedef *p = Head_Area_List; while（p-》next_Area_Inf！=NULL） { p = p-》next_Area_Inf; if（p-》Area_Inf-》ID == num）//匹配到對應的值 { *data_p = p-》Area_Inf; return true; } } return false;}/*** @brief 刪除所有區域* */int Delete_All_Area（void）{ int res = false; Area_List_Inf_Typedef *p = Head_Area_List; while（p-》next_Area_Inf！=NULL） { Area_List_Inf_Typedef *temp = p; p = p-》next_Area_Inf; temp-》next_Area_Inf = p-》next_Area_Inf; //釋放內存空間 free（p-》Area_Inf-》Area_Data）; free（p-》Area_Inf）; free（p）; p=temp; res = true; } return res;}/*** @brief 打印鏈表信息* */void Printf_Area_Inf（void）{ int i=0; Area_List_Inf_Typedef *p = Head_Area_List; printf（“list ID X Y Width Height Area_Data

”）; while（p-》next_Area_Inf！=NULL） { p = p-》next_Area_Inf; printf（“ %d %d %d %d %d %d %s

”，i，p-》Area_Inf-》ID，p-》Area_Inf-》X，p-》Area_Inf-》Y，p-》Area_Inf-》Width，p-》Area_Inf-》Height，p-》Area_Inf-》Area_Data）; i++; } printf（“----------------------end-----------------------

”）;}

3、測試函數

下面編寫一個測試函數，可以測試，鏈表的初始化，增加一個區域，刪除指定區域，根據ID返回區域信息，刪除所有區域接口。

/*** @brief 鏈表測試函數* */void list_main（）{ int i，j; Area_Inf_Typedef temp; Area_Inf_Typedef **data_p; data_p = NULL; printf（“------------------List test---------------------

”）; if（！Area_List_Init（ ）） { printf（“Memory fail.。

”）; } for（i=0;i《5;i++） { temp.ID = i; temp.X = 5+i; temp.Y = i; temp.Width = 10+i; temp.Height = 10+i; temp.data_len = i+1; temp.Area_Data = （uint8_t*）malloc（temp.data_len+1）; for（j=0;j《temp.data_len;j++） { temp.Area_Data［j］ = j+0x30; } temp.Area_Data［j］ = 0; if（！Add_Area_ToList（&temp）） { printf（“Add Area %d Area_Info fail

”，i）; } } Printf_Area_Inf（）; printf（“

-------------Delete ID of Area is 3-------------

”）; Delete_Area_Accordingn_ID（3）; Printf_Area_Inf（）; temp.ID = 9; temp.data_len = 10; temp.Area_Data = （uint8_t*）malloc（temp.data_len+1）; for（j=0;j《temp.data_len;j++） { temp.Area_Data［j］ = j+0x30; } temp.Area_Data［j］ = 0; if（！Add_Area_ToList（&temp）） { printf（“Add Area %d info fail

”，temp.ID）; } printf（“

--------------Add ID of Area is 9---------------

”）; Printf_Area_Inf（）; Find_Area_According_ID（data_p，2）; temp.ID = （*data_p）-》ID; Delete_All_Area（）; printf（“

--------------Delete All Area-------------------

”）; Printf_Area_Inf（）; while（1）;}

測試結果

如果大家手中有板子可以調試，可以看《一文了解串口打印》文章，使用串口打印。如果臨時沒有板子可以debug，可以模擬測試，IAR設置如下：

選擇Simulator調試

打開View-》TerminalI/O，就可以看到打印信息

編輯：lyn