c - 为 C 中的递归 strcat() 函数分配内存

Question

我正在尝试使用tip from other question构建一个上下文无关的语法模拟器。但我在分配足够的内存时遇到问题。

基本代码:

char * print_S ( )
{
    int los = zero_or_one();
    if ( los == 1 )
            return "1";
    else
            return strcat( print_A(), print_A() );
}

char * print_A ( )
{
    int los = zero_or_one();
    if ( los == 1 )
            return "0";
    else
            return strcat( print_S(), print_S() );
}

当 los = 0 时返回段错误。
然后我尝试了为字符串分配内存然后将其传递给函数的方法，但仍然没有运气:

char * out = (char *) malloc( 100 * sizeof(*out) );
printf("%s\n", print_S( out ) );

和

char * print_S ( char * out )
{
    int los = zero_or_one();

    if ( los == 1 ) {
        strcpy (out, "1");
        return out;
    } else {
        return strcat( print_A(out), print_A(out) );
    }
}

char * print_A ( char * out )
{
    int los = zero_or_one();

    if ( los == 1 ) {
        strcpy (out, "0");
        return out;
    } else {
        return strcat( print_S(out), print_S(out) );
    }
}

什么是正确的方法？谢谢

Answer 1

考虑到另一个问题的上下文，我认为您应该安排对函数的初始调用，以给出一个数组的开头和结尾，例如 100 个字符。当您递归地向下工作时，您会适本地增加传递给其他函数的起始指针。

这段代码对我有用:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* One of these is sufficient; symmetry requires both */
static char *print_S(char *dst, char *end);
static char *print_A(char *dst, char *end);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static char *print_S(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 0)
            *dst++ = '0';
        else
        {
            dst = print_A(dst, end);
            dst = print_A(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 1)
            *dst++ = '1';
        else
        {
            dst = print_S(dst, end);
            dst = print_S(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    for (int i = 0; i < 25; i++)
    {
        char buffer[100];
        (void)print_A(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
        (void)print_S(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
    }
    return 0;
}

请注意，序列通常很短，但也可能很长。运行一个示例:

01011
0
1
0
1
0
00
11
1
0
1
0
1
1110
00
101110101000000011100001110000100111011011000110001000000111010001000110000100010000111111001100011
1
0
11000011111000110011001000011100
0
1
1000000100001000
011
0
110
0
1
0
1
001
1
0110110011000
11110011110101100101100000111101011010001000110110010100011001100
10111001100101
1
100
100010
0
00
0
011
11
0000100010110
0
1
11
00
0
1
0

一些示例运行被截断为 99 个字符 - 正如本示例中的长字符一样。我也尝试过 300 和 1000 的尺寸；在这两种情况下，我得到的样本运行都被截断了。

如果你想做动态内存分配，你必须更狡猾一点:

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

/* One of these is sufficient; symmetry requires both */
static char *print_S(char **buffer, size_t *len, char *dst);
static char *print_A(char **buffer, size_t *len, char *dst);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static void add_space(char **buffer, size_t *len, char **dst)
{
    assert(*dst < *buffer + *len);
    if (*dst == *buffer + *len - 1)
    {
        char *newbuf = realloc(*buffer, 2 * *len);
        if (newbuf == 0)
        {
            fprintf(stderr, "Out of memory (%zu)\n", 2 * *len);
            exit(1);
        }
        *len *= 2;
        *buffer = newbuf;
        *dst = *buffer + strlen(*buffer);
    }
}

static char *print_S(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);

    if (zero_or_one() == 0)
        *dst++ = '0';
    else
    {
        dst = print_A(buffer, len, dst);
        dst = print_A(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);
    if (zero_or_one() == 1)
        *dst++ = '1';
    else
    {
        dst = print_S(buffer, len, dst);
        dst = print_S(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    size_t len = 100;
    char *buffer = malloc(len);
    for (int i = 0; i < 25; i++)
    {
        (void)print_A(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
        (void)print_S(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
    }
    free(buffer);
    return 0;
}

这样，我得到了一次运行，输出字符串的长度为 14,473,874 字节。我不会费心把它打印在这里；可以说其中有 1 和 0。