數據結構解說演示課件

《數據結構解說演示課件》由會員分享，可在線閱讀，更多相關《數據結構解說演示課件（44頁珍藏版）》請在裝配圖網上搜索。

第3章 隊列,與棧一樣，隊列也是一種操作受限的線性表。隊列在操作系統(tǒng)和事務管理等軟件設計中應用廣泛，如鍵盤輸入緩沖區(qū)問題就是利用隊列的思想實現(xiàn)的。 本章重點和難點： 1、隊列的順序表示與實現(xiàn) 2、隊列的鏈式表示與實現(xiàn),3.1 隊列的定義與抽象數據類型,隊列只允許在表的一端進行插入操作，在表的另一端進行刪除操作。 3.1.1 什么是隊列 隊列（queue）是一種先進先出（first in first out，縮寫為FIFO）的線性表，它只允許在表的一端進行插入，另一端刪除元素。這與我們日常生活中的排隊是一致的，最早進入隊列的元素最早離開。在隊列中，允許插入的一端稱為隊頭（front），允許刪除的一端稱為隊尾（rear）。因此又稱隊列為先進先出（FIFO）表。,,3.1 隊列的定義與抽象數據類型,假設隊列為q=（a1，a2，…，ai，…，an），那么a1為隊頭元素，an為隊尾元素。進入隊列時，是按照a1，a2，…，an的順序進入的，退出隊列時也是按照這個順序退出的。也就是說，當先進入隊列的元素都退出之后，后進入隊列的元素才能退出。即只有當a1，a2，…，an-1都退出隊列以后，an才能退出隊列。,,,,3.1 隊列的定義與抽象數據類型,2．基本操作集合 （1）置空隊列InitQueue(Q)：初始化操作，建立一個空隊列Q。 （2）判隊列空QueueEmpty(Q)：若Q為空隊列，返回1，否則返回0。 （3）入隊列EnQueue(Q,x)：若隊列不滿，插入元素x到隊列Q的隊尾。 （4）出隊列DeQueue(Q)：若隊列不空，刪除隊頭元素，并返回該元素。 （5）取隊頭Gethead(Q)：若隊列不空，返回隊頭元素。 （,,3.2 隊列的順序存儲及實現(xiàn),3.2.1 順序隊列的表示 順序隊列通常采用一維數組依次存放從隊頭到隊尾的元素。同時，使用兩個指針分別指示數組中存放的第一個元素和最后一個元素的位置。其中，指向第一個元素的指針被稱為隊頭指針front，指向最后一個元素的指針被稱為隊尾指針rear。 元素a、b、c、d、e、f、g依次進入隊列后的狀態(tài)如圖3.2所示。元素a存放在數組下標為0的存儲單元中，g存放在下標為6的存儲單元中，隊頭指針front指向第一個元素a，隊尾指針rear指向最后一個元素g的下一位置。,,3.2 隊列的順序存儲及實現(xiàn),在使用隊列前，先初始化隊列，此時，隊列為空，隊頭指針front和隊尾指針rear都指向隊列的第一個位置，即front=rear=0，如圖3.3所示。 每一個元素進入隊列，隊尾指針rear就會增1，若元素a、b、c依次進入空隊列，front指向第一個元素，rear指向下標為3的存儲單元，如圖3.4所示。,,,,3.2 隊列的順序存儲及實現(xiàn),當一個元素出隊列時，隊頭指針front增1，隊頭元素即a出隊后，front向后移動一個位置，指向下一個位置，rear不變，如圖3.3所示。,,,3.2 隊列的順序存儲及實現(xiàn),3.2.2 順序隊列的“假溢出” 在對順序隊列進行插入和刪除操作的過程中，可能會出現(xiàn)“假溢出”現(xiàn)象。經過多次插入和刪除操作后，實際上隊列還有存儲空間，但是又無法向隊列中插入元素，我們將這種溢出稱為“假溢出”。 例如，在圖3.2所示的隊列中插入3個元素h、i、j，然后刪除2個元素a，b之后，就會出現(xiàn)如圖3.6所示的情況。當插入元素j后，隊尾指針rear將越出數組的下界而造成“假溢出”。,,3.2 隊列的順序存儲及實現(xiàn),3.2.3 順序循環(huán)隊列的表示 1．順序循環(huán)隊列 為了充分利用存儲空間，消除這種“假溢出”現(xiàn)象，當隊尾指針rear和隊頭指針front到達存儲空間的最大值（假定隊列的存儲空間為QueueSize）的時候，讓隊尾指針和隊頭指針轉化為0，這樣就可以將元素插入到隊列還沒有利用的存儲單元中。例如，在圖3.6中，插入元素j之后，rear將變?yōu)?，可以繼續(xù)將元素插入到下標為0的存儲單元中。這樣就把順序隊列使用的存儲空間構造成一個邏輯上首尾相連的循環(huán)隊列。,3.2 隊列的順序存儲及實現(xiàn),當隊尾指針rear達到最大值QueueSize-1時，前提是隊列中還有存儲空間，若要插入元素，就要把隊尾指針rear變?yōu)?；當隊頭指針front達到最大值QueueSize-1時，若要將隊頭元素出隊，要讓隊頭指針front變?yōu)?。這可通過取余操作實現(xiàn)隊列的首尾相連。例如，假設QueueSize=10，當隊尾指針rear=9時，若要將新元素入隊，則先令rear=（rear+1）%10=0，然后將元素存入隊列的第0號單元，通過取余操作實現(xiàn)了隊列的邏輯上的首尾相連。,,3.2 隊列的順序存儲及實現(xiàn),2．順序循環(huán)隊列的隊空和隊滿判斷 但是，在順序循環(huán)隊列在隊空和隊滿的情況下，隊頭指針front和隊尾指針rear同時都會指向同一個位置，即front==rear，如圖3.7所示。即隊列為空時，有front=0，rear=0，因此front==rear。隊滿時也有front=0，rear=0，因此front==rear。,,,3.2 隊列的順序存儲及實現(xiàn),為了區(qū)分這隊空還是隊滿，通常有兩個方法： （1）增加一個標志位。設這個標志位為flag，初始時，有flag=0；當入隊列成功，則flag=1；出隊列成功，有flag=0。則隊列為空的判斷條件為：front==rear&&flag==0，隊列滿的判斷條件為：front==rear&&flag==1。 （2）少用一個存儲單元。隊空的判斷條件為front==rear，隊滿的判斷條件為front==(rear+1)%QueueSize。那么，入隊的操作語句為：rear=（rear+1）%QueueSize，Q[rear]=x。出隊的操作語句為：front=（front+1）%QueueSize。少用一個存儲單元的順序循環(huán)隊列隊滿情況如圖3.8所示。,,3.2 隊列的順序存儲及實現(xiàn),順序循環(huán)隊列類型描述如下： #define QueueSize 100 /*隊列的容量*/ typedef struct { DataType data[QueueSize]; int front,rear; /*隊頭指針和隊尾指針*/ }CirQueue; 其中，data用來存儲隊列中的元素，front和rear分別表示隊頭指針和隊尾指針。,,3.2 隊列的順序存儲及實現(xiàn),3.2.4 順序循環(huán)隊列的基本運算 順序循環(huán)隊列的基本運算算法實現(xiàn)如下。 （1）置空隊列。 void InitQueue(CirQueue *Q) /*順序循環(huán)隊列的初始化*/ { Q ->front=Q ->rear=0; },,3.2 隊列的順序存儲及實現(xiàn),（2）判斷隊列是否為空 int QueueEmpty(CirQueue *Q) { return Q ->front == Q ->rear ; } (3)判對滿 int QueueFull(CirQueue *Q) { return (Q ->rear+1)%QueueSize == Q ->front ; },,,3.2 隊列的順序存儲及實現(xiàn),（4）入隊 int EnQueue(CirQueue *Q , DataType x) { if(QueueFull(Q)) printf(“Queue overflow”); else{ Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; } },3.2 隊列的順序存儲及實現(xiàn),（5）取隊頭元素 DataType GetFront (CirQueue *Q) { if(QueueEmpty(Q)) printf(“Queue empty”); exit(0); else { return Q->data[Q->front]; } },3.2 隊列的順序存儲及實現(xiàn),（6）出隊列 DataType DeQueue(CirQueue *Q) { DataType x; if(QueueEmpty(Q)){ printf(“Queue empty”); exit(0); } else{ x=Q->data[Q->front]; /*將要刪除的元素賦值給x*/ Q->front=(Q->front+1)%QueueSize; return x; } },3.2 隊列的順序存儲及實現(xiàn),3.2.3 順序循環(huán)隊列舉例 P77,3.3 隊列的鏈式存儲及實現(xiàn),采用鏈式存儲的隊列被稱為鏈式隊列或鏈隊列。 3.3.1 鏈式隊列的表示 1．鏈式隊列 鏈式隊列通常用鏈表實現(xiàn)。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為隊頭指針和隊尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作上的方便，我們給鏈隊列添加一個頭結點，并令隊頭指針front指向頭結點，用隊尾指針rear指向最后一個結點。,,3.3 隊列的鏈式存儲及實現(xiàn),鏈式隊列的類型描述如下： /*結點類型定義*/ typedef struct QNode { DataType data; struct QNode * next; } QueueNode; /*隊列類型定義*/ typedef struct { QueueNode * front; //隊頭指針 QueueNode * rear; //隊尾指針 }LinkQueue; //隊列類型 LinkQueue Q; //定義一鏈對列Q,,3.3 隊列的鏈式存儲及實現(xiàn),一個不帶頭結點的鏈式隊列和帶頭結點的鏈隊列分別如圖3.12、圖3.13所示。,,3.3 隊列的鏈式存儲及實現(xiàn),對于帶頭結點的鏈式隊列，當隊列為空時，隊頭指針front和隊尾指針rear都指向頭結點。如圖3.14所示。 鏈式隊列中，插入和刪除操作只需要移動隊頭指針和隊尾指針，這兩種操作的指針變化如圖3.13、圖3.16和圖3.17所示。圖3.13表示在隊列中插入元素a的情況，圖3.16表示隊列中插入了元素a，b，c之后的情況，圖3.17表示元素a出隊列的情況。,,,,,3.3 隊列的鏈式存儲及實現(xiàn),3.3.2 鏈式隊列的基本運算 鏈式隊列的基本運算算法實現(xiàn)如下。 （1）初始化隊列。 void InitQueue(LinkQueue *Q) /*初始化鏈式隊列*/ { Q->front=(QueueNode*)malloc(sizeof(QueueNode)); Q->rear =Q->front; Q ->rear->next=NULL; /*把頭結點的指針域置為null*/ },,3.3 隊列的鏈式存儲及實現(xiàn),（2）判斷隊列是否為空。 int QueueEmpty(LinkQueue *Q) { return Q->rear==Q->front; //頭尾指針相等隊列為空 },,,3.3 隊列的鏈式存儲及實現(xiàn),（3）將元素x入隊。先為新結點申請一個空間，然后將x賦給數據域，并使原隊尾元素結點的指針域指向新結點，隊尾指針指向新結點，從而將結點加入隊列中。操作過程如圖3.20所示。,,將元素x入隊的算法實現(xiàn)如下。 void EnQueue(LinkQueue *Q, DataType x) /*將元素x插入到鏈式隊列尾部*/ { QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode)); p->data=x; //將元素值賦值給結點的數據域 p->next=NULL; //將結點的指針域置為空 Q->rear->next=p; //將原來隊列的隊尾指針指向p Q->rear=p; //將隊尾指針指向p },3.3 隊列的鏈式存儲及實現(xiàn),3.3 隊列的鏈式存儲及實現(xiàn),（4）取隊頭元素。 DataType GetFront (LinkQueue *Q) { if(QueueEmpty(Q)) { printf(“Queue underflow”); exit(0); }else return Q->front->next-data; },,3.3 隊列的鏈式存儲及實現(xiàn),（5）出隊列。 DataType DeQueue(LinkQueue *Q) { QueueNode *p; if(QueueEmpty(Q)) //判斷鏈式隊列是否為空 return 0; else { p=Q->front; //使指針p指向頭結點 Q->front=Q->front->next; //頭指針指向原隊列頭結點 free(p); //釋放原頭結點 return(Q->front->data); //返回原對頭結點的數據 } },3.3 隊列的鏈式存儲及實現(xiàn),,3.3 隊列的鏈式存儲及實現(xiàn),2．鏈式循環(huán)隊列 將鏈式隊列的首尾相連就構成了鏈式循環(huán)隊列。在鏈式循環(huán)隊列中，可以只設置隊尾指針，如圖3.18所示。當隊列為空時，如圖3.19所示，隊列LQ為空的判斷條件為LQ.rear->next==LQ.rear。,,,,,,3.3.3 鏈式隊列舉例 【例3_7】P81,3.3 隊列的鏈式存儲及實現(xiàn),入隊列圖,,出隊列圖,隊列是只允許在表的一端進行插入操作，在另一端進行刪除操作的線性表。 隊列有兩種存儲方式：順序存儲和鏈式存儲。采用順序存儲結構的 隊列稱為順序隊列，采用鏈式存儲結構的隊列稱為鏈式隊列。 順序隊列存在“假溢出”的問題，順序隊列的“假溢出”不是因為存儲空間不足而產生的，為了避免“假溢出”，可用循環(huán)隊列表示順序隊列。 為了區(qū)分循環(huán)隊列的隊空還是隊滿，有3種方案：設置一個標志位，少用一個存儲單元，設置一個計數器。 循環(huán)隊列P75，例題P80,3.4 小結,,1棧 1>棧的定義： 棧是限定僅在表的一端進行插入和刪除操作的線性表。 我們把插入和刪除的一端稱為棧頂（TOP），另一端稱為棧底（BOTTOM）,不包含任何元素的棧稱為空棧。棧又稱為后進先出（Last in first out）的線性表，簡稱LIFO結構。 2>棧的存儲結構 由于棧也是線性表，因此線性表的存儲結構對棧也使用，通常有順序棧和鏈棧兩種存儲結構，這兩種存儲結構的不同，即使得實現(xiàn)棧的基本運算的算法也有所不同。 （1）順序存儲結構 其實棧的順序存儲還是挺方便的，因為他只準棧頂進出元素，所以不存在線性表插入和刪除時需要移動元素的問題。不過它有一個很大,3.4 小結,,的缺陷，就是必須事先確定數組存儲空間大小，不夠用了，就需要編程手 段來擴展數組的容量，非常麻煩， （2）鏈式存儲結構 如果棧的使用過程中元素變化不可預測，有時很小，有時非常大，那 么最好是用鏈?！敬鎯臻g不固定可伸縮】。 2 隊列 1>隊列的定義 隊列(queue)是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。 隊列是一種先進先出(first in first out)的線性表，簡稱FIFO。允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭(Front)。 隊列是一種運算受限的線性表，它的運算限制與棧不同，是兩頭都有,3.4 小結,,限制，插入只能在表的一端進行(只進不出)，而刪除只能在表的另一端進 行(只出不進)。 2>隊列的存儲結構 隊列也是線性表，所以有兩種存儲方式，順序存儲和鏈式存儲。 （1）順序存儲結構（順序隊列） 缺點，存儲空間不夠用的時候需要開發(fā)人員通過編程手段來擴展數組容量。 衍生循環(huán)隊列：頭尾相接的順序存儲結構成為循環(huán)隊列。 （2）鏈式存儲結構（鏈隊） 隊列的鏈式存儲結構，其實也就是線性表的單鏈表，只不過它只能尾進頭出而已，我們把它簡稱為鏈隊列。,3.4 小結,,總結： 棧（stack）是限定在表的一端進行插入和刪除操作的線性表。 隊列（queue）是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。它們均可使用線性表的順序存儲結構來實現(xiàn)，但都存在著順序存儲的一些弊端（空間不夠用）。因此它們各自有各級的技巧來解決這個問題， 對于棧來說，如果是兩個相同數據類型的棧，則可以用數組的兩端作為棧底的方法來讓兩個棧共享數據，這就可以最大化地利用數組的空間。 對于隊列來說，為了避免數組插入和刪除時需要移動數據，于是就引入了循環(huán)隊列，使得隊頭和隊尾可以在數組中循環(huán)變化。解決了移動數據的時間損耗。 他們也都可以通過鏈式存儲結構來實現(xiàn)，實現(xiàn)原則上與線性表基本相同。,3.4 小結,,例如，一個算術表達式為 9 - (2+4*7)/5+3# 這種算術表達式中的運算符總是出現(xiàn)在兩個操作數之間，這種算術表達式被稱為中綴表達式。計算機編譯系統(tǒng)在計算一個算術表達式之前，要將中綴表達式轉換為后綴表達式，然后對后綴表達式進行計算。后綴表達式就是算術運算符出現(xiàn)在操作數之后，并且不含括號。 計算機在求算術表達式的值時分為兩個步驟： （1）將中綴表達式轉換為后綴表達式； （2）依據后綴表達式計算表達式的值。,3.5 棧和隊列的典型應用,1．將中綴表達式轉換為后綴表達式 要將一個算術表達式的中綴形式轉化為相應的后綴形式，首先了解下算術四則運算的規(guī)則。算術四則運算的規(guī)則是： （1）先乘除，后加減； （3）同級別的運算從左到右進行計算； （2）先括號內，后括號外。 上面的算術表達式轉換為后綴表達式為： 9247 *+5/-3 +,3.5 棧和隊列的典型應用,轉換后的后綴表達式具有以下兩個特點： （1）后綴表達式與中綴表達式的操作數出現(xiàn)順序相同，只是運算符先后順序改變了； （2）后綴表達式不出現(xiàn)括號。 正因為后綴表達式的以上特點，所以編譯系統(tǒng)不必考慮運算符的優(yōu)先關系。僅需要從左到右依次掃描后綴表達式的各個字符，遇到運算符時，直接對運算符前面的兩個操作數進行運算即可。,3.5 棧和隊列的典型應用,,如何將中綴表達式轉換為后綴表達式呢？ 我們約定’#’作為后綴表達式的結束標志。則中綴表達式轉換為后綴表達式的算法描述如下： （1）初始化棧，并將’#’入棧； （2）當讀到數字時，直接將其入隊列 ，并讀入下一字符； （3）當讀到運算符時，將棧中所有優(yōu)先級高于或等于該運算符的運算符彈出，并入隊列，再將當前運算符入棧； （4）當讀入左括號時，即入棧； （5）當讀入右括號時，將靠近棧頂的第一個左括號上面的運算符全部依次彈出， 送至隊列中，在刪除棧中的左括號。,3.5 棧和隊列的典型應用,,,運算符的優(yōu)先關系如表3.1所示。 表3.1 運算符的優(yōu)先關系,3.5 棧和隊列的典型應用,,初始化一個空棧，用來對運算符進行出棧和入棧操作。中綴表達式9 - (2+4*7)/5+3#轉換為后綴表達式的具體過程如圖P84所示（為了便于描述，在要轉換表達式的末尾加一個’#’作為結束標記）。,3.5 棧和隊列的典型應用,,,2．求后綴表達式的值 將中綴表達式轉換為后綴表達式后，就可以計算利用后綴表達式的值了。計算后綴表達式的值的規(guī)則如下：依次讀入后綴表達式中的每個字符，如果是操作數，則將操作數進入棧；如果是運算符，則將處于棧頂的兩個操作數出棧，然后利用當前運算符進行運算，將運行結果入棧，直到整個表達式處理完畢。 利用上述規(guī)則，后綴表達式的9247 *+5/-3 +的值的運算過程如圖P85所示。,3.5 棧和隊列的典型應用,