數(shù)據(jù)結(jié)構(gòu)解說演示課件

《數(shù)據(jù)結(jié)構(gòu)解說演示課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)解說演示課件（44頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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