字符串的分配，两个字符串合二为一的递归函数

Question

我写了一个递归函数来获取 3 个字符串，其中两个按字母顺序排序，第三个分配用于将前两个字符串放在第三个字符串中。字母顺序应该保留；例如：

s1="abbcde";
s2="bckj";

所以，

s3="abbbccdekj";

这是main()中第三个字符串的分配：

char *s3 = (char*)malloc(len*sizeof(char));
SS1together(s1,s2,s3);//send to recursive function 3 strings

这是函数：

   void SS1together(char *s1, char*s2, char*s3)
{
if (s1 == NULL || s2 == NULL)
{
    if (s1 == NULL)
    {
        s3[0] = s2[0];
        SS1together(s1, s2 + 1, s3 + 1);

    }
    else
    {
        s3[0] = s1[0];
        SS1together(s1 + 1, s2, s3 + 1);
    }
}
if (s1 != NULL && s2 != NULL)
{
    if (s1[0] <= s2[0])
    {
        s3[0] = s1[0];
        SS1together(s1 + 1, s2, s3 + 1);
    }
    else
    {
        s3[0] = s2[0];
        SS1together(s1 , s2 + 1, s3 + 1);
    }
}
}

显示是内存的问题，但是我找不到。

我的string 3分配，在main函数中，多了一个完美运行的函数，所以我把main放在全图：

  void main()
{
char *s1[N], *s2[N], *s3[N];//N=30 ,it is define in the top
int ans, len;

printf("Please enter your string  s1 and then string s2\n");
gets(s1);
gets(s2);
len = strlen(s1) + strlen(s2);

if ((CheckS(s1) == 0) || (CheckS(s2) == 0))
    printf("Not sorted\n");
else
{
    char *s3 = (char*)malloc(len*sizeof(char));
    SS1together(s1,s2,s3);
    puts(s3);
    free(s3);
}
_getch();
}

Answer 1

您的代码假定当 s1 是 NULL（第一个 if）时，s2 不是 NULL 并且递增 s2并进行递归调用。

但是当s2字符串小于s1时，s2会先到达末尾所以在递归调用中传递s2+1会导致访问越界记忆。这在技术上会导致未定义的行为，并且实际上最有可能导致崩溃的内存访问冲突。

您应该在递增指针之前执行更严格的 NULL 检查 - s1、s2 和 s3.

Answer 2

您比较接近，但没有充分考虑终止条件。迭代合并排序数据也比递归更容易整个堆。

您没有说明 len 是如何计算的（它需要 strlen(s1) + strlen(s2) + 1），但您的代码可能运行出现问题，即使那是正确的。例如，考虑最简单的情况，两个空字符串。第一个 if 执行，但递归去使用超出字符串末尾的 s2 + 1，并导致灾难。我认为，修复该问题需要类似于以下的代码：

void SS1together(char *s1, char *s2, char *s3)
{
    if (s1 == NULL || s1[0] == '[=10=]')
    {
        s3[0] = s2[0];
        if (s2[0] != '[=10=]')
            SS1together(s1, s2 + 1, s3 + 1);
    }
    else if (s2 == NULL|| s2[0]=='[=10=]')
    {
        s3[0] = s1[0];
        if (s1[0] != '[=10=]')
            SS1together(s1 + 1, s2, s3 + 1);
    }
    else if (s1[0] <= s2[0])
    {
        s3[0] = s1[0];
        SS1together(s1 + 1, s2, s3 + 1);
    }
    else
    {
        s3[0] = s2[0];
        SS1together(s1, s2 + 1, s3 + 1);
    }
}

^{警告：未经测试的代码。}

迭代替代

void SS1together(char *s1, char *s2, char *s3)
{
    if (s1 == NULL)
        s1 = "";
    if (s2 == NULL)
        s2 = "";
    while (*s1 != '[=11=]' && *s2 != '[=11=]')
    {
        if (s1[0] <= s2[0])
            *s3++ = *s1++;
        else
            *s3++ = *s2++;
    }
    while (s1[0] != '[=11=]')
        *s3++ = *s1++;
    while (s2[0] != '[=11=]')
        *s3++ = *s2++;
    *s3 = '[=11=]';
}

^{警告：也是未经测试的代码。}

字符串的分配，两个字符串合二为一的递归函数

Allocation of string, recursive function of two strings in one

c

string

recursion