如何避免 C 中带有字符串的递归函数中的分段错误？
How to avoid segmentation fault in recursive function with strings in C?
注意： 我不是要获取算法实现！我已经在 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 课程。我已经完成了 "less comfortable" 挑战，坦率地说，它们有点太简单了。我现在正努力超越要求，完成这项 "more comfortable"（阅读更具挑战性）的挑战。这是更高级的初学者挑战之一。
我不是初级程序员，但几乎是 C 的新手。
据我所知，<cs50.h> 是一个自定义头文件，它实现了一些简化（阅读摘要）命令行输入和字符串处理的内容。可以在 the cs50.net site and on the cs50lib GitHub page
我想不出将值传递给递归函数的正确方法，需要使用地址 referencing/dereferencing。不幸的是，与其他语言相比，我的 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] = '[=13=]';
}
}
printCombinationsRecur(sSet, temp1, aLength, strLength - 1);
free(temp1);
}
}
有效的 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。
你也没有正确处理基本情况。 if k == 0 打印后的Java代码returns； 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] = '[=14=]';
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] = '[=14=]';
printCombinationsRec(set, newPrefix, n, k - 1);
free(newPrefix);
}
}
#endif /* USE_VLA */
用支持VLAs的编译器用-DUSE_VLA编译，不会用malloc()。在没有选项的情况下编译，或者使用支持 C11 但不支持 VLA 的编译器，则它使用 malloc() 和 free().
有一次，我还在 main() 中添加了参数验证代码，但是 20 行左右似乎比有用更碍事，所以我在那里留下了 GIGO 注释相反。
如果这是 'production code'，我会使用错误报告函数并且不会跳过检查（部分原因是错误报告函数使它更容易，每个报告的错误使用一行而不是 5左右没有。我会使用我的 SOQ (Stack Overflow Questions) repository on GitHub as files stderr.c and stderr.h in the src/libsoq 子目录中可用的错误报告代码。
请注意，您不能轻易使用 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
$
注意： 我不是要获取算法实现！我已经在 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 课程。我已经完成了 "less comfortable" 挑战，坦率地说，它们有点太简单了。我现在正努力超越要求，完成这项 "more comfortable"（阅读更具挑战性）的挑战。这是更高级的初学者挑战之一。
我不是初级程序员，但几乎是 C 的新手。
据我所知，
<cs50.h>是一个自定义头文件，它实现了一些简化（阅读摘要）命令行输入和字符串处理的内容。可以在 the cs50.net site and on the cs50lib GitHub page 找到其中的文档
我想不出将值传递给递归函数的正确方法，需要使用地址 referencing/dereferencing。不幸的是，与其他语言相比，我的 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] = '[=13=]';
}
}
printCombinationsRecur(sSet, temp1, aLength, strLength - 1);
free(temp1);
}
}
有效的 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。
你也没有正确处理基本情况。 if k == 0 打印后的Java代码returns； 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] = '[=14=]';
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] = '[=14=]';
printCombinationsRec(set, newPrefix, n, k - 1);
free(newPrefix);
}
}
#endif /* USE_VLA */
用支持VLAs的编译器用-DUSE_VLA编译，不会用malloc()。在没有选项的情况下编译，或者使用支持 C11 但不支持 VLA 的编译器，则它使用 malloc() 和 free().
有一次，我还在 main() 中添加了参数验证代码，但是 20 行左右似乎比有用更碍事，所以我在那里留下了 GIGO 注释相反。
如果这是 'production code'，我会使用错误报告函数并且不会跳过检查（部分原因是错误报告函数使它更容易，每个报告的错误使用一行而不是 5左右没有。我会使用我的 SOQ (Stack Overflow Questions) repository on GitHub as files stderr.c and stderr.h in the src/libsoq 子目录中可用的错误报告代码。
请注意，您不能轻易使用 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
$