1

伙计们，我是队列的新手，很难理解它们是如何工作的。我所了解的是队列Append的项目和Serve附加的第一个项目。

从下面的代码中，我理解的是每次附加时，Link总是NULL，对吗？还有什么时候Tail !=NULL成真？我很困惑，因为每次我们追加Tail都设置为NULL...

int item;

struct Node
{
  int Data;
  struct Node *Link;
};
typedef struct Node *QueuePointer;

void Append(QueuePointer &Head,QueuePointer &Tail, int Num)
{
  QueuePointer NewNode;
  NewNode= (QueuePointer)malloc(sizeof(struct Node));
  NewNode->Data = Num;
  NewNode->Link = NULL;
  if(Tail == NULL)
  {
    Head = NewNode;
    // printf("Queue is empty"); //checks if queue is empty
    // printf("\n");
  }
  else
  {
    Tail->Link = NewNode;
  }
  Tail = NewNode;
  printf("Inserted number %d \n", item); //checks if Appends into Queue working
}

void Serve(QueuePointer &Head, QueuePointer &Tail, int item)
{
  QueuePointer Temp;

  printf("Served ");

  while(Head != NULL)
  {
    item = Head->Data;
    Temp = Head;
    Head = Head->Link;
    if(Head == NULL)
    {
      Tail = NULL;
    }
    free(Temp);
    printf("%d ", item); //prints out SERVED 
  }
}

int main()
{
  QueuePointer Head, Tail;
  Head = NULL;
  Tail = NULL;
  item = 1;

  for (item = 1; item <= 4; item++)
  {
    // if(item%2==0)
    // {

    Append(Head, Tail, item); //Appends For Every Even Number Detected 

    // }    
  }
  Serve(Head, Tail, item); //Calls out Serve Function, See LOOPING, please refer serve function
  //****NOTE: the loop for Removing items is inside Serve Function

  getch();
}
4

1 回答 1

0

您在 和 之间感到Tail困惑Tail->Link。在队列中，Tail->Link总是NULL。但Tail仅NULL当队列为空时。如果队列中至少有一个节点，Tail则不是。NULL

队列是一个 FIFO 结构（先进先出）。节点总是添加到队列的末尾，节点总是从队列的开头删除。因此，当您追加一个节点时，新节点将被添加到队列的末尾。因此，最近添加的节点将始终是Tail队列的节点。Tail->Link，它指向下一个节点的指针将永远是NULL，因为它是队列中的最后一个节点并且没有下一个节点。

发生的事情Append()是这样的：

  1. 为新节点分配内存。数据被复制到新节点。由于新节点将被附加到现有队列的末尾，因此新节点的链接设置为NULL。
  2. 检查现有队列。如果Tail现有队列的节点是NULL，则表示队列中没有节点。所以新节点将成为队列中唯一的节点；这意味着它将成为队列中的第一个节点；这意味着Head应该为指针分配这个新节点。您的代码适当地做到了这一点。
  3. 如果Tail现有队列的节点不是NULL，则必须将新节点添加到现有队列的末尾。即，Tail->Link应该将现有队列从更改NULL为新节点。您的代码也这样做。
  4. 最后，现有队列的Tail节点设置为新节点，因为新节点现在是队列的末尾。

这样，新节点被添加到队列的末尾。现在是Tail，因为它是尾节点，所以它的链接是NULL。

希望这很清楚。顺便说一句，您已经标记了您的问题c，但函数头中的传递引用语法void Append(QueuePointer &Head,QueuePointer &Tail, int Num)是 C++，而不是 C。

于 2013-08-31T09:48:07.340 回答