(精品)【10】Chapter6队列-循环队列 (2).ppt

《(精品)【10】Chapter6队列-循环队列 (2).ppt》由会员分享，可在线阅读，更多相关《(精品)【10】Chapter6队列-循环队列 (2).ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法数据结构与算法20092009年秋季年秋季年秋季年秋季授课教师：张剑波授课教师：张剑波授课教师：张剑波授课教师：张剑波 方方方方 芳芳芳芳授课班级：授课班级：授课班级：授课班级：111081-4111081-4班班班班 115081-2115081-2班班班班Chapter6 Chapter6 队列（队列（QueueQueue）本章教学内容本章教学内容v 6.1 6.1 队列结构特性队列结构特性队列结构特性队列结构特性v 6.2 6.2 抽象数据类型抽象数据类型抽象数据类型抽象数据类型v 6.3 6.3 公式化描述（顺序队列）公式化描述（顺序队列）公式化描述（顺序队列）公式化描述

2、（顺序队列）v 6.4 6.4 链表描述（链队列）链表描述（链队列）链表描述（链队列）链表描述（链队列）v 6.5 6.5 应用应用应用应用 1.1.火车车厢重排火车车厢重排火车车厢重排火车车厢重排6.1 队列结构特性队列结构特性2 2、几个相关的概念、几个相关的概念、几个相关的概念、几个相关的概念1 1、定义、定义、定义、定义 队列是一种特殊的线性表，是一种只允许在表的队列是一种特殊的线性表，是一种只允许在表的队列是一种特殊的线性表，是一种只允许在表的队列是一种特殊的线性表，是一种只允许在表的一端进一端进一端进一端进行插入行插入行插入行插入操作，而在操作，而在操作，而在操作，而在另一端进行删

3、除另一端进行删除另一端进行删除另一端进行删除操作的线性表。操作的线性表。操作的线性表。操作的线性表。a a1 1 a a2 2 a a3 3 a an n入队列入队列入队列入队列出队列出队列出队列出队列队头（队头（队头（队头（frontfront）队尾（队尾（队尾（队尾（rearrear）3 3、重要特征、重要特征、重要特征、重要特征 每次每次每次每次进队列进队列进队列进队列的元素都放在原队列的元素都放在原队列的元素都放在原队列的元素都放在原队列队尾队尾队尾队尾之后而成为新的队尾之后而成为新的队尾之后而成为新的队尾之后而成为新的队尾元素；元素；元素；元素；每次每次每次每次出队列出队列出队列出队

4、列的数据元素都是的数据元素都是的数据元素都是的数据元素都是原队头元素原队头元素原队头元素原队头元素；先入队列的元素先出队列，后入队列的元素后出队列。先入队列的元素先出队列，后入队列的元素后出队列。先入队列的元素先出队列，后入队列的元素后出队列。先入队列的元素先出队列，后入队列的元素后出队列。队列是一个队列是一个队列是一个队列是一个先进先出先进先出先进先出先进先出的线性表（的线性表（的线性表（的线性表（First In First OutFirst In First Out，FIFOFIFO）。）。）。）。如：（如：（如：（如：（1 1）日常生活中的排队；）日常生活中的排队；）日常生活中的排队；

5、）日常生活中的排队；（2 2）操作系统中的作业队列。）操作系统中的作业队列。）操作系统中的作业队列。）操作系统中的作业队列。C C课堂练习课堂练习u3 3、设设设设栈栈栈栈S S和和和和队队队队列列列列QQ的的的的初初初初始始始始状状状状态态态态为为为为空空空空，元元元元素素素素e1e1，e2e2，e3e3，e4e4，e5e5和和和和e6e6依依依依次次次次通通通通过过过过栈栈栈栈S S，一一一一个个个个元元元元素素素素出出出出栈栈栈栈后后后后即即即即进进进进队队队队列列列列QQ，若若若若6 6个个个个元元元元素素素素出出出出队队队队的的的的序序序序列列列列是是是是e2e2，e4e4，e3e3

6、，e6e6，e5e5，e1e1，则栈，则栈，则栈，则栈S S的容量至少应该是的容量至少应该是的容量至少应该是的容量至少应该是 。A A、6 B6 B、5 C5 C、3 D3 D、2 26.2 队列的抽象数据类型描述队列的抽象数据类型描述ADT QueueADT Queue 实例实例实例实例 有序线性表，一端称为有序线性表，一端称为有序线性表，一端称为有序线性表，一端称为frontfront，一端称为，一端称为，一端称为，一端称为rearrear操作操作操作操作 Create();Create();/创建一个空的队列创建一个空的队列创建一个空的队列创建一个空的队列 IsEmptyIsEmpty(

7、);();/如果队列为空，返回如果队列为空，返回如果队列为空，返回如果队列为空，返回true,true,否则返回否则返回否则返回否则返回falsefalse IsFullIsFull();();/如果队列满，返回如果队列满，返回如果队列满，返回如果队列满，返回true,true,否则返回否则返回否则返回否则返回falsefalse First();First();/返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素 Last();Last();/返回队列中的最后一个元素返回队列中的最后一个元素返回队列中的最后一个元素返回队列中的最后一个元素 Add(xAd

8、d(x););/向队列添加元素向队列添加元素向队列添加元素向队列添加元素x x Delete(xDelete(x););/删除队首元素，并将它传递给删除队首元素，并将它传递给删除队首元素，并将它传递给删除队首元素，并将它传递给x x 队列的两种描述形式队列的两种描述形式vv队列的物理存储可以用：队列的物理存储可以用：队列的物理存储可以用：队列的物理存储可以用：顺序顺序顺序顺序存储结构存储结构存储结构存储结构 链式链式链式链式存储结构存储结构存储结构存储结构 a a1 1，a a2 2，a a3 3，a an n出出出出队列队列队列队列入队列入队列入队列入队列队队队队头头头头队队队队尾尾尾尾da

9、ta linkdata linkfrontfrontrearrear 队列的顺序存储结构，简称队列的顺序存储结构，简称队列的顺序存储结构，简称队列的顺序存储结构，简称顺序队列顺序队列顺序队列顺序队列；顺序队列可用一个一维数组顺序队列可用一个一维数组顺序队列可用一个一维数组顺序队列可用一个一维数组queueMaxSizequeueMaxSize 来存储，其中来存储，其中来存储，其中来存储，其中MaxSizeMaxSize是队列能存放的最大元素个数；是队列能存放的最大元素个数；是队列能存放的最大元素个数；是队列能存放的最大元素个数；为了指示队头和队尾，需要设立一个队头指示器和一个队为了指示队头和队

10、尾，需要设立一个队头指示器和一个队为了指示队头和队尾，需要设立一个队头指示器和一个队为了指示队头和队尾，需要设立一个队头指示器和一个队尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，约定：约定：约定：约定：n n frontfront（头指针）：指向实际（头指针）：指向实际（头指针）：指向实际（头指针）：指向实际队头元素的前一个位置队头元素的前一个位置队头元素的前一个位置队头元素的前一个位置；n n rearrear（尾

11、指针）：指向实际（尾指针）：指向实际（尾指针）：指向实际（尾指针）：指向实际队尾元素队尾元素队尾元素队尾元素所在的位置。所在的位置。所在的位置。所在的位置。6.3 队列的公式化描述（顺序存储结构）队列的公式化描述（顺序存储结构）（1 1）初始化初始化初始化初始化（2 2）入队列（插入）入队列（插入）入队列（插入）入队列（插入）建立一个空队列，即队头指针建立一个空队列，即队头指针建立一个空队列，即队头指针建立一个空队列，即队头指针front=-1front=-1，队尾指针，队尾指针，队尾指针，队尾指针rear=-1rear=-1。当队满时（队满条件：当队满时（队满条件：当队满时（队满条件：当队满

12、时（队满条件：rear=MaxSize-1rear=MaxSize-1），产生溢出；），产生溢出；），产生溢出；），产生溢出；当队不满时，尾指针加当队不满时，尾指针加当队不满时，尾指针加当队不满时，尾指针加1 1（rear=rear+1rear=rear+1），然后把待，然后把待，然后把待，然后把待插元素插元素插元素插元素x x送入尾指针所指数组分量。送入尾指针所指数组分量。送入尾指针所指数组分量。送入尾指针所指数组分量。1、顺序队列的基本操作、顺序队列的基本操作（3 3）出队列（删除）出队列（删除）出队列（删除）出队列（删除）当队不空时（队空条件：当队不空时（队空条件：当队不空时（队空条件：

13、当队不空时（队空条件：front=rearfront=rear），队头指针加），队头指针加），队头指针加），队头指针加1 1（front=front=frontfront+1+1），返回原队头元素，即头指针所指数组，返回原队头元素，即头指针所指数组，返回原队头元素，即头指针所指数组，返回原队头元素，即头指针所指数组分量的值。分量的值。分量的值。分量的值。4 43 32 21 10 04 43 32 2C C1 1B B0 0A A4 43 32 21 10 04 4E E3 3D D2 21 10 0frontfront=rear=rear=-1=-1frontfront=-1=-1队列空队列

14、空队列空队列空A A，B B，C C入队列入队列入队列入队列D D，E E入队列入队列入队列入队列rearrear=2=2rearrear=front=front=2=2A A，B B，C C出队列出队列出队列出队列队队队队 空空空空frontfront=2=2rearrear=4=42、“假溢出假溢出”问题问题 【方法一方法一方法一方法一】按最大可能的进队列操作次数按最大可能的进队列操作次数按最大可能的进队列操作次数按最大可能的进队列操作次数，设置顺序队列，设置顺序队列，设置顺序队列，设置顺序队列的最大元素个数，这种方法很浪费空间，而且有时会因为估的最大元素个数，这种方法很浪费空间，而且有时

15、会因为估的最大元素个数，这种方法很浪费空间，而且有时会因为估的最大元素个数，这种方法很浪费空间，而且有时会因为估计不准而出错；计不准而出错；计不准而出错；计不准而出错；【方法二方法二方法二方法二】修改出队列算法修改出队列算法修改出队列算法修改出队列算法，设每次出队列后，都把队列，设每次出队列后，都把队列，设每次出队列后，都把队列，设每次出队列后，都把队列中剩余数据元素向队头方向移用一个位置，时间复杂度为中剩余数据元素向队头方向移用一个位置，时间复杂度为中剩余数据元素向队头方向移用一个位置，时间复杂度为中剩余数据元素向队头方向移用一个位置，时间复杂度为O(nO(n)，浪费了时间。，浪费了时间。，

16、浪费了时间。，浪费了时间。【方法三方法三方法三方法三】修改入队列算法修改入队列算法修改入队列算法修改入队列算法，当为真溢出时，返回，当为真溢出时，返回，当为真溢出时，返回，当为真溢出时，返回falsefalse；当；当；当；当为假溢出时，则把队列中的数据元素向队头方向移动为假溢出时，则把队列中的数据元素向队头方向移动为假溢出时，则把队列中的数据元素向队头方向移动为假溢出时，则把队列中的数据元素向队头方向移动front+1front+1个个个个位置，使队头元素位于队列的最前端后再完成新数据元素的入位置，使队头元素位于队列的最前端后再完成新数据元素的入位置，使队头元素位于队列的最前端后再完成新数据

17、元素的入位置，使队头元素位于队列的最前端后再完成新数据元素的入队操作；当为其它情况时，进队列操作算法同前。此算法的时队操作；当为其它情况时，进队列操作算法同前。此算法的时队操作；当为其它情况时，进队列操作算法同前。此算法的时队操作；当为其它情况时，进队列操作算法同前。此算法的时间复杂度也为间复杂度也为间复杂度也为间复杂度也为O(nO(n)。解决解决“假溢出假溢出”的方法的方法 【方法四方法四方法四方法四】将数组的存储区将数组的存储区将数组的存储区将数组的存储区0 0MaxSize-1MaxSize-1看成是一个看成是一个看成是一个看成是一个首尾相接的环形区域首尾相接的环形区域首尾相接的环形区域

18、首尾相接的环形区域 location(i)=(location(1)+i-1)%location(i)=(location(1)+i-1)%MaxSizeMaxSize;3、循环队列、循环队列循环队列的特点循环队列的特点循环队列头、尾指针的特点循环队列头、尾指针的特点循环队列头、尾指针的特点循环队列头、尾指针的特点:头指针头指针头指针头指针frontfront：队列中：队列中：队列中：队列中第一个第一个第一个第一个元素的下一个位置元素的下一个位置元素的下一个位置元素的下一个位置（逆时针方（逆时针方（逆时针方（逆时针方向）；向）；向）；向）；尾指针尾指针尾指针尾指针rearrear：指向队列中：

19、指向队列中：指向队列中：指向队列中最最最最后一个元素后一个元素后一个元素后一个元素。rearrearfrontfront1 10 0J J3 3J J2 2J J1 1MaxSizeMaxSize-1-1初始化：初始化：初始化：初始化：front=rear=0;front=rear=0;（1 1）插入或删除一个元素的实现）插入或删除一个元素的实现）插入或删除一个元素的实现）插入或删除一个元素的实现n n 插入插入插入插入：在队尾进行，：在队尾进行，：在队尾进行，：在队尾进行，尾指针向顺时针方向移动一个位置尾指针向顺时针方向移动一个位置尾指针向顺时针方向移动一个位置尾指针向顺时针方向移动一个位置

20、动态描述：动态描述：动态描述：动态描述：rear=rear+1;rear=rear+1;if(rearif(rear=MaxSize-1)=MaxSize-1)rear=0;rear=0;可利用数学上的可利用数学上的可利用数学上的可利用数学上的“模（）运算模（）运算模（）运算模（）运算”来实现上述过程：来实现上述过程：来实现上述过程：来实现上述过程：rear=(rear+1)%MaxSize;rear=(rear+1)%MaxSize;4、循环队列的操作、循环队列的操作rearrearfrontfront1 10 0J J3 3J J2 2J J1 1MaxSizeMaxSize-1-1n n

21、 删除删除删除删除：在队头进行，头指针向顺时针：在队头进行，头指针向顺时针：在队头进行，头指针向顺时针：在队头进行，头指针向顺时针方向移动一个位置方向移动一个位置方向移动一个位置方向移动一个位置front=(front+1)%MaxSize;front=(front+1)%MaxSize;（3 3）入队列、出队列如何判断队满、队空）入队列、出队列如何判断队满、队空）入队列、出队列如何判断队满、队空）入队列、出队列如何判断队满、队空 采用循环队列，不易区别队空和队满，都为采用循环队列，不易区别队空和队满，都为采用循环队列，不易区别队空和队满，都为采用循环队列，不易区别队空和队满，都为 front

22、=rear;front=rear;此条件用来判断此条件用来判断此条件用来判断此条件用来判断队空队空队空队空。rearrearfrontfront1 10 0J J3 3J J2 2J J1 1MaxSizeMaxSize-1-1n n 队满队满队满队满的判断：的判断：的判断：的判断：把把把把“尾指针加尾指针加尾指针加尾指针加1 1后等于头指针后等于头指针后等于头指针后等于头指针”作为队列满的条件。作为队列满的条件。作为队列满的条件。作为队列满的条件。(rear+1)%MaxSize=front (rear+1)%MaxSize=front 用以上方法判队空、队满时，队列中因留有一个空额而损用以

23、上方法判队空、队满时，队列中因留有一个空额而损用以上方法判队空、队满时，队列中因留有一个空额而损用以上方法判队空、队满时，队列中因留有一个空额而损失了一个空间，所以还可以用另一种方法：失了一个空间，所以还可以用另一种方法：失了一个空间，所以还可以用另一种方法：失了一个空间，所以还可以用另一种方法：设立标志位设立标志位设立标志位设立标志位来区别来区别来区别来区别队空、队满，例如：队空、队满，例如：队空、队满，例如：队空、队满，例如：boolbool IsFullIsFull;循环队列类循环队列类Queue（程序（程序6-1）template class Queue template class

24、Queue public:public:Queue(Queue(intint MaxQueueSizeMaxQueueSize=10);=10);Queue()Queue()delete queue;delete queue;boolbool IsEmptyIsEmpty()const return front=rear;()const return front=rear;boolbool IsFullIsFull()const()const return(rear+1)%MaxSize=front)?1:0;return(rear+1)%MaxSize=front)?1:0;T First(

25、)const;T First()const;/返回队首元素返回队首元素返回队首元素返回队首元素T Last()const;T Last()const;/返回队尾元素返回队尾元素返回队尾元素返回队尾元素Queue&Queue&Add(constAdd(const T&x);T&x);Queue&Queue&Delete(constDelete(const T&x);T&x);private:private:intint front;front;/与第一个元素在反时针方向上相差一个位置与第一个元素在反时针方向上相差一个位置与第一个元素在反时针方向上相差一个位置与第一个元素在反时针方向上相差一个位置

26、intint rear;rear;/指向最后一个元素指向最后一个元素指向最后一个元素指向最后一个元素intint MaxSizeMaxSize;/队列数组的大小队列数组的大小队列数组的大小队列数组的大小T*queue;T*queue;/数组数组数组数组;-操作操作1-创建空队列创建空队列template Queue:Queue(int MaxQueueSize)/创建一个容量为创建一个容量为MaxQueueSize的空队列的空队列MaxSize MaxQueueSize+1;queue=new TMaxSize;front=rear=0;循环队列容量比数组容量少循环队列容量比数组容量少1！-操

27、作操作2-返回队列中的第一个元素返回队列中的第一个元素template T Queue:First()const/返回队列中的第一个元素返回队列中的第一个元素if(IsEmpty()throw OutOfBounds();return queue(front+1)%MaxSize;-操作操作3-返回队列中的最后一个元素返回队列中的最后一个元素template T Queue:Last()const/返回队列中的最后一个元素返回队列中的最后一个元素if(IsFull()throw OutOfBounds();return queue rear;-操作操作4-入队列（插入）入队列（插入）templ

28、ate Queue&Queue:Add(const T&x)const/向队列添加元素向队列添加元素xif(IsFull()throw NoMem();rear=(rear+1)%MaxSize;queuerear=x;return*this;操作操作5-出队列（删除）出队列（删除）template Queue&Queue:Delete(const T&x)const/删除第一个元素删除第一个元素if(IsEmpty()throw OutOfBounds();front=(front+1)%MaxSize;x=queuefront;return*this;若循环队列以数组若循环队列以数组若循环

29、队列以数组若循环队列以数组 Q0.m-1 Q0.m-1 作为其存储结构变量作为其存储结构变量作为其存储结构变量作为其存储结构变量 rear rear 表示循环队列表示循环队列表示循环队列表示循环队列中队尾元素的实际位置中队尾元素的实际位置中队尾元素的实际位置中队尾元素的实际位置，其移动按，其移动按，其移动按，其移动按 rear=(rear+1)mod m rear=(rear+1)mod m 进行，变量进行，变量进行，变量进行，变量 length length 表示当前循表示当前循表示当前循表示当前循环队列中的元素个数，则循环队列的环队列中的元素个数，则循环队列的环队列中的元素个数，则循环队列

30、的环队列中的元素个数，则循环队列的队首元素队首元素队首元素队首元素的实际的实际的实际的实际位置是位置是位置是位置是 。A Arear-lengthrear-length B B(rear-(rear-length+mlength+m)mod m)mod m C C(1+rear+m-length)mod m(1+rear+m-length)mod m D Dm-length m-length 20042004年软件设计师试题年软件设计师试题年软件设计师试题年软件设计师试题(C)(C)课堂练习课堂练习6.4 队列的链表描述（链队列）队列的链表描述（链队列）队头在链头，队尾在链尾。队头在链头，队尾

31、在链尾。队头在链头，队尾在链尾。队头在链头，队尾在链尾。队空条件为队空条件为队空条件为队空条件为 front=NULLfront=NULLa ab bc cd de eNULLNULLfirstNodefirstNodelastNodelastNodefrontfrontrearrear这种链接方向更便于删除！这种链接方向更便于删除！两种链表队列的比较两种链表队列的比较(1)(1)(1)O(n)链队列：操作示例链队列：操作示例frontfrontrearrearx x 元素元素元素元素x x入队入队入队入队frontfrontrearrearx x y y 元素元素元素元素y y入队入队入队入

32、队frontfrontrearrearx x y y元素元素元素元素x x出队出队出队出队frontfrontrearrear 空空空空队列队列队列队列 template class LinkedQueuepublic:LinkedQueue():rear(NULL),front(NULL)LinkedQueue();bool IsEmpty()const return front?false:true;bool IsFull()const;T First()const;/返回队首元素返回队首元素 T Last()const;/返回队尾元素返回队尾元素 Queue&Add(const T&x)

33、;Queue&Delete(const T&x);private:Node*front;/指向第一个节点指向第一个节点 Node*rear;/指向最后一个元素指向最后一个元素;链式队列类的定义链式队列类的定义-操作操作1-析构函数析构函数templatetemplateLinkedQueueLinkedQueue:LinkedQueueLinkedQueue()()/析构函数，删除全部节点析构函数，删除全部节点析构函数，删除全部节点析构函数，删除全部节点Node*next;Node*next;while(frontwhile(front)next=front-next;next=front-n

34、ext;delete front;delete front;front=next;front=next;O(n)-操作操作2-判断队列是否已满判断队列是否已满templatetemplate boolbool LinkedQueueLinkedQueue:IsFullIsFull()const()const/判断队列是否已满判断队列是否已满判断队列是否已满判断队列是否已满Node*p;Node*p;try p=new Node;try p=new Node;delete p;delete p;return false;return false;catch(NoMemcatch(NoMem)re

35、turn true;)return true;-操作操作3-返回队列中的第一个元素返回队列中的第一个元素template template T T LinkedQueueLinkedQueue:First()const:First()const/返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素if(if(IsEmptyIsEmpty()throw ()throw OutOfBoundsOutOfBounds();();return front-data;return front-data;-操作操作4-返回队列中的最后一个元素返回队列中的最后一个元素te

36、mplate template T T LinkedQueueLinkedQueue:Last()const:Last()const/返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素返回队列中的第一个元素if(if(IsFullIsFull()()throw throw OutOfBoundsOutOfBounds();();return rear-data;return rear-data;-操作操作5-向队列添加元素向队列添加元素xtemplate template 向队列添加元素向队列添加元素向队列添加元素向队列添加元素x xLinkedQueueLinkedQueue

37、&LinkedQueueLinkedQueue:Add(constAdd(const T&x)T&x)Node*p=new Node;Node*p=new Node;p-data=x;p-data=x;p-link=null;p-link=null;if(front)rear-link=p;if(front)rear-link=p;后插元素后插元素后插元素后插元素else front=p;else front=p;rear=p;rear=p;return*this;return*this;-操作操作6-删除第一个元素删除第一个元素xtemplate template 删除第一个元素删除第一个元

38、素删除第一个元素删除第一个元素x xLinkedQueueLinkedQueue&LinkedQueueLinkedQueue:Delete(constDelete(const T&x)T&x)if(if(IsEmptyIsEmpty()throw ()throw OutOfBoundsOutOfBounds();();/保存第一个元素到保存第一个元素到保存第一个元素到保存第一个元素到x xx=front-data;x=front-data;/删除第一个元素删除第一个元素删除第一个元素删除第一个元素Node Node*p=front;p=front;前删元素前删元素前删元素前删元素front=

39、front=frontfront-next;-next;delete p;delete p;return*this;return*this;6.5 队列应用队列应用-火车车厢重排火车车厢重排缓冲铁轨按照缓冲铁轨按照缓冲铁轨按照缓冲铁轨按照FIFOFIFO的方式运作：队列的方式运作：队列的方式运作：队列的方式运作：队列入轨入轨入轨入轨出轨出轨出轨出轨5,8,1,7,4,2,9,6,35,8,1,7,4,2,9,6,39,8,7,6,5,4,3,2,19,8,7,6,5,4,3,2,1H1H1H2H2H3H3铁轨铁轨铁轨铁轨H H H Hk k k k作为直接将车厢从入轨移动到出轨的通道，作为直接

40、将车厢从入轨移动到出轨的通道，作为直接将车厢从入轨移动到出轨的通道，作为直接将车厢从入轨移动到出轨的通道，因此实际可作为缓冲轨道的数目为因此实际可作为缓冲轨道的数目为因此实际可作为缓冲轨道的数目为因此实际可作为缓冲轨道的数目为k-1k-1k-1k-1。5,8,1,7,4,2,9,6,35,8,1,7,4,2,9,6,33 3 Step 1 Step 1：H1H1H2H2H3H3 Step 2 Step 2：3 3H1H16 6H2H2H3H3 Step 3 Step 3：3 3H1H16 69 9H2H2H3H35,8,1,7,4,2,9,65,8,1,7,4,2,9,65,8,1,7,4,2

41、,95,8,1,7,4,2,95,8,1,7,4,25,8,1,7,4,25,8,1,7,4,25,8,1,7,4,25,8,1,7,45,8,1,7,4 Step 4 Step 4：3 3H1H16 69 9H2H2H3H32 25,8,1,75,8,1,7 Step 5 Step 5：3 3H1H16 69 9H2H2H3H32 24 45,8,15,8,1 Step 6 Step 6：3 3H1H16 69 9H2H2H3H32 24 47 75,8,15,8,11 1 Step 7 Step 7：Step 8 Step 8：3 3H1H16 69 9H2H2H3H34 47 72,12

42、,1 Step 9 Step 9：H1H16 69 9H2H2H3H34 47 73,2,13,2,1 Step 10 Step 10：H1H16 69 9H2H2H3H37 74,3,2,14,3,2,15,85,85,85,84,3,2,14,3,2,1 Step 11 Step 11：H1H16 69 9H2H2H3H37 78 85 5 Step 12 Step 12：5,4,3,2,15,4,3,2,1EmptyEmpty Step 13 Step 13：H1H19 9H2H2H3H37 78 86,5,4,3,2,16,5,4,3,2,19,8,7,6,5,4,3,2,19,8,7

43、,6,5,4,3,2,1 Step 16 Step 16：H1H1H2H2H3H3车厢分配到缓冲轨道的规则车厢分配到缓冲轨道的规则vv车厢车厢车厢车厢C C应该移动到这样的铁轨：应该移动到这样的铁轨：应该移动到这样的铁轨：应该移动到这样的铁轨：该缓冲铁轨中现有的各车厢的编号均小于该缓冲铁轨中现有的各车厢的编号均小于该缓冲铁轨中现有的各车厢的编号均小于该缓冲铁轨中现有的各车厢的编号均小于C C；如果有多个缓冲铁轨满足这样的条件，则选择一个尾如果有多个缓冲铁轨满足这样的条件，则选择一个尾如果有多个缓冲铁轨满足这样的条件，则选择一个尾如果有多个缓冲铁轨满足这样的条件，则选择一个尾部车厢编号最大的缓冲

44、铁轨，否则选择一个空的缓冲部车厢编号最大的缓冲铁轨，否则选择一个空的缓冲部车厢编号最大的缓冲铁轨，否则选择一个空的缓冲部车厢编号最大的缓冲铁轨，否则选择一个空的缓冲铁轨铁轨铁轨铁轨【如果有的话如果有的话如果有的话如果有的话】算法算法1：使用队列，程序：使用队列，程序6-7boolbool Railroad(intRailroad(int p,p,intint n,n,intint k)k)LinkedQueueLinkedQueue *H;*H;H=new H=new LinkedQueueLinkedQueue k;k;k-;/keep track k open for direct mov

45、es k-;/keep track k open for direct moves intint NowOutNowOut=1;/next car to output=1;/next car to output intint minHminH=n+1;/smallest car in a track=n+1;/smallest car in a track intint minQminQ;/track with car;/track with car minHminH for(for(intint i=1;i=n;i+)i=1;i=n;i+)if(if(pipi=NowOutNowOut)co

46、utcout Move car Move car pipi from input to output;from input to output;NowOutNowOut+;+;while(while(minHminH=NowOutNowOut)Output(minHOutput(minH,minQminQ,H,k,n);,H,k,n);车厢从缓冲轨道移动出轨车厢从缓冲轨道移动出轨车厢从缓冲轨道移动出轨车厢从缓冲轨道移动出轨 NowOutNowOut+;+;else else 将车厢将车厢将车厢将车厢C C移动到合适的缓冲轨道移动到合适的缓冲轨道移动到合适的缓冲轨道移动到合适的缓冲轨道 if(!

47、if(!Hold(piHold(pi,minHminH,minQminQ,H,k)return false;,H,k)return false;return true;return true;O(kn)算法算法2：不使用队列，程序：不使用队列，程序6-8vv简化版：如果只需简单输出车厢重排移动顺序简化版：如果只需简单输出车厢重排移动顺序简化版：如果只需简单输出车厢重排移动顺序简化版：如果只需简单输出车厢重排移动顺序vv只需了解：每个缓冲铁轨的最后一个成员是谁？以及每节只需了解：每个缓冲铁轨的最后一个成员是谁？以及每节只需了解：每个缓冲铁轨的最后一个成员是谁？以及每节只需了解：每个缓冲铁轨的最后

48、一个成员是谁？以及每节车厢当前位于那个缓冲铁轨？车厢当前位于那个缓冲铁轨？车厢当前位于那个缓冲铁轨？车厢当前位于那个缓冲铁轨？vv引入两个数组：引入两个数组：引入两个数组：引入两个数组：last1.klast1.k，表示每个缓冲铁轨中最后一个车厢的编号，表示每个缓冲铁轨中最后一个车厢的编号，表示每个缓冲铁轨中最后一个车厢的编号，表示每个缓冲铁轨中最后一个车厢的编号 track1.ntrack1.n，表示每个车厢所在的缓冲铁轨编号，表示每个车厢所在的缓冲铁轨编号，表示每个车厢所在的缓冲铁轨编号，表示每个车厢所在的缓冲铁轨编号O(kn)简化：车厢从缓冲轨道移出轨简化：车厢从缓冲轨道移出轨v下一个出

49、轨的车厢编号，与当前缓冲轨道中最后一个车厢下一个出轨的车厢编号，与当前缓冲轨道中最后一个车厢编号相同？编号相同？8,7,6,5,4,3,2,1H1H2H39课后练习：键盘缓冲区课后练习：键盘缓冲区vv当程序正在执行其它任务时，用户可以从键盘上不断键入当程序正在执行其它任务时，用户可以从键盘上不断键入当程序正在执行其它任务时，用户可以从键盘上不断键入当程序正在执行其它任务时，用户可以从键盘上不断键入所要输入的内容。所要输入的内容。所要输入的内容。所要输入的内容。vv系统在利用这种分时处理方法时，用户键入的内容不能在系统在利用这种分时处理方法时，用户键入的内容不能在系统在利用这种分时处理方法时，用

50、户键入的内容不能在系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束屏幕上立刻显示出来，直到当前正在工作的那个进程结束屏幕上立刻显示出来，直到当前正在工作的那个进程结束屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。为止。为止。为止。vv但在这个进程执行时，系统是在不断地检查键盘状态，如但在这个进程执行时，系统是在不断地检查键盘状态，如但在这个进程执行时，系统是在不断地检查键盘状态，如但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统果检测到用户键入了一个新的字符，就立刻把它存到系统果检