C语言数据结构之动态分配实现串

序言

在本文中，我们将探讨C语言中动态分配实现串的方法和技巧。本文将会从什么是动态分配串开始，详细介绍如何实现动态分配串，并给出一些示例代码帮助读者更好地理解。

什么是动态分配串

一个串（string）是由零个或多个字符组成的有限序列。串的实现可以分为两种形式：静态分配和动态分配。动态分配串是指在运行时动态地分配内存，以适应不同长度的字符串。当需要增长或缩短字符串的长度时，动态分配串可以自动调整空间大小。因此，动态分配串比静态分配串更加灵活。

动态分配串的实现

动态分配串的实现方法主要有以下两种：

方法一：使用指针实现

动态分配串可以通过指针来实现。指向串的指针通过动态分配内存来存储串的内容，并在需要的时候重新调整内存大小。下面是一个使用指针实现的动态分配串的示例代码：

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

int main() {
    char *str;
    int len = 0;
    int size = 1;

    str = malloc(size);

    // 读入字符串
    char c = getchar();
    while (c != '\n') {
        // 判断是否需要重新分配空间
        if (len == size) {
            size *= 2;
            str = realloc(str, size);
        }

        // 将字符添加到串中
        *(str + len++) = c;

        c = getchar();
    }

    // 添加结尾的'\0'
    *(str + len) = '\0';

    // 输出结果
    printf("The string is: %s\n", str);

    // 释放内存
    free(str);

    return 0;
}

在上面的代码中，我们使用了malloc和realloc函数来动态分配内存。程序首先申请了一个长度为1的内存，然后逐个字符地读入字符串。如果字符串的长度达到了申请的内存的上限（也就是len == size），则程序会重新将内存大小扩大一倍。

方法二：使用结构体实现

动态分配串也可以通过结构体来实现。结构体中包含了一个指向字符串的指针和字符串的长度，通过动态分配内存来存储字符串的内容。下面是一个使用结构体实现的动态分配串的示例代码：

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

struct string_t {
    char *str;
    int len;
};

struct string_t create_string(int len) {
    struct string_t s;
    s.str = malloc(len + 1);
    s.len = 0;
    *(s.str) = '\0';
    return s;
}

struct string_t append_char(struct string_t s, char c) {
    // 判断是否需要重新分配空间
    if (s.len == strlen(s.str)) {
        s.str = realloc(s.str, s.len * 2 + 1);
    }

    // 将字符添加到串中
    *(s.str + s.len++) = c;
    *(s.str + s.len) = '\0';

    return s;
}

int main() {
    // 创建串
    struct string_t str = create_string(1);

    // 读入字符
    char c = getchar();
    while (c != '\n') {
        str = append_char(str, c);
        c = getchar();
    }

    // 输出结果
    printf("The string is: %s\n", str.str);

    // 释放内存
    free(str.str);

    return 0;
}

在上面的代码中，我们定义了一个名为string_t的结构体，其中包括了一个指向字符串的指针和一个表示字符串长度的整型。程序首先调用了create_string函数来申请长度为1的空间，并在字符串开头添加了一个空字符。然后逐个字符地读入字符串。如果字符串的长度达到了申请的内存的上限（也就是s.len == strlen(s.str)），则程序会重新将内存大小扩大一倍。

示例说明

示例一：使用指针实现的动态分配串

假设用户需要输入一个长为n的字符串。如果使用静态分配的方式，需要先确定n的值，然后再定义一个长度为n的字符数组。但这样的方式不利于扩展，如果输入的字符串超过预定义的长度，会导致程序出现错误。下面给出使用指针实现的动态分配串的代码，用户可以根据实际需求输入任何长度的字符串。代码如下：

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

int main() {
    char *str;
    int len = 0;
    int size = 1;

    str = malloc(size);

    // 读入字符串
    char c = getchar();
    while (c != '\n') {
        // 判断是否需要重新分配空间
        if (len == size) {
            size *= 2;
            str = realloc(str, size);
        }

        // 将字符添加到串中
        *(str + len++) = c;

        c = getchar();
    }

    // 添加结尾的'\0'
    *(str + len) = '\0';

    // 输出结果
    printf("The string is: %s\n", str);

    // 释放内存
    free(str);

    return 0;
}

示例二：使用结构体实现的动态分配串

下面给出使用结构体实现的动态分配串的代码，用户可以根据实际需求输入任何长度的字符串。代码如下：

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

struct string_t {
    char *str;
    int len;
};

struct string_t create_string(int len) {
    struct string_t s;
    s.str = malloc(len + 1);
    s.len = 0;
    *(s.str) = '\0';
    return s;
}

struct string_t append_char(struct string_t s, char c) {
    // 判断是否需要重新分配空间
    if (s.len == strlen(s.str)) {
        s.str = realloc(s.str, s.len * 2 + 1);
    }

    // 将字符添加到串中
    *(s.str + s.len++) = c;
    *(s.str + s.len) = '\0';

    return s;
}

int main() {
    // 创建串
    struct string_t str = create_string(1);

    // 读入字符
    char c = getchar();
    while (c != '\n') {
        str = append_char(str, c);
        c = getchar();
    }

    // 输出结果
    printf("The string is: %s\n", str.str);

    // 释放内存
    free(str.str);

    return 0;
}

总结

本文详细介绍了C语言中动态分配实现串的方法和技巧。我们通过两个不同的示例代码演示了使用指针和结构体两种方法实现动态分配串的流程。值得注意的是，动态分配串具有较高的灵活性，但同时也需要注意内存的管理问题，确保内存重复分配的情况出现。