《栈与递归递归与回溯广义表课件》由会员分享，可在线阅读，更多相关《栈与递归递归与回溯广义表课件（74页珍藏版）》请在金锄头文库上搜索。
1、n n栈与递归n n递归与回溯n n广义表一、栈和递归递归定义递归函数递归定义先定义最基本的概念 再用已定义的概念定义新的概念例 命题演算公式的定义 （1） 单个命题变元符号是命题 （2） 如果A,B是命题，则 (A), (AB), (AB), (AB), （AB) 都是公式递归定义先定义最基本的概念 再用已定义的概念定义新的概念例 标识符的定义 （1）单个英文字母是标识符 （2）标识符后缀一个数字 或一个英文字母是标识符递归函数的定义一个算法可以分解成 若干相同的小算法 分解到某简单的子算法时终止 有一个或几个终止条件 递归：由其前面的值求当前值 递归必须导致终止条件 递归函数的例例 函数
2、xn x0=1 xn=x*xn-1 n0 xn=xn-1/x n0递归函数的例函数 C(n, m) C(0, m)=1, C(m, m)=1. C(n, m)=C(n-1,m-1)+C(n, m-1)#include / compute n! = n*(n-1)*(n-2).(2)(1), 0!=1 recursivelylong Factorial(long n) / if n = 0, then 0! = 1; otherwise, n! = n*(n-1)! if (n = 0) return 1; else return n * Factorial(n - 1);void main (
3、void) int i, n; / enter 4 positive integers and compute n! for each cout Enter 4 positive integers: ; for (i = 0; i n; cout n ! = Factorial(n) endl; /*Enter 4 positive integers: 0 7 1 4 0! = 1 7! = 5040 1! = 1 4! = 24*/阶乘堆栈阶乘堆栈 主程序参数4 4*Factorial(3)参数3 3*Factorial(2)参数2 2*Factorial(1)参数1 1*Factorial
4、(0)参数0 Factorial(0) 1 1 2 6 24递归函数递归函数 先操作 后遍历 例 void Fucnc(char ch) if(ch=z) coutch; Func(ch+1); 调用 Func(a);输出 abcdefghijklmnopqrstuvwxyz递归函数递归函数 先遍历 后操作例 void Fucnc(char ch) if(ch=z) Func(ch+1); coutch; 调用 Func(a);输出 zyxwvutsrqponmlkjihgfedcba递归函数递归函数 操作 遍历 操作例 void Fucnc(char ch) if(ch=z) coutch;
5、 Func(ch+1); coutch; 调用 Func(a);输出 abcdefghijklmnopqrstuvwxyz zyxwvutsrqponmlkjihgfedcba递归函数递归函数 遍历 操作 遍历例 void Fucnc(char ch) if(ch=d) Func(ch+1); coutch; Func(ch+1); 调用 Func(a);输出 dcdbdcdadcdbdcd河内塔问题A BC河内塔问题河内塔问题 将A塔上的金盘移到B塔上 ！要求 一次只能移动一个盘 大盘不能压小盘A BCA河内塔问题 第一次A BC河内塔问题 第二次A BC河内塔问题 第三次A BC河内塔问题
6、 第四次A BC 河内塔问题 第五次A BC河内塔问题 第六次A BC河内塔问题 第七次A BC河内塔问题河内塔问题设n个金盘移动 F(n)次F(1)=1F(n)=F(n-1)+1+F(n-1)=2*F(n-1)+1 F(n)+1=2*(F(n-1)+1) =22*(F(n-2)+1) = =2n-1*(F(1)+1)=2n F(n)=2n-1 河内塔问题程序河内塔问题程序#include #pragma hdrstop#include strclass.h/ move n disks from startpeg to endpeg,/ using middlepeg as the inter
7、mediate pegvoid hanoi(int n, char A, char B, char C) if (n = 1) cout “move ”A B endl; else hanoi(n-1,A, C, B); cout “move ”A B endl; hanoi(n-1, C, B, A); void main( ) int n; / number of disks and the peg names cout n; cout The solution for n = n endl; hanoi(n, A, B, C);/* Enter the number of disks:
8、3The solution for n = 3move A Bmove A Cmove B Cmove A Bmove C Amove C Bmove B C*/ 迷宫mazestruct Intersectionint left; int forword; int right; 4 3 5 2 1 7 660 2 03 5 60 0 40 0 00 0 07 0 07回溯 此路不通，返回回溯 此路不通，返回回溯 此路不通，返回回溯 此路不通，返回二、递归和回溯迷宫算法八皇后问题/ record that specifies the intersection you/ arrive at wh
9、en departing left, forward or right/ from the current intersectionstruct Intersection int left; int forward; int right;#include #include #include class Maze int mazesize; int EXIT; Intersection *intsec; public: Maze(char *filename); int TraverseMaze(int intsecvalue);Maze:Maze(char *filename) ifstrea
10、m fin; int i; fin.open(filename, ios:in | ios:nocreate); if (!fin) cerr The maze data file filename cannot be opened! mazesize; intsec = new Intersectionmazesize+1; for (i = 1; i intseci.left intseci.forward intseci.right; fin EXIT; fin.close( );回溯法回溯法一个变量控制递归用另一个变量来控制回溯出现特定情况时该变量取值0 回溯1。全局变量2。变量参数
11、引用变量，指针变量3。函数返回值 int Maze:TraverseMaze(int intsecvalue) if (intsecvalue 0) if (intsecvalue = = EXIT) cout intsecvalue ; return 1; else if (TraverseMaze(intsecintsecvalue.left) cout intsecvalue ; return 1; else if (TraverseMaze(intsecintsecvalue.forward) cout intsecvalue ; return 1; else if (Traverse
12、Maze(intsecintsecvalue.right) cout intsecvalue ; return 1; return 0;#include #pragma hdrstop#include maze.h / include the maze classvoid main (void) char filename32; cout filename; Maze M(filename); if (M.TraverseMaze(1) cout nYou are free! endl; else cout No path out of the maze endl;/maze1.dat60 2
13、 03 5 60 0 4 0 0 00 0 07 0 07 4 3 5 7 2 6 1/maze2.dat11 0 2 03 0 50 0 40 0 06 7 00 0 08 0 09 0 00 11 100 0 00 0 0121011 9 8 7 4 6 3 2 5 1/bigmaze.dat180 2 0 3 8 0 7 4 0 0 6 5 0 0 00 0 0 0 0 0 9 0 0 0 0 10 14 0 1112 13 0 0 0 0 0 0 0 0 15 16 0 0 017 0 0 0 18 19 0 0 019/* Enter the data file name: maze
14、1.dat7 6 2 1You are free!Enter the data file name: maze2.datNo path out of the mazeEnter the data file name: bigmaze.dat19 17 16 14 10 9 8 2 1You are free.*/ 4 3 5 7 2 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0迷宫的另一种模型迷宫的另一种模型迷宫的另一种模型迷宫的另一种模型1011 9 8 74 6 3 2 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0八皇后问题八皇后
15、问题WWW两皇后在同一行或同一列或同一对角线上互相杀死要求：一个棋盘上摆八个皇后，任意两个都不互相杀死皇后的表示皇后的表示用二维数组表示8*8棋盘 皇后用棋盘上的格点表示用坐标表示皇后的位置 (a, 4) (1, 4)用一维数组表示皇后的位置 int q9; q1=4; 表示第一行第四列有一个皇后 q4=2; 表示第四行第二列有一个皇后两个皇后冲突的特征两个皇后冲突的特征 (a1, b1)与 (a2, b2)冲突 当且仅当 a1= b1或 a2= b2 或 | a1- b1|=| a2- b2| qi与qj冲突 当且仅当 i= j 或 qi=qj 或 | i - j |=| qi - qj |
16、 三、广义表三、广义表LS=(a1, a2,an)长度 n每个 ai 1in 或是一个元素（原子原子），或是一个子广义表。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,).广义表的存储广义表的存储广义表的结点标志域标志域 表头指针表头指针
17、表尾指针表尾指针 tag=1 hp tp 表结点1标志域标志域 原子域原子域 表尾指针表尾指针 tag=0 atom tp 表结点2广义表结点类定义广义表结点类定义enum ElemTagATOM, LIST;templatestruct GLNode ElemTag tag; union T atom; GLNode *hp; GLNode *tp; tag=1 hp tp 表结点1tag=0 atom tp 表结点2广义表的链表表示广义表的链表表示1 A1B0 e C1 0 e10 a0 b0 c D11 11E10 a1广义表结点类的补充定义广义表结点类的补充定义enum ElemTag
18、ATOM, LIST;templateclass GLNode ElemTag tag; union T atom; GLNode *hp; GLNode *tp; public: GLNode(const T& item, GLNode *t=NULL); GLNode(GLNode *h,GLNode *t); ElemTag GetType( )return tag; T& GetValue( ); GLNode* Next( ); Void SetValue(GLNode & x); ; 广义表结点类的实现广义表结点类的实现template GLNode: GLNode(const T
19、& item, GLNode*t=NULL) tag=ATOM; atom=item; temp.tp=t; template GLNode:GLNode(GLNode *h,GLNode *t) tag=LIST; hp=h; tp=t;template T& GLNode:GetValue( )if (tag=ATOM) return atom; else cout“no value”; return 0;template GLNode* GLNode: Next( ) return tp;template Void GLNode: SetValue(GLNode & x) tag=x.t
20、ag; tp=x.tp; if(tag=ATOM) atom=x.atom; else hp=x.hp; 广义表类定义广义表类定义template class GList GLNode *first; GLNode *GetNode(const T&item, Node *t=NULL); GLNode *GetNode(Node *h=NULL, Node *t=NULL); void FreeGLNode(GLNode *p); void CopyList(const GList& list); void ClearGList( ); public: GList(void); Glist(
21、GLNode*p); Glist(GLNode&x,Glist&list); Glist(GList&head,Glist&tail); GList(const GList& list); GList(void); GLNode *First( ); GLNode& Head( ); GLNode *Tail( ); void Push(GLNode&x);/add node x as head void SetHead(GLNode&x);/replace x to head void SetTail(Glist&L);templateGlist:GList(const GList& lis
22、t) CopyList(list):template GLNode * Glist: GetNode(const T& item, Node *t=NULL) GLNode *p=new GLNode; p-tag=ATOM; p-atom=item; p-tp=t; return p; template GLNode * Glist:GetNode( Node *h=NULL, Node *t=NULL) GLNode*p=new GLNode; p-tag=LIST; p-hp=h; p-tp=t; return p;template void Glist:FreeGLNode(GLNod
23、e *p) free p;template GLNode* GList:CopyList( const GList& list)GLNode*p,*q; q=this; if(list.first!=NULL) p=new GLNode; p-tag=list.first-tag; if(p.-tag=ATOM) p-atom=list.first-atom; elae p-hp=CopyList(list.first-hp); p-tp=CopyList(list.first-tp); this=p; q.ClearList( ); return p;templatevoid Glist:
24、ClearGList( ) if(first-tag=LIST) ClearGList(first-hp); ClearList(first-tp); free(this);template Glist:GList(void) first=new GLNode; first-tag=LIST; first-hp=NULL; first-tp=NULL; template Glist:Glist(GLNode*p) first=p;template Glist:Glist(GLNode&x,Glist&list)first=new GLNode; first-tag=LIST; first-hp
25、=new GLNode(x); first-tp=CopyList(list);templateGlist:Glist(GList&head,Glist&tail)first=new GLNode; first-tag=LIST; first-hp=CopyList(head); fisrt-tp=CopyList(tail);templateGlist: GList(void) ClearList( );广义表的深度广义表的深度Depth(list) 1 list 为空表Depth(list)= 0 list 为原子 1+Max Depth(ai); O.W.广义表深度广义表深度Depth(list)的算法的算法int Depth(GLNode *p)if(p=NULL)return 1; if(p-tag=ATOM) return 0; GLNode *s; int dep; for(int max=0,s=p;s;s=s-tp) if(s-tag=LIST)dep=Depth(s-hp); if(depmax)max=dep; return max+1; int Depth(GList list) return Depth(list-first);
