我是C的新手,还在学习(目前正在做一些“LeetCode”的挑战)。我写了一个函数,它应该返回字符串数组中最长的公共前缀。我用几个不同的值进行了测试,一切正常。但是字符串数组{"aaa", "aa", "aaa"}
在Visual Studio中会导致“aa”(正确),但在gcc版本中会导致“aaa”,我不明白为什么。
100d 1xx 1c 1d 1x的字符串
我的代码如下:
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
char* longestCommonPrefix(char** strs, int strsSize) {
char* result = calloc(200, sizeof(char));
if (result == NULL) return NULL;
size_t result_length = strlen(strs[0]);
memcpy(result, strs[0], result_length);
char* result_end = result + result_length + 1;
for (size_t i = 1; i < strsSize; ++i) {
char* ptr_res = result;
char* ptr_cur = strs[i];
while (*ptr_res == *ptr_cur && *ptr_res > '\0' && *ptr_cur > '\0') {
++ptr_res;
++ptr_cur;
}
result_end = ptr_res;
}
*result_end = '\0';
return result;
}
int main(int argc, char* argv[]) {
char* a[3];
a[0] = "aaa";
a[1] = "aa";
a[2] = "aaa";
char* b = longestCommonPrefix(a, 2);
printf(b);
free(b);
}
字符串
@Chris; @EricPostpischil;@VladFromMoscow;
谢谢你指出我的缺点。我从你们身上学到了很多。我将@EricPostpischil的答案标记为解决方案,因为我测试了它,它适用于这个挑战。@VladFromMoscow的答案很棒,对于我实际部署的代码来说,它似乎要好得多,所以我一定会做笔记。
这里是我提交给LeetCode的工作代码,它运行得很好:
char* longestCommonPrefix(char** strs, int strsSize) {
char* result = calloc(200, sizeof(char));
if (result == NULL) return NULL;
size_t result_length = strlen(strs[0]);
memcpy(result, strs[0], result_length);
char* result_end = result + result_length;
for (size_t i = 1; i < strsSize; ++i) {
char* ptr_res = result;
char* ptr_cur = strs[i];
while (*ptr_res == *ptr_cur && ptr_res < result_end) {
++ptr_res;
++ptr_cur;
}
result_end = ptr_res;
}
*result_end = '\0';
return result;
}
型
3条答案
按热度按时间xxb16uws1#
这是错误的:
字符串
result_length
包含了strs[0]
中空字符之前的字符数,result_end
用于设置后面的空字符,所以它应该指向空字符将去的地方:型
然后这段代码:
型
允许循环进行,直到当前在
result
缓冲区中的字符串或正在与之进行比较的当前字符串结束。这可以比迄今为止建立的最长公共前缀更远。循环的长度应限制为最长的公共前缀:型
注意,不需要测试空/非空字符。如果在
ptr_cur
中遇到空字符,则*ptr_cur
与*ptr_res
不同,或者我们已经到达result
中的字符串结尾,result_end
已经指向(最初)或之前(如果它是从先前的比较中更新的)。此外,
*ptr_res > '\0'
是测试非空字符的不正确方法,因为字符值可以为负。*ptr_res != '\0'
是一个正确的测试。printf(b);
是危险的,因为如果对b
处理不当,它很容易出现不当行为。此外,通常最好用换行符终止程序输出。使用puts(b)
或printf("%s\n", b);
。ippsafx72#
在你的代码中有两个问题跳出来。
首先,您调用了
longestCommonPrefix
,其中2
而不是3
是输入数组的长度。第二,在循环中,您实际上从未通过编写新的空终止符来修改
result
。您只需在最后一次for循环迭代后解引用result_end
并为其分配null终止符。这样做的效果是只考虑数组中复制到result
的第一个字符串,以及根据传入的长度将其视为数组中的“最后一个”字符串。如果用
2
调用该函数,则输出“aa”。如果你用3
调用它,它会考虑最后一个字符串文字"aaa"
,并发现在"aaa"
和"aaa"
之间,"aaa"
是最长的公共前缀。清理一些其他的东西:
字符串
ujv3wf0j3#
首先,您声明了一个包含3个指向字符串文字的指针的数组:
字符串
但不清楚为什么要传递此调用的第二个参数:
型
等于
2
而不是3
。另一个问题是在此声明的初始化程序中使用了幻数
200
:型
在函数
longestCommonPrefix
中。一般情况下采用以下语句:
型
可能会导致未定义的行为,因为指向数组元素的字串可能会大于幻数
200
。调用
memcpy
存储字符后指针result
指向的动态分配数组不包含字符串。这种内存分配完全没有意义,因为传递的数组可以包含指向空字符串的指针。
变量
result_end
的初始化器也是:型
同样没有意义的还有再次可以调用未定义的行为归于语句:
型
因为指针
result_end
不指向存储器中复制的串的最后一个元素之后。即数组将包含不正确的数据。至少你应该写型
这个while循环
型
如果指针
ptr_cur
所指向的字符串比指针result
所指向的已存储字符序列短,则可以保持动态分配数组result
的内容不变。而for循环的效率很低,因为没有检查是否已经遇到了空字符串。
请注意,该函数是不安全的,因为第二个参数可以是非正值。
甚至这个叫
printf
的型
如果公共前缀包含形成格式规范的符号,则通常可以调用未定义的行为。
首先,您需要找到公共前缀的长度。并且只有在此之后才能分配所需大小的数组,并将前缀作为字符串复制到数组中。
函数和程序整体应如下所示
型
程序输出为:
型