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

wuliangtdi

1. typedef struct Node
   
2. {
   
3.         int data;
   
4.         struct Node* next;
   
5. }LinkQueueNode;
   
6. 
   
7. typedef struct
   
8. {
   
9.         LinkQueueNode * front;    //*队首*//
   
10.         LinkQueueNode * rear;         //*队尾*//
    
11. }LinkQueue;
    
12. //*队首队尾初始化*//
    
13. int InitQueue(LinkQueue *Q)
    
14. {
    
15.         Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueue));
    
16.         if(Q->front!=NULL)
    
17.         {
    
18.                 Q->rear=Q->front;
    
19.                 Q->front->next=NULL;
    
20.                 return 1;
    
21.         }
    
22.         else
    
23.                 return 0;
    
24. }
    
25. //*链队入队操作*//
    
26. int EnterQueue(        LinkQueue * Q,int x)
    
27. {
    
28.         LinkQueueNode * NewNode;                  
    
29.         NewNode=(LinkQueueNode * )malloc(sizeof(LinkQUeueNode));   //*为NewNode申请节点*//
    
30.         if(NewNode!=NULL)
    
31.         {
    
32.                 NewNode->data=x;
    
33.                 NewNode->next=NULL;
    
34.                 Q->rear->next=NewNode;
    
35.                 Q->rear=NewNode;
    
36.                 return 1;               
    
37.         }
    
38.         else return 0;       
    
39. }
    
40. 
    
41. //*链队出队操作*//
    
42. int Out_Queue(        LinkQueueNode * Q,int *x)
    
43. {
    
44.         LinkQueueNode *p;
    
45.         if(Q->front==Q->rear)
    
46.                 return 0;
    
47.         p=Q->front->next;
    
48.         Q->front->next=p-next;
    
49.         if(Q->rear==p)
    
50.                 Q->rear=Q->front;
    
51.         *x=p->data;
    
52.         free(p);
    
53.         return 1;
    
54. }

复制代码

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上的图

感谢感谢