数据结构算法与应用-c++语言描述06

《数据结构算法与应用-c++语言描述06》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、下载第6章队列像堆栈一样，队列也是一种特殊的线性表。队列的插入和删除操作分别在线性表的两端进行，因此，队列是一个先进先出（first-in-first-out,FIFO）的线性表。尽管可以很容易地从线性表类LinearList（见程序3-1）和链表类Chain（见程序3-8）中派生出队列类，但在本章中并没有这样做。出于对执行效率的考虑，我们把队列设计成一个基类，分别采用了公式化描述和链表描述。在本章的应用部分，给出了四个使用队列的应用。第一个应用是关于5.5.3节所介绍的火车车厢重排问题。在本章中对这个问题

2、做了修改，要求缓冲铁轨按FIFO方式而不是LIFO方式工作；第二个应用是关于寻找两个给定点之间最短路径的问题，这是一个经典的问题。可以把这个应用看成是5.5.6节迷宫问题的一种变化，即寻找从迷宫入口到迷宫出口的最短路径。5.5.6节中的代码并不能保证得到一条最短的路径，它只能保证如果存在一条从入口到出口的路径，则一定能找到这样一条路径（没有限定长度）；第三个应用选自计算机视觉领域，主要用于识别图像中的图元；最后一个应用是一个工厂仿真程序。工厂内有若干台机器，每台机器能够执行一道不同的工序。每一项任务都由一系

3、列工序组成。我们给出了一个仿真程序，它能够仿真工厂中的任务流。该程序能够确定每项任务所花费的总的等待时间以及每台机器所产生的总的等待时间，可以根据这些信息来改进工厂的设计。为了获得较高的执行效率，本章中每个应用都采用了队列数据结构。在后续章节中还会介绍其他几种队列应用。6.1抽象数据类型定义[队列]队列（quene）是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被成为队首(front)。一个三元素的队列如图6-1a所示，从中删除第一个元素A之

4、后将得到图6-1b所示的队列。如果要向图6-1b的队列中添加一个元素D，必须把它放在元素C的后面。添加D以后所得到的结果如图6-1c所示。a)b)c)图6-1队列举例所以，队列是一个先进先出（FIFO）的线性表，而堆栈是一个先进后出（LIFO）的线性表。队列的抽象数据类型描述见ADT6-1。190第二部分数据结构下载ADT6-1队列的抽象数据类型描述抽象数据类型Queue{实例有序线性表，一端称为front，另一端称为rear；操作Create():创建一个空的队列；IsEmpty():如果队列为空，则返回

5、true，否则返回false；IsFull():如果队列满，则返回true；否则返回false；First():返回队列的第一个元素；Last():返回队列的最后一个元素；Add(x):向队列中添加元素x；Delete(x):删除队首元素，并送入x;}6.2公式化描述假定采用公式（6-1）来描述一个队列。location(i)=i-1（6-1）这个公式在公式化描述的堆栈中工作得很好。如果使用公式（6-1）把数组queue[MaxSize]描述成一个队列，那么第一个元素为queue[0]，第二个元素为queu

6、e[1]，⋯。front总是为0，rear始终是最后一个元素的位置，队列的长度为rear+1。对于一个空队列，有rear=－1。使用公式（6-1），图6-1中的队列可以表示成图6-2的形式。a)b)c)图6-2使用公式（6-1）描述图6-1中的队列向队列中添加一个元素时，需要把rear增1，并把新元素放入queue[rear]。这意味着一次添加操作所需要的时间为O(1)。删除一个元素时，把位置1至位置n的元素分别左移一个位置，因此删除一个元素所花费的时间为(n)，其中n为删除完成之后队列中的元素数。如此看来

7、，公式（6-1）应用于堆栈，可使堆栈的插入和删除操作均耗时(1)，而应用于队列，则使队列的删除操作所需要的时间达到(n)。如果采用公式（6-2），就可以使队列的删除操作所需要的时间减小至(1)。location(i)=location(1)+i-1（6-2）从队列中删除一个元素时，公式（6-2）不要求把所有的元素都左移一个位置，只需简单地把location(1)增加1即可。图6-3给出了在使用公式（6-2）时，图6-1中各队列的相应描述。注意，在使用公式（6-2）时，front=location(1)，re

8、ar=location(最后一个元素)，一个空队列第6章队列191下载具有性质rear0时（表明队列未满），为了能够继续向队列尾部添加元素，必须将所有元素平移到队列的左端（如图6-4所示），以便在队列的右端留出空间。对于使用公式（6