`
jakielong
  • 浏览: 222658 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

循环队列

阅读更多

 

相信绝大多数都学习过《数据结构》这门课程,而对这门课程里最熟悉的应该是堆栈和队列。本人前段时间买了一本有关算法(C语言实现)的书,发现其中对循环队列这一结构的算法存在漏洞,故写此文与大家交流探讨。

首先提一下循环队列的概念:队头指针head,队尾指针tail。


很显然,当队列满后,即便全部元素都出队,队列还是满的状态。这种情况就叫做“假溢出”,即数组中明明有可用空间,但却无法使用。

 

这是由定长数组的特性决定的。但我们可用改变一下思路,当队尾指针指向数组最后一个位置时,如果再有数据入队,并且队头指针没有指向数组的第一个元素,那么就让队为指针绕回到数组头部。这样就形成了一个逻辑上的环 即(循环队列)。

注:以上对循环队列的介绍系转载一高人博客。

书中所述对循环队列的代码如下:

 

#define MAXSIZE 10
typedef struct _QUEUE
{
  int elems [ MAXSIZE ] ;
  int front,rear;
}QUEUE;

int Initialize(QUEUE *queue)/*初始化队列*/
{
  queue->front=queue->rear=0;
}
int InQueue(QUEUE *queue,int x)/*元素‘x’入队函数*/
{
  if (((queue->rear+1) % MAXSIZE)==queue->front)
   {
     printf("Queue is overflow!\n");
     return 0;
   }

  queue->rear=(queue->rear+1)% MAXSIZE;
  queue->elems [ queue->rear ] =x;
}
int OutQueue(QUEUE *queue)/*出队函数*/
{
  if (queue->rear==queue->front)
   {
     printf("Queue is Empty!\n");
     return 0;
   }
  queue->front=(queue->front+1)% MAXSIZE;
}
int Show(QUEUE *queue)/*显示整个队列*/
{
  int i=(queue->front+1)%MAXSIZE;
  if (queue->front==queue->rear)
   {
     printf("Queue is Empty!\n");
     return 0;
   }
  for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE))
  {
     printf("queue->elems [ %d ] =%d\n ",i,queue->elems [ i ] );
  } 
   printf("\nQueue head is %d\n",queue->front);
   printf("Queue rear is %d\n",queue->rear);
}

 

 所有问题就出在 Show(QUEUE *queue) 这个函数上,我们做第一个测试代码:

 

main()
{
 /*Initialize a queue and show it.*/
 QUEUE queue;
 Initialize(&queue);
 Show(&queue);

 /*Add elems int a queue and show it.*/
 InQueue(&queue,1);
 InQueue(&queue,2);
 InQueue(&queue,3);
 InQueue(&queue,4);
 InQueue(&queue,5);
 InQueue(&queue,6);
 InQueue(&queue,7);
 InQueue(&queue,8);
 InQueue(&queue,9);
 Show(&queue);
}

 由于队列中始终要有一个空元素,根据此段代码定义 #define MAXSIZE 10 ,所以实际队列最多存在9个元素。但我们运行程序以后会发现程序陷入死循环,即循环打印整个队列,截图如下:

 

经分析出现死循环的原因很简单,在 Show(QUEUE *queue) 里的循环条件:

for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE)) ,在上述测试代码下,9个元素入队后,

queue->front=0,queue->rear=9,FOR语句在此条件下即为:for(i=(0+1)%10;i<=9;i=((i+1)%MAXSIZE)) ,当i=9,

执行 printf("queue->elems [ %d ] =%d\n ",9,queue->elems [ 9 ] ); 之后,i=(9+1)%10,即 i 又变为 0 ,又重新符合 i<=9 的循环条件,如此反复,陷入死循环。

该程序还有个漏洞。我们来做第二个测试代码:

 

main()
{
 /*Initialize a queue and show it.*/

 QUEUE queue;
 Initialize(&queue);
 
 /*Add elems int a queue and show it.*/
 InQueue(&queue,1);
 InQueue(&queue,2);
 InQueue(&queue,3);
 InQueue(&queue,4);
 InQueue(&queue,5);
 InQueue(&queue,6);
 InQueue(&queue,7);
 InQueue(&queue,8);
 InQueue(&queue,9);
 
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 OutQueue(&queue);
 InQueue(&queue,11);
 InQueue(&queue,10);
 Show(&queue);
 
}

 这段代码运行后,发现它根本没有显示整个队列。运行结果截图如下:

 

分析原因:在上述测试代码下,先是9个元素入队,5个元素出队,又2个元素入队,即 queue->front=5 , queue->rear=1 。在此条件下,for(i=((queue->front+1)%MAXSIZE);i<=queue->rear;i=((i+1)%MAXSIZE))   就变成

for(i=(5+1)%10;i<=1;i=((i+1)%MAXSIZE)) ,从一开始就不符合 i<=1 的条件 ,故循环体没有执行。

故,Show(QUEUE *queue) 函数代码有严重漏洞。发现此问题后,本想偷懒,写封邮件给作者,希望他能修改代码,可能是作者又忙着出别的什么书了,没功夫陪我们“小孩”玩。“被逼无奈”之下,自己重写Show(QUEUE *queue) 函数,只要能摆平以上两个Bug就成。

经分析发现,若我们将循环队列看成一个首尾相连的火车轨道,无论是入队还是出队, queue->front 和 queue->rear 都是顺时针方向运动的,故新的 Show 函数如下:

 

int Show(QUEUE *queue)
{
  int i=(queue->front+1)%MAXSIZE;
  if (queue->front==queue->rear)
   {
     printf("Queue is Empty!\n");
     return 0;
   }

 while(i!=queue->rear)
 {
   printf("queue->elems [ %d ] =%d\n",i,queue->elems [ i ] );
   i=(i+1)%MAXSIZE;
 }
   if(i==queue->rear)/*如果不加这句,此程序将有一个Bug,即队尾元素(最后一个元素)打印不出来*/
   {
    printf("queue->elems [ %d ] =%d\n",i,queue->elems [ i ] );
   }
   printf("\nQueue head is %d\n",queue->front);
   printf("Queue rear is %d\n",queue->rear);
}

 经初步测试,上文所述的两个BUG不会出现。但感觉代码写的有点窝囊,由于本人水平与学识的限制,不排除会被大本营的高人找出Bug,希望大家能写出更好的代码,供大家交流学习。

 

转自:http://student.csdn.net/space.php?uid=50992&do=blog&id=20368

 

 

 

 

 

分享到:
评论

相关推荐

    wheel-0.13.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码ST反弹限位器焊机14

    三菱PLC例程源码ST反弹限位器焊机14本资源系百度网盘分享地址

    asp代码asp教师信息管理系统(源代码+论文)

    asp代码asp教师信息管理系统(源代码+论文)本资源系百度网盘分享地址

    tensorflow_serving_api_gpu-2.3.3-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_serving_api-2.0.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_model_remediation-0.1.6.tar.gz

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码PID程序

    三菱PLC例程源码PID程序本资源系百度网盘分享地址

    tensorflow_recommenders-0.5.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于ssm珠宝首饰交易平台.zip

    基于ssm珠宝首饰交易平台.zip

    tensorflow_protobuf-2.11.0-py3-none-any.whl

    算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于ssm的小区物业管理系统.zip

    基于ssm的小区物业管理系统.zip

    tensorflow_serving_api_gpu-2.2.0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    基于javaweb+ssm的企业人事信息管理系统.zip

    基于javaweb+ssm的企业人事信息管理系统.zip

    asp代码asp旅游信息管理系统(源代码+论文)

    asp代码asp旅游信息管理系统(源代码+论文)本资源系百度网盘分享地址

    WeRoBot-1.7.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    三菱PLC例程源码步进对标定位

    三菱PLC例程源码步进对标定位本资源系百度网盘分享地址

    (完整word版)单片机_温度控制系统_外文翻译_外文文献_英文文献_中英翻译.doc

    (完整word版)单片机_温度控制系统_外文翻译_外文文献_英文文献_中英翻译.doc

    tensorflow_transform-0.1.8-py2-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    asp代码ASP基于Web的C语言教学系统的研究与实现(源代码+论文)

    asp代码ASP基于Web的C语言教学系统的研究与实现(源代码+论文)本资源系百度网盘分享地址

    三菱PLC例程源码String-32bit-Logging-Mitsubishi-cn

    三菱PLC例程源码String_32bit_Logging_Mitsubishi_cn本资源系百度网盘分享地址

Global site tag (gtag.js) - Google Analytics