[已解决]C语言链式队列的问题

wuliangtdi

typedef struct Node
{
        int data;
        struct Node* next;
}LinkQueueNode;

typedef struct
{
        LinkQueueNode * front;    //*队首*//
        LinkQueueNode * rear;         //*队尾*// 
}LinkQueue;
//*队首队尾初始化*// 
int InitQueue(LinkQueue *Q)
{
        Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueue));
        if(Q->front!=NULL)
        {
                Q->rear=Q->front;
                Q->front->next=NULL;
                return 1;
        }
        else
                return 0;
}
//*链队入队操作*//
int EnterQueue(        LinkQueue * Q,int x)
{
        LinkQueueNode * NewNode;                   
        NewNode=(LinkQueueNode * )malloc(sizeof(LinkQUeueNode));   //*为NewNode申请节点*// 
        if(NewNode!=NULL)
        {
                NewNode->data=x;
                NewNode->next=NULL;
                Q->rear->next=NewNode;
                Q->rear=NewNode;
                return 1;                
        }
        else return 0;        
 }
 
 //*链队出队操作*//
 int Out_Queue(        LinkQueueNode * Q,int *x)
 {
         LinkQueueNode *p;
         if(Q->front==Q->rear)
                 return 0;
         p=Q->front->next;
         Q->front->next=p-next;
         if(Q->rear==p)
                 Q->rear=Q->front;
         *x=p->data;
         free(p);
         return 1;
 }

Q->front->next=p-next;这条语句可以写成Q->front=p-next;吗？
p=Q->front->next;是把下一个节点全部赋值给p吗？

最佳答案

月排行榜 / 总排行榜

暗pluto

2019-4-11 22:32:54

    首先，楼主要明白，front这个节点是不存储数据的，就是一个头节点，用来方便链路的处理

1.一开始队列是空的，front和rear是是同一个节点，front的next指向NULL

2.第一个元素入队，创建一个节点now，然后把rear的下一个节点设为now，然后把第一个元素设为rear

然后我们就要考虑两种情况了，1种是现在出队，另一种是继续加元素

（1）现在出队：

  现在出队，那么队列中只有一个元素，具体节点的表示为：front节点  -->  第一个节点（rear节点）-->NULL

  由于队列是先进先出，那么，我们可以利用这种思想，把front的下一个节点设为第一个节点的下一个节点，那么第一个节点就被略过了，也就是出队了，然后再把rear节
点=front，回到原来空队列（如果队列里只有一个节点的话，rear = front）

（2）继续加元素：

  继续加元素，加第二个元素，那么具体的节点表示就是：front节点  --> 第一个节点 --> 第二个节点（rear）-->NULL

  好，现在来出队，那么还是先进先出，只要把front的下一个节点设为第一个节点的下一个节点，那么第一个节点就出队了，然后继续，把front的下一个节点设为第二个节点的下一个节点，那么第二个节点就出队了

这就是所有的情况了，楼主如果还是不懂的话，我可以画图表示一下，或者提出哪里不懂

跳转到最佳答案楼层

暗pluto

    首先，楼主要明白，front这个节点是不存储数据的，就是一个头节点，用来方便链路的处理

1.一开始队列是空的，front和rear是是同一个节点，front的next指向NULL

2.第一个元素入队，创建一个节点now，然后把rear的下一个节点设为now，然后把第一个元素设为rear

然后我们就要考虑两种情况了，1种是现在出队，另一种是继续加元素

（1）现在出队：

  现在出队，那么队列中只有一个元素，具体节点的表示为：front节点  -->  第一个节点（rear节点）-->NULL

  由于队列是先进先出，那么，我们可以利用这种思想，把front的下一个节点设为第一个节点的下一个节点，那么第一个节点就被略过了，也就是出队了，然后再把rear节
点=front，回到原来空队列（如果队列里只有一个节点的话，rear = front）

（2）继续加元素：

  继续加元素，加第二个元素，那么具体的节点表示就是：front节点  --> 第一个节点 --> 第二个节点（rear）-->NULL

  好，现在来出队，那么还是先进先出，只要把front的下一个节点设为第一个节点的下一个节点，那么第一个节点就出队了，然后继续，把front的下一个节点设为第二个节点的下一个节点，那么第二个节点就出队了

这就是所有的情况了，楼主如果还是不懂的话，我可以画图表示一下，或者提出哪里不懂

82457097

1.不可以，队头出列后，要将队伍头指针指向现任队头，也就是Q->front->next=p-next
2.理解对 但说法不准确 指针之间传递的是地址 不是把值全部赋给它 只是传个首地址给它

wuliangtdi

82457097 发表于 2019-4-12 09:31
1.不可以，队头出列后，要将队伍头指针指向现任队头，也就是Q->front->next=p-next
2.理解对 但说法不准确 ...

如图，当队列中只有一个元素a时，47、48行p=Q->front->next; Q->front->next=p->next;
其中Q->front->next=p->next; p->next=NULL;那队首不就是指向了NULL了吗？

82457097

wuliangtdi 发表于 2019-4-12 13:05
如图，当队列中只有一个元素a时，47、48行p=Q->front->next; Q->front->next=p->next;
其中Q->front->ne ...

如果队列只有一个元素 那么进行完出队操作后 队头队尾指针指向同一个地址 data为NULL

扩展阅读

（新手个人理解，勿喷）                             我怎么觉得  入队操作的函数 中的     Q->rear->next = NewNode 是多余的呢？？  我的理解是    在 Q->rear = NewNode 的时候 不是把 NewNode 的整体赋值给 Q->rear  了吗？   既然前面已经写有了 NewNode->next = NULL。  那Q->rear->next = NewNode的 这部操作是什么呢？ 是让 Q->rear->next 指向 NewNode的？  可是前面的NewNode-> = NULL， 不就是让Q->rear->next所指向的NewNode->next = NULL了吗？？那既然是这样，后一句的Q->rear = NewNode;  是不是就出错了？？因为Q->rear指向的是 NewNode 整体且NewNode->next = NULL。那是不是相当于 Q->rear的下一个节点是NULL?那么Q->rear->next这句是不是错的语句呢？？    求指点一下，谢谢。

wuliangtdi

82457097 发表于 2019-4-12 15:26
如果队列只有一个元素 那么进行完出队操作后 队头队尾指针指向同一个地址 data为NULL

这个我知道，其实我想问的是当队列中只有一个元素时Q->front->next=p->next， p->next不是指向NULL吗？那Q->front->next不就是指向NULL吗？后面的if(Q->rear==q) Q->rear=Q->front;这条语句就是把Q->rear指向了Q->front,我不知道这样理解对不对。

82457097

wuliangtdi 发表于 2019-4-12 17:19
这个我知道，其实我想问的是当队列中只有一个元素时Q->front->next=p->next， p->next不是指向NULL吗？那 ...

对的 因为p指向的地址就是a 原来rear指向的也是a所以 p==rear 在执行Q->front->next=p->next后 front指向了NULL a出队之后 这就是一个空队列 front和rear应该都指向NULL的

暗pluto

扩展阅读 发表于 2019-4-12 17:15
（新手个人理解，勿喷）                             我怎么觉得  入队操作的函数 中的     Q->rear->nex ...

Q->rear->next=NewNode;表示把rear的下一个节点设为刚进来的节点
Q->rear=NewNode; 表示把刚进来的节点设为rear（也就是最后一个节点）
画个图就知道了
一开始
front  -->NULL (进来一个节点now)      front（也指向now)    这时候很明显now是最后一个节点了
rear(也指向NULL)                              rear  --->  now

所以，应该变成
front --> now(也是rear)  -->NULL

如果还是不懂，可以看我下面的解释

wuliangtdi

暗pluto 发表于 2019-4-12 18:38
首先，楼主要明白，front这个节点是不存储数据的，就是一个头节点，用来方便链路的处理

1.一开始队 ...

大佬大佬  懂了 懂了

82457097

扩展阅读 发表于 2019-4-12 17:15
（新手个人理解，勿喷）                             我怎么觉得  入队操作的函数 中的     Q->rear->nex ...

我觉得你的理解有偏差
其实这个和链表的尾插法很相似，Q->rear其实指向的是最后一个元素的首地址，那么Q->rear->next就是最后一个元素->next 也就是NULL，让rear->next指向新入队列元素就是让最后一个元素->next指向新入队列的元素，你就把rear看做一个中介指针，他永远都指向最后一个元素，所以新加入一个元素之后，需要让Q->rear=NewNode；保持rear指向队尾，不然rear存在有何意义，再加新元素，让谁做中介；

扩展阅读

82457097 发表于 2019-4-12 19:08
我觉得你的理解有偏差
其实这个和链表的尾插法很相似，Q->rear其实指向的是最后一个元素的首地址，那么Q ...

可以画个图吗，还是不太了解。

扩展阅读

暗pluto 发表于 2019-4-12 18:54
Q->rear->next=NewNode;表示把rear的下一个节点设为刚进来的节点
Q->rear=NewNode; 表示把刚进来的节点 ...

可以帮画个图吗？还是不太了解

82457097

扩展阅读 发表于 2019-4-15 17:19
可以帮画个图吗？还是不太了解

csdn上的图

扩展阅读

82457097 发表于 2019-4-16 08:18
csdn上的图

感谢感谢