首页 文章

节点在双向链表中删除

提问于
浏览 次
1

我正在开发一个删除双向链表节点的函数 . 这是我的头文件：

class LinkedList
{
private:
      struct Node
      {
         int data;
         Node *next;
         Node *previous;
      };

      int count;
      Node *head;
      Node *tail;

public:
      LinkedList() {head = NULL; tail = NULL; count = 0;} //Constructor

      void insert(const int );
      bool remove(const int );
      bool contains(const int );

      size_t lenght() {return count;}
};

我的其他函数工作正常，但它的删除函数在运行时断开 . 当我运行我的代码时，我得到了一个分段错误，经过2天的尝试找出我逻辑中的缺陷后，我转向社区寻求帮助 . 我很感激此时的任何反馈，谢谢 . 这是我的删除功能：

bool LinkedList::remove(const int item)
{//if the list is empty returns false
if(head == NULL) {return false;}

Node *hptr = head;
Node *tptr = tail;

if((hptr -> data) == item)
{//if the node is at the head of the list
  hptr = hptr -> next;
  delete head;
  hptr -> previous = NULL;
  head = hptr;
  --count;
  return true;

} else if((tptr -> data) == item) {
 //if the node is at the tail of the list
  tptr = tptr -> previous;
  delete tail;
  tail = tptr;
  tptr -> next = NULL;
  --count;
  return true;

} else {//if the node is in he middle of the list
  Node *ptr_head = head;   Node *ptr_headp = NULL;
  Node *ptr_tail = tail;   Node *ptr_tailp = NULL;

  while((ptr_head -> data) != item || (ptr_tail -> data) != item)
  {//pointers pass each other then data was not found
     if((ptr_tail -> data) < (ptr_head -> data)) {return false;}
   //traversing the list from the head and tail simultaniously
     ptr_headp = ptr_head;
     ptr_head = ptr_head -> next;

     ptr_tailp = ptr_tail;
     ptr_tail = ptr_tail -> previous;
  }

  if((ptr_head == ptr_tail) && ((ptr_tail -> data) == (ptr_head -> data)))
  {//the item is at the intersection of both head and tail pointers
     ptr_headp -> next = ptr_tailp;
     ptr_tailp -> previous = ptr_headp;
     delete ptr_head;
     delete ptr_tail;
     --count;
     return true;
  }

  if((ptr_head -> data) == item)
  {//the item is before middle node
     ptr_headp -> next = ptr_head -> next;
    (ptr_head -> next) -> previous = ptr_headp;
     delete ptr_head;
     --count;
     return true;
  }

  if((ptr_tail -> data) == item)
  {//the item is after the middle node
     ptr_tailp -> previous = ptr_tail -> previous;
    (ptr_tail -> previous) -> next = ptr_tailp;
     delete ptr_tail;
     --count;
     return true;
  }
}

return false;
}
c++ doubly-linked-list

2 回答

  • 1

    这是一个常见的例子，当改变数据结构时，通过统一看起来不同的情况*可以使逻辑变得非常简单 .

    逻辑的主要问题是您有很多条件需要检查：

    • 删除后面有其他节点的第一个节点

    • 删除前面有其他节点的最后一个节点

    • 删除唯一的节点

    • 删除中间的节点

    通过确保左侧始终有节点和任何节点右侧的节点，您可以使这四个条件与最后一个条件相同 . 以下是如何做到这一点：

    class LinkedList
{
private:
      struct Node
      {
         int data;
         Node *next;
         Node *previous;
      };

      int count;
      // The change begins here
      Node headTail;
      // End of the change

public:
      LinkedList() {head = NULL; tail = NULL; count = 0;} //Constructor

      void insert(const int );
      bool remove(const int );
      bool contains(const int );

      size_t lenght() {return count;}
};

    head 指针是 headTail 的 next ; tail 指针是 previous . 下一个和上一个点都在一个空列表中回到自身 .

    这样效率有点低，因为 headTail 的 data 未使用 . 该列表变为循环，始终存在一个节点 . 使用此节点，您可以安全地删除中间的任何节点，并更新前一个和下一个指针，就好像它们属于不同的对象一样 .

    *这是一个非常好的阅读，与手头的问题没有直接关系，但对于理解这种方法的哲学非常有用 .

    回复于
  • 2
    // Locate the item to remove
Node* to_remove = head;
while(to_remove && to_remove->data != item)
  to_remove = to_remove->next;

// Do the removal if we found it
if(to_remove)
{
  // If it was at the head, advance the head to the next item
  if(to_remove == head)
    head = head->next;
  // If it was at the tail, advance the tail to the previous item
  if(to_remove == tail)
    tail = tail->previous;

  // Remove from the list
  if(to_remove->next)
    to_remove->next->previous = to_remove->previous;
  if(to_remove->previous)
    to_remove->previous->next = to_remove->next;

  // Free the removed node
  delete to_remove;
  count--;
  return true;
}

return false;
    回复于

相关问题