C_指针的应用

C_指针的应用

动态内存分配

动态内存分配是链式结构的基础。可以把动态分配的内存链接在一起，形成链表、树、图等灵活的数据结构。

内存分配函数

在 <stdlib.h> 头文件中，三个函数可以进行动态内存分配：

  • void* malloc(size_t size)

    1
    2
    3
    4
    5

       分配 `size` 个字节的内存块，不对内存块进行清零；如果无法分配指定大小的内存块，返回空指针。

    -  ```c
       void* calloc(size_t nmemb, size_t size) 
    

为有 `nmemb` 个元素的数组分配内存块，其中每个元素占 `size` 个字节，并且对内存块进行清零；如果无法分配指定大小的内存块，返回空指针。

  • void* realloc(void *ptr, size_t size)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

       调整先前分配内存块的大小。如果重新分配内存大小成功，返回指向新内存块的指针，否则返回空指针。

     `malloc` 效率最高， `malloc` 和 `realloc` 函数的`size`是数组总大小，`calloc` 函数的`size`是数组中一个元素的大小。

    返回 `void*` 类型的指针。 `void*` 类型的值是"通用"指针。 `void* `类型的指针可以转换成其它类型的指针，其它类型的指针也可以转换成 `void*` 类型的指针。

    ### 空指针

    调用内存分配函数时，找不到足够大的内存空间，函数就会返回空指针。空指针是"不指向任何对象的指针"。通常是将它指向一个特殊的地址(0x00000000)，并且用宏 `NULL` 表示。

    >对空指针进行解引用，其行为是未定义的。不过在实现上，一般会报空指针异常，导致程序崩溃。

    当函数可能返回空指针的时候，在使用指针之前，应该进行判断。

    ```c
    void *p = malloc(1024);
    if (p == NULL) {
    	/* allocation failed; take appropriate action */
    }

if (p == NULL) 可以写成if (!p) ； if (p != NULL) 也可以写成 if (p) 。

动态分配字符串

需要给有 n 个字符的字符串分配内存空间：

1
char *p = malloc(n + 1);

注意：

  1. 在 C 语言中，字符串是以 \0 结尾的，因此参数为 n+1 而非 n。

  2. 通用指针类型void* 可以自动转换为任意指针类型，因此可以不需要强制类型转换。(强制力类型转换如下)

1
>p = (char *) malloc(n + 1);

动态分配数组

  1. 使用 malloc 为数组分配内存空间

    1
    int *arr = malloc(size * sizeof(int));

    用 sizeof 运算符计算所需的内存空间，同一类型在不同平台上所占内存大小可能是不相同的。

    申请内存成功后，可以像使用普通数组一样使用动态数组

    1
    2
    3
    for (int i = 0; i < n; ++i) {
    	arr[i] = 0;
    }

  2. 使用 calloc 为数组分配内存空间

    1
    int *arr = calloc(size, sizeof(int));

    数组在需要初始化为 0 的情况下，calloc 比 malloc 效率更高。结构体需要清零操作，可以使用 calloc 为结构体变量申请内存空间：

    1
    2
    3
    4
    5
    typedef struct {
     int x;
     int y;
    } Point;
    p = calloc(1, sizeof(Point));

  3. 使用 realloc 重新调整数组的大小

    1
    2
    int *arr = (int *)malloc(size * sizeof(int));
    arr = realloc(arr, size * sizeof(int));

    在需要调整数组大小的情况下，realloc 比手动释放和重新分配内存空间更高效。调用 realloc 函数时，ptr 必须指向先前通过 malloc , calloc 或者 realloc 获得的内存块(即堆内存空间)。

    C 标准没有明确指明 realloc 的工作原理，但实际上会比较高效：

    1. 当新内存块比旧内存块小的时候，会直接截断旧内存块。
    2. 当新内存块比旧内存块大的时候，会试图原地扩大旧内存块，如果不可行，再在别处申请内存块，并把旧内存块里的数据复制到新内存块，同时释放旧内存块。

    关于 realloc 函数的规则：

    1. 申请新内存块不成功， realloc 函数会返回空指针；并且旧内存块的数据不会发生改变。
    2. 新内存块比旧内存块大，超过的部分内存是不会被初始化的。
    3. realloc 的第一个参数为空指针，它的行为和 malloc 一样。
    4. realloc 的第二个参数为 0，它会释放 ptr 指向的内存块。

注意： realloc 可能会移动内存块，所以一定要记得更新所有指向旧内存块的指针。

释放内存空间

malloc , calloc 和 realloc 函数都是在堆上申请内存空间。丢失了对内存块的跟踪就会产生内存泄漏。

内存泄漏：程序在动态分配内存后，无法释放已经不再需要的内存，导致系统中的可用内存不断减少，直至耗尽，造成程序性能下降甚至崩溃的问题。

1
2
3
p = malloc(...);
q = malloc(...);
p = q;
内存泄漏

C 语言要求负责垃圾的回收，提供了 free 函数：

1
void free(void *ptr);

指向不再需要的内存块的指针传递给 free 函数：

1
2
3
4
p = malloc(...);
q = malloc(...);
free(p);
p = q;
free函数

使用 free 函数注意：

  1. 传递给 free 的参数必须是由内存分配函数返回的指针，否则 free 函数的行为是未定义的。
  2. 同一片内存空间不能被 free 两次，否则会出现 double-free 现象。

悬空指针问题

悬空指针是指指向已经释放的内存地址的指针，或者指向未分配的内存区域的指针，程序会导致未定义的行为。因为释放后的内存，可能被重新分配。调用 free(p) 会释放 p 指向的内存空间，但并不会改变 p 的值。

1
2
3
4
5
char *p = malloc(10);
char *q = p;
free(p); // free之后，p和q都成为了悬空指针
strcpy(p, "abc"); 	/* 错误! */
strcat(q, "def"); 	/* 错误! */

当能有几个指针指向相同的内存块，在释放该内存块后，所有的指针都”悬空”了。

动态分配的结构体

动态分配的结构体对构建链表、树、图等其它链式结构是非常有用的。

定义结点类型：

1
2
3
4
typedef struct node {
    int data;
    struct node* next;	//next是一个指针，指向与当前结构体相同类型的另一个结构体对象。
}Node;

定义一个 addNode 方法，它可以在链表的前面添加一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* addNode(Node* list, int data) {
    // 动态分配一个结点
   Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Error: malloc failed in addNode\n");
        exit(1);
   }
    // 初始化结点
    newNode->data = data;
    // 头插法
    newNode->next = list;  // 指针变量的赋值：类似p = q
    
    return newNode;
}

在 main 方法中进行调用：

1
2
3
4
5
6
7
8
int main(void) {
    Node* list = NULL; // 空链表
    list = addNode(list, 3); // 3
    list = addNode(list, 2); // 2 --> 3
    list = addNode(list, 1); // 1 --> 2 --> 3
    
    return 0;
}

二级指针

二级指针（Double Pointer）是指向指针的指针。它是指针变量的地址。一级指针指向一个变量，二级指针则是指向一级指针的指针。基本格式：

1
int **p;	//type **pp;

p 是一个二级指针， p 指向一个一级指针，该一级指针再指向一个整数。基本使用示例：

1
2
3
4
5
6
7
8
9
int main() {
    int a = 10;
    int *p = &a;   // 一级指针，指向整数变量a
    int **pp = &p; // 二级指针，指向指针变量p
    printf("a = %d\n", a);          // 输出：a = 10
    printf("*p = %d\n", *p);        // 输出：*p = 10
    printf("**pp = %d\n", **pp);    // 输出：**pp = 10
    return 0;
}

进阶使用方法：

  1. 二级指针的动态内存分配
    二级指针常用于动态分配二维数组。

    1
    2
    3
    4
    5
    int rows = 3, cols = 4;
    int **arr = (int **)malloc(rows * sizeof(int *));  
    for (int i = 0; i < rows; i++) {
        arr[i] = (int *)malloc(cols * sizeof(int));
    }

  2. 二级指针作为函数参数
    二级指针经常用于修改指针的指向，特别是在函数内部动态分配内存时。

    1
    2
    3
    void allocateMemory(int **p, int size) {
        *p = (int *)malloc(size * sizeof(int));
    }

特殊使用方法：

  1. 操作链表或树等复杂数据结构：以下是链表头插法，前者是错误的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void addNode(Node* list, int data) {
        // 动态分配一个结点
        Node* newNode = (Node*)malloc(sizeof(Node));
        if (newNode == NULL) {
            printf("Error: malloc failed in addNode\n");
            exit(1);
        }
        // 初始化结点
        newNode->data = data;
        // 头插法
        newNode->next = list;
        list = newNode;
    }

    list 是一个指向 Node 的指针，即一级指针。在函数内部修改list的值（ list = newNode; ）时，修改的是 list 复制的实体参数，并没有改变函数外部 list 指针的值。当函数执行完后，外部的链表并没有真正更新，新的节点也没有插入到链表中。函数的修改只对函数内部的list有效。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void addNode(Node** plist, int data) {
        // 动态分配一个结点
        Node* newNode = (Node*)malloc(sizeof(Node));
        if (newNode == NULL) {
            printf("Error: malloc failed in addNode\n");
            exit(1);
        }
        newNode->data = data;
        newNode->next = *plist;
        *plist = newNode;
    }

    plist 是一个二级指针（ Node** ），指向的是一级指针 Node* 的地址。虽然也是实体参数，但是解引用符号*，修改的是二级指针解引用后的一级指针地址，通过使用 *plist ，能够直接修改外部链表指针的值。在函数内部对 *plist 的修改会反映到函数外部。

  2. 处理多维数组

    在处理高维数组时，二级指针及以上级别的指针可以方便地管理数组内存。

    1
    2
    3
    4
    5
    6
    7
    8
    int depth = 2, rows = 3, cols = 4;
    int ***arr = (int ***)malloc(depth * sizeof(int **));
    for (int i = 0; i < depth; i++) {
        arr[i] = (int **)malloc(rows * sizeof(int *));
        for (int j = 0; j < rows; j++) {
            arr[i][j] = (int *)malloc(cols * sizeof(int));
        }
    }

  3. 指向字符串数组的指针

    二级指针可以用于指向字符串数组，例如命令行参数 argv 。

    1
    2
    3
    4
    5
    6
    int main(int argc, char *argv[]) {
        for(int i = 0; i < argc; i++) {
            printf("Argument %d: %s\n", i, argv[i]);
        }
        return 0;
    }

    argv 是一个指向字符串数组的指针，每个元素是一个字符串（即字符指针 char * ）。

函数指针

函数指针：

函数指针是指向函数的指针变量。通过函数指针，可以调用函数并传递参数。

1
返回类型 (*指针变量)(参数列表);
1
2
3
4
5
6
int (*funcPtr)(int, int);
int add(int a, int b) {
    return a + b;
}
funcPtr = add;
int result = funcPtr(2, 3); // 调用 add 函数，结果为 5

指针函数：

指针函数是返回值为指针类型的函数。

1
返回类型* 函数名(参数列表);
1
2
3
4
5
int* getPointer(int* p) {
    return p;
}
int value = 10;
int* ptr = getPointer(&value); // 返回指向 value 的指针

进阶内容

  • 函数指针数组：可以定义一个函数指针数组，用来存储多个函数的地址。

    1
    2
    3
    int (*funcArr[2])(int, int) = {add, subtract};
    int result1 = funcArr[0](5, 3); // 调用 add 函数
    int result2 = funcArr[1](5, 3); // 调用 subtract 函数

  • 回调函数：函数指针常用于实现回调机制，将函数作为参数传递给另一个函数。

    1
    2
    3
    4
    void execute(int (*func)(int, int), int a, int b) {
        printf("Result: %d\n", func(a, b));
    }
    execute(add, 2, 3); // 输出 Result: 5

特殊使用方法

  • 返回函数指针的函数：可以定义一个返回函数指针的函数。

    1
    2
    3
    4
    5
    6
    int (*getFunc(char op))(int, int) {
        if (op == '+') return add;
        else return subtract;
    }
    int (*func)(int, int) = getFunc('+');
    int result = func(10, 5); // 调用 add 函数，结果为 15

  • 指向指针函数的指针：可以定义一个指向返回值为指针的函数的指针。

    1
    2
    3
    int* (*funcPtr)(int*);
    funcPtr = getPointer;
    int* ptr = funcPtr(&value); // 返回指向 value 的指针

两者的对比

  • 功能差异：
    • 函数指针主要用于引用和调用函数，常用于回调、函数表等场景。
    • 指针函数主要用于返回指针类型的数据，常用于动态内存分配、链表操作等场景。
  • 语法差异：
    • 函数指针的定义中，*和函数名在括号内，表示变量是一个指向函数的指针。
    • 指针函数的定义中，*在返回类型之前，表示返回类型是指针。

qsort 函数

qsort 声明在 <stdlib.h> 头文件中，是可以给任意数组排序的通用函数。数组的元素也可以是任意类型，甚至可以是结构体或者指针，但必须告诉 qsort 函数如何比较数组元素的大小。传入一个比较函数可以提供信息。

qsort 函数的原型如下：

1
void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

  • base 指向数组中要排序的第一个元素 (一般是数组的第一个元素)。

  • nmemb 是要排序元素的数量 (可以小于或等于数组中元素的个数)。

  • size 表示数组元素的大小。

  • compar 是比较函数，第一个参数比第二个参数小则返回负数，相等则返回零，第一个参数大于第二个参数则返回正数。