c - 如何避免 C 中字符串递归函数中的段错误？

Question

注意: 我并不是想获得算法实现!我已经用Java弄清楚了。我似乎无法让我的逻辑在 C 中工作。下面是 Java 代码(可以工作)，后面是中断的 C99 代码。

在我的实现中出现段错误的高级编码挑战是:

How to find all combinations of k length and smaller using alphabet of length n with repeating elements in C?

问题

代码可以编译，但在运行时出现段错误。

注释/观察

• 这是我正在学习的自定进度的 edX 类(class)。我已经完成了“不太舒服”的挑战，坦率地说，它们有点太简单了。我现在正在尝试超越要求并完成这个“更舒适”(更具挑战性)的挑战。这是更高级的初学者挑战之一。

• 我不是初学者程序员，但几乎是 C 新手。

• 据我了解，<cs50.h>是一个自定义头文件，它实现了一些简化(读取抽象)命令行输入和字符串处理的功能。其中的文档可以在 the cs50.net site 找到。并在cs50lib GitHub page上

• 我无法找出将值传递给递归函数的正确方法，并且需要利用地址引用/取消引用。不幸的是，与其他语言相比，我的 C 语言有点模糊。

使用所需的输出结果测试调用

~/myTerminal $ ./printall ab 3
aaa
aab
aba
abb
baa
bab
bba
bbb
aa
ab
ba
bb
a
b
~/myTerminal $ ./printall abc 2
aa
ab
ac
ba
bb
bc
ca
cb
cc
a
b
c
myTerminal $ ./printall abcd 1
a
b
c
d

有效的 Java 代码

public class Main {

    public static void main(String[] args) {
        System.out.println("First Test");
        char[] set1 = {'a', 'b'};
        int k = 3;
        printCombinations(set1, k);

        System.out.println("\nSecond Test");
        char[] set2 = {'a', 'b', 'c'};
        k = 2;
        printCombinations(set2, k);

        System.out.println("\nThird Test");
        char[] set3 = {'a', 'b', 'c', 'd'};
        k = 1;
        printCombinations(set3, k);
    }

// Print all possible strings of length k or smaller.
    static void printCombinations(char[] set, int k) {
        int n = set.length;
        for(int i = k; i > 0; i--)
        {
            printCombinationsRec(set, "", n, i);
        }

    }

// Print all combinations of length k
    static void printCombinationsRec(char[] set, String prefix, int n, int k)
    {
        if (k == 0)
        { // Base case
            System.out.println(prefix);
            return;
        }

        // One by one add all characters
        // from set and recursively
        // call for k equals to k-1
        for (int i = 0; i < n; ++i)
        {
            String newPrefix = prefix + set[i];
            printCombinationsRec(set, newPrefix, n, k - 1);
        }
    }
}

C 代码导致段错误

// CS50 custom header file
#include <cs50.h>
// "Regular" headers
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printCombinations();
void printCombinationsRecur();
int main(int argc, string argv[])
{
    if (argc == 3) // Correct number of arguments
    {
        string strSet = argv[1];
        int maxLength = atoi(argv[2]);
        printCombinations(strSet, maxLength);
        return 0;
    }
    // Incorrect usage
    printf("Usage: %s <charset>:string\n <maxLength>:int\n", argv[0]);
    return 1;
}

// Functions below were adapted and modified from code at :
// https://www.geeksforgeeks.org/print-all-combinations-of-given-length/
// Accessed : 2018-07-13
void printCombinations(string sSet, int strLength)
{
    int aLength = strlen(sSet);
    for (int i = strLength; i > 0; i--)
    {
        printCombinationsRecur(sSet, "", aLength, strLength);
    }
}

void printCombinationsRecur(string *sSet, string prefix, int aLength, int strLength )
{
    // printf("sSet: %s\nprefix: %s\naLength: %i\nstrLength: %i\n", *sSet, prefix, aLength, strLength);
    // In terms of the traditional equation k=> strLength, n=>aLength, S=>sSet

    if (strLength == 0)
    {
        printf("%s\n", prefix);
    }
    for (int i = 0; i < aLength; i++)
    {
        string temp1 = "";
        strcat(temp1, prefix); // <== SEGFAULT HAPPENING HERE!
        string newPrefix = strcat(temp1, sSet[i]);
        printCombinationsRecur(sSet, newPrefix, aLength, strLength - 1);
    }
}

我对递归函数进行了以下更改(由@Stargateur建议)，但仍然出现段错误!

    void printCombinationsRecur(string *sSet, string prefix, int aLength, int strLength )
{
    // printf("sSet: %s\nprefix: %s\naLength: %i\nstrLength: %i\n", *sSet, prefix, aLength, strLength);
    // In terms of the traditional equation k=> strLength, n=>aLength, S=>sSet

    if (strLength == 0)
    {
        printf("%s\n", prefix);
    }
    for (int i = 0; i < aLength; i++)
    {
        printf("This prints");
        char  *temp1 = malloc((strLength +2) * sizeof(char));
        for (int j = 0; j < strLength + 2; j++){
            if(j < strLength)
            {
                temp1[j] = prefix[j];
            }
            if(j == strLength)
            {
                temp1[j] = *sSet[i];
            }
            if(j == strLength + 1){
                temp1[j] = '\0';
            }
        }

        printCombinationsRecur(sSet, temp1, aLength, strLength - 1);
        free(temp1);
    }
}

Answer 1

有效的 Java 代码与无效的 C 代码之间的主要区别之一在于 printCombinations()功能。

工作 Java:

for(int i = k; i > 0; i--)
{
    printCombinationsRec(set, "", n, i);
}

损坏的C:

int aLength = strlen(sSet);
for (int i = strLength; i > 0; i--)
{
    printCombinationsRecur(sSet, "", aLength, strLength);
}

您正在一遍又一遍地调用具有相同长度的递归函数。为了匹配Java，strLength参数应该是 i相反。

您也没有正确处理基本情况。 Java 代码在打印 if k == 0 后返回; C 代码则不然。

工作 Java:

if (k == 0)
{ // Base case
    System.out.println(prefix);
    return;
}

损坏的C:

if (strLength == 0)
{
    printf("%s\n", prefix);
}

然后你错误地处理了字符串连接。 C不太宽容。至少有两种方法可以处理它。适用于任何版本的 C 的方法使用 malloc() 。只要编译器未定义 __STDC_NO_VLA__，该方法就适用于 C99 或 C11 ，使用 VLA。使用 malloc() 的版本还可以调用free()因此它比另一个做更多的工作。

由于分配的长度始终相同，因此您可以通过调用malloc()来抵消成本。循环之前一次和 free()循环后一次，您只需要复制一次前缀，然后简单地设置额外的字符(甚至可以设置一次 null )。您还可以增强 VLA 代码，在循环外定义一次新的前缀数组，复制一次前缀，设置一次空字节，然后在循环内设置额外的字符。

您还应该对函数使用正式的原型(prototype)声明，而不仅仅是不关心所提供的参数的函数声明。

下面显示的代码是惰性的，不会检查malloc()打电话工作。它也不能验证字母表是否是合理的长度，也不能验证最大长度是否合理，也不能验证字母表中的元素是唯一的。

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

static void printCombinations(const char *set, int strLength);
static void printCombinationsRec(const char *set, const char *prefix, int aLength, int strLength);

int main(int argc, char *argv[])
{
    if (argc != 3)
    {
        fprintf(stderr, "Usage: %s alphabet maxlen\n", argv[0]);
        return 1;
    }
    /* GIGO: garbage in, garbage out */
    char *strSet = argv[1];
    int maxLength = atoi(argv[2]);
    printCombinations(strSet, maxLength);
    return 0;
}

static void printCombinations(const char *set, int k)
{
    int n = strlen(set);
    for (int i = k; i > 0; i--)
    {
        printCombinationsRec(set, "", n, i);
    }
}

#if defined(USE_VLA) && __STDC_NO_VLA__ != 1

static void printCombinationsRec(const char *set, const char *prefix, int n, int k)
{
    if (k == 0)
    {
        printf("%s\n", prefix);
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        size_t len = strlen(prefix);
        char newPrefix[len + 2];
        strcpy(newPrefix, prefix);
        newPrefix[len + 0] = set[i];
        newPrefix[len + 1] = '\0';
        printCombinationsRec(set, newPrefix, n, k - 1);
    }
}

#else

static void printCombinationsRec(const char *set, const char *prefix, int n, int k)
{
    if (k == 0)
    {
        printf("%s\n", prefix);
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        size_t len = strlen(prefix);
        char *newPrefix = malloc(len + 2);
        strcpy(newPrefix, prefix);
        newPrefix[len + 0] = set[i];
        newPrefix[len + 1] = '\0';
        printCombinationsRec(set, newPrefix, n, k - 1);
        free(newPrefix);
    }
}

#endif /* USE_VLA */

编译为-DUSE_VLA对于支持 VLA 的编译器，它不会使用 malloc() 。如果不使用该选项进行编译，或者使用支持 C11 但不支持 VLA 的编译器进行编译，则它使用 malloc()和free() .

有一次，我还在 main() 中添加了参数验证代码，但是这 20 行左右似乎更多的是阻碍而不是有用，所以我留下了 GIGO在那里发表评论。

如果这是“生产代码”，我将使用错误报告函数并且不会跳过检查(部分原因是错误报告函数使检查变得更容易，每个报告的错误使用一行而不是 5 行左右，而不需要.我将使用 GitHub 上的 SOQ(Stack Overflow Questions)存储库中提供的错误报告代码作为 stderr.c 和 stderr.h 子目录中的文件。

请注意，您不能使用 strcat()很容易，因为您想附加单个字符，而不是字符串。因此使用这两个作业。 + 0强调两个作业之间的相似性；编译器不会为 + 0 生成任何代码.

运行时(我称之为 comb47.c ，编译为 comb47 )，它会产生所需的输出:

$ comb47 ab 3
aaa
aab
aba
abb
baa
bab
bba
bbb
aa
ab
ba
bb
a
b
$ comb47 abc 2
aa
ab
ac
ba
bb
bc
ca
cb
cc
a
b
c
$ comb47 abcd 1
a
b
c
d
$