清华大学数据结构05recursiv课件.ppt

n n递归递归(ss)的概念的概念n n迷宫迷宫(Maze)问题问题n n递归过程与递归工作栈递归过程与递归工作栈n n广义表广义表 (General Lists )n n小结小结清华大学数据结构05recursiv递归的概念递归的概念n n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, 或用它自己给自己定义或用它自己给自己定义, 则称则称这个对象是递归的；若一个过程这个对象是递归的；若一个过程直接直接地或间接地调用自己地或间接地调用自己, 则称这个过程是则称这个过程是递归的过程递归的过程n n以下三种情况常常用到递归方法以下三种情况常常用到递归方法uu 定义是递归的定义是递归的uu 数据结构是递归的数据结构是递归的uu 问题的解法是递归的问题的解法是递归的清华大学数据结构05recursiv定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) { if ( n == 0 ) return 1; else return n*Factorial (n-1);}例如，阶乘函数例如，阶乘函数清华大学数据结构05recursiv求解阶乘求解阶乘 n! 的过程的过程清华大学数据结构05recursiv计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }清华大学数据结构05recursiv数据结构是递归的数据结构是递归的搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find ( ListNode *f ) { if ( f →link == NULL ) cout << f →data << endl; else Find ( f →link );} 例如，单链表结构例如，单链表结构清华大学数据结构05recursiv在链表中寻找等于给定值的结点并打印在链表中寻找等于给定值的结点并打印其数值其数值template void Print ( ListNode *f, Type& x ) { if ( f != NULL) if ( f →data == x ) cout << f→data << endl; else Print ( f→link, x );}清华大学数据结构05recursiv 问题的解法是递归的问题的解法是递归的 例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题问题清华大学数据结构05recursiv#include #include "strclass.h”void Hanoi (int n, String A, String B, String C ) { //解决汉诺塔问题的算法解决汉诺塔问题的算法 if ( n == 1 ) cout << " move " << A << " to ” << C << endl; else { Hanoi ( n-1, A, C, B ); cout << " move " << A << " to " << C << endl; Hanoi ( n-1, B, A, C ); }}清华大学数据结构05recursiv迷宫问题迷宫问题小型迷宫小型迷宫 路口路口 动作动作 结果结果 1 1 (入口入口) 正向走正向走 进到进到 2 2 2 2 左拐弯左拐弯 进到进到 3 3 3 3 右拐弯右拐弯 进到进到 4 4 4 4 (堵死堵死) 回溯回溯 退到退到 3 3 3 3 (堵死堵死) 回溯回溯 退到退到 2 2 2 2 正向走正向走 进到进到 5 5 5 5 (堵死堵死) 回溯回溯 退到退到 2 2 2 2 右拐弯右拐弯 进到进到 6 6 6 6 左拐弯左拐弯 进到进到 7 7 (出口出口)4352176 6 左左 0 直直 2 右右 0 行行 3 行行 5 行行 6 0 0 4 0 0 0 0 0 0 7 0 0 7小小型型迷迷宫宫的的数数据据清华大学数据结构05recursiv迷宫的类定义迷宫的类定义#include #include #include class Maze {private: int MazeSize; int EXIT; Intersection *intsec;public: Maze ( char * ); int TraverseMaze ( int CurrentPos );}交通路口结构定义交通路口结构定义struct Intersection { int left; int forward; int right;}清华大学数据结构05recursivMaze :: Maze ( char * ) {//构造函数：从文件构造函数：从文件 中读取各路口中读取各路口//和出口的数据和出口的数据 ifstream fin; fin.open ( , ios::in | ios::nocreate ); //为输入打开文件为输入打开文件,文件不存在则打开失败文件不存在则打开失败 if ( !fin ) { cout << “迷宫数据文件迷宫数据文件” << << “打不开打不开” << endl; exit (1); } fin >> MazeSize; //输入迷宫路口数输入迷宫路口数清华大学数据结构05recursiv intsec = new Intersection[MazeSize+1]; //创建迷宫路口数组创建迷宫路口数组 for ( int i = 1; i <= MazeSize; i++ ) fin >> intsec[i].left >> intsec[i].forward >> intsec[i].right; fin >> EXIT; //输入迷宫出口输入迷宫出口 fin.close ( );}迷宫漫游与求解算法迷宫漫游与求解算法int Maze::TraverseMaze ( int CurrentPos ) { if ( CurrentPos > 0 ) { //路口从路口从 1 开始开始清华大学数据结构05recursiv if ( CurrentPos == EXIT ) { //出口处理出口处理 cout << CurrentPos << " "; return 1; } else //递归递归向左向左搜寻可行搜寻可行 if (TraverseMaze(intsec[CurrentPos].left )) { cout << CurrentPos << “ ”; return 1; } else //递归递归向前向前搜寻可行搜寻可行 if (TraverseMaze(intsec[CurrentPos].forward)) { cout << CurrentPos << “ ”; return 1; } else //递归递归向右向右搜寻可行搜寻可行 if (TraverseMaze(intsec[CurrentPos].right)) { cout << CurrentPos << " "; return 1; } } return 0;}清华大学数据结构05recursiv递归过程与递归工作栈递归过程与递归工作栈n n递归过程在实现时，需要自己调用自己。

递归过程在实现时，需要自己调用自己n n每一次递归调用时，需要为过程中使用的参每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间数、局部变量等另外分配存储空间n n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反： 递归次序递归次序递归次序递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序返回次序返回次序n n因此，每层递归调用需分配的空间形成递归因此，每层递归调用需分配的空间形成递归工作记录工作记录，按后进先出的栈组织按后进先出的栈组织 清华大学数据结构05recursiv函数递归时的活动记录函数递归时的活动记录清华大学数据结构05recursiv long Factorial ( long n ) { int temp; if ( n == 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; } void main ( ) { int n; n = Factorial (4); RetLoc1 }清华大学数据结构05recursiv计算计算Factorial时活动记录的内容时活动记录的内容清华大学数据结构05recursiv调用次数调用次数 NumCall(k) = 2* *Fib(k+1) - - 1。

斐波那契数列的递归调用树斐波那契数列的递归调用树清华大学数据结构05recursiv打印数组打印数组A[n]的值的值void recfunc ( int A[ ], int n ) { if ( n >= 0 ) { cout << A[n] << " "; n--; recfunc ( A, n ); }} 25 36 72 18 99 49 54 63 81清华大学数据结构05recursivvoid iterfunc ( int A[ ], int n ) {//消除了尾递归的非递归函数消除了尾递归的非递归函数 while ( n >= 0 ) { cout << "value " << A[n] << endl;n--; }} 清华大学数据结构05recursiv广义表广义表 (General Lists )n n 广义表的概念广义表的概念 n (   0 )个表元素组成的有个表元素组成的有 限序列限序列，记作，记作 LS = (a0, a1, a2, …, an-1) LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表(称为称为 子表子表)，可以是数据元素，可以是数据元素(称为称为原子原子)。

n n n为表的长度为表的长度n = 0 的广义表为空表的广义表为空表n n n > 0时，时，表的表的第一个表元素第一个表元素称为广义表称为广义表 的的表头表头(head)，，除此之外，除此之外，其它表元素组其它表元素组 成的表成的表称为广义表的称为广义表的表尾表尾(tail) 清华大学数据结构05recursiv广义表的特性广义表的特性n n有次序性有次序性n n有长度有长度n n有深度有深度n n可递归可递归n n可共享可共享A = ( )B = ( 6, 2 )C = ( ‘a’, ( 5, 3, ‘x’ ) )D = ( B, C, A )E = ( B, D )F = ( 4, F )清华大学数据结构05recursiv各种广义表的示意图各种广义表的示意图清华大学数据结构05recursiv广义表的表示广义表的表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示清华大学数据结构05recursiv广义表结点定义广义表结点定义n n标志域标志域 utype, 表明结点类型。

表明结点类型0为表头结点，为表头结点，1 为整型原子结点，为整型原子结点，2为字符型原子结点，为字符型原子结点，3为子为子表结点n n值域值域 value当 utype = 0 时为时为表引用计数表引用计数，，= 1时为时为整数值整数值，，= 2 时为时为字符值字符值，， = 3 时为时为指向指向子表的表头结点的指针子表的表头结点的指针n n尾指针域尾指针域 tlink当 utype = 0 时为指向该表表时为指向该表表头元素的指针；当头元素的指针；当 utype   0 时为指向同一层下时为指向同一层下一个表结点的指针一个表结点的指针utype = 0/1/2/3value = ref /intgrinfo /charinfo / hlink tlink清华大学数据结构05recursiv广义表的带表头结点的存储表示广义表的带表头结点的存储表示清华大学数据结构05recursiv广义表的类定义广义表的类定义#define HEAD 0#define INTGR 1#define CH 2#define LST 3class GenList;class GenListNode { //广义表结点类广义表结点类friend class Genlist;private: int utype; GenListNode * tlink;清华大学数据结构05recursiv union { int ref;//utype = 0, 表头结点表头结点 int intgrinfo;//utype = 1, 整型整型char charinfo; //utype = 2, 字符型字符型 GenListNode *hlink; //utype = 3, 子表结点子表结点 } value;public: GenListNode & Info ( GenListNode *elem ); int nodetype ( GenListNode *elem ) { return elem→utype; } void setInfo ( GenListNode *elem, GenListNode *x );};清华大学数据结构05recursivclass GenList { //广义表类广义表类private: GenListNode* first; //广义表表头指针广义表表头指针 GenListNode* Copy ( GenListNode* ls ); int depth ( GenListNode *ls ); int equal ( GenListNode *s, GenListNode *t ); void Remove (GenListNode *ls );public: Genlist ( ); ~GenList ( ); GenListNode& Head ( ); GenListNode& Tail ( );清华大学数据结构05recursiv GenListNode *First ( ); GenListNode *Next ( GenListNode *elem ); void Push ( GenListNode& x ); GenList & Addon ( GenList& list, GenListNode& x ); void setHead ( GenListNode& x ); void setNext ( GenListNode *elem1, GenListNode *elem2 ); void setTail ( GenList& list ); void Copy ( const GenList& l ); int depth ( ); int Createlist ( GenListNode* ls, char* s );}清华大学数据结构05recursiv广义表的访问算法广义表的访问算法 广义表结点类的存取成员函数广义表结点类的存取成员函数GenListNode& GenListNode ::Info (GenListNode* elem ) {//提取广义表中指定表元素提取广义表中指定表元素elem的值的值 GenListNode * pitem = new GenListNode; pitem→utype = elem→utype; pitem→value = elem→value; return * pitem;}清华大学数据结构05recursivvoid GenListNode :: setInfo(GenListNode* elem, GenListNode& x ) {//将表元素将表元素elem中的值修改为中的值修改为x elem→utype = x→utype; elem→value = x→value; } 广义表类的构造和访问成员函数广义表类的构造和访问成员函数Genlist :: GenList ( ) { GenListNode *first = new GenListNode; first→utype = 0; first→ref = 1; first→tlink = NULL; //仅建立表头结点仅建立表头结点}清华大学数据结构05recursivGenListNode& GenList :: Head ( ) {//若广义表非空，返回表的表头元素的值若广义表非空，返回表的表头元素的值 if ( first→tlink == NULL ) { //空表空表 cout << “无效的无效的 head 操作操作.” << endl; exit (1); } else { GenListNode * temp = new GenListNode; temp→utype = frist→tlink→utype; temp→value = frist→tlink→value; return *temp; }}清华大学数据结构05recursivGenListNode& GenList :: Tail ( ) {//若广义表非空，返回广义表除表头元素外其若广义表非空，返回广义表除表头元素外其//它元素组成的表，否则函数没有定义它元素组成的表，否则函数没有定义 if ( first→tlink == NULL ) { //空表空表 cout << “无效的无效的 Tail 操作操作.” << endl; exit (1); } else { GenListNode * temp = new GenListNode; temp→frist→tlink = frist→tlink→tlink; return *temp; }}清华大学数据结构05recursivvoid GenList :: Push ( GenListNode& x ) {//将表结点将表结点 x 加到表的最前端加到表的最前端 if ( first→tlink == NULL ) first→tlink = x; else { x→tlink = first→tlink; first→tlink = x; }} 清华大学数据结构05recursivGenList & GenList :: Addon ( GenList & list, GenListNode& x ) {//返回一个以返回一个以x为头，为头，list为尾的新广义表为尾的新广义表 GenList * newlist = new GenList; newlist→first = Copy ( list.first ); x→tlink = newlist→frist→tlink; newlist→frist→tlink = x; return * newlist;} 清华大学数据结构05recursiv广义表的递归算法广义表的递归算法广义表的复制算法广义表的复制算法 void GenList::Copy ( const GenList & l ) { first = Copy ( l.first );}GenListNode* GenList :: Copy(GenListNode *ls){ GenListNode *q = NULL; if ( ls != NULL ) { q = new GenListNode; //创建表结点创建表结点 q→utype = ls→utype; //复制复制 utype清华大学数据结构05recursiv switch ( ls→utype ) { case HEAD : q→value.ref = ls→value.ref; break; case INTGR : q→value.intgrinfo = ls→value.intgrinfo; break; case CH : q→value.charinfo = ls→value.charinfo; break; case LST : q→value.hlink = Copy ( ls→value.hlink ); break; } 清华大学数据结构05recursiv q→tlink = Copy ( ls→tlink ); } return q;}清华大学数据结构05recursiv求广义表的深度求广义表的深度例如，对于广义表例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z)), A ( ) ) )按递归算法分析：按递归算法分析： Depth (E) = 1+Max { Depth (B), Depth (D) } Depth (B) = 1+Max { Depth (a), Depth (b) } = 1 Depth (D) = 1+Max { Depth (B), Depth (C), Depth (A)}清华大学数据结构05recursiv Depth (C) = 1+Max { Depth (u), Depth ((x, y, z)) } Depth (A) = 1 Depth (u) = 0 Depth ((x, y, z)) = 1+Max {Depth (x), Depth (y), Depth (z) } = 1 Depth (C) = 1+Max { Depth (u), Depth ((x, y, z)) } = 1+Max {0, 1} = 2 Depth (D) = 1+Max { Depth (B), Depth (C), Depth (A)} = 1+Max {1, 2, 1} = 3 Depth (E) = 1+Max { Depth (B), Depth (D) } = 1+Max {1, 3} = 4E ( B (a, b), D ( B (a, b), C (u, (x, y, z)), A ( ) ) )清华大学数据结构05recursivint GenList :: depth ( GenListNode *ls ) { if ( ls→tlink == NULL ) return 1; //空表空表 GenListNode *temp = ls→tlink; int m = 0; while ( temp != NULL ) { //横扫广义横扫广义表表 if ( temp→utype == LST ) { //子表深度子表深度 int n = depth ( temp→value.hlink ); if ( m < n ) m = n; } //不是子表不加深度不是子表不加深度 temp = temp→tlink; } return m+1;}清华大学数据结构05recursivint GenList::depth ( ) { return depth ( first );}广义表的删除算法广义表的删除算法删除删除'x'前的广义表链表结构前的广义表链表结构n n 扫描子链表扫描子链表uu 若结点数据为若结点数据为‘x’, 删除。

可能做循环连续删可能做循环连续删uu 若结点数据不为若结点数据不为‘x’，，不执行删除不执行删除uu 若结点为子表，递归在子表执行删除若结点为子表，递归在子表执行删除清华大学数据结构05recursivvoid delvalue (GenListNode * ls, const value x) {//在广义表中删除所有含在广义表中删除所有含 x 的结点的结点 if ( ls→tlink != NULL ) { GenListNode * p = ls→tlink; //横扫链表横扫链表 while ( p != NULL && ( ( p→utype==INTGR && p→value.intgrinfo == x ) || ( p→utype==CH && p→value.charinfo == x ) ) { ls→tlink = p→tlink; delete p; //删除删除 p = ls→tlink; // p指向同层下一结点指向同层下一结点 } 清华大学数据结构05recursiv //链表检测完或遇到子表或走到子表表链表检测完或遇到子表或走到子表表 //头结点或不是含头结点或不是含x结点结点, 转出循环转出循环 if ( p != NULL ) { if ( p→utype == LST ) //到子表中删到子表中删除除 delvalue ( p→value.hlink, x ); delvalue ( p, x ); //向后递归删向后递归删除除 } }} GenList :: ~GenList ( ) { //析构函数析构函数 Remove ( first );}清华大学数据结构05recursivvoid GenList :: Remove (GenListNode *ls ) { ls→value.ref --; //引用计数减一引用计数减一 if ( !ls→value.ref ) { //引用计数减至引用计数减至0才能才能删除删除 GenListNode * y = ls; while ( y→tlink != NULL ) { //横扫链表横扫链表 y = y→tlink; if ( y→utype == LST ) //遇到子表遇到子表 Remove ( y→value.hlink ); //递归删除递归删除 } y→tlink = av; av = ls; //扫描完后扫描完后,回收到可利用空间表回收到可利用空间表 }}清华大学数据结构05recursiv从字符串从字符串s建立广义表的链表表示建立广义表的链表表示ls int Genlist ::CreateList ( GenListNode *ls, char * s ) { char *sub, *hsub; int tag; ls = new GenListNode ( ); //建立表头结点建立表头结点 ls→utype = HEAD; ls→value.ref = 1; if ( strlen (s) == 0 || !strcmp ( s,"( )" ) ) ls→tlink = NULL; //空表空表 else { strncpy ( sub, s+1, strlen (s)-2 ); //脱去广义表外面的引号脱去广义表外面的引号 GenListNode* p = ls;清华大学数据结构05recursivwhile ( strlen (sub) != 0 ) { //建立表结点建立表结点 p = p→tlink = new GenListNode ( ); //创建新结点创建新结点,向表尾链接向表尾链接 if ( sever ( sub, hsub ) ) { //以逗号为界以逗号为界,分离第一个表元素分离第一个表元素hsub if ( hsub[0] != '(' && hsub[0] != ’\0' ) { //非子表非子表,非字符分界符非字符分界符 p→utype = INTGR; //转换整型结点转换整型结点 p→value.intgrinfo = atoi ( hsub ); } else if ( hsub[0] != '(' && hsub[0] == ’\0' ) { //非子表且是字符分界符非子表且是字符分界符清华大学数据结构05recursiv p→utype = CH; p→value.charinfo = hsub; } else { //是子表是子表,递归建立子表递归建立子表 p→utype = LST; CreateList ( p→value.hlink, hsub ); } } else return 0; //字符串表达式有错字符串表达式有错 } //循环完成循环完成 p→tlink = NULL; //封闭最后一个结点封闭最后一个结点 } return 1;}清华大学数据结构05recursivint Genlist::sever ( char *str1, char *hstr1 ) {//对不含外分界符的字符串分离第一个元素对不含外分界符的字符串分离第一个元素 char ch = str1[0]; int n = strlen ( str1 ); int i = 0, k = 0; //检测检测str1,扫描完或遇到扫描完或遇到', '且括号配对则停且括号配对则停 while ( i < n && ( ch != ',' || k != 0 ) ) { if ( ch == '(' ) k++; else if ( ch == ')' ) k--; i++; ch = str1[i]; // i 计数计数, 取一字符取一字符 } 清华大学数据结构05recursiv if ( i < n ) { strncpy ( hstr1, str1, i-1 ); //str1的前的前 i- -1 个字符传送到个字符传送到hstr1 strncpy ( str1, str1+i, n-i ); //后后n- -i个字符留在个字符留在str1, 滤去滤去‘,’ return 1; } else if ( k != 0 ) return 0; //括号不配对出错括号不配对出错 else { //括号配对括号配对 strcpy ( hstr1, str1 ); str1 = 0; //str1全部传送给全部传送给hstr1 return 1; }}清华大学数据结构05recursiv设设 str = ‘( ( 2, ( ‘b’, 7 ) ), ( ), ( ‘d’ ) )’得到的广义表链表结构得到的广义表链表结构清华大学数据结构05recursiv小结小结 需要复习的知识点需要复习的知识点n n递归概念：递归概念：uu 什么是递归？什么是递归？uu 递归的函数定义递归的函数定义uu 递归的数据结构递归的数据结构uu 递归问题的解法递归问题的解法 Ø 链表是递归的数据结构链表是递归的数据结构Ø 可用递归过程求解有关链表的问题可用递归过程求解有关链表的问题清华大学数据结构05recursivn n递归实现时栈的应用递归实现时栈的应用uu递归求解思路递归求解思路uu递归过程与递归工作栈：递归过程递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用实现的机制及递归工作栈的引用 Ø递归的分层递归的分层(树形树形)表示表示 :递归树递归树Ø递归深度递归深度(递归树的深度递归树的深度)与递归工作与递归工作栈的关系栈的关系Ø单向递归与尾递归的迭代实现单向递归与尾递归的迭代实现清华大学数据结构05recursivn n广义表广义表uu广义表定义广义表定义uu广义表长度、深度、表头、表广义表长度、深度、表头、表尾尾uu广义表的表示及操作广义表的表示及操作Ø用图形表示广义表的存储结构用图形表示广义表的存储结构Ø广义表的递归算法广义表的递归算法清华大学数据结构05recursiv递归举例递归举例【例例1】】求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n- -1) + Fib (n- -2); }清华大学数据结构05recursiv考虑使用递归算法求解的思路考虑使用递归算法求解的思路n n递归算法的一般形式递归算法的一般形式 void p ( 参数表参数表 ) if ( 递归结束条件递归结束条件) 可直接求解步骤；可直接求解步骤； 基本项基本项 else p ( 较小的参数较小的参数 ); 递归项递归项清华大学数据结构05recursiv【例例2】】求数组求数组 A 中中 n 个整数的和个整数的和 int sum ( int n ) { int result; if ( n == 1 ) result = A[0]; else result = A[n-1] + sum(n-1); return result;} 清华大学数据结构05recursiv递归与回溯递归与回溯 常用于搜索过程常用于搜索过程【例例3】】n皇后问题皇后问题 在在 n 行行 n 列的国际象棋棋盘上，列的国际象棋棋盘上，若若两个皇后两个皇后位于位于同一行同一行、、同一列同一列、、同一对角线同一对角线上，则称为它们为上，则称为它们为互相互相攻击攻击。

n皇后问题是指皇后问题是指找到这找到这 n 个个皇后的互不攻击的布局皇后的互不攻击的布局清华大学数据结构05recursiv1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k = i+jk = n+i- -j- -1清华大学数据结构05recursiv解题思路解题思路n n安放安放第第 i 行行皇后时，需要在列的方向从皇后时，需要在列的方向从 1 到到 n 试探试探 ( j = 1, …, n ) n n在在第第 j 列列安放一个皇后：安放一个皇后：uu如果在如果在列列、、主对角线主对角线、、次对角线次对角线方向方向有其它皇后，则出现攻击，撤消在有其它皇后，则出现攻击，撤消在第第 j 列列安放的皇后安放的皇后uu如果没有出现攻击，在如果没有出现攻击，在第第 j 列列安放的安放的皇后不动，递归安放第皇后不动，递归安放第 i+1行皇后。

行皇后清华大学数据结构05recursivn n设置设置 4 个数组个数组u col [n] ：：col[i] 标识第标识第 i 列是否安列是否安放了皇后放了皇后u md[2n-1] : md[k] 标识第标识第 k 条主对条主对角线是否安放了皇后角线是否安放了皇后u sd[2n-1] : sd[k] 标识第标识第 k 条次对角条次对角线是否安放了皇后线是否安放了皇后u q[n] : q[i] 记录第记录第 i 行皇后在第几列行皇后在第几列清华大学数据结构05recursivvoid Queen( int i ) { for ( int j = 1; j <= n; j++ ) { if ( 第第 i 行第行第 j 列没有攻击列没有攻击 ) { 在在第第 i 行第行第 j 列安放皇后列安放皇后；； if ( i == n ) 输出一个布局输出一个布局；； else Queen ( i+1 ); } 撤消撤消第第 i 行第行第 j 列的皇后列的皇后；； }}清华大学数据结构05recursiv算法求精算法求精void Queen( int i ) { for ( int j = 1; j <= n; j++ ) { if ( !col[j] && !md[n+i-j-1] && !sd[i+j] ) { /*第第 i 行第行第 j 列没有攻击列没有攻击 */ col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; /*在在第第 i 行第行第 j 列安放皇后列安放皇后*/ 清华大学数据结构05recursiv if ( i == n ) { /*输出一个布局输出一个布局*/ for ( j = 0; j <= n; j++ ) cout << q[j] << ‘,’; cout << endl; } else Queen ( i+1 ); } col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; /*撤消撤消第第 i 行第行第 j 列的皇后列的皇后*/ }}清华大学数据结构05recursiv。