注意: 我并不是想获得算法实现!我已经用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);
}
}
最佳答案
有效的 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
$
关于c - 如何避免 C 中字符串递归函数中的段错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51333684/