栈与递归递归与回溯广义表

《栈与递归递归与回溯广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

栈与递归递归与回溯广义表第五章递归 一、栈和递归递归定义递归函数 递归定义先定义最基本的概念再用已定义的概念定义新的概念例命题演算公式的定义（1）单个命题变元符号是命题（2）如果A,B是命题，则(┐A),(A∧B),(A∨B),(A→B),（A←→B)都是公式 递归定义先定义最基本的概念再用已定义的概念定义新的概念例标识符的定义（1）单个英文字母是标识符（2）标识符后缀一个数字或一个英文字母是标识符 递归函数的定义一个算法可以分解成若干相同的小算法分解到某简单的子算法时终止有一个或几个终止条件递归：由其前面的值求当前值递归必须导致终止条件 递归函数的例例函数xnx0=1xn=x*xn-1n>0xn=xn-1/xn<0例函数n!0!=1n!=n*(n-1)!n>0 递归函数的例函数C(n,m)C(0,m)=1,C(m,m)=1.C(n,m)=C(n-1,m-1)+C(n,m-1) #include//computen!=n*(n-1)*(n-2)...(2)(1),0!=1recursivelylongFactorial(longn){//ifn==0,then0!=1;otherwise,n!=n*(n-1)!if(n==0)return1;elsereturnn*Factorial(n-1);} voidmain(void){inti,n;//enter4positiveintegersandcomputen!foreachcout<<"Enter4positiveintegers:";for(i=0;i<4;i++){cin>>n;cout<Enter4positiveintegers:07140!=17!=50401!=14!=24*/ 阶乘堆栈主程序参数44*Factorial(3)参数33*Factorial(2)参数22*Factorial(1)参数11*Factorial(0)参数0Factorial(0)112624 递归函数先操作后遍历例voidFucnc(charch){if(ch<=‘z’){cout<#pragmahdrstop#include"strclass.h"//movendisksfromstartpegtoendpeg,//usingmiddlepegastheintermediatepeg voidhanoi(intn,charA,charB,charC){if(n==1)cout<<“move”<>n;cout<<"Thesolutionforn="<Enterthenumberofdisks:3Thesolutionforn=3moveA→BmoveA→CmoveB→CmoveA→BmoveC→AmoveC→BmoveB→C*/ 迷宫mazestructIntersection{intleft;intforword;intright;};435217660203560040000007007回溯此路不通，返回回溯此路不通，返回回溯此路不通，返回回溯此路不通，返回 二、递归和回溯迷宫算法八皇后问题 //recordthatspecifiestheintersectionyou//arriveatwhendepartingleft,forwardorright//fromthecurrentintersectionstructIntersection{intleft;intforward;intright;}; #include#include#includeclassMaze{intmazesize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intintsecvalue);}; Maze::Maze(char*filename){ifstreamfin;inti;fin.open(filename,ios::in|ios::nocreate);if(!fin){cerr<<"Themazedatafile"<>mazesize;intsec=newIntersection[mazesize+1];for(i=1;i<=mazesize;i++)fin>>intsec[i].left>>intsec[i].forward>>intsec[i].right;fin>>EXIT;fin.close();} 回溯法一个变量控制递归用另一个变量来控制回溯出现特定情况时该变量取值0回溯1。全局变量2。变量参数引用变量，指针变量3。函数返回值 intMaze::TraverseMaze(intintsecvalue){if(intsecvalue>0){if(intsecvalue==EXIT){cout<#pragmahdrstop#include"maze.h"//includethemazeclass voidmain(void){charfilename[32];cout<<"Enterthedatafilename:";cin>>filename;MazeM(filename);if(M.TraverseMaze(1))cout<<" Youarefree!"<Enterthedatafilename:maze1.dat7621Youarefree!Enterthedatafilename:maze2.datNopathoutofthemazeEnterthedatafilename:bigmaze.dat19171614109821Youarefree.*/ 43572610000000000000迷宫的另一种模型 迷宫的另一种模型1011987463251000000000000000000000 八皇后问题WWW两皇后在同一行或同一列或同一对角线上互相杀死要求：一个棋盘上摆八个皇后，任意两个都不互相杀死 皇后的表示用二维数组表示8*8棋盘皇后用棋盘上的格点表示用坐标表示皇后的位置(a,4)(1,4)用一维数组表示皇后的位置intq[9];q[1]=4;表示第一行第四列有一个皇后q[4]=2;表示第四行第二列有一个皇后 两个皇后冲突的特征(a1,b1)与(a2,b2)冲突当且仅当a1=b1或a2=b2或|a1-b1|=|a2-b2|q[i]与q[j]冲突当且仅当i=j或q[i]=q[j]或|i-j|=|q[i]-q[j]| 三、广义表LS=(a1,a2,······,an)长度n每个ai1≤i≤n或是一个元素（原子），或是一个子广义表。a1是表头head,a2,······,an是表尾。用小写字母表示原子，大写字母表示广义表。 广义表的例A=()长度为0的空表。B=(e)只有一个元素的表，长为1。C=(a,(b,c,d))长度为2的广义表，第二个元素是长度为3的子表。D=(A,B,C)长度为3的广义表，三个元素都是长度为3的子表。D=((),(e),(a,(b,c,d)))E=(a,E)递归定义的表。E=(a,(a,(a,······))). 广义表的存储广义表的结点标志域表头指针表尾指针tag=1hptp表结点1标志域原子域表尾指针tag=0atomtp表结点2 广义表结点类定义enumElemTag{ATOM,LIST};templatestructGLNode{ElemTagtag;union{Tatom;GLNode*hp;}GLNode*tp;};tag=1hptp表结点1tag=0atomtp表结点2 广义表的链表表示1^^A1^B0e^C1^0e1^0a0b0c^D1^1^11^E1^0a1^ 广义表结点类的补充定义enumElemTag{ATOM,LIST};templateclassGLNode{ElemTagtag;union{Tatom;GLNode*hp;}GLNode*tp;public:GLNode(constT&item,GLNode*t=NULL);GLNode(GLNode*h,GLNode*t);ElemTagGetType(){returntag;}T&GetValue();GLNode*Next();VoidSetValue(GLNode&x);}; 广义表结点类的实现templateGLNode::GLNode(constT&item,GLNode*t=NULL){tag=ATOM;atom=item;temp.tp=t;} templateGLNode::GLNode(GLNode*h,GLNode*t){tag=LIST;hp=h;tp=t;} templateT&GLNode::GetValue(){if(tag==ATOM)returnatom;elsecout<<“novalue”;return0;} templateGLNode*GLNode::Next(){returntp;} templateVoidGLNode::SetValue(GLNode&x){tag=x.tag;tp=x.tp;if(tag==ATOM)atom=x.atom;elsehp=x.hp;} 广义表类定义templateclassGList{GLNode*first;GLNode*GetNode(constT&item,Node*t=NULL);GLNode*GetNode(Node*h=NULL,Node*t=NULL);voidFreeGLNode(GLNode*p);voidCopyList(constGList&list);voidClearGList(); public:GList(void);Glist(GLNode*p);Glist(GLNode&x,Glist&list);Glist(GList&head,Glist&tail);GList(constGList&list);~GList(void);GLNode*First();GLNode&Head();GLNode*Tail();voidPush(GLNode&x);//addnodexasheadvoidSetHead(GLNode&x);//replacextoheadvoidSetTail(Glist&L);}; templateGlist::GList(constGList&list){CopyList(list):} templateGLNode*Glist::GetNode(constT&item,Node*t=NULL){GLNode*p=newGLNode;p->tag=ATOM;p->atom=item;p->tp=t;returnp;} templateGLNode*Glist::GetNode(Node*h=NULL,Node*t=NULL){GLNode*p=newGLNode;p->tag=LIST;p->hp=h;p->tp=t;returnp;} templatevoidGlist::FreeGLNode(GLNode*p){freep;} templateGLNode*GList::CopyList(constGList&list){GLNode*p,*q;q=this;if(list.first!=NULL){p=newGLNode;p->tag=list.first->tag;if(p.->tag==ATOM)p->atom=list.first->atom;elaep->hp=CopyList(list.first->hp);p->tp=CopyList(list.first->tp);this=p;q.ClearList();returnp;} templatevoidGlist::ClearGList(){if(first->tag==LIST)ClearGList(first->hp);ClearList(first->tp);free(this);} templateGlist::GList(void){first=newGLNode;first->tag=LIST;first->hp=NULL;first->tp=NULL;} templateGlist::Glist(GLNode*p){first=p;} templateGlist::Glist(GLNode&x,Glist&list){first=newGLNode;first->tag=LIST;first->hp=newGLNode(x);first->tp=CopyList(list);} templateGlist::Glist(GList&head,Glist&tail){first=newGLNode;first->tag=LIST;first->hp=CopyList(head);fisrt->tp=CopyList(tail);} templateGlist::~GList(void){ClearList();} 广义表的深度Depth(list)1list为空表Depth(list)=0list为原子1+Max{Depth(ai)};O.W. 广义表深度Depth(list)的算法intDepth(GLNode*p){if(p==NULL)return1;if(p->tag==ATOM)return0;GLNode*s;intdep;for(intmax=0,s=p;s;s=s->tp){if(s->tag==LIST)dep=Depth(s->hp);if(dep>max)max=dep;}returnmax+1;} intDepth(GListlist){returnDepth(list->first);}