目录

1. 动态扩容

1.1 realloc 是什么

1.2 realloc 的定义

1.3 重写简易realloc

1.3.1 进行安全检查

1.3.2 创建新空间 

1.3.3 赋值新空间 

1.3.4 释放与返回 

1.3.5 调用查看结果

2. 单向链表 

 2.1 什么是单向链表

2.2 使用尾插法插入单向链表 

---

1. 动态扩容

1.1 realloc 是什么

 在C语言中，我们知道在动态内存的部分有这样几个函数：malloc, free, calloc, realloc

我们用的最多的函数无非是malloc, free 一个创建动态内存，一个释放动态内存，今天我想谈谈realloc —— 动态扩容

动态扩容 是一种在程序运行时根据需要动态调整数据结构（如数组、链表等）容量的机制。它通常用于处理数据量不确定的场景，确保数据结构能够灵活地适应数据的变化，而不会因为容量不足导致程序崩溃或性能下降。

动态扩容通常用于解决在 动态分配内存后容量不足的问题。

1.2 realloc 的定义

在man手册中这样写到：

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

The realloc() function changes the size of the memory block pointed to by ptr to size bytes.  The contents will be unchanged in the  range  from  the  start  of  the
       region  up to the minimum of the old and new sizes.  If the new size is larger than the old size, the added memory will not be initialized.  If ptr is NULL, then the
       call is equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr).  Unless  ptr  is
       NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc().  If the area pointed to was moved, a free(ptr) is done.

①realloc（）函数将 ptr 所指向的内存块的大小更改为size bytes，从区域的开始到新旧大小的最小值的范围内，内容将保持不变。
②如果新大小大于旧大小，则不会初始化添加的内存。
③如果ptr为NULL，则调用相当于malloc(size)，对于size的所有值；
④如果size等于零，且ptr不为NULL，则调用相当于free（ptr）。
⑤除非ptr为NULL，否则它一定是由先前调用malloc（）、calloc（）或realloc（）返回的。
⑥如果所指向的区域被移动，则执行free（ptr）操作。
 

在realloc（）函数的基本逻辑中，

• ptr是要调整的内存地址
• size 调整之后新的大小

• 返回值为调整之后的内存起始位置

  需要注意的是：
  这个函数调整原内存空间大小的基础上，还会将原来内存中的数据移动到新的空间。

也就是说当原有空间后面有足够大小的空间的时候，要扩展内存就直接原有内存之后直接追加空间，原来空间的数据不发生变化。 原有空间之后没有足够多的空间时，它会在堆空间上另找一个合适大小的连续空间来使用。这样函数返回的是一个新的内存地址。

如果将原内存的指针ptr直接realloc操作，那么如果内存分配失败，将ptr的指针直接指向了NULL，那么在没有free这块ptr的内存之前，就造成了ptr的内存丢失，这块内存会因为没有指针指向它而造成内存泄漏。

1.3 重写简易realloc

在了解realloc的机制后，我们重写一个自己的realloc来进行动态扩容。

int * my_realloc(int * arr , size_t size)

arr代表传入的内存地址，size代表调整后的大小 

1.3.1 进行安全检查

根据上文man手册的第③和第④条，我们应该在函数中加入这样的保护机制

if(size == 0 && arr!=NULL)
{
    free(arr);
    return NULL;
}
//如果size等于零，且ptr不为NULL，则调用相当于free（ptr）。


if(arr == NULL)
{
    printf("空指针\n");
    return (int *)malloc(size * sizeof(int));
}
// 如果原指针为空，相当于 malloc

1.3.2 创建新空间 

同样，我们开辟一片大小为size的空间，作为新的数组。

int *new_arr = (int *)malloc(size*sizeof(int));
if (new_arr == NULL)
{
    // 如果分配失败，返回 NULL
    return NULL;
}

1.3.3 赋值新空间 

 我们使用memcpy函数进行赋值操作，memcpy的用法如下

 #include <string.h>

       void *memcpy(void *dest, const void *src, size_t n);

memcpy（）函数从内存区域src复制n个字节到内存区域dest，内存区域不能重叠。
如果内存区域重叠，使用memmove(3)。 

这里我们假设要扩容为原来的2倍。

// 3. 将老空间的数据 赋值 新空间
memcpy(new_arr,arr,size/2*sizeof(int));

1.3.4 释放与返回 

// 4. 释放老空间
free(arr);
// 5. 返回新空间的地址
return new_arr;

1.3.5 调用查看结果

接下来我们先初始化一个数组，大小为5，赋值为1，2，3，4，5

在扩容后我们把6，7，8，9，10放入这个大小为10的数组的后半部分，printf打印后，如果赋值成功则应显示正确的数组。

原码展示：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 自己编写一个 扩容    
int * my_realloc(int * arr , size_t size)
{
    // 1. 安全检查
    if(size == 0 && arr!=NULL)
    {
        free(arr);
        return NULL;
    }
    // 如果原指针为空，相当于 malloc
    if(arr == NULL)
    {
        printf("空指针\n");
        return (int *)malloc(size * sizeof(int));
    }

    // 2. 创建新空间
    int *new = (int *)malloc(size*sizeof(int));
    if (new == NULL)
    {
        // 如果分配失败，返回 NULL
        return NULL;
    }
    // 3. 将老空间的数据 赋值 新空间
    memcpy(new,arr,size/2*sizeof(int));
    
    // 4. 释放老空间
    free(arr);
    // 5. 返回新空间的地址
    return new;
}

int main(int argc, char const *argv[])
{
    int len = 5;
     // 初始化一个数组
    int *arr = (int *)malloc(len * sizeof(int));

    //填充数组
    for (size_t i = 0; i < len; i++)
    {
        arr[i] = i + 1;
    }

    //打印原数组
    printf("原数组: ");
    for (size_t j = 0; j < len; j++)
    {
        printf("%d ", arr[j]);
    }
    printf("\n");


    int new_len = 10;
    int *new_arr = (int *)my_realloc(arr,new_len);
    if (new_arr == NULL)
    {
        perror("my_realloc failed");
        return 1;
    }

    // 填充新数组的剩余部分
    for (size_t i = len; i < new_len; i++)
    {
        new_arr[i] = i + 1;
    }

    // 打印新数组
    printf("扩容后的数组: ");
    for (size_t i = 0; i < new_len; i++)
    {
        printf("%d ", new_arr[i]);
    }
    printf("\n");

    // 释放新数组
    free(new_arr);
    


    return 0;
}

2. 单向链表 

 2.1 什么是单向链表

单向链表  是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：

1. 数据域：存储实际的数据。

2. 指针域：存储指向下一个节点的指针。

单向链表的特点是：

• 每个节点只有一个指针，指向下一个节点。

• 链表的最后一个节点的指针域为 NULL，表示链表的结束。

• 只能从头节点开始顺序访问链表中的元素，不能反向遍历。

2.2 使用尾插法插入单向链表 

//创建了一个结构体
typedef struct std
{
    int data;
    struct std *next;
}std;

首先我们创建一个结构体，data用于存储数据，next是指向 struct std 类型的指针，用于指向下一个节点。 

std * linked_init()
{
    std * s1 = (std *)malloc(sizeof(std));

    if (NULL == s1)
    {
        perror("malloc failed");
        return NULL;
    }

    s1->data = 10;
    s1->next = NULL;

    return s1;
}

创建链表，先创建一个std的结构体，s1指向这个结构体。再将std结构体里的打他赋值为10，指针next指向NULL。 

void list_add(std *list, std data)
{
    // 安全判定
    if (NULL == list)
    {
        perror("传入链表为空");
        return;
    }
    
    // 遍历到链表尾部
    std *current = list;
    while (current->next != NULL)
    {
        current = current->next;
    }
    
    // 创建新节点并插入到链表尾部
    std *new_std = (std *)malloc(sizeof(std));
    if (NULL == new_std)
    {
        perror("malloc failed");
        return;
    }
    *new_std = data;
    new_std->next = NULL;
    current->next = new_std;
}

 添加尾插函数，通过遍历找到链表尾部来插入新的数据。

int main(int argc, char const *argv[])
{
    std *list = list_init();

    // 插入数据
    std data = {.data = 20, .next = NULL};
    std data1 = {.data = 30, .next = NULL};
    list_add(list, data);
    list_add(list, data1);

    // 数据打印
    std *print_ptr = list;
    while (print_ptr != NULL)
    {
        printf("data = %d\n", print_ptr->data);
        print_ptr = print_ptr->next;
    }

    // 释放空间
    std *current = list;
    while (current != NULL)
    {
        std *temp = current;
        current = current->next;
        free(temp);
    }
    list = NULL;

    return 0;
}

 ​​​​​

 成功插入数据 20 30