尝试从列表中删除节点时出现分段错误？

Question

我正在研究一个双向链表的删除方法，我试图在将一些节点添加到我的列表后删除它们。下面我提供了一些可重现性最低的代码。

当我运行此代码时，我收到错误 Segmentation Fault: 11。我知道我试图两次删除同一个节点，但这只会导致我的代码出错，并显示 Invalid command\n 消息，但是当这种情况发生时，我的整个程序停止并且我收到 Segmentation Fault: 11。我相信这与下面我的 delete 方法中的 (*current)->next->prev = (*current)->prev; 有关。

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};


/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *list;

List *makeList();
void insert(int idInsert, List *list);
static void *addRecord(List *list, int newID);
static void printReverse(List *list);
void delete(int key, List *list);
bool search(List *list, int x);

int main(void) {

  //Create an empty list for you to start.
  list = (List *)makeList();

  addRecord(list, 1);
  addRecord(list, 2);
  addRecord(list, 3);
  addRecord(list, 4);
  addRecord(list, 4);
  addRecord(list, 7);
  insert(15, list);
  delete(7, list);
  delete(1, list);
  delete(4, list);
  delete(2, list);
  delete(5, list);
  delete(2, list);
  printReverse(list);

}

List *makeList()
{
  List *list = (List *) malloc( sizeof( List ) );
  list->head = NULL;
  list->last = NULL;
  return list;
}

void insert(int idInsert, List *list)
{
  //Insert the record based on the ID if no duplicates exist
  //Special case: insert at front if idInsert is less than the ID of the current head
  if (idInsert < list->head->id) {
    //Make the node with idInsert the first node
    Node *new = malloc(sizeof(Node)); //Allocate memory for the new node

    list->head->prev = new;
    new->prev = NULL;
    //Add in data
    new->id = idInsert;

    new->next = list->head;

    list->head = new;
    // if the new node is the last one
  } else if (idInsert > list->last->id) {
    addRecord(list, idInsert);
    printf("RECORD INSERTED: %d\n", idInsert);
    return;
  } else { //Locate the node before the point of insertion
    //Allocate memory for the node
    Node *new = malloc(sizeof(Node));

    //Add in data
    new->id = idInsert;

    Node *current = list->head;
    while (current->next != NULL && current->next->id < new->id) {
      current = current->next;
    }
    new->next = current->next;
    if (current->next != NULL) {
      new->next->prev = new;
    }
    current->next = new;
    new->prev = current;
  }

  //Print this message if successful
  printf("RECORD INSERTED: %d\n", idInsert);
}

static void *addRecord(List *list, int newID) 
{
  //Allocate memory for the node
  Node *new = malloc(sizeof(Node)); 

  //Add in data
  new->id = newID; 

  new->prev = list->last;
  new->next = NULL;

  list->last = new;

  // if list is empty
  if(!list->head)
  {
    list->head = new;
    return EXIT_SUCCESS;
  }

  Node **next_p = &list->head;
  while (*next_p) {
    next_p = &(*next_p)->next;
  }
  *next_p = new;

  return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

void delete(int key, List *list)
{
  //Check if ID exists in list
  if (search(list, key) == false) {
    printf("Invalid command\n");
  } else {
    printf("RECORD DELETED: %d\n", key);
  }

  //If linked list is empty (base case)
  Node **current = &list->head;

  //current points to the pointer pointing towards the current node
  //For the first iteration, it is the address of the head pointer
  while (*current && key != (*current)->id) {
    current = &(*current)->next;
  }

  (*current)->next->prev = (*current)->prev;

  if (*current) {
    Node *temp = *current;
    *current = (*current)->next;
    free(temp);
  }

}

bool search(List *list, int x)
{
  Node *current = list->head; //Initialize current node
  while (current != NULL) {
    if (current->id == x) {
      return true;
    }
    current = current->next;
  }
  return false;
}

我想要的结果是：

RECORD INSERTED: 15
RECORD DELETED: 7
RECORD DELETED: 1
RECORD DELETED: 4
RECORD DELETED: 2
RECORD DELETED: 5
Invalid command
LIST IN REVERSE ORDER: 
Item ID: 15
Item ID: 3

而不是分段错误。我怎样才能改进我的删除方法中的代码，这样我就不会收到这个错误，为什么它目前会出现？

Answer 1

打印出 Invalid Command 后，您的代码做了什么？它继续在函数内执行，最终到达 (*current)->next->prev = (*current)->prev; 行，这将导致段错误，因为 *current 将为 NULL。

这暴露了三个问题。第一个是您有效地搜索 key 两次：一次是查看它是否在列表中，然后第二次是在列表中找到该节点所在的位置，以便将其删除。这些应该结合起来，因此只需要进行一次搜索。一种方法是使用 find return 一个合适的指针，这样您就可以找到并删除该节点。另一种方法是手动搜索（不调用 find）并在找不到 key.

时报告错误

第二个问题是打印Invalid Command后缺少return，虽然执行前面的建议可以避免这个问题。

第三个问题是对(*current)->next->prev的赋值应该在后面的if (*current)内，以避免解引用空指针。

尝试从列表中删除节点时出现分段错误？

Getting a segmentation fault when trying to delete a node from the list?

c

pointers

segmentation-fault

doubly-linked-list