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

TheAbstractDataTypeDerivedClassesandInheritanceFormula-BasedRepresentationLinkedRepresentationApplicationsChapter5堆棧(Stacks)9/2/20231TheAbstractDataTypeChapter堆棧的實(shí)現(xiàn)堆棧的應(yīng)用本章重點(diǎn)9/2/20232堆棧的實(shí)現(xiàn)本章重點(diǎn)8/2/20232定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表的同一端進(jìn)行。允許插入和刪除的一端被稱為棧頂(top)，另一端被稱為棧底(bottom)。堆棧是一個(gè)后進(jìn)先出（last-in-first-out,LIFO）的數(shù)據(jù)結(jié)構(gòu)。堆棧(Stacks)9/2/20233定義堆棧是一個(gè)線性表，其插入(也稱為添加)和刪除操作都在表堆棧9/2/20234堆棧8/2/20234堆棧ADT9/2/20235堆棧ADT8/2/20235公式化描述(Formula-BasedRepresentation)效率、改進(jìn)鏈接描述(Linked)Representation效率比較堆棧9/2/20236公式化描述(Formula-BasedRepresenta堆棧數(shù)據(jù)對(duì)象是更通用的線性表對(duì)象的限制版本。(插入和刪除操作僅能在表的同一端進(jìn)行)例如，如果把表的左端定義為棧底，右端定義為棧頂，那么堆棧的添加操作等價(jià)于在表的右端進(jìn)行插入操作，刪除操作等價(jià)于在表的右端進(jìn)行刪除操作。繼承9/2/20237堆棧數(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;}};公式化描述的堆棧類(派生)9/2/20238template<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ù)組};自定義Stack9/2/20239template<classT>自定義Stack8/2/2template<classT>Stack<T>::Stack(intMaxStackSize){ MaxTop=MaxStackSize-1; stack=newT[MaxStackSize]; top=-1;}Stack類構(gòu)造函數(shù)9/2/202310template<classT>Stack類構(gòu)造函數(shù)8/template<classT>TStack<T>::Top()const{ if(IsEmpty())throwOutOfBounds(); elsereturnstack[top];}復(fù)雜性?返回棧頂元素9/2/202311template<classT>返回棧頂元素8/2/202template<classT>Stack<T>&Stack<T>::Add(constT&x){ if(IsFull())throwNoMem(); stack[++top]=x; return*this;}復(fù)雜性?添加元素x9/2/202312template<classT>添加元素x8/2/2023template<classT>Stack<T>&Stack<T>::Delete(T&x){ if(IsEmpty())throwOutOfBounds(); x=stack[top--]; return*this;}復(fù)雜性?刪除棧頂元素，并將其送入x9/2/202313template<classT>刪除棧頂元素，并將其送入x哪一端對(duì)應(yīng)棧頂?鏈表描述9/2/202314哪一端對(duì)應(yīng)棧頂?鏈表描述8/2/202314template<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派生的鏈表形式的堆棧9/2/202315template<classT>從Chain派生的鏈表形式template<classT>boolLinkedStack<T>::IsFu11()const{//堆棧是否滿?try{ ChainNode<T>*p=newChainNode<T>; deletep; returnfalse; }catch(NoMem){returntrue;}}從Chain派生的鏈表形式的堆棧9/2/202316template<classT>從Chain派生的鏈表形式template<classT>classNode{friendLinkedStack<T>;private: Tdata; Node<T>*link;};自定義鏈表形式的堆棧9/2/202317template<classT>自定義鏈表形式的堆棧8/template<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)}:自定義鏈表形式的堆棧9/2/202318template<classT>自定義鏈表形式的堆棧8/2template<classT>LinkedStack<T>::~LinkedStack(){ Node<T>*next; while(top){ next=top->link; deletetop; top=next; }}析構(gòu)函數(shù)9/2/202319template<classT>析構(gòu)函數(shù)8/2/20231template<classT>boolLinkedStack<T>::IsFu11()const{try{Node<T>*p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}堆棧是否滿?9/2/202320template<classT>堆棧是否滿?8/2/202template<classT>TLinkedStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();returntop->data;}返回棧頂元素9/2/202321template<classT>返回棧頂元素8/2/202template<classT>LinkedStack<T>&LinkedStack<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=top;top=p;return*this;}添加元素x9/2/202322template<classT>添加元素x8/2/2023template<classT>LinkedStack<T>&LinkedStack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=top->data;Node<T>*p=top;top=top->link;deletep;return*this;}刪除棧頂元素，并將其送入x9/2/202323template<classT>刪除棧頂元素，并將其送入x鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作比較9/2/202324鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充比較8/2/202324括號(hào)匹配(ParenthesisMatching)漢諾塔(TowersofHanoi)火車車廂重排(RearrangingRailroadCars)開關(guān)盒布線(SwitchBoxRouting)離線等價(jià)類(OfflineEquivalenceProblem)迷宮老鼠(RatinaMaze)應(yīng)用9/2/202325括號(hào)匹配(ParenthesisMatching)應(yīng)用8/目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。例：字符串(a*(b+c)+d)例：字符串(a+b))(括號(hào)匹配9/2/202326目標(biāo):輸入一個(gè)字符串，輸出相互匹配的括號(hào)以及未能匹配的括號(hào)。如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)未匹配的左括號(hào)相匹配。如何實(shí)現(xiàn)？觀察9/2/202327如果從左至右掃描一個(gè)字符串，那么每個(gè)右括號(hào)將與最近遇到的那個(gè)可以在從左至右的掃描過程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào)（如果存在）相匹配，同時(shí)從棧頂刪除該左括號(hào)。方法9/2/202328可以在從左至右的掃描過程中把所遇到的左括號(hào)存放到堆棧內(nèi)。每當(dāng)已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的底部堆放至頂部，需要把碟子都移動(dòng)到塔2，每次移動(dòng)一個(gè)碟子，而且任何時(shí)候都不能把大碟子放到小碟子的上面。漢諾塔問題9/2/202329已知n個(gè)碟子和3座塔。初始時(shí)所有的碟子按從大到小次序從塔1的為了把最大的碟子移動(dòng)到塔2，必須把其余n-1個(gè)碟子移動(dòng)到塔3，然后把最大的碟子移動(dòng)到塔2。接下來是把塔3上的n-1個(gè)碟子移動(dòng)到塔2，為此可以利用塔2和塔1?？梢酝耆鲆曀?上已經(jīng)有一個(gè)碟子的事實(shí)，因?yàn)檫@個(gè)碟子比塔3上將要移過來的任一個(gè)碟子都大，因此，可以在它上面堆放任何碟子。漢諾塔問題-遞歸方法9/2/202330為了把最大的碟子移動(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);}}求解漢諾塔問題的遞歸程序9/2/202331voidTowersOfHanoi(intn,int希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一步要求9/2/202332希望給出每次移動(dòng)之后三座塔的狀態(tài)（即塔上的碟子及其次序）進(jìn)一classHanoi{friendvoidTowersOfHanoi(int);public: voidTowersOfHanoi(intn,intx,inty,intz);private: Stack<int>*S[4];};使用堆棧求解漢諾塔問題9/2/202333classHanoi{使用堆棧求解漢諾塔問題8/2/202voidHanoi::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);}}使用堆棧求解漢諾塔問題9/2/202334voidHanoi::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);}使用堆棧求解漢諾塔問題9/2/202335voidTowersOfHanoi(intn)使用堆棧求在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖鐵軌(位于入軌和出軌之間)?；疖囓噹嘏艈栴}9/2/202336在一個(gè)轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動(dòng)到緩沖鐵軌上，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。緩沖鐵軌按照何種方式使用?火車車廂重排方案9/2/202337從前至后依次檢查入軌上的所有車廂?；疖囓噹嘏欧桨?/2/2boolRailroad(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)的緩沖鐵軌火車車廂重排程序9/2/202338boolRailroad(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;}火車車廂重排程序9/2/202339//車廂重排火車車廂重排程序8/2/202339voidOutput(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;//通過檢查所有的棧頂，搜索新的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ù)9/2/202340voidOutput(int&minH,int&miboolHold(intc,int&minH,int&minS,LinkedStack<int>H[],intk,intn)(//在一個(gè)緩沖鐵軌中放入車廂c//如果沒有可用的緩沖鐵軌，則返回false//如果空間不足，則引發(fā)異常NoMem，否則返回true//為車廂c尋找最優(yōu)的緩沖鐵軌//初始化intBestTrack=0,//目前最優(yōu)的鐵軌BestTop=n+1,//最優(yōu)鐵軌上的頭輛車廂x;//車廂索引Hold函數(shù)9/2/202341boolHold(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ù)9/2/202342//掃描緩沖鐵軌Hold函數(shù)8/2/202342 if(!BestTrack)returnfalse;//沒有可用的鐵軌 //把車廂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ù)9/2/202343 if(!BestTrack)returnfalse;給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過布設(shè)一條金屬線路而實(shí)現(xiàn)互連。這條線路被稱為電線，被限制在矩形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會(huì)發(fā)生電流短路。所以，不允許電線間的交叉。每對(duì)互連的針腳被稱為網(wǎng)組。目標(biāo)是要確定對(duì)于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。開關(guān)盒布線問題9/2/202344給定一個(gè)矩形布線區(qū)域，其外圍有若干針腳。兩個(gè)針腳之間通過布設(shè)四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)可布線開關(guān)盒(routableswitchbox)開關(guān)盒布線示例9/2/202345四個(gè)網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)開關(guān)當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。如果有一個(gè)網(wǎng)組，其兩個(gè)針腳分別位于這兩個(gè)不同的分區(qū)，那么這個(gè)網(wǎng)組是不可以布線的，因而整個(gè)電路也是不可布線的。如果沒有這樣的網(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ū)就是可布線的。策略9/2/202346當(dāng)兩個(gè)針腳互連時(shí)，其電線把布線區(qū)分成兩個(gè)分區(qū)。策略8/2/2可以按順時(shí)針或反時(shí)針方向沿著開關(guān)盒的外圍進(jìn)行遍歷。例：按順時(shí)針方向從針腳1開始遍歷，將依次檢查針腳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è)過程使我們僅在處理完一個(gè)分區(qū)之后才能進(jìn)入下一個(gè)分區(qū)。方案9/2/202347可以按順時(shí)針或反時(shí)針方向沿著開關(guān)盒的外圍進(jìn)行遍歷。方案8/2輸入是元素?cái)?shù)目n、關(guān)系數(shù)目r以及r對(duì)關(guān)系，問題的目標(biāo)是把n個(gè)元素分配至相應(yīng)的等價(jià)類。離線等價(jià)類問題9/2/202348輸入是元素?cái)?shù)目n、關(guān)系數(shù)目r以及r對(duì)關(guān)系，問題的目標(biāo)是把等價(jià)關(guān)系與等價(jià)類(EquivalenceClass)在求解實(shí)際應(yīng)用問題時(shí)常會(huì)遇到等價(jià)類問題。從數(shù)學(xué)上看，等價(jià)類是一個(gè)對(duì)象(或成員)的集合，在此集合中所有對(duì)象應(yīng)滿足等價(jià)關(guān)系。若用符號(hào)“

”表示集合上的等價(jià)關(guān)系，那么對(duì)于該集合中的任意對(duì)象x,y,

z，下列性質(zhì)成立：自反性：x

x(即等于自身)。對(duì)稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

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

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

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

S。這些子集即為等價(jià)類。確定等價(jià)類的方法分兩步走。第一步，讀入并存儲(chǔ)所有的等價(jià)對(duì)(i,j)；第二步，標(biāo)記和輸出所有的等價(jià)類。9/2/202350“相等”(=)就是一種等價(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

09/2/202351給定集合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}9/2/202352初始{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)輸出。

9/2/202353確定等價(jià)類的鏈表方法設(shè)等價(jià)對(duì)個(gè)數(shù)為m，對(duì)象個(gè)數(shù)為n。算法的輸出從編號(hào)i=0的對(duì)象開始，對(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à)類完全輸出為止。接下來再找一個(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ì)象的單鏈表。9/2/202354算法的輸出從編號(hào)i=0的對(duì)象開始，對(duì)所有的對(duì)象進(jìn)行檢輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容9/2/202355輸入所有等價(jià)對(duì)后的seq數(shù)組及各單鏈表的內(nèi)容8/2/2023voidmain(void){//離線等價(jià)類問題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à)類程序(一)9/2/202356voidmain(void)離線等價(jià)類程序(一)8/2/2//創(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à)類程序(一)9/2/202357//創(chuàng)建一個(gè)指向n個(gè)鏈表的數(shù)組離線等價(jià)類程序(一)8/2/2//對(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]){//開始一個(gè)新的等價(jià)類 cout<<"Nextclassis:"<<i<<''; out[i]=true;

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