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 = https://www.cnblogs.com/Fireflycjd/p/(uint8_t*)malloc(Area_Inf->data_len); if(p->Area_Inf->Area_Data =https://www.cnblogs.com/Fireflycjd/p/= 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\r\n"); while(p->next_Area_Inf!=NULL) { p = p->next_Area_Inf; printf(" %d %d %d %d %d %d %s\r\n",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-----------------------\r\n"); }
3、測驗函式
下面撰寫一個測驗函式，可以測驗，鏈表的初始化，增加一個區域，洗掉指定區域，根據ID回傳區域資訊，洗掉所有區域介面，
/** * @brief 鏈表測驗函式 * */ void list_main() { int i,j; Area_Inf_Typedef temp; Area_Inf_Typedef **data_p; data_p = NULL; printf("------------------List test---------------------\r\n"); if(!Area_List_Init( )) { printf("Memory fail..\r\n"); } 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\r\n",i); } } Printf_Area_Inf(); printf("\r\n-------------Delete ID of Area is 3-------------\r\n"); 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\r\n",temp.ID); } printf("\r\n--------------Add ID of Area is 9---------------\r\n"); Printf_Area_Inf(); Find_Area_According_ID(data_p,2); temp.ID = (*data_p)->ID; Delete_All_Area(); printf("\r\n--------------Delete All Area-------------------\r\n"); Printf_Area_Inf(); while(1); }
測驗結果
IAR和keil工程代碼開源地址：
https://github.com/strongercjd/STM32_Linklist
如果大家手中有板子可以除錯，可以看《一文了解串口列印》文章，使用串口列印，如果臨時沒有板子可以debug，可以模擬測驗，IAR設定如下：
選擇Simulator除錯
打開View->TerminalI/O，就可以看到列印資訊
點擊查看本文所在的專輯，STM32F207教程
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/270501.html
標籤：嵌入式
上一篇：Mac安裝HomeBrew