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

4.1ADT隊(duì)列隊(duì)列是另一種特殊的表，也是操作受限4.1ADT隊(duì)列隊(duì)列是另一種特殊的表，也是操作受限隊(duì)尾(rear)——允許插入的一隊(duì)頭(front)——允許刪除的一特點(diǎn)：先進(jìn)先出例如：排隊(duì)上車2BusStop3BusStop3BusStop4BusStop4BusStop5BusStop5BusStop6BusStop6假設(shè)隊(duì)列，，，則就是隊(duì)首元素，為隊(duì)尾元素。隊(duì)列中的元素按，，的次序進(jìn)出假設(shè)隊(duì)列，，，則就是隊(duì)首元素，為隊(duì)尾元素。隊(duì)列中的元素按，，的次序進(jìn)出 入隊(duì)列7ADT測(cè)試隊(duì)列QQueueFull(Q):測(cè)試隊(duì)列Q返回隊(duì)列Q返回隊(duì)列QADT測(cè)試隊(duì)列QQueueFull(Q):測(cè)試隊(duì)列Q返回隊(duì)列Q返回隊(duì)列QEnterQueue(x，Q):在隊(duì)列Q的隊(duì)尾插入元素DeleteQueue(Q):刪除并返回隊(duì)列Q8用指針實(shí)現(xiàn)隊(duì)與棧的情形相同，任何一種實(shí)用指針實(shí)現(xiàn)隊(duì)與棧的情形相同，任何一種實(shí)現(xiàn)表的方法都可以用9typedefstructqnode*qlink;typedefstructqnode{QItemelement; }用指針實(shí)現(xiàn)的隊(duì)列Queuetypedefstructlque*Queue;typedefstructlque{qlinkfront; 用指針實(shí)現(xiàn)的隊(duì)列Queuetypedefstructlque*Queue;typedefstructlque{qlinkfront; qlinkrear; 1、創(chuàng)將隊(duì)首指針和隊(duì)尾指針均置為空指針，創(chuàng)建一個(gè)空隊(duì)列，實(shí)現(xiàn)方法如下：1、創(chuàng)將隊(duì)首指針和隊(duì)尾指針均置為空指針，創(chuàng)建一個(gè)空隊(duì)列，實(shí)現(xiàn)方法如下：QueueQueueInit({QueueQ=malloc(sizeof*Q);returnQ;}2、判檢測(cè)frontintQueueEmpty(Queue{returnQ-2、判檢測(cè)frontintQueueEmpty(Queue{returnQ-}3、判為隊(duì)列QintQueueFull(Queue{returnQMemFull(}int3、判為隊(duì)列QintQueueFull(Queue{returnQMemFull(}intQMemFull({qlinkreturn{return}4、返QItemQueueFirst(Queue{ Error(“Queue4、返QItemQueueFirst(Queue{ Error(“Queueis returnQ->front-}5、返QItemQueueLast(Queue{ Error(“Queue5、返QItemQueueLast(Queue{ Error(“Queueis returnQ->rear-}6、在隊(duì)列Q的隊(duì)尾插入元素6、在隊(duì)列Q的隊(duì)尾插入元素voidEnterQueue(QItemx,Queue{qlinkp; elseQ–>front=p;}7、刪除并返回隊(duì)列Q7、刪除并返回隊(duì)列QQItemDeleteQueue(Queue{qlink QItem Error(“Queueisreturn}用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)個(gè)游標(biāo)來指示隊(duì)尾，使得Et用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)個(gè)游標(biāo)來指示隊(duì)尾，使得Ete運(yùn)算在1時(shí)間內(nèi)完成，但在執(zhí)行e時(shí)，為了刪除隊(duì)首元素，必須將數(shù)組中其他所有元素都前移一個(gè)位置，很浪費(fèi)時(shí)間。設(shè)想數(shù)組queue[0:maxsize-1]而是圍成一個(gè)首尾相接的圓環(huán)，即queue[0]queue[maxsize-1]的后面。這種意義下的數(shù)組稱為數(shù)組0Maxsize-設(shè)想數(shù)組queue[0:maxsize-1]而是圍成一個(gè)首尾相接的圓環(huán)，即queue[0]queue[maxsize-1]的后面。這種意義下的數(shù)組稱為數(shù)組0Maxsize-實(shí)現(xiàn)：利用“?！背鲫?duì)：將隊(duì)首游標(biāo)front隊(duì)滿、隊(duì)空判定條5 43012543015243012初始解決5 43012543015243012初始解決方案另外設(shè)一個(gè)布爾量用循環(huán)數(shù)組實(shí)現(xiàn)的隊(duì)列Queuetypedefstructaque*Queue;typedefstructaque{intmaxsize; 用循環(huán)數(shù)組實(shí)現(xiàn)的隊(duì)列Queuetypedefstructaque*Queue;typedefstructaque{intmaxsize; intfront; intrear; QItem*queue; 1、創(chuàng)為隊(duì)列分配一個(gè)容量為sizefront和隊(duì)尾游標(biāo)rear均置為0，創(chuàng)1、創(chuàng)為隊(duì)列分配一個(gè)容量為sizefront和隊(duì)尾游標(biāo)rear均置為0，創(chuàng)QueueQueueInit(int{QueueQ=malloc(sizeofreturnQ;}2、判通過檢測(cè)隊(duì)列Q的隊(duì)首游標(biāo)front與隊(duì)尾游標(biāo)rear是否合來判斷隊(duì)列Q2、判通過檢測(cè)隊(duì)列Q的隊(duì)首游標(biāo)front與隊(duì)尾游標(biāo)rear是否合來判斷隊(duì)列QintQueueEmpty(Queue{returnQ->front==Q-}3、判通過在隊(duì)列Q的隊(duì)尾插入一個(gè)元素后隊(duì)首游標(biāo)front尾游標(biāo)rear是否重合，來判斷隊(duì)列Q3、判通過在隊(duì)列Q的隊(duì)尾插入一個(gè)元素后隊(duì)首游標(biāo)front尾游標(biāo)rear是否重合，來判斷隊(duì)列QintQueueFull(Queue{return(((Q->rear+1)%Q->maxsize==Q-}4、返回隊(duì)列Q的隊(duì)4、返回隊(duì)列Q的隊(duì)QItemQueueFirst(Queue{ Error(“QueueisreturnQ->queue[(Q->front+1)%Q-}5、返回隊(duì)列Q的隊(duì)QItemQueueLast(Queue5、返回隊(duì)列Q的隊(duì)QItemQueueLast(Queue{ Error(“Queueis returnQ->queue[Q-}6、在隊(duì)列Q的隊(duì)尾插入元素先計(jì)算出在循環(huán)的意義隊(duì)列的隊(duì)尾元素在循環(huán)數(shù)組中的下一個(gè)位置(z6、在隊(duì)列Q的隊(duì)尾插入元素先計(jì)算出在循環(huán)的意義隊(duì)列的隊(duì)尾元素在循環(huán)數(shù)組中的下一個(gè)位置(ze，然后在該位置插入元素。voidEnterQueue(QItemx,Queue{ Error(“QueueisFull”);Q->rear=(Q->rear+1)%Q->maxsize;}7、刪除并返回隊(duì)列Q7、刪除并返回隊(duì)列QQItemDeleteQueue(Queue{ Error(“Queueisempty”);Q->front=(Q->front+1)%Q->maxsize;returnQ->queue[Q->front];}隊(duì)列的應(yīng)用舉例1在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時(shí)主機(jī)就要停下來等待打印機(jī)。顯然，這樣會(huì)降低主機(jī)的使用效率。為此人們?cè)O(shè)想了一種辦法：為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時(shí)，先將數(shù)據(jù)依次寫入這個(gè)緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)隊(duì)列的應(yīng)用舉例1在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時(shí)主機(jī)就要停下來等待打印機(jī)。顯然，這樣會(huì)降低主機(jī)的使用效率。為此人們?cè)O(shè)想了一種辦法：為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，當(dāng)主機(jī)需要打印數(shù)據(jù)時(shí)，先將數(shù)據(jù)依次寫入這個(gè)緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個(gè)隊(duì)列結(jié)隊(duì)列的應(yīng)用舉例2CPU在一個(gè)帶有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中，同時(shí)有多個(gè)用戶需要使用U運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用隊(duì)列的應(yīng)用舉例2CPU在一個(gè)帶有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中，同時(shí)有多個(gè)用戶需要使用U運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用P的請(qǐng)求，操作系統(tǒng)通常按每次把CPU分配給當(dāng)前隊(duì)首的請(qǐng)求用戶，即將該用戶用程序投入運(yùn)行，當(dāng)該程序運(yùn)行完畢或用完規(guī)定的時(shí)間片后，操作系統(tǒng)再將PU分配給新的隊(duì)首請(qǐng)求用戶，這樣即可以滿足每個(gè)用戶的請(qǐng)求，又可以使P正常工作。例3例3R={(ai,aj)|ai,aj∈A,i≠j}，其中(ai,aj)表示ai與aj間存在沖系，同時(shí)要求分子集個(gè)數(shù)盡可能少R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集A1={1,3,4,8A2={2,7A3={5A4={6,9算法思想：利用循環(huán)篩選算法思想：利用循環(huán)篩選沖突關(guān)系矩r[i][j]=1,i,jr[i][j]=0,i,j循環(huán)隊(duì)列數(shù)組result[n]存放每個(gè)元素分組工作數(shù)組初始狀態(tài)：A中元素放于q中，t和w初始狀態(tài)：A中元素放于q中，t和wr數(shù)組清零，組號(hào)第一個(gè)元素出隊(duì)，將r矩陣中第一行“”拷入r中對(duì)應(yīng)位置，這樣，凡與第一個(gè)元素有沖突的元素在wr中對(duì)應(yīng)位置處均為“下一個(gè)元素出隊(duì)若其在ner中對(duì)應(yīng)位置為“1”，有沖突，重新插入cq隊(duì)尾，參加下一次分組若其在newr中對(duì)應(yīng)位置為“0”,無沖突，可劃歸本組；再將r如此反復(fù)，直到個(gè)元素依次出隊(duì)，由中為“的單元對(duì)應(yīng)的元素構(gòu)成第組將組號(hào)u值“寫入l對(duì)應(yīng)單元中令group=2,newr清零，對(duì)cq中元素重復(fù)上述操作，直cq中front==rear,即隊(duì)空，運(yùn)算結(jié)R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123456780100000001000110110000011000000100010101011010110101000R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf初012345678012345678000000000000000000123456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234567801234567810000000001000000023456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567810000000001000000023456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf0123456780123456781010000000100011002456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234567801000000010001101100000110000001000101010110101101010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000f7r0123456801234567810110001001001110125679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567810110001001001110125679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123456780123456781211000101000110115679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123456780123456781211000101000110116795R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234 780123456781211000101000110117956R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234 78012345678121100210101011011956R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678121100210101011011569R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123 678010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123 678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123 67801234567812113021001010110169R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567812113021001010110196R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000