大话数据结构中的代码错误-顺序循环队列的QueueTraverse()函数

84 阅读 0 评论 56 点赞

我是靠谱客的博主无奈柠檬，这篇文章主要介绍大话数据结构中的代码错误-顺序循环队列的QueueTraverse()函数，现在分享给大家，希望可以做个参考。

疫情期间，被困家中，闲来无事，过一遍数据结构中的基础知识，再看《大话数据结构》中循环队列时，看到这个一段代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(SqQueue Q)
{ 
	int i;
	i=Q.front;
	while((i+Q.front)!=Q.rear)
	{
		visit(Q.data[i]);
		i=(i+1)%MAXSIZE;
	}
	printf("n");
	return OK;
}

看到循环的终止条件时，越想越不对劲，又担心是自己学识浅薄对大佬的代码妄加指责，于是先合上书自己回想一下，正常而言队列时怎么遍历的：

找到队列的第一个元素的位置，假设为start，使用探针needle检测时候到达队列末尾；
从start开始，往后依次访问；
由于是循环队列，所以走到数组的末尾位置时，可能需要回到数组的第一个位置，使用模运算%可以达到目的；
探针needle到达队列末尾时，输出最后一个元素end的值，然后终止遍历。

捋清楚思维之后，再来看上面的代码，可以肯定的是，循环体中的内容没有问题，而while中判断终止的条件则应该改成：

复制代码

1
while( i != Q.rear )

至于为什么原先的代码在运行时没有出现问题，我推测是书中的例子在进行遍历时，队列的第一个元素位置为0，所以显示不出来问题。

接下来验证我的假设：可以将队列调整为：队列第一个元素位置*2 = 队列末尾元素位置，这样就可以触发原先代码的终止条件，将问题显现出来，使用的代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    InitQueue(&Q);

    EnQueue(&Q, 0);
    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    EnQueue(&Q, 4);

    DeQueue(&Q, &data);
    printf("取出来的元素值：%d。n", data);
    DeQueue(&Q, &data);
    printf("取出来的元素值：%d。n", data);

    QueueTraverse(Q);

此时队列中元素分布应该是这种情况：