如何从双向链表中删除节点

3 回答

• 1

  我觉得你做得太复杂了 . 你没有将“list”类型与“node”类型分开，但我认为如果你只是返回一个替代品，你可以顺利通过指针指针 .

  您可能希望编写一个“查找”方法来处理查找字符并返回指向该节点的指针 .

  /**
    Delete the node containing value from the list starting with start.
    If value is not found in list, then the list is unchanged. Returns
    a replacement value for start, which may be needed if the value is
    contain in the start node.
  */
  
  ListNodePtr  del(ListNodePtr start, char value)
  {
      ListNodePtr curr;
  
      for (curr = start; curr && curr->data != value; curr = curr->nextPtr) {
          // skip this node
      }
  
      if (!curr) {
          // Value not found in list. List is unchanged.
          return start;
      }
  
      /* Compute return value */
  
      if (curr == start) {
          start = start->nextPtr;
      }
  
      /* Remove curr node from chain */
  
      if (curr->prevPtr) {
          curr->prevPtr->nextPtr = curr->nextPtr;
      }
  
      if (curr->nextPtr) {
          curr->nextPtr->prevPtr = curr->prevPtr;
      }
  
      free(curr);
      return start;
  }
  

  回复于 2024-05-03T22:21:36+08:00
• 0

  删除最后一个节点后，您的代码不会检查新的头节点是否为空，因此当您尝试将头节点的下一个指针设置为null时，代码会崩溃 .

  修复代码（在valgrind下运行无泄漏且无错误）：

  #include <assert.h>
  #include <stdio.h>
  #include <stdlib.h>
  
  struct listNode
  {
      char data;
      struct listNode *nextPtr;
      struct listNode *prevPtr;
  };
  
  typedef struct listNode ListNode;
  typedef ListNode *ListNodePtr;
  
  void insert(ListNodePtr *sPtr, char value);
  char del(ListNodePtr *sPtr, char value);
  int isEmpty(ListNodePtr sPtr);
  void printList(ListNodePtr currentPtr);
  void printReverse(ListNodePtr currentPtr);
  
  static void ins_check(ListNode **list, char c)
  {
      printf("Inserting [%c] (%p)\n", c, (void *)*list);
      insert(list, c);
      printList(*list);
      printReverse(*list);
  }
  
  static void del_check(ListNode **list, char c)
  {
      printf("Deleting [%c] (%p)\n", c, (void *)*list);
      if (del(list, c) != c)
          printf("Did not find [%c] in list.\n", c);
      printList(*list);
      printReverse(*list);
  }
  
  int main(void)
  {
      ListNodePtr startPtr = NULL;
  
      printList(startPtr);
      printReverse(startPtr);
  
      ins_check(&startPtr, 'a');
      ins_check(&startPtr, 'b');
      ins_check(&startPtr, 'c');
  
      del_check(&startPtr, 'c');
      del_check(&startPtr, 'a');
      del_check(&startPtr, 'b');
  
      assert(startPtr == 0);
  
      printf("End of run.\n");
      return 0;
  }
  
  void printList(ListNodePtr currentPtr)
  {
      if (currentPtr == NULL)
          printf("List is empty.\n");
      else
      {
          printf("The list is: ");
          while (currentPtr != NULL)
          {
              printf("%c --> ", currentPtr->data);
              currentPtr = currentPtr->nextPtr;
          }
          printf("NULL\n");
      }
  }
  
  void printReverse(ListNodePtr currentPtr)
  {
      if (currentPtr == NULL)
          printf("List is empty (even in reverse).\n");
      else
      {
          printf("The list in reverse is: ");
          while (currentPtr->nextPtr != NULL)
              currentPtr = currentPtr->nextPtr;
          while (currentPtr != NULL)
          {
              printf("%c --> ", currentPtr->data);
              currentPtr = currentPtr->prevPtr;
          }
          printf("NULL\n");
      }
  }
  
  char del(ListNodePtr *sPtr, char value)
  {
      ListNodePtr previousPtr;
      ListNodePtr currentPtr;
      ListNodePtr tempPtr;
  
      assert(*sPtr != 0);
      if (value == (*sPtr)->data)
      {
          tempPtr = *sPtr;
          printf("Deleting 1: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
                  (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
          *sPtr = (*sPtr)->nextPtr;
          if (*sPtr != 0)   // Crucial change!
              (*sPtr)->prevPtr = NULL;
          free(tempPtr);
          return value;
      }
      else
      {
          previousPtr = *sPtr;
          currentPtr = (*sPtr)->nextPtr;
  
          while (currentPtr != NULL && currentPtr->data != value)
          {
              previousPtr = currentPtr;
              currentPtr = currentPtr->nextPtr;
          }
  
          if (currentPtr != NULL)
          {
              assert(previousPtr != 0);
              tempPtr = currentPtr;
              printf("Deleting 2: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data,
                      (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr);
              previousPtr->nextPtr = currentPtr->nextPtr;
              free(tempPtr);
              return value;
          }
          else
              printf("Did not find [%c]\n", value);
      }
  
      return '\0';
  }
  
  void insert(ListNode **list, char value)
  {
      ListNode *node = malloc(sizeof(*node));
      if (node == 0)
      {
          fprintf(stderr, "Out of memory\n");
          exit(EXIT_FAILURE);
      }
      node->data = value;
      node->nextPtr = 0;
      node->prevPtr = 0;
      if (*list != 0)
      {
          node->nextPtr = *list;
          assert((*list)->prevPtr == 0);
          (*list)->prevPtr = node;
      }
      *list = node;
  }
  

  示例运行：

  List is empty.
  List is empty (even in reverse).
  Inserting [a] (0x0)
  The list is: a --> NULL
  The list in reverse is: a --> NULL
  Inserting [b] (0x7fccc3503070)
  The list is: b --> a --> NULL
  The list in reverse is: a --> b --> NULL
  Inserting [c] (0x7fccc3503090)
  The list is: c --> b --> a --> NULL
  The list in reverse is: a --> b --> c --> NULL
  Deleting [c] (0x7fccc35030b0)
  Deleting 1: [c] (node = 0x7fccc35030b0, next = 0x7fccc3503090, prev = 0x0
  The list is: b --> a --> NULL
  The list in reverse is: a --> b --> NULL
  Deleting [a] (0x7fccc3503090)
  Deleting 2: [a] (node = 0x7fccc3503070, next = 0x0, prev = 0x7fccc3503090
  The list is: b --> NULL
  The list in reverse is: b --> NULL
  Deleting [b] (0x7fccc3503090)
  Deleting 1: [b] (node = 0x7fccc3503090, next = 0x0, prev = 0x0
  List is empty.
  List is empty (even in reverse).
  End of run.
  

  注意使用包装函数（ ins_check() 和 del_check() ）以及使用固定数据使其易于测试（无需输入） . 还要注意打印正在发生的事情 .

  我希望你的 insert() 有点类似于我设计的那个 - 真正的MCVE（How to create a Minimal, Complete, and Verifiable Example?）或SSCCE（Short, Self-Contained, Correct Example）会提供该功能 .

  请注意'new'代码遵循Is it a good idea to typedef pointers建议的限制 - 简洁的答案是"No"（对于非不透明的数据指针） .

  请注意，您的删除功能与单链表一样复杂，但可以简单得多，因为双链表中的每个节点都知道它自己的前任 . 这个版本也干净利落：

  char del(ListNodePtr *sPtr, char value)
  {
      assert(*sPtr != 0);
      ListNode *curr = *sPtr;
      while (curr != NULL)
      {
          if (curr->data == value)
          {
              if (curr->prevPtr != NULL)
                  curr->prevPtr->nextPtr = curr->nextPtr;
              if (curr->nextPtr != NULL)
                  curr->nextPtr->prevPtr = curr->prevPtr;
              if (*sPtr == curr)
                  *sPtr = curr->nextPtr;
              free(curr);
              return value;
          }
          curr = curr->nextPtr;
      }
  
      printf("Did not find [%c]\n", value);
      return '\0';
  }
  

  回复于 2024-05-03T22:21:36+08:00
• 0

  我最终意识到自己的问题 . Visual Studio并没有让我使用断点，但那是因为我没有意识到我将它设置为“Release”而不是“Debug” . 这样做我跟踪了指针，找出它们在哪里被取消链接或链接到错误的链接并提出了这个解决方案：

  /* Delete a list element */
  char del(ListNodePtr *sPtr, char value)
  {
      ListNodePtr previousPtr; /* pointer to previous node in list */
      ListNodePtr currentPtr; /* pointer to current node in list */
      ListNodePtr tempPtr; /* temporary node pointer */
  
      /* delete first node */
      if (value == (*sPtr)->data) {
              tempPtr = *sPtr; /* hold onto node being removed */
              *sPtr = (*sPtr)->nextPtr; /* de-thread the node */
              if(*sPtr != NULL) /* if the list is not empty */
                  (*sPtr)->prevPtr = NULL; /* the previos pointer is null*/
              free(tempPtr); /* free the de-threaded node */
              return value;
      } /* end if */
      else {
          previousPtr = *sPtr;
          currentPtr = (*sPtr)->nextPtr;
  
          /* loop to find the correct location in the list */
          while (currentPtr != NULL && currentPtr->data != value) {
              previousPtr = currentPtr; /* walk to ...   */
              currentPtr = currentPtr->nextPtr; /* ... next node */
          } /* end while */
  
            /* delete node at currentPtr */
  
          if (currentPtr != NULL) {
              tempPtr = currentPtr;
              previousPtr->nextPtr = currentPtr->nextPtr;
              if(previousPtr->nextPtr != NULL) /* if the next pointer isn't null */
                  previousPtr->nextPtr->prevPtr = currentPtr->prevPtr; /* the previous pointer of the next pointer is the previous pointer of the current pointer */
              free(tempPtr);
              return value;
          } /* end if */
  
      } /* end else */
      return '\0';
  } /* end function delete */
  

  回复于 2024-05-03T22:21:36+08:00