1、為何引入鏈表

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

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

通常情況下，最簡(jiǎn)單易懂的做法是，限制最多5個(gè)區(qū)域，每個(gè)區(qū)域存儲(chǔ)1K數(shù)據(jù)。因此設(shè)置了這樣的一個(gè)結(jié)構(gòu)體（類似于面向?qū)ο笳Z言里說的成員屬性）。

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;

然后定義結(jié)構(gòu)體的實(shí)體。

#define Area_Num 5#define Area_cache 1024

Area_Inf_Typedef Area_Info［Area_Num］;uint8_t Area_Data［Area_Num*Area_cache］;//存儲(chǔ)區(qū)域的數(shù)據(jù)

/*找到ID為5的區(qū)域，并將數(shù)據(jù)拷貝出去*/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）; } }}

上面這種做法是最簡(jiǎn)單易懂的，但不靈活，比如有客戶要求10個(gè)區(qū)域，但是每個(gè)區(qū)域存儲(chǔ)的數(shù)據(jù)很少，根本用不到1K。雖然上面的程序已經(jīng)使用了宏定義，只需要修改宏定義就能實(shí)現(xiàn)要求。但這意味著不同的客戶，需要編譯不同的固件。

#define Area_Num 10#define Area_cache 512

這樣的程序存在的問題：

1、在內(nèi)存資源很緊缺的單片機(jī)程序中，當(dāng)區(qū)域數(shù)據(jù)很少時(shí)，這種程序的處理方法浪費(fèi)了大量的內(nèi)存空間。

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

這時(shí)需要引入鏈表來解決這個(gè)問題。

2、鏈表實(shí)現(xiàn)

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

對(duì)于上面的問題，我們使用鏈表解決，需要配合內(nèi)存管理才能實(shí)現(xiàn)。內(nèi)存管理這一塊，大家可以自己編寫內(nèi)存管理驅(qū)動(dòng)，也可以使用C庫的malloc和free函數(shù)。如何字節(jié)編寫內(nèi)存管理驅(qū)動(dòng)不是本文的重點(diǎn)，下文將使用C庫的malloc和free函數(shù)進(jìn)行內(nèi)存管理。

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

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; //用于指向下一個(gè)}Area_List_Inf_Typedef;

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

由于在定義的時(shí)候，只定義了一個(gè)頭指針，那么它也只是個(gè)指向了Area_List_Inf_Typedef也就是鏈表結(jié)構(gòu)體的指針，同樣沒有內(nèi)存空間，在沒有創(chuàng)建新增鏈表之前，它是一個(gè)野指針。

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

/*** @brief 動(dòng)態(tài)區(qū)鏈表初始化* @return int */int Area_List_Init（void）{ //申請(qǐng)鏈表類型大小的空間，并讓頭指針指向它 Head_Area_List = （Area_List_Inf_Typedef*）malloc（sizeof（Area_List_Inf_Typedef））; if（Head_Area_List == NULL） return false; //同時(shí)要標(biāo)記下一個(gè)信息為空 Head_Area_List-》next_Area_Inf = NULL; return true;}

通過PC下發(fā)一個(gè)新的區(qū)域信息后，增加新區(qū)域到鏈表末尾。

/*** @brief 在鏈表末尾增加一個(gè)區(qū)域參數(shù)* @param Area_Inf 增加的區(qū)域區(qū)參數(shù)指針* @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; } //先申請(qǐng)鏈表結(jié)構(gòu)體的空間，因?yàn)楹罄m(xù)還要繼續(xù)增加 p-》next_Area_Inf = （Area_List_Inf_Typedef*）malloc（sizeof（Area_List_Inf_Typedef））; if（p-》next_Area_Inf == NULL） return false;//申請(qǐng)不到內(nèi)存，返回失敗 //指向剛剛申請(qǐng)的空間，并為需要存放的動(dòng)態(tài)區(qū)信息申請(qǐng)對(duì)應(yīng)的內(nèi)存 p = p-》next_Area_Inf; p-》Area_Inf = （Area_Inf_Typedef*）malloc（sizeof（Area_Inf_Typedef））; if（p-》Area_Inf == NULL） { free（p）;//由于申請(qǐng)失敗，先前申請(qǐng)的鏈表空間也要釋放 return false; } memcpy（p-》Area_Inf，Area_Inf，sizeof（Area_Inf_Typedef））; /*拷貝數(shù)據(jù)*/ 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）; //標(biāo)記這個(gè)鏈表的尾部 p-》next_Area_Inf=NULL; //添加成功 return true;}

通過PC下發(fā)一個(gè)刪除指定ID的區(qū)域命令。

/*** @brief 根據(jù)區(qū)域ID刪除動(dòng)態(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）//匹配到對(duì)應(yīng)的值 { temp-》next_Area_Inf = p-》next_Area_Inf; //釋放內(nèi)存空間 free（p-》Area_Inf-》Area_Data）; free（p-》Area_Inf）; free（p）; p=temp; res = true; } } return res;}

看了上面的驅(qū)動(dòng)函數(shù)，相信大家已經(jīng)明白，大家可以自行編寫一些驅(qū)動(dòng)，下面我實(shí)現(xiàn)的三個(gè)簡(jiǎn)單函數(shù)。

/*** @brief 根據(jù)區(qū)域ID找到鏈表* @param data_p 鏈表指針* @param num 區(qū)域ID編號(hào)* @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）//匹配到對(duì)應(yīng)的值 { *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; //釋放內(nèi)存空間 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、測(cè)試函數(shù)

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

/*** @brief 鏈表測(cè)試函數(shù)* */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）;}

測(cè)試結(jié)果

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

選擇Simulator調(diào)試

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

編輯：lyn