2020年01月07日 | 浅谈链表对stm32等芯片程序中的提升作用（C语言）

程序中经常面临这样的一个问题，需要创建一定数量的对象，但事前又不知道对象的具体个数，因此新手通常的做法都会为了能处理足够的对象信息，创建一个足够大的空间数组。这里举个简单的例子，某个应用要求管理学生信息，因此设置了这样的一个结构体（类似于面向对象语言里说的成员属性）

typedef struct 

{

int num;

int age;

char *name;

}studentInfo;

在不引入链表的情况下，为了能管理尽可能多的学生信息，可能会这样创建这个结构体的实体：

studentInfo student[1024*100];

int studentCnt = 0;    //记录已经管理的学生数量

这样的处理方法，理论上能实现需求，而且在学生数量还小的时候，这个程序基本也不会出现明显的问题。但这样的做法存在很多方面的问题，当一个数组被创建时，其在内存中的大小就已经被固定了，所以，1，当学生数量较小时，这个程序的处理方法浪费了大量的内存空间，特别是在资源紧缺的单片机或嵌入式系统中，这样的做法是不符合要求的。2，当学生数量大于设置的数量时（即例子中的1024*100），即使系统中还剩有内存空间可以继续添加，而这个程序也无法再添加学生信息。3，当学生数量比较大时，遇到删除信息的操作，程序的处理效率非常低，处理方法通常是，找个需要删除的信息的存放位置，然后把后面的信息逐步往前覆盖，如果删除的是最后一个，则设置为0，从而达到删除的目的。

如果引入链表，以上的三个问题都能完美解决，但需要配合内存管理才能实现，因此如果是嵌入式系统，还需要实现内存管理方面的功能，关于内存管理，将在下篇文章中提到。使用链表的方式，在原有的成员属性结构体的前提上，还要再封装多一层链表管理。以单向链表为例：

typedef struct 

{

int num;

int age;

char *name;

}studentInfo;

typedef struct students

{

struct students *nextStudent;    //用于指向下一个学生信息

studentInfo *Info;     //具体的信息

}studentsTypedef; 

studentsTypedef *headStudents; //链表的头指针

看到这里，会发现用到的基本上是指针，有些同学可能会比较害怕用指针，其实用多了就会发现，指针也就是那么回事。好了，既然是指针，那么它是没有用来存放数据的内存空间的，而链表的精髓在于，具体的数据信息是通过内存管理申请内存存放，而链表结构则负责指向各自负责管理的数据，从而实现关联。

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

所以，在具体应用之前，需要先执行一个初始化操作，也就是申请空间给链表管理结构体，然后头指针指向这个空间。

//

//初始化

//

bool studentsListInit(void)

{

    //申请链表类型大小的空间，并让头指针指向它

headStudents = (studentsTypedef*)malloc(sizeof(studentsTypedef));

if(headStudents == NULL) return false;

    //同时要标记下一个信息为空

headStudents->nextStudent = NULL;

return true;

}

这里使用了一个malloc函数，作用是申请内存，在PC端编写测试程序时可以使用这个函数，需要包含的头文件时malloc.h。如果是在嵌入式系统中，直接使用malloc会导致一些内存碎片的问题，比较多的做法是自己实现一定的内存管理方法，包括申请内存，释放内存，高端的内存管理方法还会包含碎片整理的功能。如果是使用类似FreeRTOS这样的操作系统，RTOS中已经为我们提供了几种内存管理的方法，使用较广泛的heap4。

需要新增一个学生信息，实现方法可以这样写：

bool AddStudentToList(studentInfo *stuInfo)

{

    //在链表的最后加入

studentsTypedef *p = headStudents;

while(p->nextStudent!=NULL)

{

p = p->nextStudent;

}

    //先申请链表结构体的空间，因为后续还要继续增加

p->nextStudent =  (studentsTypedef*)malloc(sizeof(studentsTypedef));

if(p->nextStudent == NULL) return false;

    //指向刚刚申请的空间，并为需要存放的学生信息申请对应的内存

p = p->nextStudent;

p->Info = (studentInfo*)malloc(sizeof(studentInfo));

if(p->Info == NULL) 

    {

        free(p);//由于申请失败，先前申请的链表空间也要释放

        return false;

    }    

    //具体信息赋值

memcpy(p->Info,stuInfo,sizeof(studentInfo));

    //标记这个链表的尾部

p->nextStudent=NULL;

    //添加成功

return true;

}

到这里可以发现，当需要添加一个学生的管理信息时，这里的程序就相应的申请一个学生信息所需要的空间，这样一来，可以实现内存的利用最大化，不会出现申请了内存但不使用的情况。到这里已经解决了上面说到的2个问题。

下面再来看删除操作：

bool deleteStudentInfo_AccordingNum(int num)

{

bool res = false;

studentsTypedef *p =  headStudents;

while(p->nextStudent!=NULL)

{

studentsTypedef *temp = p;

p = p->nextStudent;

if(p->Info->num == num)

{

temp->nextStudent = p->nextStudent;

//释放内存空间 

free(p->Info);

free(p);

p=temp;

res = true;

}

}

return res;

}

可以看到，删除一个节点，只需要找到该节点的位置，至于怎么找这个节点，可以根据不同的方法，我这里只是随便举个例子。找到之后，只需要改变一下原来链表结构的指向，并释放被删除节点所占用的内存空间，整个删除操作就完成了，不需要像数组那样，找到之后，还要把后面的节点逐个往前面移动，效率非常低。当然，链表也并不是完全优于数组的，链表的访问只能从头节点开始，而数组的访问，可以直接使用下标，结合一定的算法，如二分排序法等，使用数组的方法的查找效率就高于链表的方法，具体如何选择，需要看实际的应用场景。

最后再贴上main函数中，测试的部分。

void printfStudentInfo(void)

{

printf(" list      num age namern");

studentsTypedef *p = headStudents;

int i=0;

while(p->nextStudent!=NULL)

{

p = p->nextStudent;

printf("  %d %d %d %srn",i,p->Info->num,p->Info->age,p->Info->name);

i++;

}

printf("----------------------------end--------------------rn");

} 

int main(int argc,char *argv[])

{

printf("-------------List test---------------rn"); 

if(!studentsListInit( ))

{

printf("Memory fail..rn");

}

studentInfo temp;

for(int i=0;i<5;i++)

{

temp.age = 20+i;

temp.num = i;

temp.name = (char*)"A";

if(!AddStudentToList(&temp))

{

printf("Add student %d info failrn",i);

}

}

printfStudentInfo();

deleteStudentInfo_AccordingNum(4);

printfStudentInfo();

temp.age = 18;

temp.num = 1001;

temp.name = (char*)"TEST";

if(!AddStudentToList(&temp))

{

printf("Add student %d info failrn",1001);

}

printfStudentInfo();

}