数据结构6.ppt

《数据结构6.ppt》由会员分享，可在线阅读，更多相关《数据结构6.ppt（64页珍藏版）》请在第壹文秘上搜索。

1、3/2/202311.The Abstract Data Type2.Formula-Based Representation3.Linked Representation4.ApplicationsChapter6 队列(Queues)3/2/202321.队列的实现2.队列的应用本章重点3/2/202331.定义 是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被称为队首(front)。2.队列是一个先进先出（ first-in-first-out, FIFO）的线性表。队列(Queues)3/2/20234队列3/2/202

2、35队列3/2/20236公式化描述 公式6-1location (i)=i-13/2/202371.front:02.rear:最后一个元素的位置3.空队列:rear=-1性质3/2/20238公式化描述 公式6-2location(i)=location(1)+ i-13/2/202391.front:location(1)2.rear:location(最后一个元素)3.空队列:rearfront性质3/2/202310插入操作location(i)=location(1)+ i-13/2/202311公式化描述 公式6-3location(i)=(location(1)+i-1)% M

3、axsize3/2/2023121.front:指向队列首元素的下一个位置(逆时针方向)2.rear:队列尾3.空队列:front = rear4.队列满?性质3/2/202313队列满?3/2/202314循环队列的进队和出队3/2/202315公式化类Queuetemplateclass Queue / FIFO 对象public:Queue(int MaxQueueSize = 10);Queue() delete queue;bool IsEmpty() const return front = rear;bool IsFull() const return (rear + 1) %

4、MaxSize = front) ? 1 : 0);T First() const; /返回队首元素T Last() const; / 返回队尾元素Queue& Add(const T& x);Queue& Delete(T& x);3/2/202316公式化类Queueprivate:int front; /与第一个元素在反时针方向上相差一个位置int rear; / 指向最后一个元素int MaxSize; / 队列数组的大小T *queue; / 数组 ;3/2/202317构造函数templateQueue:Queue(int MaxQueueSize)/ 创建一个容量为MaxQueu

5、eSize的空队列MaxSize = MaxQueueSize + 1;queue = new TMaxSize;front = rear = 0;3/2/202318公式化类QueuetemplateT Queue:First() const/ 返回队列的第一个元素/ 如果队列为空，则引发异常OutOfBoundsif (IsEmpty() throw OutOfBounds();return queue(front + 1) % MaxSize;3/2/202319公式化类QueuetemplateT Queue:Last() const/ 返回队列的最后一个元素/ 如果队列为空，则引发异

6、常OutOfBoundsif (IsEmpty() throw OutOfBounds();return queuerear;3/2/202320公式化类QueuetemplateQueue& Queue:Add(const T& x)/ 把x 添加到队列的尾部/ 如果队列满，则引发异常NoMemif (IsFull() throw NoMem();rear = (rear + 1) % MaxSize;queuerear = x;return *this;3/2/202321公式化类QueuetemplateQueue& Queue:Delete(T& x)/ 删除第一个元素，并将其送入x/

7、 如果队列为空，则引发异常OutOfBoundsif (IsEmpty() throw OutOfBounds();front = (front + 1) % MaxSize;x = queuefront;return *this;3/2/202322链表描述n可以使用单向链表来实现一个队列。n思考：链表中使用几个指针？3/2/202323链表描述n需要两个变量front和rear来分别跟踪队列的两端。3/2/202324链表描述的两种方式n思考：性能相同吗？3/2/202325链表插入3/2/202326链表删除3/2/202327链表队列的类定义templateclass LinkedQu

8、eue / FIFO对象p u b l i c :LinkedQueue() front = rear = 0; / 构造函数LinkedQueue(); / 析构函数bool IsEmpty() constreturn (front) ? false : true);bool IsFull() const;T First() const; / 返回第一个元素T Last() const; / 返回最后一个元素LinkedQueue& Add(const T& x);LinkedQueue& Delete(T& x);private:Node *front; / 指向第一个节点Node *re

9、ar; /指向最后一个节点 ;3/2/202328删除所有节点templateLinkedQueue: LinkedQueue( )/ 队列析构函数，删除所有节点Node *next;while (front) next = front-link;delete front;front = next;3/2/202329判断队列是否已满templatebool LinkedQueue:IsFull() const/ 判断队列是否已满Node *p;try p = new Node;delete p;return false;catch (NoMem) return true;3/2/202330

10、返回队列的第一个元素templateT LinkedQueue:First() const/ 返回队列的第一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();return front-data;3/2/202331返回队列的最后一个元素templateT LinkedQueue:Last() const/ 返回队列的最后一个元素/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();return rear-data;3/

11、2/202332把x 添加到队列的尾部templateLinkedQueue& LinkedQueue:Add(const T& x)/ 把x 添加到队列的尾部/ 不捕获可能由n e w引发的NoMem 异常/ 为新元素创建链表节点Node *p = new Node;p-data = x;p-link = 0;if (front) rear-link = p; /队列不为空else front = p; / 队列为空rear = p;return *this;3/2/202333删除第一个元素templateLinkedQueue& LinkedQueue:Delete(T& x)/ 删除第

12、一个元素，并将其放入x/ 如果队列为空，则引发异常O u t O f B o u n d sif (IsEmpty() throw OutOfBounds();/ /保存第一个节点中的元素x = front-data;/ 删除第一个节点Node *p = front;front = front-link;delete p;return *this;3/2/2023341.火车车厢重排(Railroad Car Rearrangement)2.电路布线(Wire Routing) 3.工 厂 仿 真 ( M a c h i n e S h o p Simulation)应用3/2/202335n

13、缓冲铁轨运作方式？n缓冲铁轨个数？(Hk作为从入轨道出轨的通道)火车车厢重排问题3/2/202336n仅允许以下移动：1.入轨右端-缓冲铁轨2.入轨右端-出轨3.缓冲铁轨右端-出轨火车车厢重排-约束3/2/202337n从前至后依次检查入轨上的所有车厢。n如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。n重排演示。火车车厢重排方案3/2/202338bool Railroad(int p, int n, int k)/ k 个缓冲铁轨，车厢初始排序为p 1 : n / 如果重排成功，返回tr

14、ue，否则返回false/ 如果内存不足，则引发异常NoMem 。/创建与缓冲铁轨对应的堆栈LinkedQueue *H;H = new LinkedQueue k;k-;int NowOut = 1; /下一次要输出的车厢int minH = n+l; /缓冲铁轨中编号最小的车厢int minQ; /minH号车厢对应的缓冲铁轨火车车厢重排程序-队列3/2/202339/车厢重排for(int i = 1; i = n; i+)if (pi = NowOut) / 直接输出tcout“将车厢”pi“从入轨移至出轨endl;NowOut+ ;/从缓冲铁轨中输出while (minH = Now

15、Out) Output(minH, minQ, H, k, n);NowOut+ ;else / 将pi 送入某个缓冲铁轨if (!Hold(pi, minH, minQ, H, k)return false; return true; 火车车厢重排程序3/2/202340void Output(int& minH, int& minQ, LinkedQueue H, int k, int n) / /从缓冲铁轨移动到出轨，并修改minH 和minQ .int c; / 车厢编号/ 从队列minQ 中删除编号最小的车厢minHHminQ.Delete(c) ;cout Move car min

16、H from holding track minQ to output endl;/ 通过检查所有队列的首部，寻找新的minH和minQminH = n + 2;for (int i = 1; i = k; i+)if (!Hi.IsEmpty() & c = Hi.First() minH) minH = c;minQ = i;Output 函数3/2/202341bool Hold(int c, int& minH, int &minQ, LinkedQueue H, int k)/把车厢c 移动到缓冲铁轨中/ 如果没有可用的缓冲铁轨，则返回false，否则返回true/ 为车厢c 寻找最优的缓冲铁轨/ 初始化int BestTrack = 0, / 目前最优的铁轨 BestLast = 0, / BestTrack 中最后一节车厢 x; / 车厢编号Hold函数3/2/202342/ 扫描缓冲铁轨for (int i = 1; i x & x BestLast) / 铁轨i 尾部的车厢编号较大BestLast = x;BestTrack = i;else / 铁轨i 为空if (