时间戳

首页 > 解决方案 > 如何避免在 C 中使用字符串的递归函数中的分段错误？

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

问题描述

注意： 我不是想获得算法实现！我已经用Java弄清楚了。我似乎无法让我的逻辑在 C 中工作。下面是 Java 代码（有效），后面是中断的 C99 代码。

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

如何使用长度为 n 的字母表和C中的重复元素找到 k 长度和更小长度的所有组合？

问题

代码编译，但我在运行时遇到分段错误。

注释/观察

具有所需输出结果的测试调用

~/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);
    }
}

标签： cpointersrecursionsegmentation-faultcs50

解决方案

有效的 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 代码以在循环外定义新的前缀数组，复制一次前缀，设置一次空字节，然后在循环内设置额外的字符。

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

下面显示的代码是惰性的，不检查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()and free().

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

如果这是“生产代码”，我将使用错误报告功能并且不会跳过检查（部分原因是错误报告功能使其更容易，每个报告的错误使用一行而不是 5 行左右。我' d 使用我在 GitHub 上的 SOQ（堆栈溢出问题）存储库中提供的错误报告代码作为文件和stderr.csrc /libsoq子目录。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
$

推荐阅读