【链表3】动态内存分配

文/Edward

这一小节是为了讲述第2小节链表而做的只是铺垫。在9.2节中，我们通过一种非常朴素的方式来为大家展示了“链式”数据结构的基本方法，即，我们先定义好一个结构体存储类型，接着，在这个结构体存储类型中，一定要定义一个可以用于指向本存储类型的结构体指针，这个本定义的结构体存储类型，后续会被用作我们链式数据结构的一个节点。但是，在讲述前面章节的时候，我们那个代码再怎么简单，也无法达到我们的预期。这是因为，我们要是这些节点建立好链式关系，首先有一个前提必须要得到保证，那就是必定要事先知道这个链式结构里面有多少个链接节点。因为我们需要根据这些链接节点数量去定义相应的结构体变量。这种一开始就将变量写死的方法，在程序设计里面被称为静态方法获取内存。

在我们平时写程序的时候，需要定义的变量如“unsignedchar a[100];”，这句语句执行的时候，编译器就会给数组a分配100个字节的内存空间。但是，这个我们之前也简单提到过，“unsignedchar a[100];”这句数组定义语句，其实其本身是一种Auto类型的变量类型。而我们前面说过，Auto类型的变量，编译器会自动将其存储在“栈”空间。这种方式有个非常不方便的地方，一旦当我需要对数组a存储超过100长度的数据，那么整个程序就会出现内存溢出。而如果一开始就将这个数组定义的很大，但是在实际使用中绝大多数实际数据量又不需要那么大，这样也会产生存储空间的浪费。

那有没有一种办法可以让一个这个数组的存储空间随心所欲的变化呢？答案显然是有的，这就是将内存申请动态化，C语言提供了两个库函数malloc和free，分别用于执行动态内存的分配和释放。注意，在C语言中，用malloc申请的内存在使用完成后，一定要进行手动释放，否则会使内存消耗殆尽，程序停止运行。malloc和free维护了一个可用的内存池，也就是我们之前所谓的“堆”区。当一个程序需要一块合适的内存时，就使用malloc函数进行申请，即取出一块合适的内存，并返回一个指向这块内存的指针。需要注意的是，这块内存在被取出来之后，它并没有被初始化过，因此我们需要手动对其初始化。接着，当程序不想再使用这块内存时，使用free函数把它归还给内存池。

这两个函数都在<std< span="">lib.h>头文件中声明，它们的原型为：</std<>

void *malloc(size_t size);void free(void *pointer);

malloc的参数就是需要分配的内存的字节数，如果内存池中的可用内存能满足这个size的大小需求，那么malloc就会返回一个指向被分配的内存块的起始位置的指针。

使用malloc分配的内存是一整块连续的内存。如我们请求它分配100个字节的内存，那么它实际分配的就是100个连续的字节。

free函数调用时，其形式参数pointer一定要是一个先前从malloc函数分配的动态内存的指针，或者是一个NULL参数，如果传入NULL的话，free函数将不会产生任何作用。

这里大家注意下，malloc函数在使用的时候，除了我们需要输入一个表示申请内存大小的参数外，就不需要输入其他任何信息了。那么一旦当内存申请好之后，编译器又是如何知道它会被用作整型，浮点型，数组还是其它的一些数据类型的变量呢？这里大家注意一下，malloc函数的返回值类型，它是一个void *类型的指针，void*指针有一个非常强大的技能，即它可以转换为其它任何类型的指针，不管是C语言的标准数据类型，还是我们自己定义的一些结构类型，都是可以完美转换的。

接下来，让我们写一段代码来申请一块长度为10的int类型的内存。如图1所示。

图1 内存申请成功

此时，我们已经获得了一块长度为“sizeof(int) * 10”长度的内存了。为什么这里要写成“sizeof(int) * 10”的方式呢？因为不同平台int的长度是不同的，所以使用这种方式更加有利于程序的移植。内存申请好之后，接下来的问题是我们该如何来使用这一块内存呢？使用的方式有几种，第一种方式为使用指针的间接访问。比如，我们为之前申请的内存依次赋值0~9，那么使用指针的间接访问如图2所示。

图2 指针间接访问申请到的内存

如图2的代码所示，如果利用指针的间接访问，我们每次都需要定义一个用于存储当前地址首地址的指针变量。这个指针变量绝对任何时候都不能改变的，一旦改变之后，当我们需要释放这段内存的时候，就无法找到首地址了。

第二种使用这段内存的方式为指针的下标引用。图2同样的内存赋值代码如图3所示。

图3 下标索引访问申请到的内存

上面两种对比很明显，对于简单的数据排列，如数组之类的，那么使用下标索引比指针间接访问要简单很多。