山大數(shù)據(jù)結(jié)構(gòu)5精講課件

TheAbstractDataTypeDerivedClassesandInheritanceFormula-BasedRepresentationLinkedRepresentationApplicationsChapter5堆棧(Stacks)12/12/20221TheAbstractDataTypeChapter堆棧的實(shí)現(xiàn)堆棧的應(yīng)用本章重點(diǎn)12/12/20222堆棧的實(shí)現(xiàn)本章重點(diǎn)12/11/20222定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表的同一端進(jìn)行。允許插入和刪除的一端被稱為棧頂(top)，另一端被稱為棧底(bottom)。堆棧是一個(gè)后進(jìn)先出（last-in-first-out,LIFO）的數(shù)據(jù)結(jié)構(gòu)。堆棧(Stacks)12/12/20223定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表堆棧12/12/20224堆棧12/11/20224堆棧ADT12/12/20225堆棧ADT12/11/20225公式化描述(Formula-BasedRepresentation)效率、改進(jìn)鏈接描述(Linked)Representation效率比較堆棧12/12/20226公式化描述(Formula-BasedRepresenta堆棧數(shù)據(jù)對(duì)象是更通用的線性表對(duì)象的限制版本。(插入和刪除操作僅能在表的同一端進(jìn)行)例如，如果把表的左端定義為棧底，右端定義為棧頂，那么堆棧的添加操作等價(jià)于在表的右端進(jìn)行插入操作，刪除操作等價(jià)于在表的右端進(jìn)行刪除操作。繼承12/12/20227堆棧數(shù)據(jù)對(duì)象是更通用的線性表對(duì)象的限制版本。(插入和刪除操作template<classT>classStack::privateLinearList<T>{//LIFO對(duì)象public:Stack(intMaxStackSize=10):LinearList<T>(MaxStackSize){}boolIsEmpty()const {returnLinearList<T>::IsEmpty();}boolIsFull()const {return(Length()==GetMaxSize());}TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(Length(),x);returnx;}Stack<T>&Add(constT&x) {Insert(Length(),x);return*this;}Stack<T>&Delete(T&x) {LinearList<T>::Delete(Length(),x); return*this;}};公式化描述的堆棧類(派生)12/12/20228template<classT>公式化描述的堆棧類(派生)template<classT>classStack{//LIFO對(duì)象public: Stack(intMaxStackSize=10); ~Stack(){delete[]stack;} boolIsEmpty()const{returntop==-1;} boolIsFull()const{returntop==MaxTop;} TTop()const; Stack<T>&Add(constT&x); Stack<T>&Delete(T&x);private: inttop;//棧頂 intMaxTop;//最大的棧頂值 T*stack;//堆棧元素?cái)?shù)組};自定義Stack12/12/20229template<classT>自定義Stack12/11template<classT>Stack<T>::Stack(intMaxStackSize){ MaxTop=MaxStackSize-1; stack=newT[MaxStackSize]; top=-1;}Stack類構(gòu)造函數(shù)12/12/202210template<classT>Stack類構(gòu)造函數(shù)12template<classT>TStack<T>::Top()const{ if(IsEmpty())throwOutOfBounds(); elsereturnstack[top];}復(fù)雜性?返回棧頂元素12/12/202211template<classT>返回棧頂元素12/11/2template<classT>Stack<T>&Stack<T>::Add(constT&x){ if(IsFull())throwNoMem(); stack[++top]=x; return*this;}復(fù)雜性?添加元素x12/12/202212template<classT>添加元素x12/11/20template<classT>Stack<T>&Stack<T>::Delete(T&x){ if(IsEmpty())throwOutOfBounds(); x=stack[top--]; return*this;}復(fù)雜性?刪除棧頂元素，并將其送入x12/12/202213template<classT>刪除棧頂元素，并將其送入x哪一端對(duì)應(yīng)棧頂?鏈表描述12/12/202214哪一端對(duì)應(yīng)棧頂?鏈表描述12/11/202214template<classT>classLinkedStack:privateChain<T>{public:boolIsEmpty()const {returnChain<T>::IsEmpty();}boolIsFull()const;TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(1,x);returnx;}LinkedStack<T>&Add(constT&x) {Insert(0,x);return*this;}LinkedStack<T>&Delete(T&x) {Chain<T>::Delete(1,x);return*this;}};從Chain派生的鏈表形式的堆棧12/12/202215template<classT>從Chain派生的鏈表形式template<classT>boolLinkedStack<T>::IsFu11()const{//堆棧是否滿?try{ ChainNode<T>*p=newChainNode<T>; deletep; returnfalse; }catch(NoMem){returntrue;}}從Chain派生的鏈表形式的堆棧12/12/202216template<classT>從Chain派生的鏈表形式template<classT>classNode{friendLinkedStack<T>;private: Tdata; Node<T>*link;};自定義鏈表形式的堆棧12/12/202217template<classT>自定義鏈表形式的堆棧12template<classT>classLinkedStack{public:LinkedStack(){top=0;}~LinkedStack();boolIsEmpty()const{returntop==0;}boolIsFull()const;TTop()const;LinkedStack<T>&Add(constT&x);LinkedStack<T>&Delete(T&x);private:Node<T>*top;//指向棧頂節(jié)點(diǎn)}:自定義鏈表形式的堆棧12/12/202218template<classT>自定義鏈表形式的堆棧12/template<classT>LinkedStack<T>::~LinkedStack(){ Node<T>*next; while(top){ next=top->link; deletetop; top=next; }}析構(gòu)函數(shù)12/12/202219template<classT>析構(gòu)函數(shù)12/11/202template<classT>boolLinkedStack<T>::IsFu11()const{try{Node<T>*p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}堆棧是否滿?12/12/202220template<classT>堆棧是否滿?12/11/2template<classT>TLinkedStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();returntop->data;}返回棧頂元素12/12/202221template<classT>返回棧頂元素12/11/2template<classT>LinkedStack<T>&LinkedStack<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=top;top=p;return*this;}添加元素x12/12/202222template<classT>添加元素x12/11/20template<classT>LinkedStack<T>&LinkedStack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=top->data;Node<T>*p=top;top=top->link;deletep;return*this;}刪除棧頂元素，并將其送入x12/12/202223template<classT>刪除棧頂元素，并將其送入x鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作比較12/12/202224鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充比較12/11/202224括號(hào)匹配(ParenthesisMatching)漢諾塔(TowersofHanoi)火車車廂重排(RearrangingRailroadCars)開(kāi)關(guān)盒布線(SwitchBoxRouting)離線等價(jià)類(OfflineEquivalenceProblem)迷宮老鼠(RatinaMaze)應(yīng)用12/12/202225括號(hào)匹配(ParenthesisMatching)應(yīng)用12目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。例：字符串(a*(b+c)+d)例：字符串(a+b))(括號(hào)匹配12/12/202226目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)未匹配的左括號(hào)相匹配。如何實(shí)現(xiàn)？觀察12/12/202227如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)可以在從左至右的掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào)（如果存在）相匹配，同時(shí)從棧頂刪除該左括號(hào)。方法12/12/202228可以在從左至右的掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的底部堆放至頂部，需要把碟子都移動(dòng)到塔2，每次移動(dòng)一個(gè)碟子，而且任何時(shí)候都不能把大碟子放到小碟子的上面。漢諾塔問(wèn)題12/12/202229已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的為了把最大的碟子移動(dòng)到塔2，必須把其余n-1個(gè)碟子移動(dòng)到塔3，然后把最大的碟子移動(dòng)到塔2。接下來(lái)是把塔3上的n-1個(gè)碟子移動(dòng)到塔2，為此可以利用塔2和塔1?？梢酝耆鲆曀?上已經(jīng)有一個(gè)碟子的事實(shí)，因?yàn)檫@個(gè)碟子比塔3上將要移過(guò)來(lái)的任一個(gè)碟子都大，因此，可以在它上面堆放任何碟子。漢諾塔問(wèn)題-遞歸方法12/12/202230為了把最大的碟子移動(dòng)到塔2，必須把其余n-1個(gè)碟子移動(dòng)到塔voidTowersOfHanoi(intn,intx,inty,intz){//把n個(gè)碟子從塔x移動(dòng)到塔y，可借助于塔zif(n>0){ TowersOfHanoi(n-1,x,z,y);

cout<<"Movetopdiskfromtower"<<x<<"totopoftower"<<y<<endl; TowersOfHanoi(n-l,z,y,x);}}求解漢諾塔問(wèn)題的遞歸程序12/12/202231voidTowersOfHanoi(intn,int希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一步要求12/12/202232希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一classHanoi{friendvoidTowersOfHanoi(int);public: voidTowersOfHanoi(intn,intx,inty,intz);private: Stack<int>*S[4];};使用堆棧求解漢諾塔問(wèn)題12/12/202233classHanoi{使用堆棧求解漢諾塔問(wèn)題12/11/2voidHanoi::TowersOfHanoi(intn,intx,inty,intz){//把n個(gè)碟子從塔x移動(dòng)到塔y，可借助于塔z intd;//碟子編號(hào) if(n>0){ TowersOfHanoi(n-l,x,z,y); S[x]->Delete(d);//從x中移走一個(gè)碟子 S[y]->Add(d);//把這個(gè)碟子放到y(tǒng)上 ShowState(); TowersOfHanoi(n-l,z,y,x);}}使用堆棧求解漢諾塔問(wèn)題12/12/202234voidHanoi::TowersOfHanoi(intvoidTowersOfHanoi(intn){//Hanoi::towersOfHanoi的預(yù)處理程序HanoiX；X.S[1]=newStack<int>(n);X.S[2]=newStack<int>(n);X.S[3]=newStack<int>(n);for(intd=n;d>0;d--)//初始化X.S[1]->Add(d);//把碟子d放到塔1上//把塔1上的n個(gè)碟子移動(dòng)到塔2上，借助于塔3的幫助X.TowersOfHanoi(n,1,2,3);}使用堆棧求解漢諾塔問(wèn)題12/12/202235voidTowersOfHanoi(intn)使用堆棧求在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖鐵軌(位于入軌和出軌之間)?；疖囓噹嘏艈?wèn)題12/12/202236在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動(dòng)到緩沖鐵軌上，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。緩沖鐵軌按照何種方式使用?火車車廂重排方案12/12/202237從前至后依次檢查入軌上的所有車廂。火車車廂重排方案12/11boolRailroad(intp[],intn,intk){//k個(gè)緩沖鐵軌，車廂初始排序?yàn)閜[1:n]//如果重排成功，返回true，否則返回false//如果內(nèi)存不足，則引發(fā)異常NoMem。//創(chuàng)建與緩沖鐵軌對(duì)應(yīng)的堆棧LinkedStack<int>*H;H=newLinkedStack<int>[k+1];intNowOut=1;//下一次要輸出的車廂intminH=n+l;//緩沖鐵軌中編號(hào)最小的車廂intminS;//minH號(hào)車廂對(duì)應(yīng)的緩沖鐵軌火車車廂重排程序12/12/202238boolRailroad(intp[],intn,//車廂重排for(inti=1;i<=n;i++) if(p[i]==NowOut){//直接輸出t cout<<“將車廂”<<p[i]<<“從入軌移至出軌"<<endl;

NowOut++; //從緩沖鐵軌中輸出

while(minH==NowOut){

Output(minH,minS,H,k,n); NowOut++; } }else{//將p[i]送入某個(gè)緩沖鐵軌 if(!Hold(p[i],minH,minS,H,k,n)) returnfalse;}returntrue;}火車車廂重排程序12/12/202239//車廂重排火車車廂重排程序12/11/202239voidOutput(int&minH,int&minS,LinkedStack<int>H[],intk,intn){//把車廂從緩沖鐵軌送至出軌處，同時(shí)修改minS和minHintc;//車廂索引//從堆棧minS中刪除編號(hào)最小的車廂minHH[minS].Delete(c);cout<<"Movecar"<<minH<<"fromholdingtrack"<<minS<<"tooutput"<<endl;//通過(guò)檢查所有的棧頂，搜索新的minH和minSminH=n+2;for(inti=1;i<=k;i++) if(!H[i].IsEmpty()&&(c=H[i].Top())<minH){ minH=c; minS=i;}}Output函數(shù)12/12/202240voidOutput(int&minH,int&miboolHold(intc,int&minH,int&minS,LinkedStack<int>H[],intk,intn)(//在一個(gè)緩沖鐵軌中放入車廂c//如果沒(méi)有可用的緩沖鐵軌，則返回false//如果空間不足，則引發(fā)異常NoMem，否則返回true//為車廂c尋找最優(yōu)的緩沖鐵軌//初始化intBestTrack=0,//目前最優(yōu)的鐵軌BestTop=n+1,//最優(yōu)鐵軌上的頭輛車廂x;//車廂索引Hold函數(shù)12/12/202241boolHold(intc,int&minH,in//掃描緩沖鐵軌for(inti=1;i<=k;i++) if(!H[i].IsEmpty()){//鐵軌i不空 x=H[i].Top(); if(c<x&&x<BestTop){ //鐵軌i頂部的車廂編號(hào)最小 BestTop=x; BestTrack=i;} } else//鐵軌i為空 if(!BestTrack)BestTrack=i;Hold函數(shù)12/12/202242//掃描緩沖鐵軌Hold函數(shù)12/11/202242 if(!BestTrack)returnfalse;//沒(méi)有可用的鐵軌 //把車廂c送入緩沖鐵軌 H[BestTrack].Add(c); cout<<"Movecar"<<c<<"frominput""toholdingtrack"<<BestTrack<<endl; //必要時(shí)修改minH和minS if(c<minH){ minH=c; minS=BestTrack; } returntrue;}復(fù)雜性？Hold函數(shù)12/12/202243 if(!BestTrack)returnfalse;給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過(guò)布設(shè)一條金屬線路而實(shí)現(xiàn)互連。這條線路被稱為電線，被限制在矩形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會(huì)發(fā)生電流短路。所以，不允許電線間的交叉。每對(duì)互連的針腳被稱為網(wǎng)組。目標(biāo)是要確定對(duì)于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。開(kāi)關(guān)盒布線問(wèn)題12/12/202244給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過(guò)布設(shè)四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)可布線開(kāi)關(guān)盒(routableswitchbox)開(kāi)關(guān)盒布線示例12/12/202245四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)開(kāi)關(guān)當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。如果有一個(gè)網(wǎng)組，其兩個(gè)針腳分別位于這兩個(gè)不同的分區(qū)，那么這個(gè)網(wǎng)組是不可以布線的，因而整個(gè)電路也是不可布線的。如果沒(méi)有這樣的網(wǎng)組，則可以繼續(xù)判斷每個(gè)獨(dú)立的分區(qū)是不是可布線的。為此，可以從一個(gè)分區(qū)中取出一個(gè)網(wǎng)組，利用該網(wǎng)組把這個(gè)分區(qū)又分成兩個(gè)子分區(qū)，如果任一個(gè)網(wǎng)組的兩個(gè)針腳都分布在同一個(gè)子分區(qū)之中(即不會(huì)出現(xiàn)兩個(gè)針腳分別位于兩個(gè)子分區(qū)的情形)，那么這個(gè)分區(qū)就是可布線的。策略12/12/202246當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。策略12/11可以按順時(shí)針或反時(shí)針?lè)较蜓刂_(kāi)關(guān)盒的外圍進(jìn)行遍歷。例：按順時(shí)針?lè)较驈尼樐_1開(kāi)始遍歷，將依次檢查針腳1,2,...,8。針腳1和4屬于同一個(gè)網(wǎng)組，那么在針腳1至針腳4之間出現(xiàn)的所有針腳構(gòu)成了第一個(gè)分區(qū)，而在針腳4至針腳1之間未出現(xiàn)的所有針腳構(gòu)成了第二個(gè)分區(qū)。把針腳1放入堆棧，然后繼續(xù)處理，直至遇到針腳4。這個(gè)過(guò)程使我們僅在處理完一個(gè)分區(qū)之后才能進(jìn)入下一個(gè)分區(qū)。方案12/12/202247可以按順時(shí)針或反時(shí)針?lè)较蜓刂_(kāi)關(guān)盒的外圍進(jìn)行遍歷。方案12/輸入是元素?cái)?shù)目n、關(guān)系數(shù)目r以及r對(duì)關(guān)系，問(wèn)題的目標(biāo)是把n個(gè)元素分配至相應(yīng)的等價(jià)類。離線等價(jià)類問(wèn)題12/12/202248輸入是元素?cái)?shù)目n、關(guān)系數(shù)目r以及r對(duì)關(guān)系，問(wèn)題的目標(biāo)是把等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)在求解實(shí)際應(yīng)用問(wèn)題時(shí)常會(huì)遇到等價(jià)類問(wèn)題。從數(shù)學(xué)上看，等價(jià)類是一個(gè)對(duì)象(或成員)的集合，在此集合中所有對(duì)象應(yīng)滿足等價(jià)關(guān)系。若用符號(hào)“”表示集合上的等價(jià)關(guān)系，那么對(duì)于該集合中的任意對(duì)象x,y,

z，下列性質(zhì)成立：自反性：xx(即等于自身)。對(duì)稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

z。因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系。12/12/202249等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)在求解

“相等”(=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特性。一個(gè)集合S

中的所有對(duì)象可以通過(guò)等價(jià)關(guān)系劃分為若干個(gè)互不相交的子集S1,S2,S3,…，它們的并就是

S。這些子集即為等價(jià)類。確定等價(jià)類的方法分兩步走。第一步，讀入并存儲(chǔ)所有的等價(jià)對(duì)(i,j)；第二步，標(biāo)記和輸出所有的等價(jià)類。12/12/202250“相等”(=)就是一種等價(jià)關(guān)系，它滿足上述的三個(gè)特給定集合

S={0,1,2,3,4,5,6,7,8,9,10,11},及如下等價(jià)對(duì):

0

4,3

1,6

10,8

9,7

4,

6

8,3

5,2

11,11

012/12/202251給定集合S={0,1,2,3,4,5,6初始

{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}0

4

{0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}3

1

{0,4},{1,3},{2},{5},{6},{7},{8},{9},{10},{11}6

10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}

8

9

{0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}7

4

{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}6

8

{0,4,7},{1,3},{2},{5},{6,8,9,10},{11}3

5

{0,4,7},{1,3,5},{2},{6,8,9,10},{11}2

11{0,4,7},{1,3,5},{2,11},{6,8,9,10}11

0{0,2,4,7,11},{1,3,5},{6,8,9,10}12/12/202252初始{0},{1},{2},{3},{4},{5},{6}確定等價(jià)類的鏈表方法

設(shè)等價(jià)對(duì)個(gè)數(shù)為m，對(duì)象個(gè)數(shù)為n。一種可選的存儲(chǔ)表示為單鏈表?？蔀榧系拿恳粚?duì)象建立一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，并建立一個(gè)一維的指針數(shù)組seq[n]作為各單鏈表的表頭結(jié)點(diǎn)向量。seq[i]是第i個(gè)單鏈表的表頭結(jié)點(diǎn)，第i個(gè)單鏈表中所有結(jié)點(diǎn)的data域存放在等價(jià)對(duì)中與i等價(jià)的對(duì)象編號(hào)。

當(dāng)輸入一個(gè)等價(jià)對(duì)(i,j)后，就將集合元素i鏈入第j個(gè)單鏈表，且將集合元素j鏈入第i個(gè)單鏈表。在輸出時(shí)，設(shè)置一個(gè)布爾數(shù)組out[n]，用out[i]標(biāo)記第i個(gè)單鏈表是否已經(jīng)輸出。

12/12/202253確定等價(jià)類的鏈表方法設(shè)等價(jià)對(duì)個(gè)數(shù)為m，對(duì)象個(gè)數(shù)為n。算法的輸出從編號(hào)i=0的對(duì)象開(kāi)始，對(duì)所有的對(duì)象進(jìn)行檢測(cè)。在i=0時(shí)，循第0個(gè)單鏈表先找出形式為(0,j)的等價(jià)對(duì)，把0和j作為同一個(gè)等價(jià)類輸出。再根據(jù)等價(jià)關(guān)系的傳遞性，找所有形式為(j,k)的等價(jià)對(duì)，把k也納入包含0的等價(jià)類中輸出。如此繼續(xù)，直到包含0的等價(jià)類完全輸出為止。接下來(lái)再找一個(gè)未被標(biāo)記的編號(hào)，如i=1，該對(duì)象將屬于一個(gè)新的等價(jià)類，我們?cè)儆蒙鲜龇椒▌澐?、?biāo)記和輸出這個(gè)等價(jià)類。在算法中使用了一個(gè)棧。每次輸出一個(gè)對(duì)象編號(hào)時(shí)，都要把這個(gè)編號(hào)進(jìn)棧，記下以后還要檢測(cè)輸出的等價(jià)對(duì)象的單鏈表。12/12/202254算法的輸出從編號(hào)i=0的對(duì)象開(kāi)始，對(duì)所有的對(duì)象進(jìn)行檢輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容12/12/202255輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容12/11/20voidmain(void){//離線等價(jià)類問(wèn)題intn,r;//輸入n和rcout<<"Enternumberofelements"<<endl;cin>>n;if(n<2){cerr<<"Toofewelements"<<endl;exit(l);}cout<<"Enternumberofrelations"<<endl;cin>>r;if(r<1){cerr<<"Toofewrelations"<<endl;exit(l);}離線等價(jià)類程序(一)12/12/202256voidmain(void)離線等價(jià)類程序(一)12/11//創(chuàng)建一個(gè)指向n個(gè)鏈表的數(shù)組Chain<int>*chain;try{chain=newChain<int>[n+1];}catch(NoMem){cerr<<"Outofmemory"<<endl;exit(1);}//輸入r個(gè)關(guān)系，并存入鏈表for(inti=1;i<=r;i++){cout<<"Enternextrelation/pair"<<endl;inta,b;cin>>a>>b;chain[a].Insert(0,b);chain[b].Insert(0,a);}離線等價(jià)類程序(一)12/12/202257//創(chuàng)建一個(gè)指向n個(gè)鏈表的數(shù)組離線等價(jià)類程序(一)12/11//對(duì)欲輸出的等價(jià)類進(jìn)行初始化LinkedStack<int>stack;bool*out;try{out=newbool[n+1];}catch(NoMem){cerr<<"Outofmemory"<<endl;exit(l);}for(inti=1;i<=n;i++) out[i]=false;//輸出等價(jià)類for(inti=1;i<=n;i++) if(!out[i]){//開(kāi)始一個(gè)新的等價(jià)類 cout<<"Nextclassis:"<<i<<''; out[i]=true;

stack.Add(i);離線等價(jià)類程序(二)12/12/202258//對(duì)欲輸出的等價(jià)類進(jìn)行初始化離線等價(jià)類程序(二)12/11//從堆棧中取其余的元素while(!stack.IsEmpty()){ int*q,j;

stack.Delete(j); //鏈表chain[j]中的元素在同一個(gè)等價(jià)類中，使用遍歷器取這些元素 ChainIterator<int>c; q=c.Initialize(chain[j]); while(q){ if(!out[*q]){cout<<"q<<'';out[*q]=true;

stack.Add(*q);} q=c.Next(); }}cout<<endl;}cout<<endl<<"Endofclasslist"<<endl;}離線等價(jià)類程序(二)12/12/202259//從堆棧中取其余的元素離線等價(jià)類程序(二)12/11/20迷宮老鼠(ratinamaze)問(wèn)題要求尋找一條從入口到出口的路徑。路徑是由一組位置構(gòu)成的，每個(gè)位置上都沒(méi)有障礙，且每個(gè)位置(第一個(gè)除外)都是前一個(gè)位置的東、南、西或北的鄰居。迷宮老鼠問(wèn)題12/12/202260迷宮老鼠(ratinamaze)問(wèn)題要求尋找一條從入口假定用n×m的矩陣來(lái)描述迷宮，位置(1,1)表示入口，(n,m)表示出口，n和m分別代表迷宮的行數(shù)和列數(shù)。迷宮中的每個(gè)位置都可用其行號(hào)和列號(hào)來(lái)指定。在矩陣中，當(dāng)且僅當(dāng)在位置(i,j)處有一個(gè)障礙時(shí)其值為1，否則其值為0。迷宮的描述12/12/202261假定用n×m的矩陣來(lái)描述迷宮，位置(1,1)表示入口迷宮的描述12/12/202262迷宮的描述12/11/202262首先把迷宮的入口作為當(dāng)前位置。如果當(dāng)前位置是迷宮出口，那么已經(jīng)找到了一條路徑，搜索工作結(jié)束。如果當(dāng)前位置不是迷宮出口，則在當(dāng)前位置上放置障礙物，以便阻止搜索過(guò)程又繞回到這個(gè)位置。然后檢查相鄰的位置中是否有空閑的(即沒(méi)有障礙物)，如果有，就移動(dòng)到這個(gè)新的相鄰位置上，然后從這個(gè)位置開(kāi)始搜索通往出口的路徑。如果不成功，選擇另一個(gè)相鄰的空閑位置，并從它開(kāi)始搜索通往出口的路徑。如果所有相鄰的空閑位置都已經(jīng)被探索過(guò)，并且未能找到路徑，則表明在迷宮中不存在從入口到出口的路徑。方案12/12/202263首先把迷宮的入口作為當(dāng)前位置。方案12/11/202263對(duì)于迷宮內(nèi)部的位置(非邊界位置)，有四種可能的移動(dòng)方向：右、下、左和上。對(duì)于迷宮的邊界位置，只有兩種或三種可能的移動(dòng)。為了避免在處理內(nèi)部位置和邊界位置時(shí)存在差別，可以在迷宮的周圍增加一圈障礙物。簡(jiǎn)化算法12/12/202264對(duì)于迷宮內(nèi)部的位置(非邊界位置)，有四種可能的移動(dòng)方向：右、迷宮的描述12/12/202265迷宮的描述12/11/202265可以用行號(hào)和列號(hào)來(lái)指定每個(gè)迷宮位置，行號(hào)和列號(hào)被分別稱之為迷宮位置的行坐標(biāo)和列坐標(biāo)?？梢远x一個(gè)相應(yīng)的類Position來(lái)表示迷宮位置，它有兩個(gè)私有成員row和col。為保存從入口到當(dāng)前位置的路徑，可以采用以下基于公式化描述的堆棧： Stack<Position>path(MaxPathLength);其中MaxPathLength是指最大可能的路徑長(zhǎng)度（從入口到迷宮中任一位置）。位置表示12/12/202266可以用行號(hào)和列號(hào)來(lái)指定每個(gè)迷宮位置，行號(hào)和列號(hào)被分別稱之為迷按一種固定的方式來(lái)選擇可行的位置，將可以使問(wèn)題得到簡(jiǎn)化。例如，可以首先嘗試向右移動(dòng)，然后是向下，向左，最后是向上。移動(dòng)到相鄰位置的方法12/12/202267按一種固定的方式來(lái)選擇可行的位置，將可以使問(wèn)題得到簡(jiǎn)化。移動(dòng)移動(dòng)到相鄰位置的方法12/12/202268移動(dòng)到相鄰位置的方法12/11/202268假定maze、m(迷宮的大小)和path都是按如下方式定義的全局變量：int**maze,m;Stack<Position>*path;迷宮算法實(shí)現(xiàn)12/12/202269假定maze、m(迷宮的大小)和path都是按如下方式定義boolFindPath(){//尋找從位置(1,1)到出口(m,m)的路徑//如果成功則返回true，否則返回false//如果內(nèi)存不足則引發(fā)異常NoMempath=newStack<Position>(m*m-1);//對(duì)偏移量進(jìn)行初始化Positionoffset[4];offset[0].row=0;offset[0].col=1;//向右offset[l].row=1;offset[l].col=0;//向下offset[2].row=0;offset[2].col=-1;//向左offset[3].row=-1;offset[3].col=0;//向上搜索迷宮路徑的代碼12/12/202270boolFindPath()搜索迷宮路徑的代碼12/11///在迷宮周圍增加一圈障礙物for(inti=0;i<=m+l;i++){ maze[0][i]=maze[m+l][i]=1;//底和頂 maze[i][0]=maze[i][m+l]=1;//左和右}Positionhere;here.row=1;here.col=1;maze[i][i]=1;//阻止返回入口intoption=0;intLastOption=3;搜索迷宮路徑的代碼12/12/202271//在迷宮周圍增加一圈障礙物搜索迷宮路徑的代碼12/11/2//尋找一條路徑while(here.row!=m||here.col!=m){//不是出口 //尋找并移動(dòng)到一個(gè)相鄰位置 intr,c;

while(option<=LastOption){ r=here.row+offset[option].row; c=here.col+offset[option].col; if(maze[r][c]==0)break; option++;//下一個(gè)選擇 }搜索迷宮路徑的代碼12/12/202272//尋找一條路徑搜索迷宮路徑的代碼12/11/202272//找到一個(gè)相鄰位置了嗎?if(option<=LastOption){//移動(dòng)到maze[r][c]

path->Add(here); here.row=r;here.col=c; //設(shè)置障礙物以阻止再次訪問(wèn) maze[r][c]=1; option=0;}搜索迷宮路徑的代碼12/12/202273//找到一個(gè)相鄰位置了嗎?搜索迷宮路徑的代碼12/11/2else{//沒(méi)有可用的相鄰位置，回溯 if(path->IsEmpty())returnfalse; Positionnext; path->Delete(next); if(next.row==here.row)//here為next鄰居 option=2+next.col-here.col; elseoption=3+next.row-here.row; here=next;}}returntrue;//到達(dá)迷宮出口}搜索迷宮路徑的代碼12/12/202274else{//沒(méi)有可用的相鄰位置，回溯搜索迷宮路徑的代碼1迷宮問(wèn)題輸入：錄入或從文件讀取n*n迷宮方陣輸出：自(1,1)至(n,n)的路徑。輸出：自(1,1)至(n,n)的最短路徑。課程設(shè)計(jì)12/12/202275迷宮問(wèn)題課程設(shè)計(jì)12/11/202275課程設(shè)計(jì)題目姓名、學(xué)號(hào)、班級(jí)日期課程設(shè)計(jì)內(nèi)容描述:需求(輸入、輸出、功能、測(cè)試數(shù)據(jù))實(shí)現(xiàn)思想、算法描述使用說(shuō)明調(diào)試說(shuō)明實(shí)現(xiàn)代碼(帶注釋)課程設(shè)計(jì)報(bào)告要求12/12/202276課程設(shè)計(jì)題目課程設(shè)計(jì)報(bào)告要求12/11/202276堆棧的實(shí)現(xiàn)方式括號(hào)匹配漢諾塔火車車廂重排開(kāi)關(guān)盒布線離線等價(jià)類迷宮老鼠第五章總結(jié)12/12/202277堆棧的實(shí)現(xiàn)方式第五章總結(jié)12/11/202277TheAbstractDataTypeDerivedClassesandInheritanceFormula-BasedRepresentationLinkedRepresentationApplicationsChapter5堆棧(Stacks)12/12/202278TheAbstractDataTypeChapter堆棧的實(shí)現(xiàn)堆棧的應(yīng)用本章重點(diǎn)12/12/202279堆棧的實(shí)現(xiàn)本章重點(diǎn)12/11/20222定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表的同一端進(jìn)行。允許插入和刪除的一端被稱為棧頂(top)，另一端被稱為棧底(bottom)。堆棧是一個(gè)后進(jìn)先出（last-in-first-out,LIFO）的數(shù)據(jù)結(jié)構(gòu)。堆棧(Stacks)12/12/202280定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表堆棧12/12/202281堆棧12/11/20224堆棧ADT12/12/202282堆棧ADT12/11/20225公式化描述(Formula-BasedRepresentation)效率、改進(jìn)鏈接描述(Linked)Representation效率比較堆棧12/12/202283公式化描述(Formula-BasedRepresenta堆棧數(shù)據(jù)對(duì)象是更通用的線性表對(duì)象的限制版本。(插入和刪除操作僅能在表的同一端進(jìn)行)例如，如果把表的左端定義為棧底，右端定義為棧頂，那么堆棧的添加操作等價(jià)于在表的右端進(jìn)行插入操作，刪除操作等價(jià)于在表的右端進(jìn)行刪除操作。繼承12/12/202284堆棧數(shù)據(jù)對(duì)象是更通用的線性表對(duì)象的限制版本。(插入和刪除操作template<classT>classStack::privateLinearList<T>{//LIFO對(duì)象public:Stack(intMaxStackSize=10):LinearList<T>(MaxStackSize){}boolIsEmpty()const {returnLinearList<T>::IsEmpty();}boolIsFull()const {return(Length()==GetMaxSize());}TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(Length(),x);returnx;}Stack<T>&Add(constT&x) {Insert(Length(),x);return*this;}Stack<T>&Delete(T&x) {LinearList<T>::Delete(Length(),x); return*this;}};公式化描述的堆棧類(派生)12/12/202285template<classT>公式化描述的堆棧類(派生)template<classT>classStack{//LIFO對(duì)象public: Stack(intMaxStackSize=10); ~Stack(){delete[]stack;} boolIsEmpty()const{returntop==-1;} boolIsFull()const{returntop==MaxTop;} TTop()const; Stack<T>&Add(constT&x); Stack<T>&Delete(T&x);private: inttop;//棧頂 intMaxTop;//最大的棧頂值 T*stack;//堆棧元素?cái)?shù)組};自定義Stack12/12/202286template<classT>自定義Stack12/11template<classT>Stack<T>::Stack(intMaxStackSize){ MaxTop=MaxStackSize-1; stack=newT[MaxStackSize]; top=-1;}Stack類構(gòu)造函數(shù)12/12/202287template<classT>Stack類構(gòu)造函數(shù)12template<classT>TStack<T>::Top()const{ if(IsEmpty())throwOutOfBounds(); elsereturnstack[top];}復(fù)雜性?返回棧頂元素12/12/202288template<classT>返回棧頂元素12/11/2template<classT>Stack<T>&Stack<T>::Add(constT&x){ if(IsFull())throwNoMem(); stack[++top]=x; return*this;}復(fù)雜性?添加元素x12/12/202289template<classT>添加元素x12/11/20template<classT>Stack<T>&Stack<T>::Delete(T&x){ if(IsEmpty())throwOutOfBounds(); x=stack[top--]; return*this;}復(fù)雜性?刪除棧頂元素，并將其送入x12/12/202290template<classT>刪除棧頂元素，并將其送入x哪一端對(duì)應(yīng)棧頂?鏈表描述12/12/202291哪一端對(duì)應(yīng)棧頂?鏈表描述12/11/202214template<classT>classLinkedStack:privateChain<T>{public:boolIsEmpty()const {returnChain<T>::IsEmpty();}boolIsFull()const;TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(1,x);returnx;}LinkedStack<T>&Add(constT&x) {Insert(0,x);return*this;}LinkedStack<T>&Delete(T&x) {Chain<T>::Delete(1,x);return*this;}};從Chain派生的鏈表形式的堆棧12/12/202292template<classT>從Chain派生的鏈表形式template<classT>boolLinkedStack<T>::IsFu11()const{//堆棧是否滿?try{ ChainNode<T>*p=newChainNode<T>; deletep; returnfalse; }catch(NoMem){returntrue;}}從Chain派生的鏈表形式的堆棧12/12/202293template<classT>從Chain派生的鏈表形式template<classT>classNode{friendLinkedStack<T>;private: Tdata; Node<T>*link;};自定義鏈表形式的堆棧12/12/202294template<classT>自定義鏈表形式的堆棧12template<classT>classLinkedStack{public:LinkedStack(){top=0;}~LinkedStack();boolIsEmpty()const{returntop==0;}boolIsFull()const;TTop()const;LinkedStack<T>&Add(constT&x);LinkedStack<T>&Delete(T&x);private:Node<T>*top;//指向棧頂節(jié)點(diǎn)}:自定義鏈表形式的堆棧12/12/202295template<classT>自定義鏈表形式的堆棧12/template<classT>LinkedStack<T>::~LinkedStack(){ Node<T>*next; while(top){ next=top->link; deletetop; top=next; }}析構(gòu)函數(shù)12/12/202296template<classT>析構(gòu)函數(shù)12/11/202template<classT>boolLinkedStack<T>::IsFu11()const{try{Node<T>*p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}堆棧是否滿?12/12/202297template<classT>堆棧是否滿?12/11/2template<classT>TLinkedStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();returntop->data;}返回棧頂元素12/12/202298template<classT>返回棧頂元素12/11/2template<classT>LinkedStack<T>&LinkedStack<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=top;top=p;return*this;}添加元素x12/12/202299template<classT>添加元素x12/11/20template<classT>LinkedStack<T>&LinkedStack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=top->data;Node<T>*p=top;top=top->link;deletep;return*this;}刪除棧頂元素，并將其送入x12/12/2022100template<classT>刪除棧頂元素，并將其送入x鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作比較12/12/2022101鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充比較12/11/202224括號(hào)匹配(ParenthesisMatching)漢諾塔(TowersofHanoi)火車車廂重排(RearrangingRailroadCars)開(kāi)關(guān)盒布線(SwitchBoxRouting)離線等價(jià)類(OfflineEquivalenceProblem)迷宮老鼠(RatinaMaze)應(yīng)用12/12/2022102括號(hào)匹配(ParenthesisMatching)應(yīng)用12目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。例：字符串(a*(b+c)+d)例：字符串(a+b))(括號(hào)匹配12/12/2022103目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)未匹配的左括號(hào)相匹配。如何實(shí)現(xiàn)？觀察12/12/2022104如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)可以在從左至右的掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào)（如果存在）相匹配，同時(shí)從棧頂刪除該左括號(hào)。方法12/12/2022105可以在從左至右的掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的底部堆放至頂部，需要把碟子都移動(dòng)到塔2，每次移動(dòng)一個(gè)碟子，而且任何時(shí)候都不能把大碟子放到小碟子的上面。漢諾塔問(wèn)題12/12/2022106已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的為了把最大的碟子移動(dòng)到塔2，必須把其余n-1個(gè)碟子移動(dòng)到塔3，然后把最大的碟子移動(dòng)到塔2。接下來(lái)是把塔3上的n-1個(gè)碟子移動(dòng)到塔2，為此可以利用塔2和塔1。可以完全忽視塔2上已經(jīng)有一個(gè)碟子的事實(shí)，因?yàn)檫@個(gè)碟子比塔3上將要移過(guò)來(lái)的任一個(gè)碟子都大，因此，可以在它上面堆放任何碟子。漢諾塔問(wèn)題-遞歸方法12/12/2022107為了把最大的碟子移動(dòng)到塔2，必須把其余n-1個(gè)碟子移動(dòng)到塔voidTowersOfHanoi(intn,intx,inty,intz){//把n個(gè)碟子從塔x移動(dòng)到塔y，可借助于塔zif(n>0){ TowersOfHanoi(n-1,x,z,y);

cout<<"Movetopdiskfromtower"<<x<<"totopoftower"<<y<<endl; TowersOfHanoi(n-l,z,y,x);}}求解漢諾塔問(wèn)題的遞歸程序12/12/2022108voidTowersOfHanoi(intn,int希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一步要求12/12/2022109希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一classHanoi{friendvoidTowersOfHanoi(int);public: voidTowersOfHanoi(intn,intx,inty,intz);private: Stack<int>*S[4];};使用堆棧求解漢諾塔問(wèn)題12/12/2022110classHanoi{使用堆棧求解漢諾塔問(wèn)題12/11/2voidHanoi::TowersOfHanoi(intn,intx,inty,intz){//把n個(gè)碟子從塔x移動(dòng)到塔y，可借助于塔z intd;//碟子編號(hào) if(n>0){ TowersOfHanoi(n-l,x,z,y); S[x]->Delete(d);//從x中移走一個(gè)碟子 S[y]->Add(d);//把這個(gè)碟子放到y(tǒng)上 ShowState(); TowersOfHanoi(n-l,z,y,x);}}使用堆棧求解漢諾塔問(wèn)題12/12/2022111voidHanoi::TowersOfHanoi(intvoidTowersOfHanoi(intn){//Hanoi::towersOfHanoi的預(yù)處理程序HanoiX；X.S[1]=newStack<int>(n);X.S[2]=newStack<int>(n);X.S[3]=newStack<int>(n);for(intd=n;d>0;d--)//初始化X.S[1]->Add(d);//把碟子d放到塔1上//把塔1上的n個(gè)碟子移動(dòng)到塔2上，借助于塔3的幫助X.TowersOfHanoi(n,1,2,3);}使用堆棧求解漢諾塔問(wèn)題12/12/2022112voidTowersOfHanoi(intn)使用堆棧求在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖鐵軌(位于入軌和出軌之間)?；疖囓噹嘏艈?wèn)題12/12/2022113在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動(dòng)到緩沖鐵軌上，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。緩沖鐵軌按照何種方式使用?火車車廂重排方案12/12/2022114從前至后依次檢查入軌上的所有車廂?；疖囓噹嘏欧桨?2/11boolRailroad(intp[],intn,intk){//k個(gè)緩沖鐵軌，車廂初始排序?yàn)閜[1:n]//如果重排成功，返回true，否則返回false//如果內(nèi)存不足，則引發(fā)異常NoMem。//創(chuàng)建與緩沖鐵軌對(duì)應(yīng)的堆棧LinkedStack<int>*H;H=newLinkedStack<int>[k+1];intNowOut=1;//下一次要輸出的車廂intminH=n+l;//緩沖鐵軌中編號(hào)最小的車廂intminS;//minH號(hào)車廂對(duì)應(yīng)的緩沖鐵軌火車車廂重排程序12/12/2022115boolRailroad(intp[],intn,//車廂重排for(inti=1;i<=n;i++) if(p[i]==NowOut){//直接輸出t cout<<“將車廂”<<p[i]<<“從入軌移至出軌"<<endl;

NowOut++; //從緩沖鐵軌中輸出

while(minH==NowOut){

Output(minH,minS,H,k,n); NowOut++; } }else{//將p[i]送入某個(gè)緩沖鐵軌 if(!Hold(p[i],minH,minS,H,k,n)) returnfalse;}returntrue;}火車車廂重排程序12/12/2022116//車廂重排火車車廂重排程序12/11/202239voidOutput(int&minH,int&minS,LinkedStack<int>H[],intk,intn){//把車廂從緩沖鐵軌送至出軌處，同時(shí)修改minS和minHintc;//車廂索引//從堆棧minS中刪除編號(hào)最小的車廂minHH[minS].Delete(c);cout<<"Movecar"<<minH<<"fromholdingtrack"<<minS<<"tooutput"<<endl;//通過(guò)檢查所有的棧頂，搜索新的minH和minSminH=n+2;for(inti=1;i<=k;i++) if(!H[i].IsEmpty()&&(c=H[i].Top())<minH){ minH=c; minS=i;}}Output函數(shù)12/12/2022117voidOutput(int&minH,int&miboolHold(intc,int&minH,int&minS,LinkedStack<int>H[],intk,intn)(//在一個(gè)緩沖鐵軌中放入車廂c//如果沒(méi)有可用的緩沖鐵軌，則返回false//如果空間不足，則引發(fā)異常NoMem，否則返回true//為車廂c尋找最優(yōu)的緩沖鐵軌//初始化intBestTrack=0,//目前最優(yōu)的鐵軌BestTop=n+1,//最優(yōu)鐵軌上的頭輛車廂x;//車廂索引Hold函數(shù)12/12/2022118boolHold(intc,int&minH,in//掃描緩沖鐵軌for(inti=1;i<=k;i++) if(!H[i].IsEmpty()){//鐵軌i不空 x=H[i].Top(); if(c<x&&x<BestTop){ //鐵軌i頂部的車廂編號(hào)最小 BestTop=x; BestTrack=i;} } else//鐵軌i為空 if(!BestTrack)BestTrack=i;Hold函數(shù)12/12/2022119//掃描緩沖鐵軌Hold函數(shù)12/11/202242 if(!BestTrack)returnfalse;//沒(méi)有可用的鐵軌 //把車廂c送入緩沖鐵軌 H[BestTrack].Add(c); cout<<"Movecar"<<c<<"frominput""toholdingtrack"<<BestTrack<<endl; //必要時(shí)修改minH和minS if(c<minH){ minH=c; minS=BestTrack; } returntrue;}復(fù)雜性？Hold函數(shù)12/12/2022120 if(!BestTrack)returnfalse;給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過(guò)布設(shè)一條金屬線路而實(shí)現(xiàn)互連。這條線路被稱為電線，被限制在矩形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會(huì)發(fā)生電流短路。所以，不允許電線間的交叉。每對(duì)互連的針腳被稱為網(wǎng)組。目標(biāo)是要確定對(duì)于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。開(kāi)關(guān)盒布線問(wèn)題12/12/2022121給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過(guò)布設(shè)四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)可布線開(kāi)關(guān)盒(routableswitchbox)開(kāi)關(guān)盒布線示例12/12/2022122四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)開(kāi)關(guān)當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。如果有一個(gè)網(wǎng)組，其兩個(gè)針腳分別位于這兩個(gè)不同的分區(qū)，那么這個(gè)網(wǎng)組是不可以布線的，因而整個(gè)電路也是不可布線的。如果沒(méi)有這樣的網(wǎng)組，則可以繼續(xù)判斷每個(gè)獨(dú)立的分區(qū)是不是可布線的。為此，可以從一個(gè)分區(qū)中取出一個(gè)網(wǎng)組，利用該網(wǎng)組把這個(gè)分區(qū)又分成兩個(gè)子分區(qū)，如果任一個(gè)網(wǎng)組的兩個(gè)針腳都分布在同一個(gè)子分區(qū)之中(即不會(huì)出現(xiàn)兩個(gè)針腳分別位于兩個(gè)子分區(qū)的情形)，那么這個(gè)分區(qū)就是可布線的。策略12/12/2022123當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。策略12/11可以按順時(shí)針或反時(shí)針?lè)较蜓刂_(kāi)關(guān)盒的外圍進(jìn)行遍歷。例：按順時(shí)針?lè)较驈尼樐_1開(kāi)始遍歷，將依次檢查針腳1,2,...,8。針腳1和4屬于同一個(gè)網(wǎng)組，那么在針腳1至針腳4之間出現(xiàn)的所有針腳構(gòu)成了第一個(gè)分區(qū)，而在針腳4至針腳1之間未出現(xiàn)的所有針腳構(gòu)成了第二個(gè)分區(qū)。把針腳1放入堆棧，然后繼續(xù)處理，直至遇到針腳4。這個(gè)過(guò)程使我們僅在處理完一個(gè)分區(qū)之后才能進(jìn)入下一個(gè)分區(qū)。方案12/12/2022124可以按順時(shí)針或反時(shí)針?lè)较蜓刂_(kāi)關(guān)盒的外圍進(jìn)行遍歷。方案12/輸入是元素?cái)?shù)目n、關(guān)系