3

基本上，我正在使用链表实现一个队列，以尝试模拟一天中在商店排队的人，他们等到他们面前的人完成他们的业务。前几个人很好，但是当我第二次调用 dequeue 时，它​​会出现段错误。gdb 调试器说错误来自这一行 head=current->next; （其中电流=头部）。

这是我的出队功能：

    void BankQueue::dequeue()
   {
      Node* current=head;
      head=current->next;
      if(head!=NULL)
      {
            head->prev=NULL;
      }
      delete current;
   }

这是入队函数（以防入队时我导致内存泄漏）：

    void BankQueue::enqueue(Customer s)
    {
         Node* node= new node;
         node->data=s;
         node->next=NULL;
         if(tail==NULL)
         {
              head=node;
              tail=node;
              node->prev=NULL;
         }
         else
         {
              node->prev=tail;
              tail->next=node;;
              tail=node;
         }

你们可以提供的关于段错误可能发生在哪里的任何帮助都会很棒，在此先感谢。

如有必要，PSI 可以提供更多信息。

4

3 回答 3

1

你的dequeue功能有缺陷。看看如果head是会发生什么NULL：

void BankQueue::dequeue()
{
    // current == NULL
    Node* current = head;
    // Setting head to NULL->next
    // This will reference memory location 0x00000000 + (some offset)
    head=current->next;
    // This is undefined, but it most likely will return true
    if(head!=NULL)
    {
        // undefined
        head->prev=NULL;
    }
    // Delete NULL
    delete current;
}

另外，是的，也tail需要在那里更新。

// After you've made sure that head is valid
if (head == tail) {
    // there is only node, so we just clear tail
    tail = NULL;
}
// Then you proceed with removal

托马斯，回应您的评论：

void BankQueue::dequeue()
{
    // If the queue has instances
    if (head)
    {
        // If there is only one instance
        if (head == tail)
        {
            tail = NULL;
        }

        // set the new head
        head = head->next;
        // delete the old head if it exists
        if (head->prev)
        {
            delete head->prev;
        }
        // null data
        head->prev = NULL;
    }
}
于 2013-03-26T02:16:32.873 回答
0

我有一个评论，但我会扩展，因为我认为这很可能是问题所在。

您的dequeue函数不会重置tail指针。因为该enqueue函数使用它来确定队列是否为空，所以如果您清空队列然后再次将项目放入其中（因为head将是 NULL），您将遇到问题。

于 2013-03-26T02:17:41.383 回答
0

在 dequeue 中设置条件 if(!head) return; 作为第一行。正如建议的那样，您将在此之后设置。

于 2013-03-26T02:21:56.313 回答