《数据结构6.ppt》由会员分享，可在线阅读，更多相关《数据结构6.ppt（64页珍藏版）》请在课桌文档上搜索。
1、3/2/2023,1,The Abstract Data TypeFormula-Based RepresentationLinked RepresentationApplications,Chapter6 队列(Queues),3/2/2023,2,队列的实现队列的应用,本章重点,3/2/2023,3,定义 是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被称为队首(front)。队列是一个先进先出（first-in-first-out,FIFO）的线性表。,队列(Queues),3/2/2023,4,队列,3/2/2023,5
2、,队列,3/2/2023,6,公式化描述 公式6-1,location(i)=i-1,3/2/2023,7,front:0rear:最后一个元素的位置空队列:rear=-1,性质,3/2/2023,8,公式化描述 公式6-2,location(i)=location(1)+i-1,3/2/2023,9,front:location(1)rear:location(最后一个元素)空队列:rearfront,性质,3/2/2023,10,插入操作,location(i)=location(1)+i-1,3/2/2023,11,公式化描述 公式6-3,location(i)=(location(1)
3、+i-1)%Maxsize,3/2/2023,12,front:指向队列首元素的下一个位置(逆时针方向)rear:队列尾空队列:front=rear队列满?,性质,3/2/2023,13,队列满?,3/2/2023,14,循环队列的进队和出队,3/2/2023,15,公式化类Queue,templateclass Queue/FIFO 对象public:Queue(int MaxQueueSize=10);Queue()delete queue;bool IsEmpty()const return front=rear;bool IsFull()const return(rear+1)%Max
4、Size=front)?1:0);T First()const;/返回队首元素T Last()const;/返回队尾元素Queue,3/2/2023,16,公式化类Queue,private:int front;/与第一个元素在反时针方向上相差一个位置int rear;/指向最后一个元素int MaxSize;/队列数组的大小T*queue;/数组;,3/2/2023,17,构造函数,templateQueue:Queue(int MaxQueueSize)/创建一个容量为MaxQueueSize的空队列MaxSize=MaxQueueSize+1;queue=new TMaxSize;fro
5、nt=rear=0;,3/2/2023,18,公式化类Queue,templateT Queue:First()const/返回队列的第一个元素/如果队列为空，则引发异常OutOfBoundsif(IsEmpty()throw OutOfBounds();return queue(front+1)%MaxSize;,3/2/2023,19,公式化类Queue,templateT Queue:Last()const/返回队列的最后一个元素/如果队列为空，则引发异常OutOfBoundsif(IsEmpty()throw OutOfBounds();return queuerear;,3/2/20
6、23,20,公式化类Queue,templateQueue,3/2/2023,21,公式化类Queue,templateQueue,3/2/2023,22,链表描述,可以使用单向链表来实现一个队列。思考：链表中使用几个指针？,3/2/2023,23,链表描述,需要两个变量front和rear来分别跟踪队列的两端。,3/2/2023,24,链表描述的两种方式,思考：性能相同吗？,3/2/2023,25,链表插入,3/2/2023,26,链表删除,3/2/2023,27,链表队列的类定义,templateclass LinkedQueue/FIFO对象p u b l i c:LinkedQueue
7、()front=rear=0;/构造函数LinkedQueue();/析构函数bool IsEmpty()constreturn(front)?false:true);bool IsFull()const;T First()const;/返回第一个元素T Last()const;/返回最后一个元素LinkedQueue,3/2/2023,28,删除所有节点,templateLinkedQueue:LinkedQueue()/队列析构函数，删除所有节点Node*next;while(front)next=front-link;delete front;front=next;,3/2/2023,2
8、9,判断队列是否已满,templatebool LinkedQueue:IsFull()const/判断队列是否已满Node*p;try p=new Node;delete p;return false;catch(NoMem)return true;,3/2/2023,30,返回队列的第一个元素,templateT LinkedQueue:First()const/返回队列的第一个元素/如果队列为空，则引发异常O u t O f B o u n d sif(IsEmpty()throw OutOfBounds();return front-data;,3/2/2023,31,返回队列的最后一
9、个元素,templateT LinkedQueue:Last()const/返回队列的最后一个元素/如果队列为空，则引发异常O u t O f B o u n d sif(IsEmpty()throw OutOfBounds();return rear-data;,3/2/2023,32,把x 添加到队列的尾部,templateLinkedQueue,3/2/2023,33,删除第一个元素,templateLinkedQueue,3/2/2023,34,火车车厢重排(Railroad Car Rearrangement)电路布线(Wire Routing)工厂仿真(Machine Shop S
10、imulation),应用,3/2/2023,35,缓冲铁轨运作方式？缓冲铁轨个数？(Hk作为从入轨道出轨的通道),火车车厢重排问题,3/2/2023,36,仅允许以下移动：入轨右端-缓冲铁轨入轨右端-出轨缓冲铁轨右端-出轨,火车车厢重排-约束,3/2/2023,37,从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。重排演示。,火车车厢重排方案,3/2/2023,38,bool Railroad(int p,int n,int k)/k 个缓冲铁轨，车厢初始
11、排序为p 1:n/如果重排成功，返回true，否则返回false/如果内存不足，则引发异常NoMem。/创建与缓冲铁轨对应的堆栈LinkedQueue*H;H=new LinkedQueue k;k-;int NowOut=1;/下一次要输出的车厢int minH=n+l;/缓冲铁轨中编号最小的车厢int minQ;/minH号车厢对应的缓冲铁轨,火车车厢重排程序-队列,3/2/2023,39,/车厢重排for(int i=1;i=n;i+)if(pi=NowOut)/直接输出tcout“将车厢”pi“从入轨移至出轨endl;NowOut+;/从缓冲铁轨中输出while(minH=NowOut
12、)Output(minH,minQ,H,k,n);NowOut+;else/将pi 送入某个缓冲铁轨if(!Hold(pi,minH,minQ,H,k)return false;return true;,火车车厢重排程序,3/2/2023,40,void Output(int,Output 函数,3/2/2023,41,bool Hold(int c,int/车厢编号,Hold函数,3/2/2023,42,/扫描缓冲铁轨for(int i=1;i x,Hold函数,3/2/2023,43,if(!BestTrack)return false;/没有可用的铁轨/把c移动到最优铁轨HBestTra
13、ck.Add(c);cout Move car c from input to holding track BestTrack endl;/如果有必要，则修改minH和minQif(c minH)minH=c;minQ=BestTrack;return true;复杂性？,Hold函数,3/2/2023,44,在迷宫中寻找最短路径的问题也存在于其他许多领域。例如，在解决电路布线问题时，一种很常用的方法就是在布线区域叠上一个网格，该网格把布线区域划分成nm个方格，就像迷宫一样。从一个方格a的中心点连接到另一个方格b的中心点时，转弯处必须采用直角。如果已经有某条线路经过一个方格，则封锁该方格。我们
14、希望使用a和b之间的最短路径来作为布线的路径，以便减少信号的延迟。,迷宫最短路径问题扩展,3/2/2023,45,电路布线,3/2/2023,46,为了找到网格中位置a和b之间的最短路径，先从位置a 开始搜索，把a 可到达的相邻方格都标记为1(表示与a 相距为1)，然后把标号为1的方格可到达的相邻方格都标记为2(表示与a相距为2)，继续进行下去，直到到达b或者找不到可到达的相邻方格为止。,方案,3/2/2023,47,方案演示,3/2/2023,48,为了得到a与b之间的最短路径，从b开始，首先移动到一个比b 的编号小的相邻位置上。一定存在这样的相邻位置，因为任一个方格上的标号与它相邻方格上的
15、标号都至少相差1。接下来，从当前位置开始，继续移动到比当前标号小1的相邻位置上。重复这个过程，直至到达a为止。,输出方案,3/2/2023,49,bool FindPath(Position start,Position finish,int/左和右,寻找电路布线最短路径,3/2/2023,50,/初始化offsetPosition offset 4;offset0.row=0;offset0.col=1;/右offset1.row=1;offset1.col=0;/下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上i
16、nt NumOfNbrs=4;/一个网格位置的相邻位置数Position here,nbr;here.row=start.row;here.col=start.col;gridstart.rowstart.col=2;/封锁,寻找电路布线最短路径,3/2/2023,51,/标记可到达的网格位置LinkedQueue Q;do/标记相邻位置for(int i=0;i NumOfNbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=0)/新位置gridnbr.rownbr.co
17、l=gridhere.rowhere.col+1;if(nbr.row=finish.row)/if 结束/for 结束,寻找电路布线最短路径,3/2/2023,52,/已到达finish吗?if(nbr.row=finish.row),寻找电路布线最短路径,3/2/2023,53,/构造路径PathLen=gridfinish.rowfinish.col-2;path=new Position PathLen;here=finish;/回溯至finishfor(int j=PathLen-1;j=0;j-)pathj=here;/寻找前一个位置for(int i=0;i NumOfNbrs;
18、i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.row nbr.col=j+2)break;here=nbr;/移动到前一个位置 return true;,寻找电路布线最短路径,3/2/2023,54,一间工厂由m台机器组成。工厂中所执行的每项任务都由若干道工序构成，一台机器用来完成一道工序，不同的机器完成不同的工序。一旦一台机器开始处理一道工序，它会连续不断地进行处理，直到该工序被完成为止。,工厂仿真,3/2/2023,55,对于一项任务中的每道工序来说，都有两个属性：一是工时（即完成该道工序需要
19、多长时间），一是执行该工序的机器。一项任务中的各道工序必须按照一定的次序来执行。一项任务的执行是从处理第一道工序的机器开始的，当第一道工序完成后，任务转至处理第二道工序的机器，依此进行下去，直到最后一道工序完成为止。当一项任务到达一台机器时，若机器正忙，则该任务将不得不等待。,工序属性,3/2/2023,56,在工厂中每台机器都可以有如下三种状态：活动、空闲和转换。在活动状态，机器正在处理一道工序。在空闲状态机器无事可做。在转换状态，机器刚刚完成一道工序，并在为一项新任务的执行做准备，比如机器操作员可能需要清理机器并稍作休息等。每台机器在转换状态期间所花费的时间可能各不相同。,机器状态,3/2
20、/2023,57,当一台机器可以处理一项新任务时，它可能需要从各个等待者中挑选一项任务来执行。在这里，每台机器都按照FIFO的方式来处理等待者，因此每台机器旁的等待者构成了一个FIFO队列。在其他类型的工厂中，可以为每项任务指定不同的优先权，当机器变成空闲时，从等待者中首先选择具有最高优先权的任务来执行。,任务队列,3/2/2023,58,为了让顾客满意，希望尽量减少任务在机器队列中的等待时间。如果能够知道每项任务所花费的等待时间是多少，并且知道哪些机器所导致的等待时间最多，就可以据此来改进和提高工厂的效能。,目标,3/2/2023,59,在对工厂进行仿真时，采用一个模拟时钟来进行仿真计时，每
21、当一道工序完成或一项新任务到达工厂时，模拟时钟就推进一个单位。在完成老任务时，将产生新的任务。每当一道工序完成或一项新任务到达工厂时，称发生了一个事件(event)。另外，还存在一个启动事件(start event)，用来启动仿真过程。,工厂仿真实现,3/2/2023,60,三台机器M1、M2和M3的转换状态所花费的时间分别为2、0和1。因此，当一道工序完成时，机器M1在启动下一道工序之前必须等待2个时间单元，机器M2可以立即启动下一道工序，机器M3必须等待1个时间单元。,示例,3/2/2023,61,每道工序用形如(machine，time)的值对来描述。各项任务的长度分别为7，6，8和4。,四项任务的特征,3/2/2023,62,仿真,3/2/2023,63,2号和4号任务在第12时刻完成，1号任务在第15时刻完成，3号任务在第19时刻完成。由于2号任务的长度为6，而它的完成时刻为12，所以2号任务在队列中所花费的等待时间为12-6=6个时间单元。类似地，4号任务在队列中的等待时间为12-4=8个时间单元，1号和3号任务的等待时间分别为8和11个时间单元。总的等待时间为33个时间单元。,结果,3/2/2023,64,队列的逻辑结构和实现方式火车车厢重排电路布线工厂仿真,第六章 总结,
