隊(duì)列及相關(guān)算法

隊(duì)列及相關(guān)算法

2010/03/291作業(yè)分析

表達(dá)式轉(zhuǎn)換中綴式轉(zhuǎn)前綴式

Exp=ab

+

(cd/e)f后綴式:ab

cde/f

+前綴式:+

ab

c/def后綴式的運(yùn)算后綴式的運(yùn)算規(guī)則為:運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)，且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式（算子）。例：31*(5–22)+7031522-*70+

帶括號(hào)的表達(dá)式的計(jì)算*6)/3#operatorstackoperandstackexpression???push(data);Push(oper);getResult();checkIn(oper);棧抽象數(shù)據(jù)類型定義幾個(gè)常用函數(shù)優(yōu)先級(jí)矩陣及優(yōu)先級(jí)判斷當(dāng)前運(yùn)算符優(yōu)先級(jí)低…By00811093賴俊By00811093賴俊By00811093賴俊一個(gè)中綴式到其他式子的轉(zhuǎn)換方法（）這里給出一個(gè)中綴表達(dá)式~

a+b*c-(d+e)

第一步：按照運(yùn)算符的優(yōu)先級(jí)對(duì)所有的運(yùn)算單位加括號(hào)，式子變成：((a+(b*c))-(d+e))

第二步：轉(zhuǎn)換前綴與后綴表達(dá)式

前綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)前面

則變成拉：-(+(a*(bc))+(de))

把括號(hào)去掉：-+a*bc+de

前綴式子出現(xiàn)

后綴：把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)后面

則變成拉：((a(bc)*)-(de)+)-

把括號(hào)去掉：abc*-de+-

后綴式子出現(xiàn)

隊(duì)列

：隊(duì)列的引入與抽象數(shù)據(jù)類型定義隊(duì)列的存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)隊(duì)列的應(yīng)用隊(duì)列特點(diǎn)隊(duì)列是一種特殊的線性表，只允許在表的一端有插入操作，而在另一端有刪除操作。隊(duì)頭：允許刪除的這一端叫隊(duì)列的頭。隊(duì)尾：允許插入的這一端叫隊(duì)列的尾。空隊(duì)列：當(dāng)隊(duì)列中沒(méi)有任何元素時(shí)，稱為空隊(duì)列。進(jìn)隊(duì)/出隊(duì)：隊(duì)列的插入操作通常稱為進(jìn)隊(duì)列或入隊(duì)列，隊(duì)列的刪除操作通常稱為退隊(duì)列或出隊(duì)列。

隊(duì)列基本概念隊(duì)列也稱作先進(jìn)先出表（FirstInFirstOut，F(xiàn)IFO表）。支持隊(duì)尾插入，隊(duì)頭刪除操作。

a0a1a2an-1入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列隊(duì)列的示意圖隊(duì)列ADTADTQueueisoperations QueuecreateEmptyQueue(void);//創(chuàng)建一個(gè)空隊(duì)列。 intisEmptyQueue(Queuequ);//判隊(duì)列qu是否為空隊(duì)列。 voidenQueue(Queuequ,DataTypex); //往隊(duì)列qu尾部插入一個(gè)值為x的元素。 voiddeQueue(Queuequ);//從隊(duì)列qu頭部刪除一個(gè)元素。 DataTypefrontQueue(Queuequ);//求隊(duì)列qu頭部元素的值。endADTQueue順序結(jié)構(gòu)隊(duì)列frontrearenQueue:{qBuffer[rear]=inData;rear++;}deQueue:{outData=qBuffer[rear];front++;}isEmpty(){…}環(huán)形存儲(chǔ)結(jié)構(gòu)隊(duì)列frontrearmodMAXSIZEenQueue:{qBuffer[rear]=inData;rear=(rear+1)%MAXSIZE;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}isOverflow(){…}把數(shù)組paqu->q[MAXNUM]從邏輯上看成一個(gè)環(huán)，這種隊(duì)列稱為環(huán)形隊(duì)列。當(dāng)表中已有MAXNUM－1個(gè)結(jié)點(diǎn)時(shí)，如果還要插入，paqu->r和paqu->f就會(huì)重合，而這與空隊(duì)列的情形相混。為區(qū)分空隊(duì)列與滿隊(duì)列兩種情況的環(huán)形隊(duì)列，一般是犧牲隊(duì)列中的一個(gè)結(jié)點(diǎn)，當(dāng)隊(duì)列中已有MAXNUM－1個(gè)結(jié)點(diǎn)時(shí)就稱滿，再要插入就發(fā)生溢出。環(huán)形存儲(chǔ)結(jié)構(gòu)隊(duì)列順序結(jié)構(gòu)隊(duì)列的類型定義順序結(jié)構(gòu)隊(duì)列操作的實(shí)現(xiàn)順序結(jié)構(gòu)隊(duì)列操作的實(shí)現(xiàn)鏈接結(jié)構(gòu)隊(duì)列尾部插入頭部刪除。r->link=newNode;r=newNode;newNode.link=NULL;ptr=f;f=f->next;