數(shù)據(jù)結(jié)構(gòu)-課件第3章棧和隊(duì)列

3和隊(duì)兩種特殊的線性表——棧和隊(duì)棧棧棧的邏輯結(jié)棧：限定僅在表的一端進(jìn)行和刪除操作的線性允 （a1,a2,……, 棧 棧棧棧棧的邏輯結(jié)入入出棧 ：入棧、進(jìn)棧棧 刪除：出棧、彈棧棧棧的邏輯結(jié)入入出棧 ：入棧、進(jìn)棧棧 刪除：出棧、彈棧棧的操作特性：后進(jìn)先棧的邏輯結(jié)情況棧棧cba棧cba棧棧棧的邏輯結(jié)情況cba出棧序列cba棧棧 出棧序列：c、棧 出棧序列：c、b、棧棧的邏輯結(jié)情況ba出棧序列ba棧棧的邏輯結(jié)情況ca出棧序列ca棧 出棧序列：b、棧棧 出棧序列：b、c、注注意：棧只是對(duì)制，并沒(méi)有限和刪除操作的位置進(jìn)行了和刪除操作進(jìn)行的時(shí)棧的抽象數(shù)據(jù)類型定ADTStack棧中元素具有相同類型及后進(jìn)先出特性相鄰元素具有前驅(qū)和后繼關(guān)前置條件：棧不輸入：后置條件：構(gòu)造一個(gè)空棧的抽象數(shù)據(jù)類型定后置條件：棧所占用的空功能：在棧頂一個(gè)元素輸出：如果不成功，拋出異后置條件：如果成功，棧頂增加了一個(gè)元棧的抽象數(shù)據(jù)類型定功能：刪除棧輸出：如果刪除成功，返回被刪元素值，否則，拋出異后置條件：如果刪除成功，棧減少了一個(gè)元功能：當(dāng)前的棧頂元輸出：若棧不空，返回當(dāng)前的棧頂元素后置條件：棧不棧的抽象數(shù)據(jù)類型定功能：判斷棧是否為輸出：如果棧為空，返回1，否則，返回0后置條件：棧不變棧的順序結(jié)構(gòu)及實(shí)順序?！獥５捻樞蚪Y(jié)如何改造數(shù)組實(shí)現(xiàn)棧的順序012345678確定確定用數(shù)組的哪一端表示棧底附設(shè)指針top指示棧頂元素在數(shù)組中的位置棧的順序結(jié)構(gòu)及實(shí)012345678

進(jìn)棧：top加進(jìn)棧：top加?？眨簍op=-出棧出棧：top減棧滿：top=MAX_SIZE-constintMAX_SIZE=100;template<classDataType>classseqStackseqStack()~seqStack(voidPush(DataTypex); Pop(); GetTop();boolEmpty();DataTypedata[MAX_SIZE];inttop;}順序棧的實(shí)現(xiàn)——入操作接口voidPushDataTypextemplate<classvoidseqStack<DataType>::Push(DataType{data[top]=iftopMAX_SIZE-1)throwdata[top]=data[++top]=}時(shí)間復(fù)雜度順序棧的實(shí)現(xiàn)——出操作接口DataTypePop(template<classDataTypeseqStack<DataType>::Pop({iftop-1)throw“溢出”;x=data[top--];return}時(shí)間復(fù)雜度兩棧共享空兩個(gè)棧，如何順序這兩個(gè)棧？解決方案直接解決：為每個(gè)棧開辟一個(gè)數(shù)組空間順序棧單向延伸——使用一個(gè)數(shù)組來(lái)兩個(gè)兩棧共享空兩棧共享空間：使用一個(gè)數(shù)組來(lái)兩個(gè)棧，讓一個(gè)兩棧共享空012…S-………棧1

棧2棧1的底固定在下標(biāo)為0的一端棧2的底固定在下標(biāo)為StackSize-1的一top1和top2分別為棧1和棧2的棧頂指針Stack_Size為整個(gè)數(shù)組空間的大?。▓D中用S表示兩棧共享空012…S-………

什么時(shí)候棧1

top1=-1兩棧共享空012012…S-………什么時(shí)候棧2

top1=-1top2=

兩棧共享空012…S-…………

什么時(shí)候棧1

top1=-什么時(shí)候棧2為空 top2=什么時(shí)候棧滿 top2={BothStack(~BothStack(voidPush(inti,DataTypex);DataTypePop(inti);DataTypeGetTop(inti);boolEmpty(inti);inttop1,top2;兩棧共享空間的實(shí)現(xiàn)操作接口：voidPush(inti,DataTypex)如果棧滿，則拋出上溢異常判斷是插在棧1還是棧若在棧1，top1加在top1處填入若在棧2，top2減在top2處填入兩棧共享空間的實(shí)現(xiàn)——?jiǎng)h操作接口：DataTypePop(inti)若是在棧1刪除，若棧1為空棧，拋出下溢異刪除并返回棧1的棧頂元素若是在棧2若棧2為空棧，拋出下溢異刪除并返回棧2的棧頂元素棧的結(jié)構(gòu)及實(shí)鏈棧：棧的結(jié)如何改造鏈表實(shí)現(xiàn)棧的∧將哪一端作為棧頂？將鏈頭作為棧頂，方便操作鏈棧需要加頭結(jié)點(diǎn)嗎？鏈棧不需要附設(shè)頭結(jié)棧的結(jié)構(gòu)及實(shí)鏈棧：棧 結(jié)∧an-an-棧

棧an-∧∧an-∧∧應(yīng)同一種狀態(tài)棧template<classDataType>classLinkStackLinkStack(~LinkStack(voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();Node<DataType>}鏈棧的實(shí)現(xiàn)template<classvoidtemplate<classvoidLinkStack<DataType>::Push(DataType{s=newNode<DataType>;s->data=x;s->next=top=}xaan-∧為什么沒(méi)有判斷棧滿∧鏈棧的實(shí)現(xiàn)操作接口DataTypePoptemplate<class

DataTypeLinkStack<DataType>::Pop({an-if(topNULL)throw"an-x=top-p=∧top=top-∧deletep;returnx;}top++可以嗎順序棧和鏈棧的比順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題隊(duì)隊(duì)列隊(duì)隊(duì)列的邏輯結(jié) （a1,a2,……,隊(duì) 隊(duì)出出a1a2a入3隊(duì)隊(duì)隊(duì)隊(duì)隊(duì)列的操作特性：先進(jìn)先隊(duì)隊(duì)隊(duì)列的抽象數(shù)據(jù)類型定ADTQueue相鄰元素具有前驅(qū)和后繼關(guān)系后置條件：創(chuàng)建一個(gè)空隊(duì)隊(duì)列的抽象數(shù)據(jù)類型定后置條件：隊(duì)列所占用的空功能：在隊(duì)入一個(gè)元輸出：如果不成功，拋出異后置條件：如果成功，隊(duì)尾增加了一個(gè)元隊(duì)列的抽象數(shù)據(jù)類型定功能：刪除隊(duì)頭元輸出：如果刪除成功，返回被刪元素后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元前置條件：隊(duì)列已存輸入：功能：隊(duì)頭元隊(duì)列的抽象數(shù)據(jù)類型定功能：判斷隊(duì)列是否為輸出：如果隊(duì)列為空，返回1，否則，返回后置條件：隊(duì)列不變隊(duì)列的順序結(jié)構(gòu)及實(shí)順序隊(duì)列——隊(duì)列的順序結(jié)出 入入隊(duì)操作時(shí)間性能為隊(duì)列的順序結(jié)構(gòu)及實(shí)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序？出 隊(duì)列的順序結(jié)構(gòu)及實(shí)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序？出 隊(duì)列的順序結(jié)構(gòu)及實(shí)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序？出 入出出隊(duì)操作時(shí)間性能為隊(duì)列的順序結(jié)構(gòu)及實(shí)如何改進(jìn)出隊(duì)的時(shí)間性能放寬隊(duì)放寬隊(duì)列的所有元素必條件，只要求隊(duì)列的元在數(shù)組的前n個(gè)單元這在數(shù)組中連續(xù)的位置設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指隊(duì)列的順序結(jié)構(gòu)及實(shí)例：a1a2a3a4依次出

隊(duì)尾指針rear入入隊(duì)操作時(shí)間性能仍為隊(duì)列的順序結(jié)構(gòu)及實(shí)例：a1a2依次出出 frontfront 出出隊(duì)操作時(shí)間性能提高為隊(duì)列的順序結(jié)構(gòu)及實(shí)例：a1a2依次出出 入 隊(duì)列的移動(dòng)有什么特點(diǎn)隊(duì)列的順序結(jié)構(gòu)及實(shí)例：a1a2依次出出 入 整個(gè)隊(duì)整個(gè)隊(duì)列向數(shù)組下標(biāo)較大單向移動(dòng)隊(duì)列的順序結(jié)構(gòu)及實(shí)繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況出 入

假溢出：假溢出：后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組 還隊(duì)列的順序結(jié)構(gòu)及實(shí)如何解決假溢出01234入01234入

循環(huán)隊(duì)列：將隊(duì)列的數(shù)組頭尾相接隊(duì)列的順序結(jié)構(gòu)及實(shí)如何實(shí)現(xiàn)循環(huán)隊(duì)出 不不存在物理的循環(huán)結(jié)構(gòu)，求模：（4＋1）mod方法實(shí)隊(duì)列的順序結(jié)構(gòu)及實(shí)出 入 隊(duì)列的順序結(jié)構(gòu)及實(shí)出 入frontfront隊(duì)隊(duì)空隊(duì)列的順序結(jié)構(gòu)及實(shí)出

隊(duì)列的順序結(jié)構(gòu)及實(shí)出

隊(duì)列的順序結(jié)構(gòu)及實(shí)為什么要將隊(duì)空和隊(duì)滿的判定條件分開方法二：附設(shè)一個(gè)隊(duì)列中元素個(gè)數(shù)的變量num，方法三：設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時(shí)為隊(duì)隊(duì)列的順序結(jié)構(gòu)及實(shí)現(xiàn)(隊(duì)滿用方法一判斷

入

入 隊(duì)隊(duì)滿的條件：(rear+1mod{CirQueue(~CirQueue(voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();boolEmpty()；intfront,rear;循環(huán)隊(duì)列的實(shí)現(xiàn)——入template<classvoidCirQueue<DataType>::EnQueue(DataType{if((rear+1QueueSizefrontthrow上溢";rear=(rear+1%QueueSize;data[rear]=}出 入

循環(huán)隊(duì)列的實(shí)現(xiàn)——出template<classDataTypeCirQueue<DataType>::DeQueue({if(rear==front)throw"下溢";frontfront1)QueueSize;returndata[front];}出

循環(huán)隊(duì)列的實(shí)現(xiàn)——讀隊(duì)頭元template<classDataTypeCirQueue<DataType>::GetQueue({ifrearfront)throw下溢";i=(front+1)%QueueSize;returndata[i];}出

隊(duì)列的結(jié)構(gòu)及實(shí)鏈隊(duì)列：隊(duì)列的結(jié)如何改造單鏈表實(shí)現(xiàn)隊(duì)列 ∧∧

隊(duì)列的結(jié)構(gòu)及實(shí)非空鏈隊(duì)∧∧空鏈隊(duì)∧∧template<classDataType>classLinkQueueLinkQueue(~LinkQueue(voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue()；boolEmpty()；鏈隊(duì)列的實(shí)現(xiàn)——構(gòu)造函操作接口LinkQueue(算法描述template<classDataType>LinkQueue<DataType>::LinkQueue(){front=newfront->next=NULL;rear=front;

∧∧}鏈隊(duì)列的實(shí)現(xiàn)——入∧x∧操作接口voidEnQueue(DataTypex);∧x∧如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣

rear

∧

∧∧xrear

算法描述鏈隊(duì)列的實(shí)現(xiàn)——入∧x∧操作接口voidEnQueue(DataType∧x∧如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣

rear算法描述鏈隊(duì)列的實(shí)現(xiàn)——入如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣

∧xrear∧x算法描述

算法描述鏈隊(duì)列的實(shí)現(xiàn)——入template<class{s=news->data=s->next=NULL;rear->next=s;rear=s;}鏈隊(duì)列的實(shí)現(xiàn)——出p∧∧算法描述鏈隊(duì)列的實(shí)現(xiàn)——出p∧∧考慮邊界情況：隊(duì)列中只有一個(gè)元素

如何判斷邊界情∧∧算法∧∧if(p->next==NULL)rear=front;鏈隊(duì)列的實(shí)現(xiàn)——出template<class{ifrearfront)throw下溢p=front->next;x=p->data;front->next=p-if(p->next==NULL)rear=deletep;returnx;}隊(duì)隊(duì)循環(huán)隊(duì)列和鏈隊(duì)列的比時(shí)間性能循環(huán)隊(duì)列和鏈隊(duì)列的基本操作都需要常數(shù)時(shí)間O(1)。循環(huán)隊(duì)列：必須預(yù)先確定一個(gè)固定的長(zhǎng)度，所以有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題鏈隊(duì)列：沒(méi)有隊(duì)列滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)隊(duì)列滿，但是每個(gè)元素都需要一應(yīng)用舉棧應(yīng)用的典型例——表達(dá)式求值的實(shí)遞迷宮求隊(duì)列的應(yīng)——打印三角表達(dá)式求值算表達(dá)式都是由操作數(shù)（opnd）運(yùn)算符（oor）和界限符（dliir）組成的。簡(jiǎn)單算術(shù)表達(dá)式的求值問(wèn)題——四則運(yùn)算，所有的運(yùn)算對(duì)象均為數(shù)，并以“#”為結(jié)束符常用算法——算符優(yōu)先法就是根據(jù)運(yùn)算符和界限符的優(yōu)先次序的規(guī)定來(lái)實(shí)現(xiàn)達(dá)式求值的算術(shù)四則運(yùn)算規(guī)則——先乘除從左算到右先括號(hào)中綴(infix)<操作數(shù)操作符><操作數(shù)>，前綴(prefix)表示——波蘭式表<操作符操作數(shù)操作數(shù)>，后綴(postfix)表示——逆波蘭式表<操作數(shù)操作數(shù)><操作符>，中綴表達(dá)式和后綴表達(dá)1)X- 2)5+(6-（字母表示運(yùn)算數(shù)1) 2)5642/-中綴到后中綴5+(6-到后綴5642/-3*+的轉(zhuǎn)5(6-4/2)*3+ 5(6-4/2)→564/2- 5642/-后綴表達(dá)式的作去掉中綴表達(dá)式的括隱含中綴表達(dá)式的運(yùn)算次其右邊最接近運(yùn)算符的先算的次序算結(jié)果放回原處

/3*/3*計(jì)算過(guò)

5642/-3* 562–3*543* 512 ←最后結(jié)應(yīng)用后綴表示計(jì)算表達(dá)式的從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)

/3*利用棧的計(jì)算后綴表達(dá)式的過(guò)棧55642/-3*5265345545 265345545結(jié)后綴表達(dá)式計(jì)算器的實(shí)classCalculator{Calculator(intsz=20):s(sz){};voidRun();//計(jì)算表達(dá)式voidClear();//清空計(jì)算器voidAddOperand(doublevalue);//操作數(shù)入棧BooleanGet2Operands(double&left,double& voidDoOperator(charop);//根據(jù)運(yùn)算符計(jì)算，結(jié)果入Stack<double>s;//voidCalculator::AddOperand(doublevalue){s.Push(value);//操作數(shù)入棧}BooleanCalculator::Get2Operands(double&left,double&cerr<<"Missingreturn}cerr<<"MissingOperand!"<<endl;returnFalse;}returnTrue;}doubleleft,right;Booleanresult;case'+':s.Push(left+right);break;case'-':s.Push(left-right);break;case'*':s.Push(left*right);break;casecerr<<"Dividedby0!"<<endl; elses.Push(left/right);break;case'^':s.Push(pow(left,right));}elsevoidcharch; case'+':case'-':case'*':case'/‘:case'^':DoOperator(ch);break;default:cin.putback(ch);}}assert(!s.Empty());//若棧底無(wú)數(shù)，錯(cuò)誤！終cout<<"Theresult//輸出結(jié)果（棧底元素}void}voidCalculatorcal(10);}中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)建立運(yùn)算符棧,并向棧底壓入#(若表達(dá)式以#結(jié)束從左向右依次讀入表達(dá)如果是運(yùn)算數(shù),則輸如果是操作符則按下面操運(yùn)算符出棧輸出直至棧頂運(yùn)算符優(yōu)先級(jí)低于棧外運(yùn)算符,棧外運(yùn)算符如棧.當(dāng)棧外為),棧內(nèi)運(yùn)算符退至(為當(dāng)棧外為#,棧內(nèi)運(yùn)算符退至#為算符優(yōu)先關(guān)算符——根據(jù)前述算術(shù)四則運(yùn)算三條規(guī)則，在運(yùn)算的每一步中，任意兩個(gè)相繼出現(xiàn)的算符p和p2之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一:op1<op2op1的優(yōu)先權(quán)低于op2op1=op2op1的優(yōu)先權(quán)等于op2op1>op2op1的優(yōu)先權(quán)高于算符間的優(yōu)先級(jí)關(guān)算符θ1在算符θ2前面。在算法中，相對(duì)應(yīng)于θ1在棧內(nèi)，θ2+—*/()#+>><<<>>—>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=利用棧的轉(zhuǎn)換過(guò)5+(6–4/2)* 5642/-3*)/-(+#+#(+#-)/-(+#+#(+#-(+#/-(+#*+##*+#+##中綴表達(dá)式求值將前面中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，及后綴表達(dá)式計(jì)算兩過(guò)程結(jié)合起來(lái)，利用所給的+、-、*、/、（、）、和#的算術(shù)運(yùn)算符間的優(yōu)先級(jí)的關(guān)系，可計(jì)算中綴表達(dá)式。設(shè)置兩個(gè)棧操作數(shù)棧（OPRD）。運(yùn)算符棧（OPTR）。#首先在運(yùn)算符棧中先在棧底壓入一個(gè)表達(dá)式的結(jié)束符#

表表達(dá)式求值算計(jì)算表達(dá)式:5+(6-4/2)*3#的過(guò)程↑首先在運(yùn)算符棧中先在棧底壓入一個(gè)表達(dá)式

#運(yùn)算數(shù)#

算符表表達(dá)式求值算計(jì)算表達(dá)式:5+(6-4/2)*3#的過(guò)程↑表達(dá)式第一個(gè)字符，是數(shù)，壓入運(yùn)算數(shù)

5運(yùn)算數(shù)5

#算符#表達(dá)式第2個(gè)字符優(yōu)先級(jí)：“+”>“#

5運(yùn)算數(shù)5

+#算符+#表表達(dá)式求值算計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第3個(gè)字符優(yōu)先級(jí)：在棧外“(”>“+

5運(yùn)算數(shù)5

(+#算(+#計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第4個(gè)字符65(+65(+#

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第5個(gè)字符優(yōu)先級(jí)：在棧外“–”>棧內(nèi)“(

65運(yùn)算數(shù)65

—(+#—(+#計(jì)算表達(dá)式564/2*3的過(guò)↑表達(dá)式第6個(gè)字符

465運(yùn)算465

—(+#—(+#計(jì)算表達(dá)式564/2*3的過(guò)↑表達(dá)式第7個(gè)字符優(yōu)先級(jí)：在棧外“/”>棧內(nèi)“–

465運(yùn)算465

/—(+/—(+#計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第8個(gè)字符

2465運(yùn)2465

/—(+/—(+#計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算2465/—(2465/—(+#

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算2465/—(2465/—(+#

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算65—(+#直至65—(+#

4/2=

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算265—(+#265—(+#

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算5(+#直至5(+#

6－2=

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第9個(gè)字符優(yōu)先級(jí)：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算45(+#直至45(+#

運(yùn)算數(shù)

算符計(jì)算表達(dá)式5642*3的過(guò)↑表達(dá)式第10個(gè)字優(yōu)先級(jí)：在棧外“*”>棧內(nèi)“+”，算符“*”入

45運(yùn)算數(shù)45

*+#算*+#計(jì)算表達(dá)式5642*3#的過(guò)↑表達(dá)式第11個(gè)字運(yùn)算數(shù)“3

345運(yùn)算345

*+#算*+#計(jì)算表達(dá)式5642*3#的過(guò)↑表達(dá)式第12個(gè)字優(yōu)先級(jí)：在棧外“#”<棧內(nèi)“*”，“*”出棧計(jì)

345運(yùn)算345

*+#算*+#計(jì)算表達(dá)式5642*3#的過(guò)↑表達(dá)式第12個(gè)字優(yōu)先級(jí)：在棧外“#”<棧內(nèi)“