数据结构参与命题课件第4章队列

1、 算 法 与 数 据 结 构 Algorithms and Data Structures队列第4章4.0 Bus Stop Queue4.1 ADT队列4.2 用指针实现ADT队列4.3 用循环数组实现ADT队列4.4 ADT队列的应用电路布线问题4.5 ADT队列的其它应用举例2011-9-291吴英杰 算 法 与 数 据 结 构 Algorithms and Data Structures4.0 Bus Stop Queuefront rearrearrearrearrear2011-9-292Bus Stop 算 法 与 数 据 结 构 Algorithms and Data Stru

2、ctures4.0 Bus Stop Queuefrontrearrearrear2011-9-293Bus Stop 算 法 与 数 据 结 构 Algorithms and Data Structures4.0 Bus Stop Queuefrontrearrear2011-9-294Bus Stop 算 法 与 数 据 结 构 Algorithms and Data Structures4.0 Bus Stop Queuefrontrearrear2011-9-295Bus Stop 算 法 与 数 据 结 构 Algorithms and Data Structures4.1ADT队列

3、(Queue)队列是一种特殊的线性表，是操作受限的线性表，称其为限定性数据结构。队列的定义及特点定义：队列是限定只能在表的一端进行另一端进行删除的线性表，在表的队尾(rear)允许的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)2011-9-296 算 法 与 数 据 结 构 Algorithms and Data Structures出队a1a2a3an入队frontrear队列Q=(a1,a2,an)双端队列出队入队出队a1a2a3an入队端1端22011-9-297 算 法 与 数 据 结 构 Algorithms and Data Structures4.1ADT队

4、列(Queue)ADT队列上定义的常用的基本运算):):):):(4)(5) EnterQueue(x,Q):(6) DeleteQueue(Q):2011-9-298 算 法 与 数 据 结 构 Algorithms and Data Structures4.2用指针实现ADT队列链队列结点定义2011-9-299typedef struct qnode *qlink; typedef struct qnode QItem element; qlinknext; Qnode; 算 法 与 数 据 结 构 Algorithms and Data Structures用指针实现的队列Queue的

5、定义2011-9-2910typedef struct lque *Queue; typedef struct lqueqlink front; /队首结点指针qlink rear; /队尾结点指针Lqueue; 算 法 与 数 据 结 构 Algorithms and Data Structures空队列front rear入队frontrearyz入队rearfront出队rearfront2011-9-2911zyzy 算 法 与 数 据 结 构 Algorithms and Data Structures入队算法2011-9-2912void EnterQueue (QItem x,

6、Queue Q)qlink p;p=NewQNode(); /*创建一个新结点*/ p->element=x;p->next=0;/*在队尾新结点*/if(Q->front) Q->rear->next=p; /*队列非空*/ else Q->front=p;/*空队列*/Q->rear=p; 算 法 与 数 据 结 构 Algorithms and Data Structures出队算法2011-9-2913QItem DeleteQueue(Queue Q)qlink p; QItem x;if(QueueEmpty(Q) Error(“Queue

7、 is empty”); x= Q->front->element;p= Q->front;Q->front= Q->front->next; free(p);return x; 算 法 与 数 据 结 构 Algorithms and Data Structures4.3 用循环数组实现ADT队列1、先考虑用一维数组sqM实现ADT队列rear5432105432105454321321rearrearrearfrontfrontfrontrear00front=-1 rear=-1frontfrontJ1,J2,J3 入队frontJ4,J5,J6入队J

8、1,J2,J3 出队队空设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-12011-9-29空队列条件：front=rear入队列：sq+rear=x; 出队列：x=sq+front;14J3J2J1J6J5J4J3J2J1 算 法 与 数 据 结 构 Algorithms and Data Structures存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出溢出 当front¹-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费

9、时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;M-1rear实现：利用“模”运算入队： rear=(rear+1)%M;出队： front=(front+1)%M;队满、队空判定条件01sqrear=x;x=sqfront;front2011-9-2915 算 法 与 数 据 结 构 Algorithms and Data Structuresfrontrear队空： front=rear队满：front=rear5rear4301J552J6J4 43012frontJ55J6J44301初始状态J7J92J8解决方案：1. 另外设

10、一个标志以区别队空、队满2. 少用一个元素空间： 队空：front=rear队满：(rear+1)%M=frontfrontrear2011-9-2916 算 法 与 数 据 结 构 Algorithms and Data Structures2、用循环数组实现队列用循环数组实现的队列的特征数据及其类型队列元素的类型：QItem 循环数组的规模: MaxSize存放队列的循环数组：QItem *queue;一个分量放一个元素；约定沿着队列从首到尾的是顺时针的。指示队首元素的前一个位置的下标： front;指示队尾元素位置的下标： rear;约定：front= rear时为空队列，(rear +

11、 1) % MaxSize = front 时为满队列。2011-9-2917 算 法 与 数 据 结 构 Algorithms and Data Structures用循环数组实现的队列Queue的定义2011-9-2918typedef struct aque *Queue; typedef struct aqueint maxsize; /循环数组大小int front; /队首游标int rear; /队尾游标QItem queue; /循环数组Aqueue; 算 法 与 数 据 结 构 Algorithms and Data Structures判断队列空：判断队列满：2011-9-

12、2919Int QueueFull (Queue Q)return (Q->rear+1)%Q->maxsize=Q->front)? 1:0 ;Int QueueEmpty (Queue Q)return Q->front= = Q->rear ; 算 法 与 数 据 结 构 Algorithms and Data Structures返回队首元素：2011-9-2920QItem QueueFirst(Queue Q)if(QueueEmpty(Q) Error(“Queue is empty”); return Q->queue(Q->front

13、 + 1) % Q->maxSize; 算 法 与 数 据 结 构 Algorithms and Data Structures入队算法：出队算法：2011-9-2921QItem DeleteQueue(Queue Q)if(QueueEmpty(Q) Error(“Queue is empty”); Q->front = (Q->front + 1) % Q->maxSize; return Q->queueQ->front;void EnterQueue (QItem x, Queue Q)if (QueueFull(Q) Error(“Queue i

14、s full”); Q->rear = (Q->rear + 1) % Q->maxSize; Q->queueQ->rear = x; 算 法 与 数 据 结 构 Algorithms and Data Structures4.4 ADT队列的应用电路布线问题 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题start pinend pinLabel all reachable squares 1 unit from start.2011-9-2923 算 法 与 数 据 结 构 Algorithms and

15、Data Structures电路布线问题start pinend pinLabel all reachable unlabeled squares 2 units from start.2011-9-292411 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题start pinend pinLabel all reachable unlabeled squares 3 units from start.2011-9-29252211222 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题

16、start pinend pinLabel all reachable unlabeled squares 4 units from start.2011-9-292633221122233 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题start pinend pinLabel all reachable unlabeled squares 5 units from start.2011-9-29274332211222343444 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题sta

17、rt pinend pinLabel all reachable unlabeled squares 6 units from start.2011-9-29285453322112223434544555 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题start pinend pinEnd pin reached. Traceback.2011-9-2929656453322112226343456445656566 算 法 与 数 据 结 构 Algorithms and Data Structures电路布线问题start pinen

18、d pinEnd pin reached. Traceback.2011-9-2930656453322112226343456445656566 算 法 与 数 据 结 构 Algorithms and Data Structuresbool find_path(point start,point finish,int& plen,point *&path)/ 计算从起始位置start到目标位置finish的最短布线路径/ 找到最短布线路径则返回true,否则返回falseif(start.row=finish.row)&&(start.col=finish.

19、col)plen=0;retur n true;/ 设置方格阵列“围墙”for(int i=0;i<=m+1;i+)grid0i=gridn+1i=1;/ 顶部和底部for(int i=0;i<=n+1;i+)gridi0=gridim+1=1;/ 初始化相对位移point offset4; offset0.row=0;offset0.col=1;/ 右offset1.row=1;offset1.col=0;/ 下offset2.row=0;offset2.col=-1;/ 左offset3.row=-1;offset3.col=0;/ 上point here,nbr; here.

20、row=start.row; here.col=start.col;gridstart.rowstart.col=2; / 标记可达方格位置和右翼queue<point> que; / 待方格队列2011-9-2931 算 法 与 数 据 结 构 Algorithms and Data Structuresdo/ 标记可达相邻方格for(int i=0;i<4;i+)nbr.row=here.row+offseti.row; nbr.col=here.col+offseti.col; if(gridnbr.rownbr.col=0)/ 该方格未标记gridnbr.rownbr

21、.col=gridhere.rowhere.col+1;if(nbr.row=finish.row)&&(nbr.col=finish.col)break;que.push(nbr);/ 是否到达目标位置finish? if(nbr.row=finish.row)&&(nbr.col=finish.col)break;/ 完成布线/ 待方格队列是否非空if(que.empty()return false;/ 无解here=que.front();que.pop();/ 取下一个 while(true);2011-9-29方格32 算 法 与 数 据 结 构 Al

22、gorithms and Data Structures/ 构造最短布线路径plen=gridfinish.rowfinish.col-2; path=new point plen;/ 从目标位置finish开始向起始位置回溯here=finish;for(int j=plen-1;j>=0;j-)pathj=here;/ 找前驱位置for(int i=0;i<4;i+)nbr.row=here.row+offseti.row; nbr.col=here.col+offseti.col; if(gridnbr.rownbr.col=j+2)break;here=nbr; / 向前移

23、动return true;2011-9-2933 算 法 与 数 据 结 构 Algorithms and Data Structures2011-9-2934 算 法 与 数 据 结 构 Algorithms and Data Structures4.5 队列其它应用举例集问题划问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajÎA, i¹j，其中(ai,aj)表示ai与aj间存在关系。要求将A划分成互不相交的子集A1,A2,Ak,(k£n)，使任何子集中的元素均无关系，同时要求集个数尽可能少例A=1,2,3,4,5,6,

24、7,8,9R= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 可行的子集划分为：A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 2011-9-2935 算 法 与 数 据 结 构 Algorithms and Data Structures算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无重新找出互不所用数据结构的元素划归一组；再将剩下的元素的划归第二组；直到所有元素进组关系矩阵» rij=1, i,j有» rij=

25、0, i,j无循环队列cqn数组resultn存放每个元素分组号工作数组newrn2011-9-2936 算 法 与 数 据 结 构 Algorithms and Data Structures工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位的元素在newr中对应位置置，这样，凡与第一个元素有处均为“1”,下一个元素出队» 若其在newr中对应位置为“1”，有尾，参加下一次分组cq队，重新»若其在newr中对应位置为“0”, 无，可划归本组；再将r矩阵中该元素对应行中的“1”拷

26、入newr中如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束2011-9-2937 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 0100000001000110110000011000

27、00010001010101101011010100001011000010000000010110000012345678cqfr初始R=012345678newr012345678result2011-9-2938000000000000000000123456789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 010000000100011011000001100

28、000010001010101101011010100001011000010000000010110000012345678cqfrR=012345678newr012345678result2011-9-293910000000001000000023456789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 01000000010001101100000110000

29、0010001010101101011010100001011000010000000010110000012345678cqrfR=012345678newr012345678result2011-9-294010000000001000000023456789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 0100000001000110110000011000000

30、10001010101101011010100001011000010000000010110000012345678cqrfR=012345678newr012345678result2011-9-29411010000000100011002456789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 0100000001000110110000011000000100

31、01010101101011010100001011000010000000010110000012345678cqrfR=012345678newr012345678result2011-9-2942101100000010011101256789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 01000000010001101100000110000001000101

32、0101101011010100001011000010000000010110000012345678cqrfR=012345678newr012345678result2011-9-2943101100000010011101256789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 010000000100011011000001100000010001010101

33、101011010100001011000010000000010110000012345678cqfrR=012345678newr012345678result2011-9-2944101100000010011101256789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 010000000100011011000001100000010001010101101011010100001011000010000000010110000012345678cqrfR=012345678newr012345678result2011-9-2945101100000010011101256789 算 法 与 数 据 结 构 Algorithms and Data StructuresR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9),(5,6), (5,4), (7,5), (7,6), (3,7), (6,3) 010000000