删除 C 中链表末尾附加的节点

Question

我有一个链表，每个节点存储一个单词和一个数字。我可以在列表顶部(push(，列表中心(insertAfter(和列表末尾(append(添加节点。我现在添加了一个删除节点的函数，它将在其中获取一个 char，它将在列表中搜索该 char 并删除存储该 char 的节点。

问题是deleteNode可以使用在列表顶部添加的普通节点，但是当我在末尾附加一个节点或将其添加到列表中间时，它将不起作用。

Tl;deleteNode博士适用于使用push创建的节点，但不适用于使用append或insertAfter创建的节点。

我得到的错误是segmentation fault，所以我没有编译器的特定错误。我正在尝试通过运行代码的不同部分来调试它，但我仍然找不到问题。

struct Node
{
int data;
char *word;
struct Node *next;
};

void push(struct Node** head_ref, int new_data, char *new_word)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data  = new_data;

new_node->word= malloc(strlen(new_word));
strcpy(new_node->word, new_word);
new_node->next = (*head_ref);
(*head_ref)    = new_node;
}
/* Given a node prev_node, insert a new node after the given 
prev_node */
void insertAfter(struct Node* prev_node, int new_data, char *new_word)
{
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node =(struct Node*) malloc(sizeof(struct Node));
new_node->data  = new_data;
new_node->word= malloc(strlen(new_word));
strcpy(new_node->word, new_word);
new_node->next = prev_node->next;
prev_node->next = new_node;
}

void append(struct Node** head_ref, int new_data, char *new_word)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref;  

new_node->data  = new_data;
new_node->word= malloc(strlen(new_word));
strcpy(new_node->word, new_word);
new_node->next = NULL;

if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}

while (last->next != NULL)
last = last->next;

last->next = new_node;
return;
}

void deleteNode(struct Node **head_ref, char *word)
{
struct Node* temp = *head_ref, *prev;
if (strcmp(word, (*head_ref)->word)==0)
{
*head_ref = temp->next;   // Changed head
free(temp);               // free old head
return;
}

while (strcmp(word, (*head_ref)->word)!=0)
{
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;

prev->next = temp->next;
free(temp);  // Free memory
}

Answer 1

这部分看起来很奇怪：

while (strcmp(word, (*head_ref)->word)!=0)
{
prev = temp;
temp = temp->next;
}

在strcmp中使用head_ref但在正文中，您更新temp以移动到下一个元素。

你打算做：

while (strcmp(word, temp->word)!=0)
{
prev = temp;
temp = temp->next;
}

此外，可能应该检查temp是否为 NULL。喜欢：

while (temp && strcmp(word, temp->word)!=0)

Answer 2

除了@4386427所说的之外，您没有为那里的字符串分配足够的空间：

new_node->word= malloc(strlen(new_word));

请注意，C 库函数size_t strlen(const char *str)计算字符串 str 的长度，但不包括终止 null 字符。所以我宁愿建议：

new_node->word= malloc(strlen(new_word) + 1);
new_node->word[strlen(new_word)] = '';

这可能会导致内存出现问题。 ;)

或者事件更好，使用calloc，所以第二行将是不必要的：

new_node->word= calloc(strlen(new_word) + 1, sizeof(char));

Answer 3

你的答案还可以，但只是为了记录，经过足够的练习，它应该看起来像这样：

void deleteNode(struct Node **pplist, char *word)
{
for (struct Node *n = *pplist; n; n=*(pplist = &(n->next)))
{
if (!strcmp(n->word,word))
{
*ppnode = n->next;
free(n->word);
free(n);
break;
}
}
}

关键是，您可以在列表中将指针移动到节点指针，而不是将头部视为特例。

同样，您可以像这样追加：

void append(struct Node** pplist, int new_data, char *new_word)
{
for(; *pplist; pplist=&((*pplist)->next));
push(pplist, new_data, new_word);
}

insert_after(prev...只是push(&(prev->next)...