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

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