1、為何引入鏈表

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

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

通常情況下，最簡單易懂的做法是，限制最多5個區(qū)域，每個區(qū)域存儲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］;//存儲區(qū)域的數據

/*找到ID為5的區(qū)域，并將數據拷貝出去*/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個區(qū)域，但是每個區(qū)域存儲的數據很少，根本用不到1K。雖然上面的程序已經使用了宏定義，只需要修改宏定義就能實現要求。但這意味著不同的客戶，需要編譯不同的固件。

#define Area_Num 10#define Area_cache 512

這樣的程序存在的問題：

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

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

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

2、鏈表實現

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

對于上面的問題，我們使用鏈表解決，需要配合內存管理才能實現。內存管理這一塊，大家可以自己編寫內存管理驅動，也可以使用C庫的malloc和free函數。如何字節(jié)編寫內存管理驅動不是本文的重點，下文將使用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也就是鏈表結構體的指針，同樣沒有內存空間，在沒有創(chuàng)建新增鏈表之前，它是一個野指針。

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

/*** @brief 動態(tài)區(qū)鏈表初始化* @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下發(fā)一個新的區(qū)域信息后，增加新區(qū)域到鏈表末尾。

/*** @brief 在鏈表末尾增加一個區(qū)域參數* @param Area_Inf 增加的區(qū)域區(qū)參數指針* @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; } //先申請鏈表結構體的空間，因為后續(xù)還要繼續(xù)增加 p-》next_Area_Inf = （Area_List_Inf_Typedef*）malloc（sizeof（Area_List_Inf_Typedef））; if（p-》next_Area_Inf == NULL） return false;//申請不到內存，返回失敗 //指向剛剛申請的空間，并為需要存放的動態(tài)區(qū)信息申請對應的內存 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下發(fā)一個刪除指定ID的區(qū)域命令。

/*** @brief 根據區(qū)域ID刪除動態(tài)區(qū)* @param num 區(qū)域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 根據區(qū)域ID找到鏈表* @param data_p 鏈表指針* @param num 區(qū)域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 刪除所有區(qū)域* */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（“l(fā)ist 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、測試函數

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

/*** @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，就可以看到打印信息