我正在研究 K&R 书籍 (#6.3) 中的一个问题,用户输入一系列单词,您必须创建这些单词的列表以及每个单词出现的行。它应该涉及结构,所以这些是我现在拥有的结构:
struct entry {
int line;
int count;
struct entry *next;
};
struct word {
char *str;
struct entry *lines;
struct word *next;
};
static struct word *wordlist = NULL; // GLOBAL WORDLIST
但是,当我输入一些内容并且程序试图向结构(有点像链表)添加一个新条目时,出现了一个问题,程序终止并且没有错误消息。代码:
void add_entry(char *word, int line)
{
if (word == NULL || line <= 0 || is_blocked_word(word))
return;
struct word *w;
for (w = wordlist; w != NULL && w->next != NULL && !strcmp(w->str, word); w = w->next);
// If word is found in the wordlist, then update the entry
if (w != NULL) {
struct entry *v;
for (v = w->lines; v != NULL && v->next != NULL && v->line != line; v = v->next);
if (v == NULL) {
struct entry *new = (struct entry*) malloc(sizeof(struct entry));
new->line = line;
new->count = 1;
new->next = NULL;
if (w->lines == NULL)
w->lines = new;
else
v->next = new;
}
else v->count++;
}
// If word is not found in the word list, then create a new entry for it
else {
struct word *new = (struct word*) malloc(sizeof(struct word));
new->lines = (struct entry*) malloc(sizeof(struct entry));
new->next = NULL;
new->str = (char*) malloc(sizeof(char) * strlen(word));
new->lines->line = line;
new->lines->count = 1;
new->lines->next = NULL;
strcpy(new->str, word);
// If the word list is empty, then populate head first before populating the "next" entry
if (wordlist == NULL)
wordlist = new;
else
w->next = new;
}
}
即使只将第一个单词添加到 wordlist
中,程序也会终止。这是在表示 if (wordlist == NULL) wordlist = new;
的行上,其中 new
包含指向我分配的有效结构的指针。这怎么可能?
据我所知,这是我的指针使用问题,但我不确定它的确切位置。有人可以帮忙吗?
最佳答案
有些相当明显,有些则不太明显。
w
的 for 循环限制停止一个短
for (w = wordlist; w != NULL && w->next != NULL && !strcmp(w->str, word); w = w->next);
这将从第一个开始并继续直到
- 我们已经用完了节点
- 我们几乎(短)节点用完了。
- 当前节点中的单词不匹配
几乎相同的问题,不同的for循环
for (v = w->lines; v != NULL && v->next != NULL && v->line != line; v = v->next);
如上所述,它具有类似的属性(但不是第三个选项,因为只要行号不匹配,它就会正确地继续。一旦任何< 单词不匹配。
这是该函数的前十行。
字符串分配大小未能考虑 nulchar 终止符
这比零终止字符串所需的分配大小少了一个字符:
malloc(sizeof(char) * strlen(word))
终结符总是需要空间。记住这一点的最简单方法是考虑零长度 C 字符串需要多少个字符?答:一,因为终结者需要去某个地方。之后就是 length+1
一种可能的方法是通过指针到指针的方法,如下所示:
void add_entry(const char *word, int line)
{
if (word == NULL || line <= 0 || is_blocked_word(word))
return;
struct word **pp = &wordlist;
for (; *pp && strcmp((*pp)->str, word); pp = &(*pp)->next);
if (*pp)
{
// search for matching line number
struct entry **vv = &(*pp)->lines;
for (; *vv && (*vv)->line != line; vv = &(*vv)->next);
if (!*vv)
{
*vv = malloc(sizeof(**vv));
if (!*vv)
{
perror("Failed to allocate line entry.");
exit(EXIT_FAILURE);
}
(*vv)->count = 1;
(*vv)->line = line;
(*vv)->next = NULL;
}
else
{ // found an entry. increment count.
(*vv)->count++;
}
}
else
{ // no matching word. create a new word with a new line entry
size_t len = strlen(word);
*pp = malloc(sizeof(**pp));
if (!*pp)
{
perror("Failed to allocate word entry.");
exit(EXIT_FAILURE);
}
(*pp)->lines = malloc(sizeof(*(*pp)->lines));
if (!(*pp)->lines)
{
perror("Failed to allocate line count entry.");
exit(EXIT_FAILURE);
}
(*pp)->str = malloc(len + 1);
if (!(*pp)->str)
{
perror("Failed to allocate word string entry.");
exit(EXIT_FAILURE);
}
(*pp)->lines->count = 1;
(*pp)->lines->line = line;
(*pp)->lines->next = NULL;
(*pp)->next = NULL;
memcpy((*pp)->str, word, len+1);
}
}
工作原理
在这两种情况下,我们都使用指针到指针。当希望在链表上执行尾端插入而不必保留“单向”或“前一个”指针时,它们是最常用的构造。就像任何指针一样,它们拥有一个地址。与常规的指向某物的指针不同,指向某物的指针保存另一个指针的地址。有了它,我们可以通过最初将其设置为头指针的地址来“循环”,然后进入搜索。
struct word **pp = &wordlist;
for (; *pp && strcmp((*pp)->str, word); pp = &(*pp)->next);
这里我们从头指针的地址开始。如果 pp
中保存的地址处的指针 为 NULL,或者如果单词实际匹配,则循环将终止。否则,它会将当前节点的 next
指针设置为 of 的地址(而不是 in 的地址)。 a match 循环将中断,但最方便的结果是:pp
包含我们需要设置为新分配的指针的地址。如果列表最初为空,它包含头指针的地址。
有了它,我们就可以这样做了:
if (*pp)
{
// search for matching line number
struct entry **vv = &(*pp)->lines;
for (; *vv && (*vv)->line != line; vv = &(*vv)->next);
请注意,我们在行条目列表中使用了相同的想法。要么我们要找到一个条目,要么循环将以 *vv
为 NULL
退出,并且 vv
包含 next
指针我们要设置为我们的新分配。
我强烈敦促您在调试器中逐行调试这段代码,并理解它是如何工作的。利用这种技术有许多可取之处,其中包括在O(n)
复杂度 中填充前向链表的非常简单的方法,而无需检查头指针或遍历每次插入的列表并保留原始顺序(而不是像堆栈式解决方案那样颠倒顺序):
struct node *head = NULL;
struct node **pp = &head;
while (get-data-for-our-list)
{
*pp = malloc(sizeof(**pp));
// TODO: populate (*pp)->members here
pp = &(*pp)->next;
}
*pp = NULL;
关于C 指针,向链表的 HEAD 插入元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19416856/