1、为何引入链表

在程序中经常面临一个问题，我们需要保存一定数量的对象，但是对象数目是不确定的，或者说是随时增加或减少的。这时候最简单的方法是创建一个足够大的数组，用来存储这些对象。我最近开发一个项目就遇到类似的问题，下面我把问题简化一下。


需求：通过PC下发一些矩形的坐标和宽高信息，每个区域有个ID编号，并在这些矩形内填充一定的数据。
) D: l, L: Q8 w6 G

( h- T( R/ u( |2 `# p通常情况下，最简单易懂的做法是，限制最多5个区域，每个区域存储1K数据。因此设置了这样的一个结构体（类似于面向对象语言里说的成员属性）。

1. <font face="微软雅黑" size="3">typedef struct Area_Inf
   ! V2 h& g2 S, O7 N" P/ g2 F
2. {
   
3.   uint8_t ID;
   0 f" j7 A) z# H$ i+ g
4.   uint8_t X;
   
5.   uint8_t Y;
   + \( `# C% t( U2 S
6.   uint8_t Width;
   8 J% s- ~1 k' R# e  V- |1 c$ m
7.   uint8_t Height;
   
8.   uint8_t data_len;
   
9. }Area_Inf_Typedef;</font>

复制代码

然后定义结构体的实体。
) |: m6 Q' n- R8 a3 y, S! I

1. <font face="微软雅黑" size="3">#define Area_Num 5
   
2. #define Area_cache 1024
   ' \0 k" ?2 r$ Q. H
3. 
   
4. Area_Inf_Typedef Area_Info[Area_Num];
   
5. uint8_t Area_Data[Area_Num*Area_cache];//存储区域的数据
   ) ?0 m5 H" {7 M/ {, {
6. 
   ( M1 P& r; b- `6 W" r* X4 v4 G8 K! u
7. /*找到ID为5的区域，并将数据拷贝出去*/
   " b8 S& k+ C. Q3 |) n1 g* M- H$ ~
8. void main()
   
9. {
   ) T( b1 F8 W' E$ G% G. H1 V* |
10.     uint8_t i;
    1 c( K* Y. ~) n/ L+ x
11.     uint8_t data[1024];
    
12.     for(i = 0;i < Area_Num;i++)
      `' h3 Q! a, t
13.     {
    7 i8 a& d: \7 y5 \0 E6 ~3 {
14.         if(Area_Info[i].ID == 5)
    
15.         {
    6 b* }" F, T' M. |0 y6 C. X
16.             memcpy(data,&Area_Data[i*Area_cache ],Area_Info[i].data_len);
    ! d+ W$ e7 C  A
17.         }
    
18.     }
    
19. }</font>

复制代码

上面这种做法是最简单易懂的，但不灵活，比如有客户要求10个区域，但是每个区域存储的数据很少，根本用不到1K。虽然上面的程序已经使用了宏定义，只需要修改宏定义就能实现要求。但这意味着不同的客户，需要编译不同的固件。
6 V4 O+ B. X; @: ?

1. <font face="微软雅黑" size="3">#define Area_Num 10
   
2. #define Area_cache 512</font>

复制代码

这样的程序存在的问题：


2 a$ H9 A- g) H, K) e7 r1、在内存资源很紧缺的单片机程序中，当区域数据很少时，这种程序的处理方法浪费了大量的内存空间。
( ?: f2 N" I$ t8 [* r8 s6 N/ Z
0 C; t  o0 `5 o# f" b) C& b
5 c6 z) C6 m# v2、数值固定，需要存储更多区域，即使还有内存，还是需要修改宏定义，重新编译固件，不灵活。


; U; B) S  m' R1 l4 {! i这时需要引入链表来解决这个问题。
1 Y% {6 ]" t9 G: B
$ j9 W4 m+ i7 B2 _" `9 [" @
  ~; M# \0 R" @

2、链表实现

链表实际上是线性表的链式存储结构，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，且链表的长度不是固定的，链表数据的这一特点使其可以非常的方便地实现节点的插入和删除操作。链表的每个元素称为一个节点，每个节点都可以存储在内存中的不同的位置，为了表示每个元素与后继元素的逻辑关系，以便构成“一个节点链着一个节点”的链式存储结构，除了存储元素本身的信息外，还要存储其直接后继信息，因此，每个节点都包含两个部分，第一部分称为链表的数据区域，用于存储元素本身的数据信息。

对于上面的问题，我们使用链表解决，需要配合内存管理才能实现。内存管理这一块，大家可以自己编写内存管理驱动，也可以使用C库的malloc和free函数。如何字节编写内存管理驱动不是本文的重点，下文将使用C库的malloc和free函数进行内存管理。

8 v6 f2 q% o( v+ S( H# k! {  e) J
. G  R- U7 L% X6 z. a+ ]# g& M9 L) Z使用链表的方式，在原有的成员属性结构体的前提上，还要再封装多一层链表管理。以单向链表为例：
# m( ]- F) J# x

1. <font face="微软雅黑" size="3">typedef struct Area_Inf
   % o6 }- s7 i; v3 Z8 M
2. {
   9 o; l  }# R: Z0 W
3.   uint8_t ID;
   
4.   uint8_t X;
   7 H7 ]0 T/ l7 e/ m
5.   uint8_t Y;
   
6.   uint8_t Width;
   
7.   uint8_t Height;
   
8.   uint8_t data_len;
   
9.   uint8_t* Area_Data;
   6 n! h3 }1 w- K
10. }Area_Inf_Typedef;
    , B2 ]* p2 Z6 u$ D+ H
11. 
    
12. typedef struct Area_List_Inf
    
13. {
    
14.   Area_Inf_Typedef *Area_Inf;
    3 t) C' r/ ]+ E
15.   struct Area_List_Inf *next_Area_Inf;  //用于指向下一个
    
16. }Area_List_Inf_Typedef;
    
17. 
    
18. Area_List_Inf_Typedef *Head_Area_List; //链表的头指针</font>

复制代码

由于在定义的时候，只定义了一个头指针，那么它也只是个指向了Area_List_Inf_Typedef也就是链表结构体的指针，同样没有内存空间，在没有创建新增链表之前，它是一个野指针。

7 w/ t7 t4 W) V0 _5 _( ~! W
所以，在具体应用之前，需要先执行一个初始化操作，也就是申请空间给链表管理结构体，然后头指针指向这个空间。
4 s: X% p0 c! H- B! W/ C) a

1. <font face="微软雅黑" size="3">/**
   
2. * @brief 动态区链表初始化
   
3. * @return int
   
4. */
   
5. int Area_List_Init(void)
   6 u, u0 g2 |0 {+ l
6. {
   / q: @8 E5 U; F# Z8 P
7.   //申请链表类型大小的空间，并让头指针指向它
   
8.   Head_Area_List = (Area_List_Inf_Typedef*)malloc(sizeof(Area_List_Inf_Typedef));
   % h% A/ @5 v% E& X
9.   if(Head_Area_List == NULL)
   
10.     return false;
    ( ^; W% A  w5 g" `
11.   
    
12.   //同时要标记下一个信息为空
    2 N1 l. N1 p/ b  I1 w: J) X8 @7 Q4 ]
13.   Head_Area_List->next_Area_Inf = NULL;
    + ]2 h* ^$ h& h6 E
14.   return true;
    
15. }</font>

复制代码

通过PC下发一个新的区域信息后，增加新区域到链表末尾。

1. <font face="微软雅黑" size="3">/**
   - k) S+ {0 W. A+ r* g; k# d. W
2. * @brief 在链表末尾增加一个区域参数
   
3. * @param Area_Inf 增加的区域区参数指针
   
4. * @return int
   
5. */
   ; b6 n" T" T" N5 j. q# a9 o$ U5 G
6. int Add_Area_ToList(Area_Inf_Typedef *Area_Inf)
   7 {3 k0 ?2 o! V) Q1 E0 r* e& a2 U
7. {
   
8.   Area_List_Inf_Typedef *p = Head_Area_List;
   . `* e/ G5 g9 m. ?. _
9.   while(p->next_Area_Inf!=NULL)
   : |! B$ H7 B2 R' b" x
10.   {
    
11.     p = p->next_Area_Inf;
    ' X8 u$ Z2 V9 O  d, x
12.   }
    + B% u. Z7 g5 k+ c* K2 U; S: @! F
13.   
    
14.   //先申请链表结构体的空间，因为后续还要继续增加
    
15.   p->next_Area_Inf =  (Area_List_Inf_Typedef*)malloc(sizeof(Area_List_Inf_Typedef));
    & t: f1 n) V) x- {+ f
16.   if(p->next_Area_Inf == NULL)
    , ~: J; H, {  u5 I1 h
17.     return false;//申请不到内存，返回失败
    1 B8 L; q. \& A: Q3 _
18.   
    
19.   //指向刚刚申请的空间，并为需要存放的动态区信息申请对应的内存
    - i) H0 B9 j" E$ c4 C, B2 J
20.   p = p->next_Area_Inf;
    
21.   
    9 j, X" n# z/ I6 R2 }, q, m
22.   p->Area_Inf = (Area_Inf_Typedef*)malloc(sizeof(Area_Inf_Typedef));
    
23.   if(p->Area_Inf == NULL)
    . H0 r/ |# o7 v7 z3 R1 o
24.   {
    
25.     free(p);//由于申请失败，先前申请的链表空间也要释放
    
26.     return false;
    % i. v" A3 J% ^) E
27.   }   
    ' z2 n; k) V, P- W; G" W/ h
28.   memcpy(p->Area_Inf,Area_Inf,sizeof(Area_Inf_Typedef));
    1 L) r1 S0 L3 i1 Q& P
29.   
    ( S! Y, A2 k9 O
30.   /*拷贝数据*/
    
31.   p->Area_Inf->Area_Data = (uint8_t*)malloc(Area_Inf->data_len);
    
32.   if(p->Area_Inf->Area_Data == NULL)
    $ [' j6 r+ f+ d# `# x0 D
33.   {
    
34.     free(p->Area_Inf);
    $ T: i/ ~+ N7 A% m0 c
35.     free(p);
    
36.     return false;
    4 o0 @7 I4 \) q
37.   }
    
38.   memcpy(p->Area_Inf->Area_Data,Area_Inf->Area_Data,Area_Inf->data_len);
    , t+ A) v: o8 A
39.   //标记这个链表的尾部
    
40.   p->next_Area_Inf=NULL;
    & }  t8 N$ e7 X  d  f
41.   //添加成功
    3 X* R$ [) W$ k
42.   return true;
    + g, N( {( r( G5 Z
43. }</font>

复制代码

通过PC下发一个删除指定ID的区域命令。
% N% J$ A- c8 u* q: G, m. C" ^* [3 X

1. <font face="微软雅黑" size="3">/**
   3 p; Z& q: L3 _
2. * @brief 根据区域ID找到链表
   
3. * @param data_p 链表指针
   - C  d/ B1 v( F5 b5 W
4. * @param num    区域ID编号
   ' G& Y* P( M$ F" Q- K- g
5. * @return int
   
6. */
   
7. int Find_Area_According_ID(Area_Inf_Typedef **data_p,int num)
   
8. {
   
9.   Area_List_Inf_Typedef *p =  Head_Area_List;
   ! k+ i& J; t" x3 K  C. D
10.   while(p->next_Area_Inf!=NULL)
    
11.   {
    
12.     p = p->next_Area_Inf;
    
13.     if(p->Area_Inf->ID == num)//匹配到对应的值
    . J1 t0 y1 e; H5 K0 g
14.     {
    
15.       *data_p = p->Area_Inf;
    7 p5 n8 v+ F+ }' A$ P" E
16.       return true;
    
17.     }
    
18.   }
    
19.   return false;
    * R8 r7 _$ Y: b9 T/ H
20. }
    
21. /**
    5 {0 ]& Z% |  c! c
22. * @brief 删除所有区域
    
23. *
    
24. */
    3 x7 W/ i4 `4 A+ ^% ^9 q
25. int Delete_All_Area(void)
    
26. {
    $ b9 s1 x- h, K$ l
27.   int res = false;
    $ H1 U6 U& m% p2 y' A" `) b
28.   Area_List_Inf_Typedef *p =  Head_Area_List;
    
29.   while(p->next_Area_Inf!=NULL)
    
30.   {
      b- c  S( m" g
31.     Area_List_Inf_Typedef *temp = p;
    # ?( @1 y* m6 r& K4 g4 Z5 @+ ~
32.     p = p->next_Area_Inf;
    
33.     temp->next_Area_Inf = p->next_Area_Inf;
    3 o1 w% o2 ^. l+ x9 h% X
34.     //释放内存空间
    
35.     free(p->Area_Inf->Area_Data);
    
36.     free(p->Area_Inf);
    
37.     free(p);
    9 H- B( Q1 l2 _8 Y
38.     p=temp;
    & Q, i# J$ p0 J+ E
39.     res = true;
      q0 w* P+ z8 e/ O( |! [  r6 Y3 D  I
40.   }
    ! m- b+ o. C: @5 u1 R( ~+ r. w
41.   return res;
    % ~  f" N8 J- o. R/ x# D
42. }
    
43. /**
    - e/ m: ^7 J. n/ x, U
44. * @brief 打印链表信息
    
45. *
    
46. */
    0 c! j9 Z3 l+ q3 @
47. void Printf_Area_Inf(void)
    
48. {
    
49.   int i=0;
    $ q& D7 W6 ^6 W& p: n
50.   Area_List_Inf_Typedef *p =  Head_Area_List;
    : b1 B! x+ S+ v9 n0 U7 ]& u" _; {
51.   printf("list   ID   X   Y   Width   Height   Area_Data\r\n");
    
52.   
    ' u+ m: s8 h' ^
53.   while(p->next_Area_Inf!=NULL)
    
54.   {
    
55.     p = p->next_Area_Inf;
    
56.     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);
    
57.     i++;
    2 _0 R8 O7 h, n6 m! b  t- b
58.   }  
    
59.   printf("----------------------end-----------------------\r\n");
    3 O& e1 i. P! r8 e0 I( F
60. }</font>

复制代码

3、测试函数

下面编写一个测试函数，可以测试，链表的初始化，增加一个区域，删除指定区域，根据ID返回区域信息，删除所有区域接口。

1. <font face="微软雅黑" size="3">/**
   
2. * @brief 链表测试函数
   + |2 H, z( e  m0 N5 n( e5 F' R2 q; j. v
3. *
   2 T5 R: S" J- S9 U
4. */
   
5. void list_main()
   
6. {
   
7.   int i,j;
   
8.   Area_Inf_Typedef temp;
   
9.   Area_Inf_Typedef **data_p;
   ' m8 ~6 T2 G1 x) |4 q
10.   data_p = NULL;
    
11.   printf("------------------List test---------------------\r\n");
    2 ?1 P0 X+ W! d# ?3 u
12.   if(!Area_List_Init( ))
    
13.   {
    
14.     printf("Memory fail..\r\n");
    ; @  S3 u, @. V  z1 E: p) d
15.   }
    
16.   for(i=0;i<5;i++)
    - _8 l8 ?- g9 k4 q3 `! Z
17.   {
    
18.     temp.ID = i;
    9 t1 u) v1 {* T( v
19.     temp.X = 5+i;
    # {0 E2 d; c4 v$ v
20.     temp.Y = i;
    ! D2 q9 C* H8 a; N* g1 r  P8 p  K: M
21.     temp.Width = 10+i;
    
22.     temp.Height = 10+i;
    
23.     temp.data_len = i+1;
    
24.     temp.Area_Data = (uint8_t*)malloc(temp.data_len+1);
    8 M* R% `$ s  m$ }) X# G& u
25.     for(j=0;j<temp.data_len;j++)
    4 f$ x9 J* M) y" M
26.     {
    1 b8 E# v5 o) b0 ?% L8 o+ r
27.       temp.Area_Data[j] = j+0x30;
    
28.     }
    
29.     temp.Area_Data[j] = 0;
    / o0 @8 F5 g) H( ]+ z
30.     if(!Add_Area_ToList(&temp))
    . _: ~% n( [1 ~" F8 v# P; {% ~2 d
31.     {
    ! G5 v6 _$ K  x1 d! D
32.       printf("Add Area %d Area_Info fail\r\n",i);
    
33.     }
    
34.   }
    
35.   
    
36.   Printf_Area_Inf();
    - H1 g" u  x8 `0 O  b
37.   printf("\r\n-------------Delete ID of Area is 3-------------\r\n");
    
38.   Delete_Area_Accordingn_ID(3);
    ; r& U! g4 ]6 t3 p+ X
39.   Printf_Area_Inf();
    # F+ A+ F5 Z7 A# I1 `; U  \
40.   
    
41.   temp.ID = 9;
    3 Z5 l( t# K+ _! p
42.   temp.data_len = 10;
    * m# p" Q6 e1 s- F' l
43.   temp.Area_Data = (uint8_t*)malloc(temp.data_len+1);
    4 v- V; x/ K+ s, @6 k
44.   for(j=0;j<temp.data_len;j++)
    
45.   {
    
46.     temp.Area_Data[j] = j+0x30;
    
47.   }
    ' ]- C7 c  F" O% p. R, T
48.   temp.Area_Data[j] = 0;
    
49.   if(!Add_Area_ToList(&temp))
    & [+ L# ]% G* Z  R5 Z& ~
50.   {
    
51.     printf("Add Area %d info fail\r\n",temp.ID);
    
52.   }
    
53.   printf("\r\n--------------Add ID of Area is 9---------------\r\n");
    ; ^3 [' s0 o. l3 J
54.   Printf_Area_Inf();
    ! A3 M. q( x+ G% Q
55.   
    
56.   Find_Area_According_ID(data_p,2);
    
57.   temp.ID = (*data_p)->ID;
    
58.   
    
59.   Delete_All_Area();
    
60.   printf("\r\n--------------Delete All Area-------------------\r\n");
    
61.   Printf_Area_Inf();
    , M5 a" d$ ~. Y) k
62.   
    
63.   while(1);
    
64. }</font>

复制代码

测试结果
# S0 B- O6 x; ]7 q: |
0 U. j! v4 X9 B$ J/ H) l  rIAR和keil工程代码开源地址：
https://github.com/strongercjd/STM32_Linklist
8 |7 \: h7 Y4 C) a3 s(提示：公众号不支持外链接，请复制链接到浏览器下载)
1 g; r% r% h) P& ~( O/ W$ P
) T* B3 e4 d  X6 M6 d$ I
) w  o7 R& S' ]# d如果大家手中有板子可以调试，可以看《一文了解串口打印》文章，使用串口打印。如果临时没有板子可以debug，可以模拟测试，IAR设置如下：
8 G* [) M3 J% ^0 U2 {5 l8 Z4 o% B选择Simulator调试

6 \! ^8 M+ U; X% u8 \# Q5 u

打开View->TerminalI/O，就可以看到打印信息
5 D, D/ f. U) q4 m
+ X( t: T+ J. s5 m
! e/ v5 f2 Y# {$ t( U, G0 X0 o