數(shù)據(jù)結(jié)構(gòu)課件版章隊(duì)列

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

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

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

J7,J8,J9入隊(duì)

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

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

指示隊(duì)首元素的前一個(gè)位置的下標(biāo)：front;指示隊(duì)尾元素位置的下標(biāo)：rear;約定：front=rear時(shí)為空隊(duì)列，(rear+1)%MaxSize=front

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

intrear;//隊(duì)尾游標(biāo)

QItemqueue;//循環(huán)數(shù)組}Aqueue;2024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院19入隊(duì)算法：出隊(duì)算法：返回章目錄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隊(duì)列的應(yīng)用—電路布線問題2024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院21電路布線問題startpinendpinLabelallreachablesquares1unitfromstart.2024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院22電路布線問題startpinendpinLabelallreachableunlabeledsquares2unitsfromstart.112024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院23電路布線問題startpinendpinLabelallreachableunlabeledsquares3unitsfromstart.11222222024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院24電路布線問題startpinendpinLabelallreachableunlabeledsquares4unitsfromstart.112222233332024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院25電路布線問題startpinendpinLabelallreachableunlabeledsquares5unitsfromstart.11222223333444442024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院26電路布線問題startpinendpinLabelallreachableunlabeledsquares6unitsfromstart.11222223333444445555552024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院27電路布線問題startpinendpinEndpinreached.Traceback.1122222333344444555555666666662024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院28電路布線問題startpinendpin4Endpinreached.Traceback.1122222333344444555555666666663521返回章目錄2024/1/24福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院294.5隊(duì)列其它應(yīng)用舉例劃分子集問題 問題描述：已知集合A={a1,a2,……an}，及集合上的關(guān)系R={(ai,aj)|ai,ajA,ij}，其中(ai,aj)表示ai與aj間存在沖突關(guān)系。要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均無沖突關(guān)系，同時(shí)要求分子集個(gè)數(shù)盡可能少例A={1,2,3,4,5,6,7,8,9}R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,