數(shù)據(jù)結(jié)構(gòu)參與命題課件第4章隊列

1、 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures隊列第4章4.0 Bus Stop Queue4.1 ADT隊列4.2 用指針實現(xiàn)ADT隊列4.3 用循環(huán)數(shù)組實現(xiàn)ADT隊列4.4 ADT隊列的應(yīng)用電路布線問題4.5 ADT隊列的其它應(yīng)用舉例2011-9-291吳英杰 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.0 Bus Stop Queuefront rearrearrearrearrear2011-9-292Bus Stop 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Stru

2、ctures4.0 Bus Stop Queuefrontrearrearrear2011-9-293Bus Stop 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.0 Bus Stop Queuefrontrearrear2011-9-294Bus Stop 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.0 Bus Stop Queuefrontrearrear2011-9-295Bus Stop 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.1ADT隊列

3、(Queue)隊列是一種特殊的線性表，是操作受限的線性表，稱其為限定性數(shù)據(jù)結(jié)構(gòu)。隊列的定義及特點定義：隊列是限定只能在表的一端進行另一端進行刪除的線性表，在表的隊尾(rear)允許的一端隊頭(front)允許刪除的一端隊列特點：先進先出(FIFO)2011-9-296 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures出隊a1a2a3an入隊frontrear隊列Q=(a1,a2,an)雙端隊列出隊入隊出隊a1a2a3an入隊端1端22011-9-297 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.1ADT隊

4、列(Queue)ADT隊列上定義的常用的基本運算):):):):(4)(5) EnterQueue(x,Q):(6) DeleteQueue(Q):2011-9-298 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.2用指針實現(xiàn)ADT隊列鏈隊列結(jié)點定義2011-9-299typedef struct qnode *qlink; typedef struct qnode QItem element; qlinknext; Qnode; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures用指針實現(xiàn)的隊列Queue的

5、定義2011-9-2910typedef struct lque *Queue; typedef struct lqueqlink front; /隊首結(jié)點指針qlink rear; /隊尾結(jié)點指針Lqueue; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures空隊列front rear入隊frontrearyz入隊rearfront出隊rearfront2011-9-2911zyzy 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures入隊算法2011-9-2912void EnterQueue (QItem x,

6、Queue Q)qlink p;p=NewQNode(); /*創(chuàng)建一個新結(jié)點*/ p->element=x;p->next=0;/*在隊尾新結(jié)點*/if(Q->front) Q->rear->next=p; /*隊列非空*/ else Q->front=p;/*空隊列*/Q->rear=p; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.3 用循環(huán)數(shù)組實現(xiàn)ADT隊列1、先考慮用一維數(shù)組sqM實現(xiàn)ADT隊列rear5432105432105454321321rearrearrearfrontfrontfrontrear00front=-1 rear=-1frontfrontJ1,J2,J3 入隊frontJ4,J5,J6入隊J

8、1,J2,J3 出隊隊空設(shè)兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素前一位置初值front=rear=-12011-9-29空隊列條件：front=rear入隊列：sq+rear=x; 出隊列：x=sq+front;14J3J2J1J6J5J4J3J2J1 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures存在問題設(shè)數(shù)組維數(shù)為M，則：當front=-1,rear=M-1時，再有元素入隊發(fā)生溢出溢出 當front¹-1,rear=M-1時，再有元素入隊發(fā)生溢出假溢出解決方案隊首固定，每次出隊剩余元素向下移動浪費

9、時間循環(huán)隊列基本思想：把隊列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0;M-1rear實現(xiàn)：利用“?！边\算入隊： rear=(rear+1)%M;出隊： front=(front+1)%M;隊滿、隊空判定條件01sqrear=x;x=sqfront;front2011-9-2915 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structuresfrontrear隊空： front=rear隊滿：front=rear5rear4301J552J6J4 43012frontJ55J6J44301初始狀態(tài)J7J92J8解決方案：1. 另外設(shè)

10、一個標志以區(qū)別隊空、隊滿2. 少用一個元素空間： 隊空：front=rear隊滿：(rear+1)%M=frontfrontrear2011-9-2916 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures2、用循環(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 +

11、 1) % MaxSize = front 時為滿隊列。2011-9-2917 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures用循環(huán)數(shù)組實現(xiàn)的隊列Queue的定義2011-9-2918typedef struct aque *Queue; typedef struct aqueint maxsize; /循環(huán)數(shù)組大小int front; /隊首游標int rear; /隊尾游標QItem queue; /循環(huán)數(shù)組Aqueue; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 ; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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; 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.4 ADT隊列的應(yīng)用電路布線問題 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題start pinend pinLabel all reachable squares 1 unit from start.2011-9-2923 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and

15、Data Structures電路布線問題start pinend pinLabel all reachable unlabeled squares 2 units from start.2011-9-292411 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題start pinend pinLabel all reachable unlabeled squares 3 units from start.2011-9-29252211222 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題

16、start pinend pinLabel all reachable unlabeled squares 4 units from start.2011-9-292633221122233 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題start pinend pinLabel all reachable unlabeled squares 5 units from start.2011-9-29274332211222343444 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題sta

17、rt pinend pinLabel all reachable unlabeled squares 6 units from start.2011-9-29285453322112223434544555 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題start pinend pinEnd pin reached. Traceback.2011-9-2929656453322112226343456445656566 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures電路布線問題start pinen

18、d pinEnd pin reached. Traceback.2011-9-2930656453322112226343456445656566 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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;/ 設(shè)置方格陣列“圍墻”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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Al

22、gorithms and Data Structures/ 構(gòu)造最短布線路徑plen=gridfinish.rowfinish.col-2; path=new point plen;/ 從目標位置finish開始向起始位置回溯here=finish;for(int j=plen-1;j>=0;j-)pathj=here;/ 找前驅(qū)位置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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures2011-9-2934 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures4.5 隊列其它應(yīng)用舉例集問題劃問題描述：已知集合A=a1,a2,an，及集合上的關(guān)系R= (ai,aj) | ai,ajÎA, i¹j，其中(ai,aj)表示ai與aj間存在關(guān)系。要求將A劃分成互不相交的子集A1,A2,Ak,(k£n)，使任何子集中的元素均無關(guān)系，同時要求集個數(shù)盡可能少例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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素無重新找出互不所用數(shù)據(jù)結(jié)構(gòu)的元素劃歸一組；再將剩下的元素的劃歸第二組；直到所有元素進組關(guān)系矩陣» rij=1, i,j有» rij=

25、0, i,j無循環(huán)隊列cqn數(shù)組resultn存放每個元素分組號工作數(shù)組newrn2011-9-2936 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures工作過程初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應(yīng)位的元素在newr中對應(yīng)位置置，這樣，凡與第一個元素有處均為“1”,下一個元素出隊» 若其在newr中對應(yīng)位置為“1”，有尾，參加下一次分組cq隊，重新»若其在newr中對應(yīng)位置為“0”, 無，可劃歸本組；再將r矩陣中該元素對應(yīng)行中的“1”拷

26、入newr中如此反復(fù)，直到9個元素依次出隊，由newr中為“0”的單元對應(yīng)的元素構(gòu)成第1組,將組號group值“1”寫入result對應(yīng)單元中令group=2,newr清零，對cq中元素重復(fù)上述操作，直到cq中front=rear,即隊空，運算結(jié)束2011-9-2937 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 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