數(shù)據(jù)結構課件版章隊列

2024/1/24福州大學數(shù)學與計算機科學學院1第4章隊列4.0BusStopQueue4.1ADT隊列4.2用指針實現(xiàn)ADT隊列4.3用循環(huán)數(shù)組實現(xiàn)ADT隊列4.4ADT隊列的應用——電路布線問題4.5ADT隊列的其它應用舉例吳英杰2024/1/24福州大學數(shù)學與計算機科學學院24.0BusStopQueueBusStopfrontrearrearrearrearrear2024/1/24福州大學數(shù)學與計算機科學學院34.0BusStopQueueBusStopfrontrearrearrear2024/1/24福州大學數(shù)學與計算機科學學院44.0BusStopQueueBusStopfrontrearrear2024/1/24福州大學數(shù)學與計算機科學學院54.0BusStopQueueBusStopfrontrearrear返回章目錄2024/1/24福州大學數(shù)學與計算機科學學院6隊列是一種特殊的線性表，是操作受限的線性表，稱其為限定性數(shù)據(jù)結構。隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)——允許插入的一端隊頭(front)——允許刪除的一端隊列特點：先進先出(FIFO)4.1ADT隊列(Queue)2024/1/24福州大學數(shù)學與計算機科學學院7a1a2a3…….an入隊出隊frontrear隊列Q=(a1,a2,……,an)雙端隊列a1a2a3…….an端1端2入隊出隊入隊出隊2024/1/24福州大學數(shù)學與計算機科學學院84.1ADT隊列(Queue)ADT隊列上定義的常用的基本運算QueueEmpty(Q):QueueFull(Q):QueueFirst(Q):(4)QueueLast(Q):(5)EnterQueue(x,Q):(6)DeleteQueue(Q):

返回章目錄2024/1/24福州大學數(shù)學與計算機科學學院9鏈隊列結點定義4.2用指針實現(xiàn)ADT隊列typedefstructqnode*qlink;typedefstructqnode{QItemelement;qlinknext;}Qnode;2024/1/24福州大學數(shù)學與計算機科學學院10用指針實現(xiàn)的隊列Queue的定義typedefstructlque*Queue;typedefstructlque{qlinkfront;//隊首結點指針

qlinkrear;//隊尾結點指針}Lqueue;2024/1/24福州大學數(shù)學與計算機科學學院11frontrearx入隊^xfrontrear空隊列^^frontyz入隊xyrear^zfrontrearx出隊y^zx2024/1/24福州大學數(shù)學與計算機科學學院12入隊算法voidEnterQueue(QItemx,QueueQ){qlinkp;p=NewQNode();/*創(chuàng)建一個新結點*/p->element=x;p->next=0;/*在隊尾插入新結點*/if(Q->front)Q->rear->next=p;/*隊列非空*/elseQ->front=p;/*空隊列*/Q->rear=p;}2024/1/24福州大學數(shù)學與計算機科學學院13出隊算法返回章目錄QItemDeleteQueue(QueueQ){qlinkp;QItemx;if(QueueEmpty(Q))Error(“Queueisempty”);x=Q->front->element;p=Q->front;Q->front=Q->front->next;free(p);returnx;}2024/1/24福州大學數(shù)學與計算機科學學院144.3用循環(huán)數(shù)組實現(xiàn)ADT隊列1、先考慮用一維數(shù)組sq[M]實現(xiàn)ADT隊列front=-1rear=-1123450隊空123450frontJ1,J2,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=-1空隊列條件：front==rear入隊列：sq[++rear]=x;出隊列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront2024/1/24福州大學數(shù)學與計算機科學學院15存在問題設數(shù)組維數(shù)為M，則：當front=-1,rear=M-1時，再有元素入隊發(fā)生溢出——溢出當front-1,rear=M-1時，再有元素入隊發(fā)生溢出——假溢出解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環(huán)隊列基本思想：把隊列設想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實現(xiàn)：利用“?！边\算入隊：rear=(rear+1)%M;sq[rear]=x;出隊：front=(front+1)%M;x=sq[front];隊滿、隊空判定條件2024/1/24福州大學數(shù)學與計算機科學學院16012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊

J7,J8,J9入隊

隊空：front==rear隊滿：front==rear解決方案：1.另外設一個標志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==front2024/1/24福州大學數(shù)學與計算機科學學院172、用循環(huán)數(shù)組實現(xiàn)隊列用循環(huán)數(shù)組實現(xiàn)的隊列的特征數(shù)據(jù)及其類型隊列元素的類型：QItem循環(huán)數(shù)組的規(guī)模:MaxSize存放隊列的循環(huán)數(shù)組：QItem*queue;一個分量放一個元素；約定沿著隊列從首到尾的走向是順時針的。

指示隊首元素的前一個位置的下標：front;指示隊尾元素位置的下標：rear;約定：front=rear時為空隊列，(rear+1)%MaxSize=front

時為滿隊列。2024/1/24福州大學數(shù)學與計算機科學學院18用循環(huán)數(shù)組實現(xiàn)的隊列Queue的定義typedefstructaque*Queue;typedefstructaque{intmaxsize;//循環(huán)數(shù)組大小intfront;//隊首游標

intrear;//隊尾游標

QItemqueue;//循環(huán)數(shù)組}Aqueue;2024/1/24福州大學數(shù)學與計算機科學學院19入隊算法：出隊算法：返回章目錄voidEnterQueue(QItemx,QueueQ){if(QueueFull(Q))Error(“Queueisfull”);Q->rear=(Q->rear+1)%Q->maxSize;Q->queue[Q->rear]=x;}QItemDeleteQueue(QueueQ){if(QueueEmpty(Q))Error(“Queueisempty”);Q->front=(Q->front+1)%Q->maxSize;returnQ->queue[Q->front];}4.4ADT隊列的應用—電路布線問題2024/1/24福州大學數(shù)學與計算機科學學院21電路布線問題startpinendpinLabelallreachablesquares1unitfromstart.2024/1/24福州大學數(shù)學與計算機科學學院22電路布線問題startpinendpinLabelallreachableunlabeledsquares2unitsfromstart.112024/1/24福州大學數(shù)學與計算機科學學院23電路布線問題startpinendpinLabelallreachableunlabeledsquares3unitsfromstart.11222222024/1/24福州大學數(shù)學與計算機科學學院24電路布線問題startpinendpinLabelallreachableunlabeledsquares4unitsfromstart.112222233332024/1/24福州大學數(shù)學與計算機科學學院25電路布線問題startpinendpinLabelallreachableunlabeledsquares5unitsfromstart.11222223333444442024/1/24福州大學數(shù)學與計算機科學學院26電路布線問題startpinendpinLabelallreachableunlabeledsquares6unitsfromstart.11222223333444445555552024/1/24福州大學數(shù)學與計算機科學學院27電路布線問題startpinendpinEndpinreached.Traceback.1122222333344444555555666666662024/1/24福州大學數(shù)學與計算機科學學院28電路布線問題startpinendpin4Endpinreached.Traceback.1122222333344444555555666666663521返回章目錄2024/1/24福州大學數(shù)學與計算機科學學院294.5隊列其它應用舉例劃分子集問題 問題描述：已知集合A={a1,a2,……an}，及集合上的關系R={(ai,aj)|ai,ajA,ij}，其中(ai,aj)表示ai與aj間存在沖突關系。要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均無沖突關系，同時要求分子集個數(shù)盡可能少例A={1,2,3,4,5,6,7,8,9}R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,