第5章-遞歸數(shù)據(jù)結(jié)構(gòu)課件

第5章遞歸1.遞歸的概念1)定義是遞歸的

2)數(shù)據(jù)結(jié)構(gòu)是遞歸的

3）問(wèn)題的解法是遞歸的2.迷宮問(wèn)題

3.遞歸過(guò)程的實(shí)現(xiàn)4.利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法5.廣義表(GeneralList)1)廣義表的概念(LS)2)廣義表的性質(zhì)3)廣義表的操作4)廣義表的存儲(chǔ)結(jié)構(gòu)5）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法6)廣義表的遞歸算法求廣義表的深度、判斷兩個(gè)廣義表相等否、廣義表的復(fù)制算法1/6/20231第5章遞歸12/1第5章遞歸1.遞歸的概念n!=1n=0n*(n-1)!n>0若一個(gè)對(duì)象部分地包含它自己或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的。若一個(gè)過(guò)程直接地或間接地調(diào)用自己，則稱這個(gè)過(guò)程是遞歸的過(guò)程。*測(cè)試終結(jié)遞歸的條件遞歸出口*n問(wèn)題化為n-1問(wèn)題（或著大問(wèn)題化為小問(wèn)題）1/6/20232第5章遞歸1.遞歸的概念n!=1n=0

三種常用到遞歸的方法

定義是遞歸的。數(shù)據(jù)結(jié)構(gòu)是遞歸的。問(wèn)題的解法是遞歸的。1)定義是遞歸的例1：如上面求n！的定義就是遞歸的。longfactorial(longn){if(n==0)return1;//遞歸終結(jié)條件elsereturnn*factorial(n-1);//n問(wèn)題化為n-1問(wèn)題}1/6/20233

三種常用到遞歸的方法

定義是遞歸的。12/11/下面看一下求factorial（3）F(3)f(2)f(1)f(0)

n=3n=2n=1n=06n*f(2)n*f(1)n*f(0)3*22*11*1n=3n=2n=11/6/20234下面看一下求factorial（3）F(3)例2斐波那契數(shù)列（Fibonacci)

0，1，1，2，3，5，8，……以fn表示數(shù)列中第n個(gè)數(shù)，fn的遞歸定義：n當(dāng)n=0，1時(shí)Fib(n)=Fib(n-1)+Fib(n-2)當(dāng)n>1時(shí)longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1/6/20235例2斐波那契數(shù)列（Fibonacci)12/11/2022）數(shù)據(jù)結(jié)構(gòu)是遞歸的鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu)。

datalinkfirst是一個(gè)單鏈表first……是一個(gè)單鏈表

指向的也是一個(gè)單鏈表

^^1/6/202362）數(shù)據(jù)結(jié)構(gòu)是遞歸的鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu)。^^12/數(shù)據(jù)結(jié)構(gòu)是遞歸的，則寫算法采用遞歸方法是最方便的。例1.查找非空單鏈表的最后一個(gè)結(jié)點(diǎn)并打印其數(shù)據(jù)域。template<classtype>voidfind(listnode<type>*f){if(flink==null)cout<<fdata<<endL;elsefind(flink);}例2.查找非空單鏈表中值為x的結(jié)點(diǎn)，并輸出之。template<classtype>voidprint(listnode<type>*f){if(f!=null)if(fdata==x)cout<<fdata<<endL;elseprint(flink);}

1/6/20237數(shù)據(jù)結(jié)構(gòu)是遞歸的，則寫算法采用遞歸方法是最方便的。例1.查找3）問(wèn)題的解法是遞歸的（Hanoi塔）

ABC從A柱移到C柱：每次移一片盤，而且不允許大盤在小盤上。分析：1.先將n-1個(gè)盤由AB(遞歸）2.將一個(gè)盤由AC3.將n-1個(gè)盤由BC(遞歸）n1/6/202383）問(wèn)題的解法是遞歸的（Hanoi塔）n12/11/#include<iostream.h>#include“strclass.h”//字符串類的原型文件VoidHanoi(intn,stringA,stringB,stringC){if(n==1)cout<<“move”<<A<<“to”<<C<<endL;else{Hanoi(n-1,A,C,B);//遞歸調(diào)用。cout<<“move”<<A<<“to”<<C<<endL;Hanoi(n-1,B,A,C);//遞歸調(diào)用}}1/6/20239#include<iostream.h>12/11/2022.迷宮問(wèn)題一個(gè)小型迷宮問(wèn)題。

457

326

11/6/2023102.迷宮問(wèn)題一個(gè)小型迷宮問(wèn)題。12/11/2022103.遞歸過(guò)程的實(shí)現(xiàn)以上兩個(gè)例子以及迷宮問(wèn)題可以看到1)遞歸程序十分短,十分簡(jiǎn)練,但讀起來(lái)不容易.2)有很多工作由編譯程序做了,編譯程序要開辟:參數(shù)棧,局部變量棧,返回地址棧函數(shù)名,引用參數(shù),數(shù)值參數(shù)

1/6/2023113.遞歸過(guò)程的實(shí)現(xiàn)12/11/2022115.4利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法數(shù)據(jù)結(jié)構(gòu):1.迷宮用二維數(shù)組表示maze[m][p],但在迷宮外面加一個(gè)圈,為墻壁.Maze[m+2][p+2]即行數(shù):0~m+1;列數(shù):0~p+1111111001001maze[i][j]=0表示該位置是通路110101maze[i][j]=1………………墻壁101011入口:maze[1][1]110111出口:maze[m][p]1011001111111/6/2023125.4利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法12/11/20222.從[i][j]位置,前進(jìn)的方向有8個(gè),可測(cè)探。[i-1][j-1][i-1][j][i-1][j+1][i][j-1][i][j][i][j+1][i+1][j-1][i+1][j][i+1][j+1]8個(gè)方向用枚舉類型來(lái)表示:enumdirections{N,NE,E,SE,S,SW,W,NW}3.向8個(gè)方向移動(dòng),其坐標(biāo)位置要變化,具體實(shí)現(xiàn)放其偏移量,即:1/6/20231312/11/202213Offsetmove[8]structoffsets{inta,b;};例如,若當(dāng)前位置為[i][j],向西南SW方向移動(dòng),則下一相鄰位置[g][h]為:g=i+move[SW].a;h=j+move[SW].b這里要指出的是,用枚舉類型中的數(shù)組作為下標(biāo)變量,這是一個(gè)技巧.實(shí)際上枚舉類型在機(jī)內(nèi)實(shí)現(xiàn)為整型數(shù)ab……..move1/6/202314Offsetmove[8]例如,若當(dāng)前位置為[i][j],4.為了防止重走老路,另外又建立了一個(gè)標(biāo)志矩陣mark[m+2][p+2],初始化時(shí)都為0,一旦走到迷宮的某個(gè)位置[i][j],則得mark[i][j]置為1.表示下次這個(gè)位置不能再走了。mark與maze矩陣大小一一對(duì)應(yīng).5.設(shè)立一個(gè)棧,存儲(chǔ)在試探過(guò)程中所走過(guò)的路徑,一旦要回溯,則從棧中取得剛才走過(guò)位置的坐標(biāo)和前進(jìn)方向.棧中需保存一個(gè)三元組xydirstructitems坐標(biāo)方向{intx,y,dir;}1/6/2023154.為了防止重走老路,另外又建立了一個(gè)標(biāo)志矩陣mark[m6.具體實(shí)現(xiàn)算法1.mark[1][1]=1;//[1][1]是入口2.stack<items>st(m*p);//開辟工作棧,大小為m*p3.itemstmp;//設(shè)一工作結(jié)構(gòu)變量tmp.x=1;tmp.y=1;tmp.dir=E;st.push(tmp);4.while(!st.IsEmpty()){1）tmp=st.pop();2)inti=tmp.x;intj=tmp.y;intd=tmp.dir1/6/2023166.具體實(shí)現(xiàn)算法12/11/2022163)while(d<8){i)intg=i+move[d].a;inth=j+move[d].b;ii)if(g==m&&h==p)//判別是否出口{輸出i,j,m,p;return;}iii)if(!maze[g][h]&&mark[g][h]){a.mark[g][h]=1;//表示向東走過(guò)該坐標(biāo)b.將(i,j,d+1進(jìn)棧)如果向東走下去,到某一步走不通,則有可能回退到i,j,則要換一個(gè)方向,即d+1(SE)東南c.從新的坐標(biāo)點(diǎn)i=g,j=h,d=N開始一個(gè)個(gè)方向試探}elsed++;//遇到墻或該坐標(biāo)已走過(guò),則換一個(gè)方向試.}}1/6/2023173)while(d<8)12/11/202215.廣義表(GeneralList)

1)廣義表的概念(LS)*定義:n(n>=0)個(gè)表元素a0,a1,a2,……an-1組成的有限序列。記作:LS=(a0,a1,a2,……an-1)

其中每個(gè)表元素ai可以是原子,也可以是子表。原子:某種類型的對(duì)象,在結(jié)構(gòu)上不可分。(用小寫字母表示)子表:有結(jié)構(gòu)的。(用大寫字母表示)*廣義表的長(zhǎng)度:表中元素的個(gè)數(shù)1/6/2023185.廣義表(GeneralList)12/11/202*廣義表的表頭(head)、表尾(tail)head=a0;tail=(a1,a2,……an-1)LS=（’a’,(‘b’,’a’,’b’),(),’c’,(((2))))*廣義表的深度:表中所含括號(hào)的最大層數(shù)1)A=();2)B=(6,2)3)C=(‘a(chǎn)’,(5,3,‘x’))表頭為‘a(chǎn)’,表尾為((5,3,‘x’))4)D=(B,C,A)5)E=(B,D)6)F=(4,F)遞歸的表1/6/202319*廣義表的表頭(head)、表尾(tail)12/11

2)廣義表的性質(zhì)有序性有長(zhǎng)度,有深度可遞歸,如上面例6可共享,如E中B為E,D所共享各種廣義表都可用一種示意圖來(lái)表示,用表示表元素,表示原子A62B‘a(chǎn)’53‘x’C1/6/2023202)廣義表的性質(zhì)A62B‘a(chǎn)’53‘x’C12/11/DBCA62‘a(chǎn)’53‘x’EBDCA62‘a(chǎn)’53‘x’F41/6/202321DBCA62‘a(chǎn)’53‘x’EBDCA62‘a(chǎn)’53‘x’F3)廣義表的操作例子:list1=(5,12,‘s’,47,‘a(chǎn)’)head(list)//取第一個(gè)元素tail(list)//tail(list1)=(12,‘s’,47,‘a(chǎn)’)first(list)//返回廣義表第一個(gè)元素的指針info(elem)//返回由elem指向的廣義表節(jié)點(diǎn)的值next(elem)//返回由elem指向的下一個(gè)節(jié)點(diǎn)的指針nodetype(elem)//返回由elem指向的廣義表節(jié)點(diǎn)的類型push(list,x)//將值為x的節(jié)點(diǎn)加入到廣義表list的最前端addon(list,x)//建立以x為頭,list為尾的新表setinfo(elem,x)//將表元素elem的值修改為xsethead(list,x)//將list的頭元素重置為x1/6/2023223)廣義表的操作12/11/202222

4)廣義表的存儲(chǔ)結(jié)構(gòu)用數(shù)組存儲(chǔ)顯然不合適,因數(shù)組元素不同構(gòu)用拉鏈,但各元素類型不一致;用不等長(zhǎng)節(jié)點(diǎn)不好.用等長(zhǎng)節(jié)點(diǎn)來(lái)表示,每個(gè)表節(jié)點(diǎn)用三個(gè)域組成.標(biāo)志域值域尾指針utypevaluetlink1/6/20232312/11/202223

utype=0:廣義表專用的表頭結(jié)點(diǎn)1:整型原子結(jié)點(diǎn)2:字符型原子結(jié)點(diǎn)3:子表節(jié)點(diǎn)值域隨著不同類型的節(jié)點(diǎn),存放不同的內(nèi)容,并用不同的名字來(lái)表示,實(shí)際上value部分可變的,用union實(shí)現(xiàn).utype=0,ref:存放引用計(jì)數(shù)utype=1,intgrinfo:存放整數(shù)值utype=2,charinfo:存放字符型數(shù)據(jù)utype=3,hlink:指向子表表頭的指針1/6/202324utype=0:廣義表專用的表頭結(jié)點(diǎn)12/1

tlink:當(dāng)utype=0,tlink指向該表(表可以是子表)第一個(gè)元素的結(jié)點(diǎn)當(dāng)utype!=0,tlink指向該值域同一層的下一個(gè)表結(jié)點(diǎn)例子:L=(3,(),(‘b’,‘c’),(((‘d’))))

utypereftlinkL0L13333^0^02b2c^

03^03^02‘d’^

1/6/202325tlink:當(dāng)utype=0,tlink指向該廣義表的類聲明:#defineHEAD0#defineINTGR1#defineCH2#defineLIST31/6/202326廣義表的類聲明:12/11/202226classGenList;classGenListNode{friendclassGenList;private:intutype;//=1/2/3,表示HEAD/INTGR/CH/LSTGenListNode*tlink;union{//聯(lián)合intref;intintgrinfo;charcharinfo;GenListNode*hlinkl}value;1/6/202327classGenList;12/11/202227Public:GenListNode&Info(GenListNode*elem);intnodetype(GenListNode*elem){returnelem-->utype;}voidsetInfo(GenListNode*elem,GenListNode&x);}廣義表的類聲明中:成員數(shù)據(jù):first它指向廣義表的表頭結(jié)點(diǎn)成員函數(shù):私有--copy，depth,equal,remove公有--Head,tail,First,Next,push,Addon等等

1/6/202328Public:12/11/2022285）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法廣義表結(jié)點(diǎn)類的存取成員函數(shù)GenListNode&GenListNode::info(GenListNode*elem){//返回表元素elem的值GenListNode*pitem=newGenListNode;pitem-->utype=elem-->utype;pitem-->value=elem-->value;return*pitem;}廣義表的一些成員函數(shù)

廣義表類的構(gòu)造函數(shù)

first01NULL1/6/2023295）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法first01NGenList::GenList(){GenListNode*first=newGenListNode;first-->utype=0;first-->value.ref=1;first-->tlink=NULL;}

Head()---返回廣義表的第一個(gè)元素值,若為空表,則為非法操作.GenListNode&GenList::Head(){if(first-->tlink==NULL){cout<<“Illegalheadoperation.”<<endl;exit(1);}else{GenListNode*temp=newGenListNode;temp-->utype=first-->tlink-->utype;temp-->value=first-->tlink-->value;return*temp;}}1/6/202330GenList::GenList()12/11/20

取廣義表的表尾---tail()(若是空表,則是非法操作)GenListGenList::Tail(){if(first-->tlink==NULL){cout<<“Illegaltailoperation.”<<endl;exit(1);}else{GenList*temp=newGenList;temp-->first-->tlink=first-->tlink-->tlink;return*temp;}}

1/6/202331取廣義表的表尾---tail()(若是空表,則構(gòu)造一個(gè)以x為第一個(gè)元素,list為尾的新表----AddonGenList&GenList::Addon(GenList&list,GenListNode&x){GenList*newList=newGenList;newList-->first=copy(list.first);x-->tlink=newList-->first-->tlink;newList-->first-->tlink=x;return*newlist;}重新定義廣義表的尾----setTailvoidGenList::setTail(GenList&list){GenListNode*temp;1/6/202332構(gòu)造一個(gè)以x為第一個(gè)元素,list為尾的新表----Addotemp=first-->tlink-->tlink;first-->tlink-->tlink=list.first-->tlink;deletelist.first;freelist(temp);}1/6/202333temp=first-->tlink-->tlin6)廣義表的遞歸算法遞歸算法:*遞歸函數(shù)的外部調(diào)用-----公有函數(shù)界面*遞歸函數(shù)的內(nèi)部調(diào)用-----私有函數(shù)真正實(shí)現(xiàn)部分求廣義表的深度廣義表的深度為廣義表中最大括號(hào)的重?cái)?shù)廣義表LS==(a0,a1,a2,……an-1),其中ai(0<=i<=n-1)或者是原子或者是子表.0當(dāng)LS為原子時(shí)遞歸結(jié)束條件Depth(LS)=1當(dāng)LS為空表時(shí)1+max{depth(a0),depth(a1),………depth(an-1)}1/6/2023346)廣義表的遞歸算法12/11/202234intGenList::depth()//公共函數(shù){returndepth(first);}intGenList::depth(GenListNode*ls)//私有函數(shù){if(ls-->tlink==NULL)return1;GenListNode*temp=ls-->tlink;intm=0;while(temp!=NULL){if(temp-->utype==LST){intn=depth(temp-->hlink);if(m<n)m=n;}temp=temp-->tlink;}returnm+1;}1/6/202335intGenList::depth()//公共函數(shù)

判斷兩個(gè)廣義表相等否相等的條件:具有相同的結(jié)構(gòu)對(duì)應(yīng)的數(shù)據(jù)元素具有相等的值if(兩個(gè)廣義表都為空表)return相等elseif(都為原子^值相等)遞歸比較同一層的后面的表元素elsereturn不相等1/6/20233612/11/202236

intoperator==(constGenList&l,constGenList&m){returnequal(l.first,m.first);}intequal(GenListNode*s,GenListNode*t){intx;if(s-->tlink==NULL&&t-->tlink==NULL)return1;if((s-->tlink!=NULL&&t-->tlink!=NULL&&s-->tlink-->utype==t-->tlink-->utype){if(s-->tlink-->utype==INTGR)if(s-->tlink-->grinfo==t-->tlink-->grinfo)x=1;elsex=0;elseif(s-->tlink-->utype==CH)if(s-->tlink-->value.charinfo==t-->tlink-->value.charinfo)x=1;elsex=0;elsex=equal(s-->tlink-->value.hlink,t-->tlink-->value.hlink);if(x)returnequal(s-->tlink,t-->tlink);}return0;}1/6/202337intoperator==(constGenList

廣義表的復(fù)制算法分別復(fù)制表頭,表尾,然后合成前提是廣義表不可以是共享表或遞歸表1/6/202338

voidGenList::copy(constGenList&l){first=copy(l.first);}GenListNode*GenList::copy(GenListNode*ls){GenListNode*q=NULL;if(ls!=NULL){q=newGenListNode;q-->utype=ls-->utype;Switch(ls-->utype){caseHEAD:q-->value.ref=ls-->value.ref;break;//表頭結(jié)點(diǎn)caseINTGR:q-->grinfo=ls-->grinfo;break;caseCH:q-->value.charinfo=ls-->value.charinfo;break;caseLST:q-->value.hlink=copy(ls-->value.hlink);break;}q-->tlink=copy(ls-->tlink);}returnq;}

1/6/202339voidGenList::copy(constGenL

廣義表的析構(gòu)函數(shù)---------~GenList()GenList::~GenList(){remove(first);}voidGenList::remove(GenListNode*ls){ls->value.ref--;if(!ls->value.ref){GenListNode*y=ls;while(y-->tlink!=NULL){y=y-->tlink;if(y-->utype==LST)remove(y-->hlink);}y-->tlink=av;av=ls;//回收頂層節(jié)點(diǎn)到可利用空間表中}}1/6/202340廣義表的析構(gòu)函數(shù)---------~GenList(1/6/20234112/11/202241習(xí)題、考研題：1.5-12.5-53.5-64.5-75.2003四.26.2004四.17.遞歸算法1）求廣義表的深度2）判別原子a是否屬于廣義表L=(b,(c,a),……)假設(shè)廣義表用單鏈表方式存放。每個(gè)結(jié)點(diǎn)三個(gè)域：1/6/202342習(xí)題、考研題：12/11/202242

當(dāng)tag=0時(shí)，data域?yàn)樵颖旧恚僭O(shè)為整型）tag=1時(shí)，hlink域指向子表的第一個(gè)元素ClassGenlistClassGenListNode;{friendclassGenList;private:inttag;GenListNode*tlink;Union{intdata;GenListNode*hlink;}value;public:…..}tagtlinkhlink/data1/6/202343

intmember(GenListNode*L;inta){intcheck=0;GenListNode*ptr=L;while((ptr!=NULL)&&(!check)){if(ptr->tag==1){check=member(ptr->value.hlink,a)if(check==0)ptr=ptr->tlink;}elseif(ptr->value.data==a)check=1;elseptr=ptr->tlink;}returncheck;}1/6/202344intmember(GenListNode*L;

第5章遞歸1.遞歸的概念1)定義是遞歸的

2)數(shù)據(jù)結(jié)構(gòu)是遞歸的

3）問(wèn)題的解法是遞歸的2.迷宮問(wèn)題

3.遞歸過(guò)程的實(shí)現(xiàn)4.利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法5.廣義表(GeneralList)1)廣義表的概念(LS)2)廣義表的性質(zhì)3)廣義表的操作4)廣義表的存儲(chǔ)結(jié)構(gòu)5）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法6)廣義表的遞歸算法求廣義表的深度、判斷兩個(gè)廣義表相等否、廣義表的復(fù)制算法1/6/202345第5章遞歸12/1第5章遞歸1.遞歸的概念n!=1n=0n*(n-1)!n>0若一個(gè)對(duì)象部分地包含它自己或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的。若一個(gè)過(guò)程直接地或間接地調(diào)用自己，則稱這個(gè)過(guò)程是遞歸的過(guò)程。*測(cè)試終結(jié)遞歸的條件遞歸出口*n問(wèn)題化為n-1問(wèn)題（或著大問(wèn)題化為小問(wèn)題）1/6/202346第5章遞歸1.遞歸的概念n!=1n=0

三種常用到遞歸的方法

定義是遞歸的。數(shù)據(jù)結(jié)構(gòu)是遞歸的。問(wèn)題的解法是遞歸的。1)定義是遞歸的例1：如上面求n！的定義就是遞歸的。longfactorial(longn){if(n==0)return1;//遞歸終結(jié)條件elsereturnn*factorial(n-1);//n問(wèn)題化為n-1問(wèn)題}1/6/202347

三種常用到遞歸的方法

定義是遞歸的。12/11/下面看一下求factorial（3）F(3)f(2)f(1)f(0)

n=3n=2n=1n=06n*f(2)n*f(1)n*f(0)3*22*11*1n=3n=2n=11/6/202348下面看一下求factorial（3）F(3)例2斐波那契數(shù)列（Fibonacci)

0，1，1，2，3，5，8，……以fn表示數(shù)列中第n個(gè)數(shù)，fn的遞歸定義：n當(dāng)n=0，1時(shí)Fib(n)=Fib(n-1)+Fib(n-2)當(dāng)n>1時(shí)longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1/6/202349例2斐波那契數(shù)列（Fibonacci)12/11/2022）數(shù)據(jù)結(jié)構(gòu)是遞歸的鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu)。

datalinkfirst是一個(gè)單鏈表first……是一個(gè)單鏈表

指向的也是一個(gè)單鏈表

^^1/6/2023502）數(shù)據(jù)結(jié)構(gòu)是遞歸的鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu)。^^12/數(shù)據(jù)結(jié)構(gòu)是遞歸的，則寫算法采用遞歸方法是最方便的。例1.查找非空單鏈表的最后一個(gè)結(jié)點(diǎn)并打印其數(shù)據(jù)域。template<classtype>voidfind(listnode<type>*f){if(flink==null)cout<<fdata<<endL;elsefind(flink);}例2.查找非空單鏈表中值為x的結(jié)點(diǎn)，并輸出之。template<classtype>voidprint(listnode<type>*f){if(f!=null)if(fdata==x)cout<<fdata<<endL;elseprint(flink);}

1/6/202351數(shù)據(jù)結(jié)構(gòu)是遞歸的，則寫算法采用遞歸方法是最方便的。例1.查找3）問(wèn)題的解法是遞歸的（Hanoi塔）

ABC從A柱移到C柱：每次移一片盤，而且不允許大盤在小盤上。分析：1.先將n-1個(gè)盤由AB(遞歸）2.將一個(gè)盤由AC3.將n-1個(gè)盤由BC(遞歸）n1/6/2023523）問(wèn)題的解法是遞歸的（Hanoi塔）n12/11/#include<iostream.h>#include“strclass.h”//字符串類的原型文件VoidHanoi(intn,stringA,stringB,stringC){if(n==1)cout<<“move”<<A<<“to”<<C<<endL;else{Hanoi(n-1,A,C,B);//遞歸調(diào)用。cout<<“move”<<A<<“to”<<C<<endL;Hanoi(n-1,B,A,C);//遞歸調(diào)用}}1/6/202353#include<iostream.h>12/11/2022.迷宮問(wèn)題一個(gè)小型迷宮問(wèn)題。

457

326

11/6/2023542.迷宮問(wèn)題一個(gè)小型迷宮問(wèn)題。12/11/2022103.遞歸過(guò)程的實(shí)現(xiàn)以上兩個(gè)例子以及迷宮問(wèn)題可以看到1)遞歸程序十分短,十分簡(jiǎn)練,但讀起來(lái)不容易.2)有很多工作由編譯程序做了,編譯程序要開辟:參數(shù)棧,局部變量棧,返回地址棧函數(shù)名,引用參數(shù),數(shù)值參數(shù)

1/6/2023553.遞歸過(guò)程的實(shí)現(xiàn)12/11/2022115.4利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法數(shù)據(jù)結(jié)構(gòu):1.迷宮用二維數(shù)組表示maze[m][p],但在迷宮外面加一個(gè)圈,為墻壁.Maze[m+2][p+2]即行數(shù):0~m+1;列數(shù):0~p+1111111001001maze[i][j]=0表示該位置是通路110101maze[i][j]=1………………墻壁101011入口:maze[1][1]110111出口:maze[m][p]1011001111111/6/2023565.4利用棧實(shí)現(xiàn)的迷宮問(wèn)題的非遞歸解法12/11/20222.從[i][j]位置,前進(jìn)的方向有8個(gè),可測(cè)探。[i-1][j-1][i-1][j][i-1][j+1][i][j-1][i][j][i][j+1][i+1][j-1][i+1][j][i+1][j+1]8個(gè)方向用枚舉類型來(lái)表示:enumdirections{N,NE,E,SE,S,SW,W,NW}3.向8個(gè)方向移動(dòng),其坐標(biāo)位置要變化,具體實(shí)現(xiàn)放其偏移量,即:1/6/20235712/11/202213Offsetmove[8]structoffsets{inta,b;};例如,若當(dāng)前位置為[i][j],向西南SW方向移動(dòng),則下一相鄰位置[g][h]為:g=i+move[SW].a;h=j+move[SW].b這里要指出的是,用枚舉類型中的數(shù)組作為下標(biāo)變量,這是一個(gè)技巧.實(shí)際上枚舉類型在機(jī)內(nèi)實(shí)現(xiàn)為整型數(shù)ab……..move1/6/202358Offsetmove[8]例如,若當(dāng)前位置為[i][j],4.為了防止重走老路,另外又建立了一個(gè)標(biāo)志矩陣mark[m+2][p+2],初始化時(shí)都為0,一旦走到迷宮的某個(gè)位置[i][j],則得mark[i][j]置為1.表示下次這個(gè)位置不能再走了。mark與maze矩陣大小一一對(duì)應(yīng).5.設(shè)立一個(gè)棧,存儲(chǔ)在試探過(guò)程中所走過(guò)的路徑,一旦要回溯,則從棧中取得剛才走過(guò)位置的坐標(biāo)和前進(jìn)方向.棧中需保存一個(gè)三元組xydirstructitems坐標(biāo)方向{intx,y,dir;}1/6/2023594.為了防止重走老路,另外又建立了一個(gè)標(biāo)志矩陣mark[m6.具體實(shí)現(xiàn)算法1.mark[1][1]=1;//[1][1]是入口2.stack<items>st(m*p);//開辟工作棧,大小為m*p3.itemstmp;//設(shè)一工作結(jié)構(gòu)變量tmp.x=1;tmp.y=1;tmp.dir=E;st.push(tmp);4.while(!st.IsEmpty()){1）tmp=st.pop();2)inti=tmp.x;intj=tmp.y;intd=tmp.dir1/6/2023606.具體實(shí)現(xiàn)算法12/11/2022163)while(d<8){i)intg=i+move[d].a;inth=j+move[d].b;ii)if(g==m&&h==p)//判別是否出口{輸出i,j,m,p;return;}iii)if(!maze[g][h]&&mark[g][h]){a.mark[g][h]=1;//表示向東走過(guò)該坐標(biāo)b.將(i,j,d+1進(jìn)棧)如果向東走下去,到某一步走不通,則有可能回退到i,j,則要換一個(gè)方向,即d+1(SE)東南c.從新的坐標(biāo)點(diǎn)i=g,j=h,d=N開始一個(gè)個(gè)方向試探}elsed++;//遇到墻或該坐標(biāo)已走過(guò),則換一個(gè)方向試.}}1/6/2023613)while(d<8)12/11/202215.廣義表(GeneralList)

1)廣義表的概念(LS)*定義:n(n>=0)個(gè)表元素a0,a1,a2,……an-1組成的有限序列。記作:LS=(a0,a1,a2,……an-1)

其中每個(gè)表元素ai可以是原子,也可以是子表。原子:某種類型的對(duì)象,在結(jié)構(gòu)上不可分。(用小寫字母表示)子表:有結(jié)構(gòu)的。(用大寫字母表示)*廣義表的長(zhǎng)度:表中元素的個(gè)數(shù)1/6/2023625.廣義表(GeneralList)12/11/202*廣義表的表頭(head)、表尾(tail)head=a0;tail=(a1,a2,……an-1)LS=（’a’,(‘b’,’a’,’b’),(),’c’,(((2))))*廣義表的深度:表中所含括號(hào)的最大層數(shù)1)A=();2)B=(6,2)3)C=(‘a(chǎn)’,(5,3,‘x’))表頭為‘a(chǎn)’,表尾為((5,3,‘x’))4)D=(B,C,A)5)E=(B,D)6)F=(4,F)遞歸的表1/6/202363*廣義表的表頭(head)、表尾(tail)12/11

2)廣義表的性質(zhì)有序性有長(zhǎng)度,有深度可遞歸,如上面例6可共享,如E中B為E,D所共享各種廣義表都可用一種示意圖來(lái)表示,用表示表元素,表示原子A62B‘a(chǎn)’53‘x’C1/6/2023642)廣義表的性質(zhì)A62B‘a(chǎn)’53‘x’C12/11/DBCA62‘a(chǎn)’53‘x’EBDCA62‘a(chǎn)’53‘x’F41/6/202365DBCA62‘a(chǎn)’53‘x’EBDCA62‘a(chǎn)’53‘x’F3)廣義表的操作例子:list1=(5,12,‘s’,47,‘a(chǎn)’)head(list)//取第一個(gè)元素tail(list)//tail(list1)=(12,‘s’,47,‘a(chǎn)’)first(list)//返回廣義表第一個(gè)元素的指針info(elem)//返回由elem指向的廣義表節(jié)點(diǎn)的值next(elem)//返回由elem指向的下一個(gè)節(jié)點(diǎn)的指針nodetype(elem)//返回由elem指向的廣義表節(jié)點(diǎn)的類型push(list,x)//將值為x的節(jié)點(diǎn)加入到廣義表list的最前端addon(list,x)//建立以x為頭,list為尾的新表setinfo(elem,x)//將表元素elem的值修改為xsethead(list,x)//將list的頭元素重置為x1/6/2023663)廣義表的操作12/11/202222

4)廣義表的存儲(chǔ)結(jié)構(gòu)用數(shù)組存儲(chǔ)顯然不合適,因數(shù)組元素不同構(gòu)用拉鏈,但各元素類型不一致;用不等長(zhǎng)節(jié)點(diǎn)不好.用等長(zhǎng)節(jié)點(diǎn)來(lái)表示,每個(gè)表節(jié)點(diǎn)用三個(gè)域組成.標(biāo)志域值域尾指針utypevaluetlink1/6/20236712/11/202223

utype=0:廣義表專用的表頭結(jié)點(diǎn)1:整型原子結(jié)點(diǎn)2:字符型原子結(jié)點(diǎn)3:子表節(jié)點(diǎn)值域隨著不同類型的節(jié)點(diǎn),存放不同的內(nèi)容,并用不同的名字來(lái)表示,實(shí)際上value部分可變的,用union實(shí)現(xiàn).utype=0,ref:存放引用計(jì)數(shù)utype=1,intgrinfo:存放整數(shù)值utype=2,charinfo:存放字符型數(shù)據(jù)utype=3,hlink:指向子表表頭的指針1/6/202368utype=0:廣義表專用的表頭結(jié)點(diǎn)12/1

tlink:當(dāng)utype=0,tlink指向該表(表可以是子表)第一個(gè)元素的結(jié)點(diǎn)當(dāng)utype!=0,tlink指向該值域同一層的下一個(gè)表結(jié)點(diǎn)例子:L=(3,(),(‘b’,‘c’),(((‘d’))))

utypereftlinkL0L13333^0^02b2c^

03^03^02‘d’^

1/6/202369tlink:當(dāng)utype=0,tlink指向該廣義表的類聲明:#defineHEAD0#defineINTGR1#defineCH2#defineLIST31/6/202370廣義表的類聲明:12/11/202226classGenList;classGenListNode{friendclassGenList;private:intutype;//=1/2/3,表示HEAD/INTGR/CH/LSTGenListNode*tlink;union{//聯(lián)合intref;intintgrinfo;charcharinfo;GenListNode*hlinkl}value;1/6/202371classGenList;12/11/202227Public:GenListNode&Info(GenListNode*elem);intnodetype(GenListNode*elem){returnelem-->utype;}voidsetInfo(GenListNode*elem,GenListNode&x);}廣義表的類聲明中:成員數(shù)據(jù):first它指向廣義表的表頭結(jié)點(diǎn)成員函數(shù):私有--copy，depth,equal,remove公有--Head,tail,First,Next,push,Addon等等

1/6/202372Public:12/11/2022285）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法廣義表結(jié)點(diǎn)類的存取成員函數(shù)GenListNode&GenListNode::info(GenListNode*elem){//返回表元素elem的值GenListNode*pitem=newGenListNode;pitem-->utype=elem-->utype;pitem-->value=elem-->value;return*pitem;}廣義表的一些成員函數(shù)

廣義表類的構(gòu)造函數(shù)

first01NULL1/6/2023735）廣義表部分成員函數(shù)的實(shí)現(xiàn)算法first01NGenList::GenList(){GenListNode*first=newGenListNode;first-->utype=0;first-->value.ref=1;first-->tlink=NULL;}

Head()---返回廣義表的第一個(gè)元素值,若為空表,則為非法操作.GenListNode&GenList::Head(){if(first-->tlink==NULL){cout<<“Illegalheadoperation.”<<endl;exit(1);}else{GenListNode*temp=newGenListNode;temp-->utype=first-->tlink-->utype;temp-->value=first-->tlink-->value;return*temp;}}1/6/202374GenList::GenList()12/11/20

取廣義表的表尾---tail()(若是空表,則是非法操作)GenListGenList::Tail(){if(first-->tlink==NULL){cout<<“Illegaltailoperation.”<<endl;exit(1);}else{GenList*temp=newGenList;temp-->first-->tlink=first-->tlink-->tlink;return*temp;}}

1/6/202375取廣義表的表尾---tail()(若是空表,則構(gòu)造一個(gè)以x為第一個(gè)元素,list為尾的新表----AddonGenList&GenList::Addon(GenList&list,GenListNode&x){GenList*newList=newGenList;newList-->first=copy(list.first);x-->tlink=newList-->first-->tlink;newList-->f