我正在研究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
指针的地址(而不是地址)。如果我们用完了单词并且永远找不到匹配项,循环将中断,但有一个最方便的结果: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;