王道C++班级参考资料
——
C语言部分卷4指针
节5指针的高级应用
最新版本V2.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有
王道C++班级参考资料<br />——<br />C语言部分卷4指针<br/>节5指针的高级应用<br/><br/>最新版本V2.0<br>王道C++团队<br/>COPYRIGHT ⓒ 2021-2024. 王道版权所有概述虚拟内存空间存储期限栈区的内存管理及其特点堆区的内存管理及其特点动态内存分配和释放（重点）通用指针类型内存分配函数mallocmalloc使用示例不要用数组类型接收返回值内存泄漏free函数尽量不要移动原始指针不要两次free同一片内存区域悬空指针避免不可到达内存区域总结课堂练习清零内存分配函数calloccalloc使用示例建议(重要)内存重分配函数reallocrealloc重分配内存机制解析realloc函数正确的使用方式手动实现C++中的Vector(重点)思路讲解头文件的使用第一步: 创建和编写头文件头文件保护第二步: 包含头文件与实现函数第三步: 测试自定义动态数组Vector实现动态数组实现vector_create()实现vector_destroy()实现vector_push_back扩展二级指针 头插法实现单向链表函数返回新头指针函数没有返回值二级指针的使用语法利用二级指针实现无返回值头插函数函数指针函数指针变量的声明给函数指针类型起别名函数指针变量的初始化一个简单的计算器示例qsort函数qsort函数的行为qsort函数使用练习总结THE END
概述
Gn!
在前面的章节中，我们探索了指针的基础知识，并通过实践熟悉了其操作，包括:
将指针作为参数传递，利用函数修改指针指向的内容。
利用指针高效处理数组以及字符串。
....
现在，我们将继续深入挖掘指针的强大功能，在本章中，我们会深入学习以下技术栈：
动态内存分配：我们将学习如何运用指针和结构体动态管理内存，这是高级C语言编程的核心，也是本章的重难点。通过动态内存分配，我们可以更灵活地控制程序的资源，从而处理复杂的数据结构和算法问题。
二级指针：理解和应用二级指针对于深入掌握指针的概念至关重要，它也是理解更复杂指针使用场景的基础。
函数指针：我们会探讨如何将函数作为参数传递，这对于高级C编程技巧如函数回调等至关重要。
当然，在具体讲解高级指针应用的内容之前，我们需要更进一步的了解"内存"——也就是C程序运行的虚拟内存空间。
在本章开始，我们会回顾总结虚拟内存空间的概念，并进一步扩展，这也是本章节的重点。
虚拟内存空间
Gn!
虚拟内存空间是一个抽象的概念，它让每个程序都认为自己在独占地使用计算机的内存。
虚拟内存空间为每个程序提供了一个连续的内存地址空间，从而简化了程序的内存管理，便于编程实现。
下图是虚拟内存空间的主要组成部分：
下面首先来总结一下存储期限，然后我们再重点学习栈和堆两块内存区域的内存管理。
存储期限
Gn!
在C语言中，根据数据在虚拟内存空间中的生命周期和位置，可以划分为以下三种主要的存储期限：
自动存储期限：
数据存储在栈（Stack）上，主要指函数内部定义的局部变量，包含函数内部定义的数组和结构体。
这些变量在对应函数被调用时分配内存空间，并在函数返回时随着栈帧的出栈而销毁。
自动存储期限意味着，变量只在声明它们的函数调用期间生效。
静态存储期限：
数据存储在数据段中，主要指全局变量、静态局部变量以及static修饰的全局变量。
字符串字面值也是静态存储期限，存储在数据段的只读区域。
这些数据在程序启动时初始化，并在整个程序运行期间持续存在，直到程序结束。
动态存储期限：
数据存储在堆（Heap）上，由程序员在运行时手动申请空间，分配空间创建的变量具有动态存储期限。
动态存储期限意味着由程序员手动控制生命周期，手动分配内存，手动释放内存。
这三种存储期限反映了不同类型的数据在内存中的管理方式和生命周期，是C语言内存管理的基础。理解这些概念对于编写高效、稳定且易于维护的程序至关重要。
栈区的内存管理及其特点
Gn!
栈区域的内存管理主要依赖栈指针寄存器(Stack Pointer寄存器，简称SP寄存器)的移动来完成。
你可以简单把SP寄存器看成是一个跟踪栈顶位置的指针，它始终指向栈的顶部。
栈区域可以随着函数调用生长，而且是从高地址向低地址，向下生长，所以：
当函数开始调用，栈帧进栈时，SP会减少，栈顶移向低地址。
当函数调用结束，栈帧出栈销毁时，SP会增加，栈顶移向高地址。
这两个过程，可以参考以下两张图来理解（如果觉得图小，可以点击图片全屏显示）：
栈区域的内存管理，很明显具有以下优点：
简单高效。栈的操作（如栈帧的进出栈）通常只涉及SP寄存器的增减，这很简单，也很高效。
自动管理。栈区的数据无需程序员手动管理，自动创建、自动销毁、自动存储期限。
线程安全。线程可以看成是进程中的一条执行路径，一条函数调用链。所以栈区是线程私有的，每个线程都有自己独立的栈区。这在多线程环境下是一个优点，因为这就意味着在一般情况下，你不需要考虑栈区数据的安全问题。（当然也有一些例外）
当然也会有一些缺点：
大小非常有限。为了保障栈区的性能，避免空间浪费，栈区域的大小非常小，一般只有几MB。栈区是比较容易出现内存溢出错误的内存区域。
线程安全但也意味着线程间不同共享栈区数据。
为了通过SP寄存器的加减就能够管理栈区域，程序在编译时期就必须确定栈帧的大小。这意味着栈区域存储的数据，必须在编译时期确定它的大小。栈区域一般不能存放运行时才能确定大小的数据。
依据以上缺点，以下这些数据就无法直接存储在栈区域了：
过大的数据。比如很长的数据，字符串，很大的结构体。
多个线程间需要共享的数据。
在程序运行时期，需要动态分配内存空间的数据。
当然，利用一个东西，用好它的优点就可以了，没什么东西是十全十美的。至于它的缺点，自然有别人来完成这个工作。
每个工具和技术都有其独特的优势和局限性，关键在于充分利用其优势。在软件开发中，不存在万能的解决方案，重要的是选择合适的工具来解决特定的问题。
栈内存的局限性往往被堆内存所弥补。堆提供了灵活性和动态内存分配的能力，这使得它能够处理栈所不适合的任务，如存储大型数据结构和运行时决定大小的数据。
通过合理地结合栈和堆的使用，我们能够设计出既高效又灵活的应用程序。在这个过程中，理解每种内存区域的特性及其最佳应用场景是至关重要的。
堆区的内存管理及其特点
Gn!
堆区的内存管理完全不同于栈区简单高效、自动的内存管理，堆区的内存管理主要由程序员调用内存分配函数(如malloc、free等)来手动进行分配、释放管理。
你可以认为堆区的内存管理是依赖程序员手动完成的。
堆区域的内存管理有以下优点：
很大。虽然堆区域的大小仍受限于计算机实际可用内存的大小，但堆区域要远大于栈。堆区域可以存放很大的数据。
在多线程环境中，进程中的所有线程共享同一个的堆空间，便于实现线程间的数据共享。
动态内存分配。堆内存可以在程序运行时动态分配和释放，可以用于存储动态分配内存空间的数据。
生命周期更灵活。程序员可以手动决定堆中数据的存活与销毁，堆中数据具有动态存储期限。
优点几乎是栈区缺点反过来，当然缺点也几乎是栈区优点反过来：
管理繁琐且不安全。C程序把内存管理这么重要的事情交给程序员，充分信任程序员，但实际上很多时候程序员(尤其是初学者)无法很好的管理内存，这会为程序带来很大的安全隐患。
性能问题。动态内存分配和回收的开销比栈操作大，可能影响程序性能。堆内存动态分配过程会涉及系统调用，对程序的性能影响还是比较大的。
线程不安全。多个线程共享同一个堆，就必须考虑安全问题(需要实现线程同步，加锁等)。这一方面引入了复杂性，另一方面也会进一步导致性能下降。
基于这些缺点，我们知道：
堆空间的使用具有安全风险，还会带来性能降低，一个合理的C程序应当优先考虑使用栈内存。
当栈区无法完成任务，比如以下场景，堆空间的使用就是必须的：
存储体积较大的数据结构，如大数组、长字符串和大型结构体。
动态数据结构。如动态长度的数组，链表，树等。
多线程共享的数据。
需要作为函数返回值的数据结构的指针。（返回栈区数据的指针会引发悬空指针问题）
...
堆内存的有效和安全使用对C程序员来说是一项重要的技能。虽然它确实不太容易，但这正是C语言的魅力。
动态内存分配和释放（重点）
Gn!
讲了一大堆理论，终于到了实战环节。本小节我们就来探讨一下如何写代码来进行堆空间的动态内存分配以及手动释放。
动态内存分配在 C 语言编程中有着举足轻重的作用，因为它是链式结构的基础。我们可以把动态分配的内存链接在一起，形成链表、树、图等灵活的数据结构。
虽然动态内存分配适用于所有的数据类型，但它主要还是应用于字符串，数组和结构体中。其中，动态分配的结构体是最值得关注的，因为它们可以被链接成链表、树或其他数据结构。
注意：一般来说，如无特别需求，不要在堆上为基本数据类型动态分配空间。
通用指针类型
Gn!
在具体讲解内存分配函数之前，我们先来看一个概念——通用指针类型。
在C语言中，通用指针类型指的是void类型的指针。通用类型指针具有以下特点：
类型无关，赋值灵活：由于指针本质上是一个存储内存地址的变量，而内存地址是没有类型的，所以void指针可以存储任意类型数据的地址，指向任意类型对象。无论是整数、浮点数、字符或数组、结构体等类型都可以用void指针指向。表现在代码中就是：你可以将任意类型指针(地址)赋值给void指针，这个过程一般是没有风险的。如下列代码：
可以将任何指针地址赋值给void类型-演示代码
1int a = 10;2int arr[] = { 1,2,3 };3void* p;4// p可以用任意指针赋值5p = &a;6p = arr;7p = &arr;有风险的转换：虽然你可以将任意类型指针赋值给void指针，但将void指针转换成其它类型指针时，却是一个有风险的、受限制的行为。如果进行了错误的类型转换，将会导致未定义行为。如下代码：
void指针错误类型转换引发未定义行为-演示代码
x1int a = 42;2void* void_ptr = &a;3// void指针转换成其它类型指针,在C++语法中必须加上显式类型转换说明5// 但C语言支持void指针隐式类型转换成各种其它指针类型，所以这个强转语法可加可不加6// float* float_ptr = (float*)void_ptr;7// 错误的类型转换9float* float_ptr = void_ptr;10// 解引用产生未定义行为12printf("%f\n", *float_ptr);关于通用指针类型转换成其它指针类型，C语言和C++在语法上会有明显差别：
C语言更灵活允许隐式的类型转换，所以强转语法可加可不加。
C++则不支持这类隐式类型转换，必须要加上强转的语法，否则编译无法通过。
无法直接操作：由于 void 指针没有具体的数据类型，所以你不能直接通过 void 指针对其指向的数据进行操作。比如，你不能对 void 指针进行解引用或者进行加减操作，除非你将它转换成另一种具体的指针类型。直接操作通用指针类型，会产生编译错误。
总之，void指针的灵活性使得它在代码中非常常用，在后续学习工作中，我们都会看到它的身影。
然而它并不能直接操作，使用它时必须小心确保正确地进行类型转换，以避免产生未定义行为。
内存分配函数malloc
Gn!
在C语言中，想要在堆上动态分配内存空间，主要依赖三个函数来完成，它们都声明在头文件<stdlib.h>当中：
malloc
calloc
realloc
这里我们先讲解最重要和最常用的一个——malloc函数：
全名是：memory allocation，该函数的名字就是内存分配的意思。
该函数的声明是：
void* malloc(size_t size);此函数会在堆空间上分配一片连续的，size个字节大小的内存块
此函数不会对内存块中的数据进行初始化，内存块中的数据是随机未定义的。
如果分配成功，此函数会返回指向该内存块地址(首字节地址)的指针。注意返回的指针类型是void指针，在操作之前需要进行转换。
如果分配失败，此函数会返回一个空指针(NULL)
下面我们来看一个malloc使用示例：
malloc使用示例
Gn!
使用malloc函数动态分配内存空间，应该注意：
你应该总是检查 malloc 返回的指针是否为 NULL，以确保内存分配成功。
如果 malloc 成功分配内存，你可以利用返回的指针像以往一样操作内存(需要先将void指针转换成对应类型指针)：
如果分配的是一个数组内存空间，可以利用返回值指针进行数组操作
如果分配的是一个结构体内存空间，可以利用返回值指针进行结构体操作
....
以下代码示例就演示了该函数的基本使用：
malloc的基本使用-演示代码
xxxxxxxxxx5612345typedef struct {10int stu_id;11char name[NAME_LEN];12int total_socre;13} Student;14int main(void) {16// 使用malloc函数在堆上申请空间,创建一个长度为10的int数组18// 如果malloc成功会返回数组首元素地址19int* arr_p = malloc(ARR_LEN * sizeof(int)); // 一定要用sizeof(int),而不是直接写4,因为不同平台int大小可能不同20// 检查malloc是否成功,即检查arr_p是否是一个空指针22if (arr_p == NULL) {23printf("memory allocation failed!\n");24return -1; // 也可以exit(-1);结束程序25}26// malloc并不会初始化内存块，所以需要手动为动态分配的数组元素赋值28for (int i = 0; i < ARR_LEN; i++) {29arr_p[i] = i;30}31// 利用一个临时指针来遍历数组33int *p = arr_p; // p指针指向数组首元素34for (int i = 0; i < ARR_LEN; i++) {35printf("%d\n", *p++);36}37// 使用malloc函数在堆上申请空间,创建一个Student对象39Student* s1 = malloc(sizeof(Student));40if (s1 == NULL) {42printf("memory allocation failed!\n");43return -1;44}45s1->stu_id = 8;47// 给结构体变量的name成员赋值49// name的类型是一个字符数组类型,数组名是不允许直接"="赋值改变的,所以需要使用字符串复制函数50strncpy(s1->name, "Jack", NAME_LEN - 1);51s1->name[NAME_LEN - 1] = '\0';52s1->total_socre = 700;54return 0;56}下面我们讲解一些细节上的问题。
不要用数组类型接收返回值
Gn!
使用malloc，包括下面我们将要讲的calloc以及realloc函数，用它们动态申请内存创建数组，是非常常见的操作之一。
这时就会有些同学，习惯性的使用数组类型作为函数的返回值，例如：
用数组类型接收动态分配内存函数的返回值-演示代码
xxxxxxxxxx41// 动态分配长度为4的int数组,用数组类型接收2int arr[] = malloc(4 * sizeof(int));3// 或者4int arr[4] = malloc(4 * sizeof(int));这种代码在C语言中是不允许的，无法正常运行，一般会导致编译错误。
正确的做法应当是使用元素指针类型来接收：
xxxxxxxxxx11int *arr = malloc(4 * sizeof(int));那么为什么呢？数组名不是可以视为首元素指针吗？
这其实还是一个老生常谈的话题：
C语言的数组类型，其长度必须在编译时期确定，数组名本身在声明时就和一块固定大小的栈内存区域绑定。而malloc是在运行时动态分配内存的，数组类型变量显然不能用malloc函数进行初始化赋值。
总之，大家只需要记住：
在使用动态内存分配函数时，认准指针类型即可，不要考虑使用其它类型。
除了上面这个细节外：
使用malloc申请使用堆空间，是一个有风险的操作，它有可能引起内存泄漏，下面我们讲一下内存泄漏这个概念。
内存泄漏
Gn!
以往我们创建数组，创建结构体都是在栈上完成的，它们是栈数组、栈结构体，它们的内存空间都是由栈自动管理完成的。
但使用动态内存分配函数创建的数组、结构体都被存储在堆上，栈上存储的只不过是它的指针，如下图所示：
堆上存储的数据由程序员手动管理生命周期，手动申请内存资源，也需要手动释放内存空间。
我们先来讲一下内存泄漏：
内存泄漏是指程序在运行过程中，未能适时释放不再使用的内存区域，导致这部分内存在程序的生命周期内始终无法被重用。
比如我们上面代码示例中，使用malloc分配的数组和结构体，在使用完毕后，没有手动释放内存，就出现了"内存泄漏"。
内存泄漏在短时间内可能对程序而言，不是巨大的、致命的风险，但：
长时间运行或频繁执行的程序中如果存在内存泄漏，随着时间的推移，被泄漏的内存累积会越来越多，最终可能导致程序运行缓慢甚至崩溃，特别是在内存有限的系统中。
总之，对于C程序员而言，及时检测到程序中的内存泄漏，并处理内存泄漏是重要的职责之一。
free函数
Gn!
为了避免内存泄漏，在确定动态分配的内存不再使用后，要及时调用free函数释放它，这是非常重要的。
free函数的声明是：
void free(void *ptr);参数必须是堆上申请内存块的地址(首字节地址)，不能传递别的指针，否则会引发未定义行为。
free 函数的行为是：
free函数并不会修改它所释放的内存区域中存储的任何数据。free 的作用仅仅是告诉操作系统这块内存不再被使用了，可以将其标记为可用状态，以供将来的内存分配请求使用。
释放后的内存区域中的数据一般仍然会继续存在，直到被下一次的内存分配操作覆盖。当然即便free前的原始数据一直存在未被覆盖，这片内存区域也不再可用了，因为你不知道什么时候数据就会被覆盖掉了。
free函数不会修改传入指针指向的内容，更不会对实参指针本身做任何修改。(实际上它也没有能力修改，思考这是为什么)
下面就是一个free函数使用的基本演示：
free函数使用-演示代码1
xxxxxxxxxx81int* p = malloc(sizeof(int) * ARR_LEN);2// 手动初始化数组4for (size_t i = 0; i < ARR_LEN; i++){5p[i] = i;6}7// 确定p指向的堆数组不再使用，释放内存，避免内存泄漏8free(p);free函数使用的过程中，有很多隐蔽的坑，下面我们一一详谈。
尽量不要移动原始指针
Gn!
free函数需要传递，指向堆上动态分配内存的内存块的指针，这一点大家都能注意到，不会乱传一个指向栈区或数据段数据的指针。
但传递指向堆区指针时，也一定要注意：
free函数需要的指针是指向分配内存块首字节地址的指针，不能是其余字节的指针！
比如下列代码：
free函数使用-演示代码2
xxxxxxxxxx101int* p = malloc(sizeof(int) * ARR_LEN);2// 手动初始化数组4for (size_t i = 0; i < ARR_LEN; i++){5*p++ = i; // 看似等价于p[i] = i; 但实际上完全不同6}7// p指针已经移到了分配内存块的下一个字节9// p指针此时甚至已经不在分配内存块的内部了10free(p); // ERROR 未定义行为针对这种情况，我们给出一个非常重要的建议：
尽量不要移动指向内存块的原始指针，若有移动指针的操作，可以创建副本指针来使用。比如把上面的代码改成：
free函数使用-演示代码3
xxxxxxxxxx91int* p = malloc(sizeof(int) * ARR_LEN);2// 定义一个临时指针用于移动指针操作4int* tmp = p;5for (size_t i = 0; i < ARR_LEN; i++){6*tmp++ = i;7}8free(p); // p指针未移动，指向内存块首字节，安全当然，如果把上述代码中的指针
p传递给函数，则不必担心这个问题，可以在函数内部放心移动指针，如：free函数使用-演示代码4
xxxxxxxxxx251// 通过移位arr指针遍历打印数组2void print_arr(int* arr) {3printf("[");4for(size_t i = 0; i < ARR_LEN; i++) {5printf("%d, ", *arr++);6}7printf("\b\b]\n");8}9int main(void) {11int* p = malloc(sizeof(int) * ARR_LEN);12// 定义一个临时指针用于移动指针操作14int* tmp = p;15for (size_t i = 0; i < ARR_LEN; i++){16*tmp++ = i;17}18// 打印数组元素20print_arr(p);21// free释放，安全吗？23free(p);24return 0;25}思考下这是为什么？
不要两次free同一片内存区域
Gn!
C语言标准规定，动态分配内存的内存块可以手动free一次表明它不再被使用，但不能进行"double free"，这将导致未定义行为。
一般情况下，大家都不太会写出像下面这样的代码：
double-free代码演示
xxxxxxxxxx21free(p);2free(p);因为这很明显是故意的。
所以"double-free"往往发生在：在别的函数中已经free了一次，但随后忘记并且再次free。
所以在较大的复杂程序中，避免"double-free"不仅要靠程序员的细心，还需要一点小小的技巧。下面我们讲一下这个技巧。
悬空指针
Gn!
free函数调用后，指针指向的内存块就被释放了。
但free函数不会改变传入的实参指针本身，所以free后的实参指针就变成了指向一片已释放区域的指针。这就是"悬空指针"，悬空指针是野指针的一种特例，使用悬空指针同样会引发未定义行为。
为了避免悬空指针为程序安全带来隐患，推荐在free掉指针指向的内存块后，及时将指针置为空指针。比如：
避免悬空指针-演示代码
xxxxxxxxxx41// 伪代码,p是一个指针类型2p = malloc(...);3free(p);4p = NULL;如果仅在一个函数内部进行分配内存管理，是比较容易的。只要你不是特别马虎，悬空指针是不容易出现的。
悬空指针更多出现在多个函数调用之间，比如下图：
在复杂的代码场景中，这样的"悬空指针"往往是不易察觉的。同样的，如果在复杂的代码场景中，某个函数内部free了内存块，但在其余函数中忘记这一点继续使用内存块，也会引发未定义行为。
总得来说，没有一种万能的办法可以一劳永逸的杜绝悬空指针，一劳永逸地保障程序安全。对于C程序员而言，小心的、谨慎的管理堆空间，排查悬空指针，保障程序安全，是必修课。
避免不可到达内存区域
Gn!
比起忘记free导致的内存泄漏，"不可到达内存区域"导致的内存泄漏更加严重。
比如下列伪代码：
不可到达内存区域-演示代码
xxxxxxxxxx41// 伪代码 p和q是同类型指针2p = malloc(...);3q = malloc(...);4p = q;指针变量的赋值会将q的地址赋值给p，这样p和q都会指向同一个内存块，这会导致p指向的内存块再也无法访问，出现内存泄漏：
所以，如果在程序中需要给指向分配内存块的指针赋值，应当先进行free再赋值：
避免不可到达内存区域-演示代码
xxxxxxxxxx51// 伪代码 p和q是同类型指针2p = malloc(...);3q = malloc(...);4free(p);5p = q;此时程序中就不会出现内存泄漏了，因为p原本指向的区域已经被释放了：
也就是说：对一个指向堆区的指针，在修改它的指向之前，应该慎重考虑是否需要free，避免内存泄漏。
总结
Gn!
相信学到这里，你已经稍微认识到手动管理内存的复杂性和不易之处。针对C语言手动分配内存以及释放内存，给出以下总结和建议：
正确传参free函数。free函数需要传入指向动态分配内存块首字节的指针，free之前不妨检查指针是否已被移动。
在free内存块后，建议立刻将指针设置为NULL。这样可以规避一些常见的问题：
避免了"double free"的风险。对空指针调用
free函数是安全的，它不会有任何效果。减少悬空指针出现的风险。解引用空指针导致程序崩溃，比悬空指针带来的未定义行为要更容易检测和修正。
慎重改变堆区指针的指向。指向堆区域的指针，如果需要改变它的指向，在改变之前应当考虑指向的内存块是否需要free。
多函数共同管理同一块内存区域时，应严格遵循单一原则。尤其是，哪个函数用于分配内存，哪个函数用于free释放内存，这两个函数一定要明确单一的职责。
当然，细心耐心仔细永远是各种技巧和经验的前提，程序员应当做一个有心人。
课堂练习
Gn!
标准库函数strcat会将一个字符串追加到另一个字符串的末尾。
现在我们编写一个函数把两个字符串拼接起来，返回拼接的结果，但要求不改变其中任何一个字符串。其函数声明如下：
xxxxxxxxxx11char* dynamic_strcat(const char* prefix, const char* suffix);形参prefix表示前缀，suffix表示后缀，拼接的结果是prefix + suffix
比如：dynamic_strcat("abc", "d")，拼接的结果是"abcd"。
思路：
在堆上分配内存连续空间，用于存储结果字符串。那么这块连续空间有多大？
将prefix和suffix两个字符串的字符信息复制进去。
参考代码：
动态分配字符串题目-演示代码
xxxxxxxxxx281// 在堆上动态分配内存拼接两个字符串2char* dynamic_strcat(const char* prefix, const char* suffix) {3// 计算拼接后字符串的长度4int new_str_len = strlen(prefix) + strlen(suffix);5char *new_str = malloc(new_str_len + 1); // char在各平台上长度都是1，所以不用乘了6if (new_str == NULL) {8printf("ERROR: malloc failed in dynamic_strcat!\n");9exit(1);10}11// 长度是精确计算得出的，不用担心越界访问13strcat(strcpy(new_str, prefix), suffix);14return new_str;15}16int main(void) {18char str1[] = "hello";19char str2[] = " world!";20char* result_str = dynamic_strcat(str1, str2); // 注意只要涉及动态内存分配，一律用指针类型。这里不能用数组类型21puts(result_str);23// 现在不再使用result字符串了，不要忘记free它25free(result_str);26return 0;28}以上。
清零内存分配函数calloc
Gn!
calloc 函数也是C语言中进行动态内存分配的重要函数，下面是对 calloc 函数的详细介绍：
全名是：cleared allocation，该函数的最大特点是分配内存空间时会自动初始化0值。
该函数的声明是：
void* calloc(size_t num, size_t size);。该函数有两个参数：
num表示要分配的元素数量
size表示每个元素的内存大小此函数也会在堆空间上分配一片连续的内存空间，但不同的是，它基于元素的个数以及每个元素的大小来进行内存分配，所以calloc常用于在堆上分配数组的内存空间。
初始化为零：calloc 最重要的特性之一是它会自动将分配的内存初始化为零。这意味着不仅仅是分配内存，它还清零所有内存。
返回值在分配成功和失败时，和malloc是一致的。
calloc使用示例
Gn!
calloc用起来，除了传参有些区别，会自动初始化内存区域为0值外，基本和malloc一致。
一个使用示例如下：
calloc函数使用-代码示例
xxxxxxxxxx321234typedef struct {6int x;7int y;8} Node;9int main(void) {11// 分配一个长度为10的整数数组12int len = 10;13int *arr = calloc(len, sizeof(int));14int* p = arr;16for (int i = 0; i < len; i++){17printf("%d\n", *p++); // 此时数组中的元素都具有0值，而不是随机未定义的18}19// 使用完毕，不要忘记free21free(arr);22// 分配结构体数组24Node* node_arr_p = calloc(3, sizeof(Node));25// 分配一个结构体的内存空间26Node* node_p = calloc(1, sizeof(Node));27free(node_arr_p);29free(node_p);30return 0;32}总得来说，推荐在动态分配数组内存空间时，尤其是需要将内存空间初始化为0值时，使用calloc函数。
建议(重要)
Gn!
内存分配函数malloc(xx)和清零内存分配函数calloc(1, xx)，在分配内存的效果上看起来是一样的，都会在堆上分配一个该类型的内存空间。但它们还是有区别的：
malloc由于不需要初始化0值，性能可能会更好一些。所以在特别在意性能以及内存确实手动初始化时，优先选择用malloc函数。
calloc的优点是安全。如果使用malloc函数分配内存，那么内存块中的所有元素都只有一个随机值，此时若忘记初始化直接使用这些随机值就会产生未定义行为，这是非常危险的！！而这个危险，可以通过使用calloc函数解决。
在实际应用中，特别是当程序安全和正确性是首要考虑时，在两个函数都可用时，那么请选择使用calloc(1, xx)。
内存重分配函数realloc
Gn!
realloc函数是重要的内存分配函数之一，尤其是在需要动态扩容/收缩机制的数据结构中，它的使用几乎是必须的。
下面是它的详细介绍：
全名是：reallocation，表示内存重新分配。
函数声明是：
void* realloc(void* ptr, size_t new_size);。此函数有两个参数：
ptr：指向原来已分配内存的内存块。
new_size：新的内存块大小。该函数根据参数取值的不同，可能表现为malloc或free函数的行为：
如果ptr指针是一个空指针，那么该函数的行为和malloc一致——分配new_size字节的内存空间，并且返回该内存块的指针。
如果new_size的取值为0，那么该函数的行为就是free函数，会释放ptr指向的内存块。
如果没有出现上述两种特殊情况，realloc用于重新调整已分配内存块的大小(也就是ptr指针指向的已分配内存块的大小)：
当new_size的取值和已分配的内存块大小一致时，此函数不会做任何操作。
当new_size的取值比已分配的内存块小时(新内存块比旧内存块小时)，会在旧内存块的尾部(高地址)截断，被截断抛弃的内存块会被自动释放。
当new_size的取值比已分配的内存块大时(新内存块比旧内存块大时)，会尽可能地尝试原地扩大旧内存块(这样效率高)；
如果无法原地进行扩大，则会在别处申请空间分配new_size大小的新内存块，并将旧内存块中的数据全部复制进去后，将旧内存块自动释放。
不管采用哪种方式扩展旧内存块，新扩展部分的内存区域都不会初始化，仍只具有随机值。
如果realloc函数分配内存空间成功，它会返回指向新内存块的指针，若失败，仍会返回空指针，且不会改变旧内存块。
总之，realloc函数适用于调整已分配内存块的大小，特别是在动态数组或数据结构的大小需要在程序运行时增加或减少时使用。
realloc重分配内存机制解析
Gn!
当realloc用于重新分配内存块大小(ptr不是空指针，size不为0)时，有两种情况：
当new_size的取值比已分配的内存块小时(新内存块比旧内存块小时)，会从尾部(高地址)直接截断旧内存块，被截断抛弃的内存块会被自动释放。
我们可以从内存的角度来解释，如下图所示：
当new_size的取值比已分配的内存块大时(新内存块比旧内存块大时)，会尽可能地尝试原地扩大旧内存块(这样效率高)；如果无法原地进行扩大，则会在别处申请空间分配新内存块，并将旧内存块中的数据全部复制进去后，将旧内存块释放。
我们仍然画个图从内存的角度理解：
基于以上realloc的原理，realloc函数的使用和malloc、calloc都有明显不同，下面讲解一下如何使用它。
realloc函数正确的使用方式
Gn!
首先我们利用calloc或者malloc函数申请一片内存空间：
正确使用realloc函数-演示代码1
x1int len = 5;2int* arr_p = calloc(len, sizeof(int));3if (arr_p == NULL){4// 分配失败处理5}6// 代码运行到这里,arr_p一定不是空指针第一次分配了一个长度为5的整数数组。下面调用realloc函数对该数组做内存重分配，那么该如何写这个函数调用呢？
请看下列伪代码：
xxxxxxxxxx11realloc(arr_p, new_size); // new_size大小不确定这样写可以吗？
答案是否定的。假如这是一个扩容的过程，有可能导致旧内存块被释放。那么原本的arr_p指针就会指向一块被释放的区域，这会导致arr_p成为一个悬空指针。
于是，你想要用arr_p指针接收函数的返回值，这样就没有悬空指针了。按照下面的格式书写：
xxxxxxxxxx11arr_p = realloc(arr_p, new_size); // new_size大小不确定这样写就可以了吗？
答案还是否定的。你还需要考虑realloc分配内存失败的情况，若分配内存失败：
realloc会返回一个NULL，arr_p成为一个空指针，当然空指针本身是没有害处的。
重要的是，arr_p原本指向的旧内存块就成为了一片无法到达的区域，从而造成内存泄漏！
那么究竟应该如何正确的使用realloc函数进行内存块重分配呢？
这里给出一个惯用法，请大家参考下列伪代码：
正确使用realloc函数-演示代码2
xxxxxxxxxx71// p和arr_p指针类型一致2p = realloc(arr_p, new_size);3if (p == NULL){4// 分配失败处理5}6// 代码运行到这里,realloc分配内存成功7arr_p = p;这样写代码既避免了arr_p成为悬空指针，也不会因为realloc分配失败导致内存泄漏。请大家记住这种写法，当成一种固定规范去使用。
当然最后，我们给出一个正确使用realloc函数的演示代码：
正确使用realloc函数-演示代码3
xxxxxxxxxx61123void print_arr(int* arr, int len) {5printf("[");6for (size_t i = 0; i < len; i++) {7printf("%d, ", *arr++);8}9printf("\b\b]\n");10}11int main(void) {13int size = 5;14// 使用calloc分配内存并自动初始化为015int* arr = (int*)calloc(size, sizeof(int));16// 检查内存分配是否成功18if (arr == NULL) {19printf("calloc failed!\n");20exit(-1);21}22// 打印一下数组元素，此时全是023print_arr(arr, size);24int* p = arr; // 用于移动给数组元素赋值的指针26for (size_t i = 0; i < size; i++) {27*p++ = i;28}29print_arr(arr, size);30// 重分配内存缩减，惯用法32int new_size = 3;33int* tmp = realloc(arr, new_size * sizeof(int));34if (tmp == NULL) {35printf("realloc failed!\n");36exit(-1);37}38arr = tmp;39print_arr(arr, new_size);40// 重分配内存扩容，惯用法42int new_size2 = 10;43int* tmp2 = realloc(arr, new_size2 * sizeof(int));44if (tmp2 == NULL) {45printf("realloc failed!\n");46exit(-1);47}48arr = tmp2;49// print_arr(arr, new_size2); // Error：直接打印会出现很多随机值50int* p2 = arr + new_size; // 利用临时指针和指针算术运算将后续未初始化的元素全部初始化为852while (p2 < (arr + new_size2)) {53*p2++ = 8;54}55print_arr(arr, new_size2);56// 使用完毕后，不要忘记free58free(arr);59return 0;61}好了，到目前为止，C语言中最常用的三个内存分配函数以及free释放函数，你都已经学过了。下面是时候进行一波练习了。
手动实现C++中的Vector(重点)
Gn!
数组是一种基本的、常见的数据结构，它以其快速的访问速度而著称。
然而，在C语言中，传统的数组(指在栈上分配内存空间的数组)拥有一个显著的限制：它们的长度一旦确定便无法更改。这在处理动态数据集时显得尤为不便，如在不确定数据量的情况下存储用户输入。
C++通过引入Vector这样的动态数组解决了这个问题(Java中的ArrayList也是类似的)，它可以根据需要动态调整大小。遗憾的是，C语言标准库中并未提供类似的结构。但不要担心，借助于动态内存分配函数如malloc和realloc，我们完全可以在C中手动实现类似的功能。
在本节中，我们将一步步探索如何在C语言中实现一个自己的动态数组。
这将我们数据结构课程的开端，之后我们还会手动实现其它各种数据结构。
思路讲解
Gn!
在C语言中实现一个动态数组，通常使用一个结构体定义，如下所示：
动态数组结构体-定义
xxxxxxxxxx91// 使用别名来命名元素类型，如果未来需要改变元素类型，只需修改这个别名即可。2// 这么做提升代码的可维护性和扩展性,这实际上是模拟了C++的泛型编程3typedef int ElementType;4typedef struct {6ElementType *data; // 指向动态分配数组的指针7int size; // 当前动态数组中元素的数量8int capacity; // 动态数组当前分配的最大容量9} Vector;可以用下图来理解一个Vector动态数组：
除此之外，为了满足正常的动态数组的功能，我们还需要实现以下函数：
动态数组必要函数-声明
xxxxxxxxxx81// 初始化一个Vector动态数组.这实际上是模拟了C++的默认构造函数2Vector* vector_create();3// 销毁一个Vector动态数组，释放内存。这实际上模拟了C++的析构函数5void vector_destroy(Vector *v);6// 向动态数组末尾添加一个元素8void vector_push_back(Vector *v, ElementType element);当然你还可以提供一些其它的访问元素、插入元素的函数，但我们这里就暂时不给了。
头文件的使用
Gn!
在以往的课程中，我们都只用了一个main.c源文件就实现了整个程序的功能，这样的程序是比较简陋的，扩展性和可维护性都是比较差的。从实现这个动态数组开始，我们就教大家一种组织和管理C程序代码的标准做法——使用头文件。
头文件主要用于存放以下结构：
函数的声明
结构体的定义
类型别名的定义
宏定义
...
头文件允许程序员在多个源文件之间共享函数的声明以及结构体、类型别名和宏的定义，从这个角度讲头文件类似C++、Java等编程语言中的接口。
我们普遍采取的做法是：在头文件中声明函数，然后在某个源文件中包含头文件实现这些函数，最后在其余源文件中包含头文件，使用这些函数。
使用头文件，促进了模块化编程，提高了代码的复用性，使得代码更加易于维护。
下面基于实现动态数组Vector，给出一个具体的示例：
第一步: 创建和编写头文件
Gn!
创建一个头文件，以 .h 结尾。例如这里，我们可以把这个头文件叫vector.h。
编写头文件，把结构体的定义，函数声明等放进去：
vector.h头文件-参考代码
xxxxxxxxxx211// vector.h2// 使用别名来命名元素类型，如果未来需要改变元素类型，只需修改这个别名即可。3// 这么做提升代码的可维护性和扩展性,这实际上是模拟了C++/Java等编程语言的泛型编程4typedef int ElementType;5typedef struct {7ElementType *data; // 指向动态分配数组的指针8int size; // 当前动态数组中元素的数量9int capacity; // 动态数组当前分配的最大容量10} Vector;11// 初始化一个Vector动态数组.这实际上是模拟了C++的默认构造函数13Vector* vector_create();14// 销毁一个Vector动态数组，释放内存。这实际上模拟了C++的析构函数16void vector_destroy(Vector *v);17// 向动态数组末尾添加一个元素19void vector_push_back(Vector *v, ElementType element);20// ...其它相关声明和定义注意：头文件作为接口的目的是对外暴露公共部分，某些不属于公共部分不需要对外暴露的不要放在头文件当中！！！
比如：
在调用push_back函数向数组尾部添加元素时，必然会碰到容量不够而需要扩容的场景，此时需要扩容的函数来支持，这个扩容的函数需要声明在头文件中吗？
头文件保护
Gn!
头文件间可能会互相依赖包含，源文件又可以同时包含多个头文件，这就带来了一个比较严重的问题：一个头文件可能会被包含多次。
C/C++的头文件包含本质上是一种文本替换的过程，一个头文件被包含多次，就相当于一段代码在同一个文件中被书写多次，这在很多时候都是不允许，会引发编译错误。
程序员固然可以通过细心分析头文件的包含关系来避免头文件被包含多次，但对于一个大型项目而言，就有点强人所难了。
所以，C语言提供了"头文件保护"机制来避免同一个头文件被包含多次。
假设在上述头文件vector.h中，具体语法如下：
头文件保护机制语法-参考代码
xxxxxxxxxx71// 头文件vector.h中234// 头文件中定义的函数的声明、结构体的定义、类型别名的定义等6// !VECTOR_H这里使用了三个预处理指令，这里简单介绍一下它们的作用：
"#ifndef VECTOR_H"
ifndef是"If Not Defined"的缩写，意为如果xx宏未定义。
在这个具体指令中，它会检查宏" VECTOR_H"是否已经定义
如果宏" VECTOR_H"已经定义，则它会直接跳过到"#endif"指令之间的所有代码
如果宏" VECTOR_H"未定义，则它会继续运行。
"#define VECTOR_H"
非常简单一个宏定义
定义了一个宏，宏的名字是"VECTOR_H"
"#endif"
就是词组"end if"，没有缩写。
总是和"#ifndef"指令一起，构成一个条件处理块。
如果"#ifndef"检测到xx宏已经定义，那么就会直接跳过"#ifndef"到"#endif"指令之间的所有代码。这样就避免了重复包含头文件。
注意：
"#ifndef"和"#define"指令后面的宏命名，习惯上会和头文件名保持一致，且全部大写。宏命名时不能使用字符"."，所以使用"_"替代文件后缀名中的"."。
这三个指令结合在一起，用于防止头文件被重复包含。
以头文件vector.h为例子，当头文件第一次被包含时，宏 "VECTOR_H" 尚未定义，所以 "#ifndef VECTOR_H"条件为真，编译器继续处理到 "#define VECTOR_H"，此时宏被定义。
如果该头文件再次被包含，"#ifndef VECTOR_H" 会检测到 "VECTOR_H" 已定义，从而跳过这个头文件的其余内容，防止重复包含。
绝大多数现代编译器都支持
#pragma once指令来更简洁的实现头文件保护，你只需要在一个头文件的首行加上这个指令，也可以实现上述三个指令一样的效果。但该指令不是C/C++官方标准规范的一部分，一般还是不推荐使用，了解知道即可。于是为加上头文件保护后，
vector.h的内容如下：头文件保护语法-演示代码
xxxxxxxxxx21123typedef int ElementType;5typedef struct {7ElementType* data; // 指向动态分配数组的指针8int size; // 当前动态数组中元素的数量9int capacity; // 动态数组当前分配的最大容量10} Vector;11// 初始化一个Vector动态数组.这实际上是模拟了C++的默认构造函数13Vector* vector_create();14// 销毁一个Vector动态数组，释放内存。这实际上模拟了C++的析构函数16void vector_destroy(Vector* v);17// 向动态数组末尾添加一个元素19void vector_push_back(Vector* v, ElementType element);20// !VECTOR_H
第二步: 包含头文件与实现函数
Gn!
创建一个源文件——vector.c，然后包含头文件"vector.h"。
这里我们要讲解两种包含头文件的语法：
使用双引号 ""：
当使用双引号时，编译器首先在当前文件的目录中搜索头文件。如果在这里没有找到，它会继续在标准库头文件的路径中搜索。
""主要用于包含用户自定义的头文件。因为这种写法会告诉编译器优先查找与源文件同目录的头文件。
示例：#include "vector.h"
使用尖括号 <>：
使用尖括号时，编译器只在标准库头文件的路径中搜索头文件。它不会在当前文件的目录中查找。
尖括号用于包含标准库头文件或第三方库头文件。
示例：#include <stdio.h>、#include <stdlib.h>
所以要想包含我们自定义的头文件"my_vector.h"，需要使用双引号""，而不是尖括号<>。
包含头文件后，我们就可以得到这些函数的声明，进而实现它们：
vector.c源文件-代码
xxxxxxxxxx181// vector.c2345Vector* vector_create() {7// 实现8}9void vector_destroy(Vector *v) {11// 实现12}13void vector_push_back(Vector *v, ElementType element){15// 实现16}17// 其他函数的实现...
第三步: 测试自定义动态数组Vector
Gn!
完成一系列关于Vector的开发实现后，接下来的关键步骤就是测试。
在实际的开发中，当我们完成了某个独立模块、组件的开发后，都需要编写一系列测试用例，进行彻底的单元测试工作，来及时的发现和修复程序中的缺陷和bug，从而提高整体代码质量。
编写测试用例，完成单元测试开发，也是一个普通程序员的本职工作之一。
在这里，我们可以创建一个"test.c"的源文件，用于运行一系列的测试用例：
创建和销毁。验证 Vector 是否可以成功创建和销毁，没有内存泄漏。
添加元素：测试向 Vector 添加元素的功能，确保数组可以正确地扩容。
边界条件检查：检查 Vector 在极端情况下（如恰好超出容量）的行为是否正确。
....
test.c测试源文件-参考代码
xxxxxxxxxx231234int main(void) {6// 在栈上创建一个Vector指针，指向堆上的结构体对象7Vector* v = vector_create();8// 向Vector中添加元素10for (int i = 0; i < N; i++) {11vector_push_back(v, i);12}13// 遍历访问Vector中的元素15for (int i = 0; i < N; i++) {16printf("%d\n", v->data[i]);17}18// 用完了销毁Vector20vector_destroy(v);21return 0;23}如果测试没有问题，那么这个动态数组Vector组件就算完成开发了。
实现动态数组
Gn!
在上面"头文件的使用"小节中，程序的骨架已经搭建完成了。现在就只需要在"vector.c"源文件中实现所有的函数就可以了。
下面给出每个函数的实现思路以及参考代码：
实现vector_create()
Gn!
vector_create()函数的目的是初始化一个动态数组Vector，我们规定：
调用此函数会创建一个默认容量是10的动态数组。(你也可以做别的规定)
这个函数的编写过程中，理解动态数组的内存结构是重点：
参考代码如下：
实现vector_create()函数-参考代码
xxxxxxxxxx261// 设置动态数组的默认最小容量2// 初始化一个Vector动态数组.这实际上是模拟了C++的默认构造函数4Vector* vector_create() {5// 先在堆上分配结构体Vector6Vector* v = calloc(1, sizeof(Vector)); // malloc需要手动初始化每一个成员，calloc方便安全一些7if (v == NULL){8printf("calloc failed in vector_create.\n");9return NULL; // 创建失败返回空指针10}11// 申请动态数组，并赋值给Vector的data成员13v->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType)); // 此时数组中的元素都具有0值，而不是随机值14if (v->data == NULL){15printf("malloc failed in vector_create.\n");16// 不要忘记free结构体Vector，否则会导致内存泄漏17free(v);18return NULL; // 创建失败返回空指针19}20// 继续初始化Vector的其它成员22v->capacity = DEFAULT_CAPACITY;23// size已自动初始化为0值，所以不需要再次赋值了。但如果用malloc就不要忘记初始化它24return v;26}在此代码中，特别需要注意的是在动态数组空间申请失败时的操作。我们需要先释放已分配的 Vector 结构体空间，以避免内存泄漏。
这种细心的资源管理对于写出健壮的C语言代码是至关重要的。
实现vector_destroy()
Gn!
vector_destroy()函数的作用是在确定不使用该动态数组后，及时释放其占用的内存。
该函数的实现非常简单，只需要调用free函数即可。唯一需要注意的是：
应该先free动态数组，再free结构体。否则动态数组空间会无法释放，导致内存泄漏！
参考代码：
实现vector_destroy()函数-参考代码
xxxxxxxxxx51// 销毁一个Vector动态数组，释放内存。这实际上模拟了C++的析构函数2void vector_destroy(Vector* v) {3free(v->data);4free(v);5}
实现vector_push_back
Gn!
实现vector_push_back函数是动态数组设计中的核心环节，它的作用是向 Vector 动态数组的末尾添加一个新元素。
具体的实现逻辑是：
在添加元素之前，push_back 函数需要检查当前数组的大小（size）是否已经达到其容量（capacity）。
如果已经达到(size 等于 capacity)，这意味着没有足够的空间来存储新元素，因此需要先进行扩容操作。
如果未达到容量或扩容完成，则将新元素添加到数组末尾。
关于扩容策略的选择
C++的Vector在给动态数组扩容时，一般会在当前容量较小时直接扩容到原本的2倍，在容量已经很大时扩容到原本的1.5倍。
Java中的ArrayList在给动态数组扩容时，会无脑扩容为原本的1.5倍。
在这里我们可以给出一个阈值(threshold)，作为容量大小的判断依据，小于这个阈值时直接扩容到原本的2倍，超过这个阈值时扩容到原本的1.5倍。
当然，只要你愿意，你也可以选择其它扩容策略。
参考代码如下：
实现push_back()-演示代码
xxxxxxxxxx3312// 在C语言中,static修饰函数表示此函数仅在当前文件内部生效4// 类似于C++或Java中的访问权限修饰符private5static void vector_resize(Vector* v) {6// 只要调用这个函数肯定就是需要扩容的7int old_capacity = v->capacity;8int new_capacity = (old_capacity < THRESHOLD) ?10(old_capacity << 1) : // 容量还未超出阈值每次扩容2倍11(old_capacity + (old_capacity >> 1)); // 容量超出阈值每次扩容1.5倍12// 利用realloc重新分配动态数组14ElementType *tmp = realloc(v->data, new_capacity * sizeof(ElementType)); // realloc惯用法15if (tmp == NULL){16printf("realloc failed in resize_vector.\n");17exit(1); // 扩容失败，退出整个程序。或者也可以做别的处理18}19// 扩容成功，重新赋值Vector成员20v->data = tmp;21v->capacity = new_capacity;22}23// 向动态数组末尾添加一个元素25void vector_push_back(Vector* v, ElementType element) {26// 先判断是否需要扩容27if (v->capacity == v->size) {28vector_resize(v);29}30// 扩容完成后或不需要扩容，即向末尾添加元素31v->data[v->size] = element;32v->size++;33}该函数的实现有以下注意事项：
单一原则。vector_push_back函数用于插入元素，不应该将扩容的逻辑直接写在其中，而是重新定义一个函数vector_resize
vector_resize函数是Vector实现自动扩容功能的一部分，它对外界而言是无意义的。所以它既不需要声明在头文件中，在实现它时也应该使用static修饰，以避免它被外界所调用。
扩展
Gn!
好了，到这里你就已经实现了一个自己的，存储int类型元素的C语言动态数组Vector。现在思考一下，我想让你把它变成存储字符串的，动态字符串数组，该怎么办呢？
其实只需要改变别名
ElementType的类型即可，那应该改成什么呢？
二级指针
Gn!
二级指针，或称为指针的指针，也就是一个指向另一个指针的指针，也就是存储了另一个指针变量地址的指针。
这听起来可能有些绕口，但它在C语言中扮演着极其重要的角色。它不仅使我们能够更灵活地操作内存，还是理解和构建更复杂数据结构（如链表、树和图）的基础。
在这里，我们以构建一个基础的链表数据结构为例，引出和讲解一下二级指针。
当然在这个阶段，我们不会深入探讨链表的所有细节，链表的更多内容将在后续数据结构阶段再讲解。
头插法实现单向链表
Gn!
单向链表是由一系列结点组成的线性数据结构，其中每个结点包含数据和一个指向下一个结点的指针。如下图所示：
具体到实现，链表的每一个结点就是一个结构体对象，该结构体的定义如下：
头插法实现单向链表-结构体代码
xxxxxxxxxx71typedef int DataType;2typedef struct node { // 这里的名字不能省略3DataType data;4// 编译到该行时,别名Node还未定,所以这里仍然需要使用struct关键字来声明指向下一个结点的结构体指针5// Error: Node* next;6struct node* next;7} Node;在很多时候，我们往往还会定义一个
LinkedList结构体类型以表示单链表结构，但这里我们先不用。只在需要创建单向链表的地方，用下列代码创建一个NULL结点指针，表示此时的链表一个结点没有，是一个空链表。
xxxxxxxxxx11Node *list = NULL; // 表示链表为空,一个结点都没有随后我们可以调用头插法函数，进行链表结点的创建。所谓头插法，指的是：
先创建一个新结点。
然后将新结点的next指针指向原本的第一个结点
更新头指针，使其指向新创建的结点。
具体而言，又可分为两种情况：
头插法插入整个链表的第一个结点
头插法插入链表随后的结点
可以用下面两张图来描述：
实际上这两种情况，在代码实现上是没有区别的，你发现了吗？
将头插法的逻辑搞清楚后，具体到头插法的函数实现，有两种比较常见的做法：
函数只是将新的头指针作为返回值返回，并不会直接修改头指针指向。
函数没有返回值，但是在函数内部直接修改头指针，头指针指向新的第一个结点。
下面给出这两种做法的思路和参考代码：
函数返回新头指针
Gn!
若函数将新的头指针作为返回值返回，则意味着在main函数中，需要对头指针list进行手动赋值更新：
函数返回新头指针-演示代码1
xxxxxxxxxx61// main函数中2Node *list = NULL; // 表示链表为空,一个结点都没有3list = insert_head(list, 1);4list = insert_head(list, 2);5list = insert_head(list, 3);6list = insert_head(list, 4);头插函数的实现，参考代码如下：
函数返回新头指针-演示代码2
xxxxxxxxxx171Node* insert_head(Node* list, DataType data) {2// 1.创建新节点3Node *new_node = malloc(sizeof(Node));4if (new_node == NULL){5printf("malloc failed in insert_head.\n");6exit(1);7}8// 2.初始化新节点的数据域10new_node->data = data;11// 3.新结点的next指针指向原本第一个节点13new_node->next = list;14// 4.返回新结点指针(头指针)16return new_node;17}其中的核心代码就是：
xxxxxxxxxx11new_node->next = list;它反映了此链表是通过头插法进行创建，添加结点的。
启动main函数，此头插法创建的链表应该是：
4 --> 3 --> 2 --> 1 --> NULL
函数没有返回值
Gn!
使用有返回值的函数，更新头指针的任务就被需要函数调用者来手动完成了。若希望省略这一步骤，则需要在函数内部对头指针进行修改，函数也就不需要返回值了。
此时main函数中创建链表的代码就可以改成：
函数没有返回值-演示代码1
xxxxxxxxxx61// main函数中2Node *list = NULL; // 表示链表为空,一个结点都没有3insert_head(list, 1);4insert_head(list, 2);5insert_head(list, 3);6insert_head(list, 4);此函数的实现和上面函数的实现几乎没有区别，只是多了一步头指针的赋值罢了，参考下列代码：
函数没有返回值-演示代码2
xxxxxxxxxx171void insert_head(Node* list, E data) {2// 1.创建新节点3Node* new_node = malloc(sizeof(Node));4if (new_node == NULL) {5printf("malloc failed in insert_head.\n");6exit(1);7}8// 2.初始化新节点的数据域10new_node->data = data;11// 3.新结点的next指针指向原本第一个节点13new_node->next = list;14// 4.将头指针指向新结点16list = new_node;17}运行main函数，这个链表能够创建成功吗？
显然是失败的，那么为什么呢？
归根结底是因为C语言的值传递机制，参考下图：
由于C语言的值传递机制，insert_head函数得到的只不过是list指针的副本，在函数内部list副本确实指向了创建的新结点，但却无法影响main函数中list指针本身。除此之外，这么做还会导致内存泄漏。
这个案例，就凸显了C语言函数参数传递的两个关键特点：
如果直接传递参数本身，那么函数无法对参数本身进行修改，只能修改它的副本。
如果传递参数的指针，那么函数可以通过指针变量的副本去修改参数本身，但却无法修改指针。
现在我就希望修改这个指针本身，那怎么办呢？
很简单，传递指向指针的指针，也就是二级指针。
二级指针的使用语法
Gn!
二级指针是指向指针的指针，在C语言中通过两个星号（**）定义。例如，int **ptr 表示一个指向 int 类型指针的指针。
二级指针本质上还是一个指针变量，所以它在使用之前也需要进行初始化。
它可以初始化为一个空指针，也可以指向一个已存在的指针变量(存储指针变量的地址)。
比如以下声明和初始化二级指针的语法：
二级指针的使用语法-演示代码1
xxxxxxxxxx61int *p; // 一级指针,一般直接叫指针即可2int **pp; // 二级指针3int num = 10;5p = # // 一级指针指向value变量6pp = &p; // 二级指针指向指针变量p使用二级指针，我们可以通过一次解引用修改一级指针的指向，也可以通过两次解引用修改一级指针所指向的对象的值。例如：
二级指针的使用语法-演示代码2
xxxxxxxxxx51int num = 20;2p = &another_value; // 初始化指向num变量的一级指针变量3*pp = &p; // 初始化指向p指针变量的二级指针变量4**pp = 100; // 通过二级指针, 解引用两次修改num的值总之，利用二级指针我们可以实现：
修改对应一级指针的指向
修改对应一级指针指向的对象
这在函数调用中尤其有用，因为即使在值传递，函数只得到副本的情况下，也可以通过二级指针的副本来修改原始指针。
二级指针在处理复杂数据结构和进行动态内存分配时非常重要，是高级C编程的一个关键组成部分。
利用二级指针实现无返回值头插函数
Gn!
使用二级指针实现无返回值的头插法函数，参考代码如下：
利用二级指针实现无返回值头插函数-参考代码
xxxxxxxxxx171void insert_head(Node** p, DataType data) {2// 1.创建新节点3Node* new_node = malloc(sizeof(Node));4if (new_node == NULL) {5printf("malloc failed in insert_head.\n");6exit(1);7}8// 2.初始化新节点的数据域10new_node->data = data;11// 3.新结点的next指针指向原本第一个节点13new_node->next = *p;14// 4.将头指针指向新结点16*p = new_node;17}注意，二级指针p解引用一次才得到原本的list指针，不要忘记这个解引用操作。
除此之外，函数调用也需要做出一些修改：
利用二级指针实现无返回值头插函数-参考代码2
xxxxxxxxxx51Node* list = NULL;2insert_head(&list, 1);3insert_head(&list, 2);4insert_head(&list, 3);5insert_head(&list, 4);通过测试，我们发现该链表创建成功，并且就是"4 --> 3 --> 2 --> 1 --> NULL"
我们仍然可以通过画图来理解二级指针，以及这里的头插法，如下图所示：
于是，我们在这里总结一下C语言函数传参的规律特点：
直接传递变量值：用于读取数据，不修改原始变量。
传递一级指针：可以修改指针指向的数据，但不能改变指针自身。
传递二级指针：可以修改一级指针的指向，或者一级指针指向的数据。
传递三级指针：可以修改二级指针的指向，或者一级指针的指向以及指针指向的最终数据。
...
当然，一级指针和二级指针是比较常用的，三级指针以及更多嵌套则几乎不会在实际开发中使用，理解就可以了。
函数指针
Gn!
函数指针(Pointer to Function)，即指向函数的指针。它仍然是一个指针变量，用于存储地址，只不过存储的不再是数据的地址，而是函数的地址。
如何理解函数的地址这个概念呢？
在C语言中，函数在经过编译后变成了一系列机器指令，存储在程序的代码段(只读)当中。
函数的地址是指向这些指令序列起始点的内存地址，即函数的入口点。每个函数的指令序列从起始地址开始，到结束指令地址为止，构成了函数在内存中的一块区域。
简而言之，函数的地址可以视为指向其指令集合起始位置地址的指针。
函数指针语法在C语言中，最常见的用途就是——"将函数作为参数传递"。这种作为参数传递的函数，就是我们常说的"回调函数(callback function)"。
在具体讲解回调函数的语法之前，我们先来学习一下C语言当中，这个稍微会让人惊诧的语法——函数指针。
函数指针变量的声明
Gn!
函数指针就是一个存储函数地址的变量，所以你就把它类比于一个普通指针变量。如果它声明在局部函数体内部，那么这个指针变量就是一个局部变量，如果声明在函数体外部，那么它就是一个数据段中的全局变量....
在具体使用时，它也像普通指针变量一样，也会有声明和初始化的语法。
首先是函数指针的声明，它的语法形式如下：
xxxxxxxxxx11函数返回值类型 (*函数指针名)(函数形参列表);解释：
函数返回值类型：它指明了函数返回值的数据类型。函数指针需要指向哪个函数，就照抄这个函数的返回值类型。
函数指针名：这就是函数指针变量的名字，就是一个指针变量名。不要忘记前面的"*"星号。
函数形参列表：它指明了函数调用时接受参数的数据类型、数量以及位置。注意，此列表只需要照抄函数形参列表中的类型，而不需要写形参名，你知道这是为什么吗？
具体的，可以参考以下代码示例：
函数指针的声明语法-演示代码
xxxxxxxxxx81// 声明一个指向"返回值类型是void、不接受任何参数的函数"的指针2void (*fun_ptr)(void);3// 声明一个指向"返回值类型是int、接受两个int参数的函数"的指针5int (*fun_ptr2)(int, int);6// 声明一个指向"返回值类型是char指针、接受一个const char指针参数的函数"的指针8char* (*fun_ptr3)(const char *);我们前面讲过函数指针主要的作用就是将函数作为参数传递，所以函数指针的声明大概率要写在某一个函数的形参列表中。
此时语法中"*"可以省略(虽然也可以不省略，但建议省略)，这样语法就变成了下面的样子：
函数指针作为形参类型-演示代码
xxxxxxxxxx111// test函数需要传入一个"返回值类型是void、不接受任何参数的函数"的指针2void test(void fun_ptr(void)){3}4// test2函数需要传入一个"返回值类型是int、接受两个int参数的函数"的指针6void test2(int fun_ptr(int, int)){7}8// test3函数需要传入一个"返回值类型是char指针、接受一个const char指针参数的函数"的指针10void test3(char* fun_ptr3(const char *)){11}这样关于函数指针的声明语法，你就已经学会了。
给函数指针类型起别名
Gn!
我们之前提到过，最好不要给指针类型起别名，会影响代码的可读性。但由于函数指针类型的语法实在太奇葩、太怪异，起别名反而是一个增强可读性的手段。
所以一般我们都建议在使用函数指针类型时，给它起一个别名。
给函数指针类型起别名的语法，同样很怪异。它看起来就是在声明语法的前面加上一个"typedef"关键字，然后直接用别名替换指针名的位置。语法如下：
xxxxxxxxxx11typedef 函数返回值类型 (*函数指针别名)(函数形参列表);下面给出一个具体的代码示例，以供参考：
给函数指针类型起别名-参考代码
xxxxxxxxxx111// 一个指向"返回值类型是void、不接受任何参数的函数"的指针类型,别名是FuncPtr2typedef void (*FuncPtr)(void);3// 函数指针类型作为形参5void test(FuncPtr p){6}7void main(void){8// 声明函数指针类型指针变量9FuncPtr p;10return 0;11}可以看到，在给函数指针类型起别名后，它的使用语法确实"变得正常"了，它看起来像是一个正常的变量声明语法了。
注意，要区分以下两个语法：
以下语法是一个函数指针类型指针变量的声明，是一个指针变量的声明：
xxxxxxxxxx11函数返回值类型 (*函数指针名)(函数形参列表);它意味着这里声明一个函数指针类型的指针变量，把";"分号去掉，在后面直接加上赋值号"="，就可以进行初始化了。
但以下语法是一个函数指针类型的定义：
xxxxxxxxxx11typedef 函数返回值类型 (*函数指针别名)(函数形参列表);它一般写在头文件中，或者源文件的上面，和以往你定义结构体类型给出别名是一个概念。千万不要弄混淆了。
函数指针变量的初始化
Gn!
函数指针变量的初始化虽然有些特殊，但先定义别名，配合别名使用，其实是一个很简单直接的语法。
首先作为一个指针变量，是允许使用字面值NULL赋值的，也就是一个空指针。
若想正常将一个函数地址赋值给函数指针变量，直接使用函数名赋值即可，这是因为在C语言中函数名就代表函数地址。
在给函数指针类型起别名的情况下，参考以下初始化函数指针的代码：
函数指针变量的初始化-语法演示
xxxxxxxxxx181// 一个指向"返回值类型是void、不接受任何参数的函数"的指针类型,别名是FuncPtr2typedef void (*FuncPtr)(void);3void test(void) {}5void func(FuncPtr ptr) {}6int main(void) {7// 直接使用别名就行声明和初始化，这种做法使得函数指针的使用看起来正常了8FuncPtr p = NULL; // 可以是空指针9FuncPtr p2 = test;10FuncPtr p3 = &test; // 可以对函数名取地址,但其实没必要11// func需要传入一个函数指针13func(p2);14func(p3);15func(test);16func(&test); // 可以对函数名取地址,但其实没必要17return 0;18}总之，只要找到一个"返回值类型，形参类型"和函数指针声明一致的函数，就可以使用此函数的函数名完成对函数指针变量的初始化。
一个简单的计算器示例
Gn!
我们来演示一下在C语言中如何将函数作为参数传递，这种参数传递的函数就是编程领域中的"回调函数"。
首先，定义一个函数指针类型，用于指向不同的计算操作函数：
xxxxxxxxxx11typedef int (*Operation)(int, int);然后我们可以基于函数指针的类型，定义几个基本的计算函数，比如加、减、乘除等。
计算器示例-演示代码1
xxxxxxxxxx191int add(int a, int b) {2return a + b;3}4int subtract(int a, int b) {6return a - b;7}8int multiply(int a, int b) {10return a * b;11}12double divide(int a, int b) {14if (b != 0) {15return (double)a / b;16}17printf("error: divide by 0");18return INFINITY; // 返回无穷大，需要包含头文件<math.h>19}最后，我们实现一个calculate函数，它会根据传入的计算规则函数不同，而体现出不同行为，执行对应规则的计算：
计算器示例-演示代码2
xxxxxxxxxx31int calculate(int a, int b, Operation op) {2return op(a, b);3}在main函数中，我们就可以测试这个计算器calculator函数。如下：
计算器示例-演示代码3
xxxxxxxxxx121int main() {2int x = 10, y = 5;3// 使用加法4printf("x + y = %d\n", calculate(x, y, add));5// 使用减法6printf("x - y = %d\n", calculate(x, y, subtract));7// 使用乘法8printf("x * y = %d\n", calculate(x, y, multiply));9// 使用除法10printf("x / y = %d\n", calculate(x, y, divide));11return 0;12}在这个案例当中，通过函数指针向calculate函数传入了不同的计算规则函数，从而实现根据传入的规则进行不同的计算。
这个过程中被作为参数传递的函数，就是"回调函数"。使用回调函数，可以提高代码的灵活性和扩展性，是一种非常实用的编程技巧。
qsort函数
Gn!
C语言中的qsort 函数是一个功能强大的标准库函数，调用它需要包含头文件<stdlib.h>。
正如它的函数名一样，它的作用是进行排序，而由于在函数内部采用快速排序算法(quick sort)，所以它被命名为"qsort"。
该函数的声明是：
xxxxxxxxxx11void qsort(void *base, size_t num, size_t size, int (*compare)(const void *, const void *));函数的每一个参数意为：
base：通用指针类型，表示要排序的数组，可以是任意类型数组。
num：数组中的元素数量，也就是待排序的base数组的长度。
size：base数组中每个元素的大小，通常使用 sizeof 运算符得到。
compare：函数指针类型，表示该函数需要传入一个返回值类型是
int，形参列表是const void *, const void *的表示比较规则的函数。
qsort函数的行为
Gn!
关于qsort函数的行为，需要的有两个规则：
排序的规则：qsort函数会将base数组中的元素按照从小到大的顺序排序，这个排序的规则是固定的。
比较大小的规则：既然是按照从小到大排序，那么如何决定数组中元素的大小关系呢？答：由函数指针传入的函数决定！
函数指针传入的函数声明如下：
xxxxxxxxxx11int any_name(const void *a, const void *b);这个函数用来确定base数组中任意两个元素的大小关系，其中形参的a和b代表base数组中的两个待比较元素的指针。
返回值整数代码a和b的大小关系，实际上可以把该函数看出"(a - b)"：
如果返回值小于0是个负数，说明a < b
如果返回值大于0是个正数，说明a > b
如果返回值是0，说明a = b
注意事项：
特别需要注意的是，要理解这句：形参的a和b代表base数组中的两个待比较元素的指针。
假如base数组是一个int数组，通用指针类型a和b也就是指向int类型的指针类型，也就是int*类型，此时比较规则的函数应该按照下列格式编写：
qsort函数的行为-参考代码1
xxxxxxxxxx61int my_cmp(const void *a, const void *b){2// 将a和b转换成int*类型，然后才可以进行比较操作3const int *num1 = a;4const int *num2 = (const int*)b; // 对于C语言而言，强转语法可写可不写5// 后续表示大小规则的逻辑6}和int类型数组类似的，结构体数组也差不多，假如有一个Student类型的数组：
qsort函数的行为-参考代码2
xxxxxxxxxx61int my_cmp(const void *a, const void *b){2// 将a和b转换成Student*类型，然后才可以进行比较操作3const Student *s1 = a;4const Student *s2 = (const Student*)b; // 对于C语言而言，强转语法可写可不写5// 后续表示大小规则的逻辑6}但如果待排序的数组是一个指针数组，最常见的就是对字符串数组
char *strs[]或者char **进行排序，此时通用指针类型a和b也就是指向char*类型的指针类型，此时a和b的类型就是"char **"类型。此时比较规则的函数就应该按照下列格式去写：
qsort函数的行为-参考代码3
xxxxxxxxxx61int my_cmp(const void *a, const void *b){2// 将a和b转换成char*类型，然后才可以进行比较操作3const char *s1 = *(const char **)a; // 强转成二级指针再解引用一次，才能得到char*字符串的一级指针4const char *s2 = *(const char **)b; // 注意：此时的强转语法是不能省略的。5// 后续表示大小规则的逻辑6}尤其要注意：此时强转的语法是不能省略的，必须先强转再解引用。因为通用指针类型是明确不能直接解引用的！！！
qsort函数是函数指针和回调函数应用的经典示例。它需要传入一个比较函数用于确定"数组内元素的大小关系"，并最终将数组内的元素按照"从小到大"的顺序排序。
qsort函数使用练习
Gn!
基于以下结构体，创建一个长度为10的结构体数组：
qsort函数使用练习-结构体定义
xxxxxxxxxx61typedef struct {2int stu_id;3char name[25];4int age;5int total_socre;6} Student;并将结构体数组中的元素做以下初始化：
qsort函数使用练习-结构体数组初始化
xxxxxxxxxx341// 用于初始化一个结构体元素2void init_student(Student* stu, int stu_id, const char* name, int age, int total_socre) {3stu->stu_id = stu_id;4strncpy(stu->name, name, sizeof(stu->name) - 1);5stu->name[sizeof(stu->name) - 1] = '\0'; // 确保字符数组以空字符结束,能够表示一个字符串6stu->age = age;7stu->total_socre = total_socre;8}9// 用于打印结构体数组10void print_stus(Student* stus, int len) {11for (int i = 0; i < len; i++) {12printf("Student %d: ID=%d, Name=%s, Age=%d, Score=%d\n",13(i + 1), stus[i].stu_id, stus[i].name, stus[i].age, stus[i].total_socre);14}15}16int main(void) {17// main函数当中:18int len = 10;19Student stus[10] = { 0 };20// 初始化结构体数组22init_student(stus, 1, "ZS", 18, 600);23init_student(stus + 1, 3, "Maria", 17, 620);24init_student(stus + 2, 9, "Mark", 20, 600);25init_student(stus + 3, 6, "LS", 18, 700);26init_student(stus + 4, 4, "BS", 18, 600);27init_student(stus + 5, 7, "WS", 30, 600);28init_student(stus + 6, 10, "TS", 18, 600);29init_student(stus + 7, 2, "ABC", 16, 600);30init_student(stus + 8, 5, "AA", 18, 600);31init_student(stus + 9, 8, "GG", 18, 400);32return 0;34}基于以上结构体数组容器，利用qsort函数实现以下规则的排序：
将学生数组按照成绩由高到低排序
将学生数组按照学号从小到大排序
综合排序，先按总分从高到低进行排序，若总分相同则按照年龄从低到高排序。若仍然都相同，则按照名字的字典顺序排序。
参考代码如下：
qsort函数使用练习-自定比较规则函数
xxxxxxxxxx401// qsort函数会将学生数组按照学号,从小到大排序2// 该比较规则认为: 学号越小,学生越小3int my_cmp(const void* a, const void* b) {4// void指针需要类型转换后才能使用5Student* s1 = a;6Student* s2 = b;7return (s1->stu_id) - (s2->stu_id);9}10// qsort函数会将学生数组按照成绩由高到低排序12// 该比较规则认为: 成绩越高,学生越小13int my_cmp2(const void* a, const void* b) {14// void指针需要类型转换后才能使用15Student* s1 = a;16Student* s2 = b;17return (s2->total_socre) - (s1->total_socre);19}20/*22* qsort函数的排序规则是23* 先按总分从高到低进行排序，成绩相同则按照年龄从低到高排序24* 若仍然相同,按照名字的字典顺序排序25*/26int my_cmp3(const void* a, const void* b) {27// void指针需要类型转换后才能使用28Student* s1 = a;29Student* s2 = b;30if (s1->total_socre != s2->total_socre) {32return s2->total_socre - s1->total_socre;33}34// 运行到这里,总分一定是相同的,继续依据年龄来比较35if (s1->age != s2->age) {36return s1->age - s2->age;37}38// 运行到这里,总分和年龄都相同了,继续根据名字的字典顺序排序39return strcmp(s1->name, s2->name);40}定义好比较规则函数后，就可以调用qsort函数，传入对应比较规则函数，即可实现对应规则排序：
xxxxxxxxxx11qsort(stus, len, sizeof(Student), my_cmp3); // 按照my_cmp3函数的比较规则从小到大排序以上。
总结
Gn!
通过在qsort 函数中使用不同的比较函数作为回调函数，不仅提高了代码的灵活性和可扩展性，而且实现了代码逻辑的有效解耦：
在这种设计中，排序逻辑与比较逻辑是独立的，使得每部分都可以单独修改和优化，而不会影响到另一部分。这种方法充分展示了函数回调在提高代码结构清晰度和降低各个组件间耦合度方面的强大优势。