數(shù)據(jù)結(jié)構(gòu)與算法b-2014年3月19日課堂listmar

數(shù)據(jù)結(jié)構(gòu)與算法

—線性結(jié)構(gòu)主講教員:段凌宇2014年3月19日

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2線性結(jié)構(gòu)分類(struct)字段名訪問(wèn)，非整數(shù)下標(biāo)訪問(wèn)，不符合線性表定義

不得直接訪問(wèn)內(nèi)部元素，只允許訪問(wèn)某些入口點(diǎn)

線性表（LinearList)的一種推廣，線性表被定義為一個(gè)有限的序列（a1，a2，a3，…，an）其中ai被限定為是單個(gè)數(shù)據(jù)元素。廣義表也是n個(gè)數(shù)據(jù)元素d1，d2，d3，…，dn的有限序列，但不同的是，廣義表中的di則既可以是單個(gè)元素，還可以是一個(gè)廣義表，通常記作：GL=（d1，d2，d3，…，dn）。廣義表的定義是遞歸定義的。因?yàn)樵诙x廣義表時(shí)，又使用了廣義表的概念。一條條記錄按順序進(jìn)行存放，每條記錄的長(zhǎng)度可按需要變化。這類文件的存取類似于在磁帶上記錄和讀取信息，它按順序?qū)⑿畔念^到尾掃描一遍。訪問(wèn)：結(jié)點(diǎn)的讀取、更新、增刪通過(guò)”順序”、”鏈接”等存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page32.5.4棧的應(yīng)用遞歸函數(shù)、函數(shù)嵌套的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的棧從操作系統(tǒng)中申請(qǐng)分配的棧復(fù)雜的算術(shù)表達(dá)式的遞歸求值北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4算數(shù)表達(dá)式的描述標(biāo)準(zhǔn)的表達(dá)式如“A+B”，數(shù)學(xué)上學(xué)名叫中綴表達(dá)式（InfixNotation），原因是運(yùn)算符號(hào)在兩個(gè)運(yùn)算對(duì)象的中間。比如：“A-B*C+D”

。后綴表達(dá)式（PostfixNotation），比如中綴表達(dá)式“A-B*C+D”

轉(zhuǎn)換為后綴表達(dá)式為：“ABC*-D+”。對(duì)應(yīng)的還有前綴表達(dá)式（PrefixNotation），如：中綴表達(dá)式“A-B*C+D”

轉(zhuǎn)換為前綴表達(dá)式為：“+-A*BCD”為了紀(jì)念波蘭數(shù)學(xué)家魯卡謝維奇（JanLukasiewicz），前綴表達(dá)式被稱作波蘭表達(dá)式，后綴表達(dá)式稱為逆波蘭表達(dá)式（ReversePolishNotation）。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5波蘭表達(dá)式、逆波蘭表達(dá)式、

魯卡謝維奇（JanLukasiewicz）21Dec.1878–13Feb.19561920

PolishnotationTherootoftheideaoftherecursivestack,proposedbyTurning,Bauer,Hamblin,andfirstimplementedin1957LedtoEnglishElectricmulti-programmedKDF9computersystem(twohardwarestacks)of1963FridenEC-130ElectronicCalculator1963(第一個(gè)使用逆波蘭表達(dá)式的計(jì)算器）當(dāng)時(shí)售價(jià)$2200Itssuccessors:manyHewlettPackardcalculators,andForthprogramminglanguage北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6

FridenEC-130A13-digitcapacityandA5-inchCRTdisplay$2200北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7摩爾定律是由英特爾（Intel）創(chuàng)始人之一戈登·摩爾（GordonMoore）提出來(lái)的。其內(nèi)容為：當(dāng)價(jià)格不變時(shí)，集成電路上可容納的晶體管數(shù)目，約每隔18個(gè)月便會(huì)增加一倍，性能也將提升一倍。換言之，每一美元所能買到的電腦性能，將每隔18個(gè)月翻一倍以上。這一定律揭示了信息技術(shù)進(jìn)步的速度。盡管這種趨勢(shì)已經(jīng)持續(xù)了超過(guò)半個(gè)世紀(jì)，摩爾定律仍應(yīng)該被認(rèn)為是觀測(cè)或推測(cè)，而不是一個(gè)物理或自然法。預(yù)計(jì)定律將持續(xù)到至少2015年或2020年。然而，2010年國(guó)際半導(dǎo)體技術(shù)發(fā)展路線圖的更新增長(zhǎng)已經(jīng)放緩在2013年年底，之后的時(shí)間里晶體管數(shù)量密度預(yù)計(jì)只會(huì)每三年翻一番。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8中綴表達(dá)的算術(shù)表達(dá)式的計(jì)算次序

(1)先執(zhí)行括號(hào)內(nèi)的計(jì)算，后執(zhí)行括號(hào)外的計(jì)算。在具有多層括號(hào)時(shí)，按層次反復(fù)地脫括號(hào)，左右括號(hào)必須配對(duì)。(2)在無(wú)括號(hào)或同層括號(hào)時(shí)，先乘(*)、除(／)，后作加(+)、減(-)。(3)在同一個(gè)層次，若有多個(gè)乘除（*、／）或加減(+，-)的運(yùn)算，那就按自左至右順序執(zhí)行。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page9“中綴式”對(duì)“后綴式”中綴表達(dá)式：運(yùn)算符在中間需要括號(hào)改變優(yōu)先級(jí)

4*y*(2*y+a)–c計(jì)算機(jī)處理表達(dá)式的難點(diǎn)（嵌套）括號(hào)的處理（無(wú)括號(hào)或同層括號(hào)）運(yùn)算符的優(yōu)先級(jí)后綴表達(dá)式運(yùn)算符在后面優(yōu)勢(shì)：去掉運(yùn)算符優(yōu)先級(jí)與括號(hào)的影響4y*2y*a+*c–北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10“后綴”方式

計(jì)算表達(dá)式“中綴表達(dá)式”轉(zhuǎn)換為等價(jià)的“后綴表達(dá)式”需要括號(hào)改變優(yōu)先級(jí)，括號(hào)如何處理？運(yùn)算符的優(yōu)先級(jí)如何處理？“后綴表達(dá)式”求值北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11“后綴表達(dá)式”求值a*b+c*(d+e)=>ab*cde+*+-a+-b*+c=>a!b!c#*+構(gòu)建另外一個(gè)數(shù)據(jù)棧(DataStack,i.e.DS)從左至右掃描后綴表達(dá)式存儲(chǔ)器DTD若DTD讀出的是運(yùn)算量，則壓入數(shù)據(jù)棧DS；若DTD讀出的是符號(hào)，則從數(shù)據(jù)棧DS中彈出相應(yīng)的數(shù)據(jù)進(jìn)行運(yùn)算；再把結(jié)果壓回?cái)?shù)據(jù)棧DS；若返回結(jié)果就是棧DS中唯一的數(shù)據(jù)，完成了逆波蘭表達(dá)式的全部計(jì)算過(guò)程。當(dāng)DS中存在唯一數(shù)據(jù)時(shí)，DTD中還會(huì)有數(shù)據(jù)存在嗎？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12“中綴表達(dá)式”轉(zhuǎn)換為

等價(jià)的“后綴表達(dá)式”a*b+c*(d+e)=>ab*cde+*+-a+-b*+c=>a!b!c#*+(注：為區(qū)別減法運(yùn)算與加法運(yùn)算，用!表示負(fù)號(hào)，#表示正號(hào))“后綴表達(dá)式”構(gòu)建器由兩個(gè)主要組件組成：目標(biāo)表達(dá)式的存儲(chǔ)器(DestData,i.e.,DTD)符號(hào)棧(NotationStack,i.e.NS)掃描源表達(dá)式，存儲(chǔ)器DTD是從左向右儲(chǔ)存數(shù)據(jù)；而符號(hào)棧則遵守后進(jìn)先出的原則北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13轉(zhuǎn)換階段，中綴表達(dá)式的括號(hào)如何處理？如果是左括號(hào)"("，則直接入符號(hào)棧NS；如果是右括號(hào)“)”，則彈出符號(hào)棧NS數(shù)據(jù)，寫(xiě)入目標(biāo)表達(dá)式的存儲(chǔ)器DTD，直到左括號(hào)彈出。a*b+c*(d+e)=>ab*cde+*+“中綴表達(dá)式”轉(zhuǎn)換為

等價(jià)的“后綴表達(dá)式”處理括號(hào)帶來(lái)的運(yùn)算符優(yōu)先級(jí)改變無(wú)括號(hào)或同層括號(hào)內(nèi)的運(yùn)算符優(yōu)先級(jí)處理？北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page14“中綴表達(dá)式”至“后綴表達(dá)式”轉(zhuǎn)換流程（1）如果是單目運(yùn)算符，直接入符號(hào)棧NS；（2）如果是操作數(shù)，則直接寫(xiě)入存儲(chǔ)器DTD；檢查符號(hào)棧NS頂是否有單目運(yùn)算符，有的話則全部出棧，并寫(xiě)入存儲(chǔ)器DTD；（3）如果是左括號(hào)“(”，則直接入符號(hào)棧NS；（4）如果是右括號(hào)“)”，先判斷符號(hào)棧NS是否為空，若為空（括號(hào)不匹配），應(yīng)該當(dāng)錯(cuò)誤異常處理，清棧退出。若非空，則把符號(hào)棧NS中的元素依次彈出，直到遇到第一個(gè)左括號(hào)為止，將彈出的元素輸出到后綴表達(dá)式的DTD序列中（彈出的左括號(hào)不放到序列中）;若沒(méi)有遇到左括號(hào)，說(shuō)明括號(hào)不匹配，做異常處理，清棧退出。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15（5）如果是普通運(yùn)算符，則與NS棧頂符號(hào)比較優(yōu)先級(jí)，若大于棧頂優(yōu)先級(jí)，則入NS棧；否則彈出棧頂符號(hào)并寫(xiě)入存儲(chǔ)器DTD，直到NS棧頂符號(hào)運(yùn)算優(yōu)先級(jí)變小，遇到左括號(hào)、或棧空為止；

入棧可以實(shí)現(xiàn)“先進(jìn)后出”的符號(hào)順序；大于棧頂優(yōu)先級(jí)的符號(hào)A(比如*,/)入棧，可以在將來(lái)的出棧過(guò)程中，A優(yōu)先于之前的低級(jí)符號(hào)(比如+,-)得到計(jì)算；

如果與棧頂符號(hào)優(yōu)先級(jí)相等，先不入棧；彈出符號(hào)至存儲(chǔ)器，直到棧頂?shù)膬?yōu)先級(jí)變小（遇到左括號(hào)，或棧空）；然后再入棧；從而實(shí)現(xiàn)同級(jí)運(yùn)算符的從左到右計(jì)算原則;2.如果小于棧頂符號(hào)優(yōu)先級(jí)，先不入棧；彈出符號(hào)至存儲(chǔ)器，直到棧頂?shù)膬?yōu)先級(jí)變小（遇到左括號(hào),或?？眨蝗缓笤偃霔?。“中綴表達(dá)式”至“后綴表達(dá)式”轉(zhuǎn)換流程北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16（5）如果是普通運(yùn)算符，則與棧頂符號(hào)比較優(yōu)先級(jí)。若大于棧頂優(yōu)先級(jí)，則入棧；否則彈出棧頂符號(hào)并寫(xiě)入存儲(chǔ)器DTD，直到棧頂符號(hào)的運(yùn)算優(yōu)先級(jí)變小、遇到左括號(hào)、或棧空為止；（6）如果是結(jié)束符（表示表達(dá)式已全部讀完），則符號(hào)棧NS全部彈出并寫(xiě)入存儲(chǔ)器DTD，若彈出的元素遇到開(kāi)括號(hào)時(shí)，則說(shuō)明括號(hào)不匹配，做錯(cuò)誤異常處理，清棧退出；否則，讀取數(shù)據(jù)進(jìn)入下個(gè)過(guò)程。“中綴表達(dá)式”至“后綴表達(dá)式”轉(zhuǎn)換流程北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17示例

a*b+c*(d+-e)轉(zhuǎn)換為“后綴”表達(dá)式ab*cde!+*+后綴表達(dá)式求值北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18TokenExpressionDestData（DTD）LIFOstacka*b+c*(d+-e)##a*b+c*(d+-e)#a#*b+c*(d+-e)#a#*b+c*(d+-e)#ab#*+c*(d+-e)#ab*#c*(d+-e)#ab*#+c*(d+-e)#ab*c#+*(d+-e)#ab*c#+*(d+-e)#ab*c#+*(d+-e)#ab*cd#+*(+-e)#ab*cd#+*(+!e)#ab*cd#+*(+!e)#ab*cde#+*(+!)#ab*cde!+#+*#ab*cde!+*+#ab*cde!+*+北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page19TokenExpressionDataStack

Compute

Descriptionab*cde!+*+#ab*cde!+*+#aValue->Stackb*cde!+*+#abValue->Stack*cde!+*+#a*bPopa,bcde!+*+#msetm=a*bcde!+*+#mcValue->Stackde!+*+#mcdValue->Stacke!+*+#mcdeValue->Stack!+*+#mcd!ePope+*+#mcdnsetn=!e+*+#mcd+nPopd,n*+#mcoseto=c+n*+#mc*oPopc,o+#mpsetp=c*o+#m+pPopm,p#rsetr=m+p#rcheckAccept!a*b+c*(d+-e)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20后綴計(jì)算器的類定義enumBoolean{False,True};typedefdoubleELEM;#include"astack.h"

//文件astack.h中有棧，類stack的定義classCalculator{public: Calculator(void){}；

//創(chuàng)建計(jì)算器實(shí)例，開(kāi)辟一個(gè)空棧

voidRun（void); //后綴表達(dá)式的讀入，在遇到＝符號(hào)，啟動(dòng)求值計(jì)算

voidClear（void); //計(jì)算器的清除，為隨后的下一次計(jì)算作準(zhǔn)備北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21 private: StackS;//這個(gè)棧是用于壓入保存操作數(shù)，元素是double類型

voidEnter(doublenum);//把一個(gè)浮點(diǎn)數(shù)num壓入棧

BooleanGetTwoOperands(double&opnd1,double&opnd2); //從棧頂彈出兩個(gè)操作數(shù)，賦值給變量引用opnd1和opnd2 voidCompute(charop);//調(diào)用GetTwoOperands，

//

并按op運(yùn)算，對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22//把一個(gè)浮點(diǎn)數(shù)num壓入棧voidCalculator::Enter(doublenum) { S.Push(num); }//計(jì)算器的清除voidCalculator::Clear(void){

S.ClearStack();}后綴計(jì)算器的類

程序?qū)崿F(xiàn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23BooleanCalculator::GetTwoOperands(double&opnd1,double&opnd2){ if(S.IsEmpty()){ cerr<<"Missingoperand!"<<endl; returnFalse; } opnd1=S.Pop();//右操作數(shù)

if(S.IsEmpty()){ cerr<<"Missingoperand!"<<endl; returnFalse; } opnd2=S.Pop();//左操作數(shù)

returnTrue;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24//調(diào)用GetTwoOperands，//并依據(jù)op類型對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算voidpute（charop）{ Booleanresult; doubleoperand1,operand2; result=GetTwoOperands(operand1,operand2); if(result==True) switch(op) {北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25 case'+':S.Push(operand2+operand1); break; case'-':S.Push(operand2-operand1); break;

case'*':S.Push(operand2*operand1);

break;

case‘/’:if(operand1==0.0)//右操作數(shù)==0.0

{

cerr<<"Dividedby0!"<<endl;

S.ClearStack(); } else

S.Push(operand2/operand1);

break;

}

else S.ClearStack();//if(result==False)}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26//后綴表達(dá)式的讀入，在遇到＝符號(hào)，啟動(dòng)求值計(jì)算voidCalculator::Run(void){ charc; doublenewoperand; while(cin>>c&&c!='=')北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27 switch(c){ case'+': case'-': case'*': case'/': Compute(c); break; default: cin.putback(c); cin>>newoperand; Enter(newoperand); break; }//switchends if(!S.IsEmpty())

cout<<S.GetTop()<<endl;//印出求值的最后結(jié)果}putback會(huì)把cin剛剛“吃”進(jìn)來(lái)的字符再“吐”回去，也就是說(shuō)，下次cin>>x的時(shí)候，剛剛得到的那個(gè)字符還可用于”讀入?yún)?shù)”。請(qǐng)注意:輸入浮點(diǎn)數(shù)newoperand過(guò)程中,可以采用兩種方式分割不同的操作數(shù)1）輸入一個(gè)合法操作數(shù)，敲“回車”結(jié)束當(dāng)前操作數(shù)的輸入,終止cin讀入的過(guò)程,然后運(yùn)行至break處,

開(kāi)始while的新一輪循環(huán)。（一次輸入一個(gè)操作數(shù)，然后回車結(jié)束）；或者2）使用"空格"分隔多個(gè)操作數(shù)，同樣使用"回車"終止cin讀入過(guò)程，沒(méi)有讀至當(dāng)前newoperand的數(shù)字仍然保留在cin流中，供下次操作數(shù)讀入使用(-即在下一個(gè)循環(huán)中的cin>>newoperand語(yǔ)句處讀入，如果仍未讀完，在之后的循環(huán)繼續(xù)讀入）。（一次輸入一批操作數(shù)，操作數(shù)之間用空格分開(kāi)，最后用回車結(jié)束）。因?yàn)閏in的讀入變量序列是以空格為分隔的，當(dāng)你輸入一個(gè)空格時(shí)，那他就認(rèn)為后面的輸入不屬于當(dāng)前變量了，認(rèn)為應(yīng)該給后面的變量。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28大綱2.5棧(stack)2.5.1順序棧

2.5.2鏈?zhǔn)綏?/p>

2.5.3順序棧與鏈?zhǔn)綏５谋容^

2.5.4棧的應(yīng)用——后綴表達(dá)式求值2.6隊(duì)列(queue)2.6.1順序隊(duì)列

2.6.2鏈?zhǔn)疥?duì)列

2.2.3順序隊(duì)列與鏈?zhǔn)疥?duì)列的比較

2.7棧與遞歸(recursivefunction)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page292.6隊(duì)列(queue)

限制訪問(wèn)點(diǎn)的線性表

‘加入’新元素時(shí)，限于表的一端進(jìn)行（隊(duì)列的尾端）

元素的‘取出’則被限制于表的另一端（隊(duì)列的前端）

“先進(jìn)先出表”(FIFO，F(xiàn)irstInFirstOut)

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page30隊(duì)列的應(yīng)用

郵件緩沖器

計(jì)算機(jī)的硬設(shè)備之間的通信需要數(shù)據(jù)緩沖

北京大學(xué)