在char数组c中查找

我想在与bsearch排序的文本中找到字符串(在代码中命名为word)。为什么bsearch似乎不起作用?

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int cmp(const void *a, const void *b) {
const char *ia = *(const char **)a;
const char *ib = *(const char **)b;
return strcmp(ia, ib);
}
int main() {
char *text = malloc(sizeof(char *) * 1000);
char *word = malloc(sizeof(char *) * 30);
char **all_words = malloc(sizeof(char *) * 1);
int count_word = 0;
fgets(text, 1000, stdin);
fgets(word, 30, stdin);
char *tok = strtok(text, " .n");
while (tok != NULL) {
all_words[count_word] = malloc(sizeof(char) * (strlen(tok) + 1));
all_words[count_word] = tok;
all_words[count_word][strlen(tok)] = '';
count_word++;
all_words = realloc(all_words, (count_word + 1) * sizeof(char *));
tok = strtok(NULL, " .n");
}
qsort(all_words, count_word, sizeof(char *), cmp);
for (int i = 0; i < count_word; i++) {
puts(all_words[i]);
}
void *pointer = bsearch(&word, all_words, count_word, sizeof(char*), cmp);
if (pointer != NULL) {
puts("exists");
} else {
puts("doesn't exist");
}
for (int i = 0; i < count_word; i++) {
free(all_words[i]);    //---- error here
}
free(all_words);
free(word);
free(text);
}

为什么在使用strtok后释放char*数组时会出现此错误?使用strtok后是否有问题?(由@wildplasser和@JonathanLeffler解决)

还有一个问题是关于我的cmp功能。我知道它可以正常工作，但我不记得为什么会这样…这段代码有什么不同?(@JonathanLeffler也解释了)

int cmp(const void *a, const void *b) {
const char *ia = (const char *)a;
const char *ib = (const char *)b;
puts(ia);
return strcmp(ia, ib);
}

正如评论中所指出的，主要问题是您在没有使用strcpy()的情况下错误地分配了令牌。正如wildplasser在评论中指出的那样，使用POSIXstrdup()函数更简单(它还不是标准C的一部分，尽管在C2x中可能会改变)。

第二个问题是word包含换行符，而令牌从不包含换行符。你得把它去掉

这段代码做了这些修改，并添加了一个函数来转储字符串数组。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
static int cmp(const void *a, const void *b)
{
const char *ia = *(const char **)a;
const char *ib = *(const char **)b;
return strcmp(ia, ib);
}
static void dump_strings(const char *tag, size_t num_words, char **words);
int main(void)
{
char *text = malloc(sizeof(char *) * 1000);
char *word = malloc(sizeof(char *) * 30);
char **all_words = malloc(sizeof(char *) * 1);
int count_word = 0;
fgets(text, 1000, stdin);
fgets(word, 30, stdin);
word[strcspn(word, "n")] = '';
char *tok = strtok(text, " .n");
while (tok != NULL)
{
all_words[count_word++] = strdup(tok);
all_words = realloc(all_words, (count_word + 1) * sizeof(char *));
tok = strtok(NULL, " .n");
}
dump_strings("Before", count_word, all_words);
qsort(all_words, count_word, sizeof(char *), cmp);
dump_strings("After", count_word, all_words);
void *pointer = bsearch(&word, all_words, count_word, sizeof(char *), cmp);
if (pointer != NULL)
printf("Word [%s] existsn", word);
else
printf("Word [%s] does not existsn", word);
for (int i = 0; i < count_word; i++)
free(all_words[i]);
free(all_words);
free(word);
free(text);
return 0;
}
static void dump_strings(const char *tag, size_t num_words, char **words)
{
printf("%s (%zu):n", tag, num_words);
for (size_t i = 0; i < num_words; i++)
printf("%zu: [%s]n", i, words[i]);
}

在文件cpystr89.c中，编译成可执行文件cpystr89。我使用以下shell脚本运行命令:

./cpystr89 <<'EOF'
this is the text of the long string with many words in it and some repetition and so on.  of course, it is in mono-case for simplicity.  messieurs o'rourke and o'sullivan cause trouble; so does a semicolon
the
EOF

它的输出是:

Before (37):
0: [this]
1: [is]
2: [the]
3: [text]
4: [of]
5: [the]
6: [long]
7: [string]
8: [with]
9: [many]
10: [words]
11: [in]
12: [it]
13: [and]
14: [some]
15: [repetition]
16: [and]
17: [so]
18: [on]
19: [of]
20: [course,]
21: [it]
22: [is]
23: [in]
24: [mono-case]
25: [for]
26: [simplicity]
27: [messieurs]
28: [o'rourke]
29: [and]
30: [o'sullivan]
31: [cause]
32: [trouble;]
33: [so]
34: [does]
35: [a]
36: [semicolon]
After (37):
0: [a]
1: [and]
2: [and]
3: [and]
4: [cause]
5: [course,]
6: [does]
7: [for]
8: [in]
9: [in]
10: [is]
11: [is]
12: [it]
13: [it]
14: [long]
15: [many]
16: [messieurs]
17: [mono-case]
18: [o'rourke]
19: [o'sullivan]
20: [of]
21: [of]
22: [on]
23: [repetition]
24: [semicolon]
25: [simplicity]
26: [so]
27: [so]
28: [some]
29: [string]
30: [text]
31: [the]
32: [the]
33: [this]
34: [trouble;]
35: [with]
36: [words]
Word [the] exists

输入循环中的realloc()代码不理想。一般情况下，对于每次迭代会使内存分配增加一个单元的循环，您应该谨慎对待。随着时间的推移，这可能导致二次行为，因为旧的分配被复制到每个(或大多数)分配上。通常情况下，最好使用分配多个额外指针并一次分配一个的策略。在这种情况下，您可以简单地分配strlen(text) / 2 + 1指针;最多每隔一个字符是一个单词(例如，如果输入a b c d作为文本)。通常，您将使用两个计数器:num_alloc和num_used。num_alloc值记录了分配了多少指针;num_used记录正在使用的号码。您可以在每次调用时将num_alloc加倍。如果您担心输入完成后会出现过度分配，您可以使用一个收缩的realloc()来释放额外的空间。

您的代码没有检查每个内存分配是否成功。它应该!

我还注意到我不会将malloc()用于text和word。您可以在堆栈上分配几kb的内存。当您开始在堆栈上分配数百千字节时，就会出现问题。Windows上的默认堆栈限制通常为1 MiB;在大多数类unix系统上，它是8 MiB。在任何一种情况下，一旦您考虑分配数百kb，那么就应该考虑使用malloc()等来进行动态内存分配。不分配这些可以简化错误清理工作。

这段代码实现了这些更改。请注意对bsearch()调用中的更改。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
static int cmp(const void *a, const void *b)
{
const char *ia = *(const char **)a;
const char *ib = *(const char **)b;
return strcmp(ia, ib);
}
static void dump_strings(const char *tag, size_t num_words, char **words);
static void free_strings(size_t num_words, char **words);
int main(void)
{
char text[1000];
char word[30];
char **all_words = NULL;
int count_words = 0;
int alloc_words = 0;
fgets(text, 1000, stdin);
fgets(word, 30, stdin);
word[strcspn(word, "n")] = '';
for (char *tok = strtok(text, " .n"); tok != NULL; tok = strtok(NULL, " .n"))
{
if (count_words >= alloc_words)
{
size_t new_count = alloc_words * 2 + 2;     // + 2 to get away from zero
char **new_words = realloc(all_words, new_count * sizeof(*all_words));
if (new_words == NULL)
{
fprintf(stderr, "Failed to reallocate %zu bytes memoryn",
new_count * sizeof(*all_words));
free_strings(count_words, all_words);
exit(EXIT_FAILURE);
}
all_words = new_words;
alloc_words = new_count;
}
if ((all_words[count_words++] = strdup(tok)) == NULL)
{
fprintf(stderr, "Failed to allocate %zu bytes memoryn", strlen(tok) + 1);
free_strings(count_words, all_words);
exit(EXIT_FAILURE);
}
}
dump_strings("Before", count_words, all_words);
qsort(all_words, count_words, sizeof(char *), cmp);
dump_strings("After", count_words, all_words);
char *p_word = word;        // Irksome but necessary; using &word in call to bsearch() crashes
void *pointer = bsearch(&p_word, all_words, count_words, sizeof(char *), cmp);
if (pointer != NULL)
printf("Word [%s] existsn", word);
else
printf("Word [%s] does not existsn", word);
free_strings(count_words, all_words);
return 0;
}
static void dump_strings(const char *tag, size_t num_words, char **words)
{
printf("%s (%zu):n", tag, num_words);
for (size_t i = 0; i < num_words; i++)
printf("%zu: [%s]n", i, words[i]);
}
static void free_strings(size_t num_words, char **words)
{
for (size_t i = 0; i < num_words; i++)
free(words[i]);
free(words);
}

输出- surprise, surprise -与之前相同。

我还将错误报告和退出代码封装到函数中。我使用的代码可以在GitHub上的SOQ(堆栈溢出问题)存储库中作为文件stderr.c和stderr.h在src/libsoq子目录中获得。

if ((all_words[count_words++] = strdup(tok)) == NULL)
{
free_strings(count_words, all_words);
err_syserr("Failed to allocate %zu bytes memoryn", strlen(tok) + 1);
}

由于对free_strings()的调用，这并不像有时那样引人注目，但对于简单的情况，它将4行代码减少到1行，这使我不太愿意添加必要的错误检查。

bsearch使用的比较函数考虑一个元素数组(其大小必须作为参数传递)，然后它通过引用进行比较(这意味着，您接收到指向字符的双指针，而不是单指针)。这是因为bsearch例程是泛型的，可以传递给它的元素可以是结构体或大数组本身。唯一的要求是它们的大小必须相等。

这就是为什么在调用比较器时取消对指针的引用，然后用取消引用的指针调用strcmp的原因。Strcmp只获得指向char的指针，而不是指向char的指针的引用，这就是strcmp本身不足以用于传递给bsearch的原因。同样的问题也适用于qsort及其好友。

最后一个提示:如果不需要，永远不要使用强制类型转换。这适用于您在ia和ib声明中所做的强制转换。你最好把比较函数写成:

int cmp(const void *a, const void *b) {
const char * const *ia = a;
const char * const *ib = b;
return strcmp(*ia, *ib);
}

相关内容

最新更新

热门标签：