我正在尝试删除具有特定值的节点。我的节点的设置方式是这样的：
typedef struct NodeStruct Node;
//struct for each office item
struct NodeStruct {
int id;
struct NodeStruct *next;
};
typedef struct {
/** Pointer to the first node on the list (or NULL ). */
Node *head;
} List;
目前，我的列表如下所示(下面的每个整数代表 id 来自： 1 -> 2 -> 3 -> 4 -> 5 -> 7
我想删除 1 和 4，因此生成的链表如下所示： 2 -> 3 -> 5 -> 6 -> 7
我已经编写了下面的代码。在该方法中，key表示值，应删除具有该值的节点。
void delete(int key, List *list)
{
//If linked list is empty (base case):
if (list->head == NULL) {
printf("Invalid commandn");
exit(EXIT_BAD_INPUT);
}
//Store head node
Node *temp = list->head;
//If first node needs to be deleted (special case):
if (key == list->head->id) {
list->head = temp->next; //Change head
free(temp); //Free old head
} else {
//Find previous node of the node to be deleted
while (temp->id != key) {
temp = temp->next;
}
//If the position is more than the number of nodes, throw exception:
if (temp == NULL || temp->next == NULL) {
printf("Invalid commandn");
exit(EXIT_BAD_INPUT);
}
//Node temp->next is the node to be deleted
//Store the pointer to the next of node to be deleted
Node *next = temp->next->next;
//Unlink the node from the linked list
free(temp->next);
temp->next = next;
printf("RECORD DELETED: %dn", key);
}
}
当我运行此代码时，我收到Segmentation Fault: 11.有人可以帮我删除具有特定值和列表末尾的节点吗？此外，如何检查链表中是否存在键值？如果这是一个重复的问题，请提前道歉。
指针到指针方法没问题，但是使用两个向下行进列表的指针实际上并不复杂。 只要保持一致。有一个引导和跟踪指针。当潜在顾客找到要删除的元素时，使用跟踪更新其next。当跟踪为 null 时例外。这意味着引线指向头部元素，因此请改为更新头部指针。
/** delete node with value key from list */
void del_node (int key, List *list)
{
for (Node *p = list->head, *q = NULL; p; q = p, p = p->next) // p leads, q trails
if (p->data == key) {
if (q) q->next = p->next;
else list->head = p->next;
free(p);
return;
}
}
如果您不使用指针来跟踪上一个和下一个节点，而是使用指向当前节点的双指针(例如指针的地址)，则没有特殊情况，例如
/** delete node with value key from list */
void del_node (int key, List *list)
{
Node **pn = &list->head; /* pointer to pointer */
Node *n = list->head; /* pointer to node */
while (n) { /* iterate over nodes */
if (n->id == key) { /* if key found */
*pn = n->next; /* set address to next */
free (n); /* delete current */
break; /* done */
}
pn = &n->next; /* address of next */
n = n->next;
}
}
有一篇非常好的文章，说明为什么这让Linus在理解指针上的事情变得简单得多。
为此，您需要找到匹配的注释及其上一个节点。
我们可以循环，直到找到匹配项或列表的末尾，记住上一个节点。从list->head开始，第一个节点不需要特殊情况。
Node *match = list->head;
Node *prev = NULL;
while( match && (match->id != key) ) {
prev = match;
match = match->next;
}
如果没有匹配项，循环将退出，match将为 null。大功告成。
if( !match ) {
return NULL;
}
否则，我们将通过将前一个节点的下一个节点更改为匹配的下一个节点来删除匹配的节点。如果没有上一个节点，我们将头部更改为下一个节点。如果它与最后一个节点匹配，则不会造成伤害;match->next将为 null，因此prev->next将为 null，即列表的新末尾。
if( prev ) {
prev->next = match->next;
}
else {
list->head = match->next;
}
最后，如何处理已删除的节点？您可以按原样在函数中free它。如果您完全控制所有节点内存，这是可以接受的。否则，如果在堆栈上分配了节点，则可能会导致错误。
返回已删除的节点并让用户使用它做他们想做的事情会更灵活。这是从键/值结构中删除时的典型行为：返回值。这就是为什么当我们找不到任何东西时，我会返回上面的NULL。
return match;
至少返回一个布尔值以指示是否删除了某些内容。
你可以这样使用它。
int main() {
Node node3 = { .id = 3, .next = NULL };
Node node2 = { .id = 2, .next = &node3 };
Node node1 = { .id = 1, .next = &node2 };
List list = { .head = &node1 };
Node *deleted = delete(3, &list);
if( deleted ) {
printf("Deleted id = %dn", deleted->id);
}
else {
puts("Node not found");
}
for(
Node *node = list.head;
node;
node = node->next
) {
printf("id = %dn", node->id);
}
}
我相信你的错误就在这里。
//Find previous node of the node to be deleted
while (temp->id != key) {
temp = temp->next;
}
这不会找到前一个节点，而是找到匹配的节点。
此外，仅当节点在堆上分配了malloc时，free才有效。如果它是在堆栈上分配的，它将不起作用。例如。。。
// This is all allocated on the stack an cannot be free()d
Node node3 = { .id = 3, .next = NULL };
Node node2 = { .id = 2, .next = &node3 };
Node node1 = { .id = 1, .next = &node2 };
List list = { .head = &node1 };
delete(2, &list);
这就是为什么我建议返回已删除的节点并让用户处理它。或者完全控制列表的内存并编写处理内存分配的add_node函数。