数据结构课件c语言描述第5章课件

《数据结构课件c语言描述第5章课件》由会员分享，可在线阅读，更多相关《数据结构课件c语言描述第5章课件（79页珍藏版）》请在金锄头文库上搜索。

1、n n递归的概念递归的概念n n递归过程与递归工作栈递归过程与递归工作栈n n递归与回溯递归与回溯n n广义表广义表数据结构课件c语言描述第5章递归的概念递归的概念n n递归的定义递归的定义 若一个对象部分地包含它若一个对象部分地包含它自己自己, 或用它自己给自己定义或用它自己给自己定义, 则称这则称这个对象是递归的；若一个过程个对象是递归的；若一个过程直接地或直接地或间接地调用自己间接地调用自己, 则称这个过程是递归则称这个过程是递归的过程。的过程。n n以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。 定义是递归的定义是递归的 数据结构是递归的数据结构是递归的 问题的解法是递归

2、的问题的解法是递归的数据结构课件c语言描述第5章定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);例如，阶乘函数例如，阶乘函数数据结构课件c语言描述第5章求解阶乘求解阶乘 n! 的过程的过程主程序主程序主程序主程序 main : fact(4)参数参数 4 计算计算 4*fact(3) 返回返回 24参数参数 3 计算计算 3*fact(2) 返回返回 6参数参数 2 计算计算 2*fact(1) 返回返回 2参数参

3、数 1 计算计算 1*fact(0) 返回返回 1参数参数 0 直接定值直接定值 = 1 返回返回 1参参参参数数数数传传传传递递递递结结结结果果果果返返返返回回回回递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值数据结构课件c语言描述第5章数据结构是递归的数据结构是递归的n n 一个结点，它的指针域为一个结点，它的指针域为NULL，是一个是一个单链表单链表; ;n n 一个结点，它的指针域指向单链表，仍是一个结点，它的指针域指向单链表，仍是一个单链表。一个单链表。 例如，单链表结构例如，单链表结构f f 数据结构课件c语言描述第5章搜索链表最后一个结点并打印其数值搜索链表最后

4、一个结点并打印其数值template void Print ( ListNode *f ) if ( f -link = NULL ) cout data link );f f f f f a0a1a2a3a4递归找链尾数据结构课件c语言描述第5章在链表中寻找等于给定值的结点并打印其数在链表中寻找等于给定值的结点并打印其数值值template void Print ( ListNode *f, Type& x ) if ( f != NULL ) if ( f - data = x ) cout data link, x );f f f f 递归找含x值的结点x数据结构课件c语言描述第5章 问

5、题的解法是递归的问题的解法是递归的 例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题的解法：问题的解法： 如如果果 n = 1，则则将将这这一一个个盘盘子子直直接接从从 A 柱柱移到移到 C 柱上。否则，执行以下三步：柱上。否则，执行以下三步： 用用 C 柱柱做做过过渡渡，将将 A 柱柱上上的的 (n- -1) 个个盘子移到盘子移到 B 柱上；柱上； 将将 A 柱柱上上最最后后一一个个盘盘子子直直接接移移到到 C 柱柱上；上； 用用 A 柱做过渡，将柱做过渡，将 B 柱上的柱上的 (n- -1) 个个盘子移到盘子移到 C 柱上。柱上。数据结构课件c语言描述第5章数据结构课件c语言描

6、述第5章#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 -CA,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CA-BA-BA-CB-CC-BA-C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA-CA-C(1,B,A,C)A,B,CA-CB-CA-BB-AB-

7、CA-C数据结构课件c语言描述第5章自顶向下、逐步分解的策略自顶向下、逐步分解的策略n n子问题应与原问题做同样的事情，且更子问题应与原问题做同样的事情，且更为简单；为简单；n n解决递归问题的策略是把一个规模比较解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的再综合它们的结果，从而得到原问题的解。解。 分而治之策略（分治法）分而治之策略（分治法）n n这些比较小的问题的求解方法与原来问这些比较小的问题的求解方法与原来问题的求解方法一样

8、。题的求解方法一样。数据结构课件c语言描述第5章构成递归的条件构成递归的条件n n不能无限制地调用本身，必须有一个出口，不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。化简为非递归状况直接处理。 Procedure ( ) if ( ) return ( initial value ); else return ( ( parameter exchange ); 数据结构课件c语言描述第5章递归过程与递归工作栈递归过程与递归工作栈n n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。n n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好

9、相反： 递归调用递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序n n主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用外部调用；n n递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用内部调用。n n它们它们返回返回调用它的过程的调用它的过程的地址地址不同。不同。数据结构课件c语言描述第5章递归工作栈递归工作栈n n每一次递归调用时，需要为过程中使用的每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。参数、局部变量等另外分配存储空间。n n每层递归调用需分配的空间形成递归工作每层递归调用需分配的空间形成递归工作记录，按后进先

10、出的栈组织。记录，按后进先出的栈组织。 局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作记录工作记录数据结构课件c语言描述第5章函数递归时的活动记录函数递归时的活动记录.Function() .调用块函数块返回地址(下一条指令) 局部变量 参数数据结构课件c语言描述第5章 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

11、(4); RetLoc1 数据结构课件c语言描述第5章计算计算Fact时活动记录的内容时活动记录的内容递递归归调调用用序序列列0 1 RetLoc21 1 RetLoc22 2 RetLoc23 6 RetLoc24 24 RetLoc1参数参数参数参数 返回值返回值返回值返回值 返回地址返回地址返回地址返回地址 返回时的指令返回时的指令返回时的指令返回时的指令return 4*6 /返回返回返回返回 24 24 return 3*2 /返回返回返回返回 6 6 return 1 /返回返回返回返回 1 1 return 1*1 /返回返回返回返回 1 1 return 2*1 /返回返回返回

12、返回 2 2 数据结构课件c语言描述第5章递归过程改为非递归过程递归过程改为非递归过程n n递归过程简洁、易编、易懂；递归过程简洁、易编、易懂；n n递归过程效率低，重复计算多；递归过程效率低，重复计算多；n n改为非递归过程的目的是改为非递归过程的目的是提高效率；提高效率；n n单向递归和尾递归可直接用迭代实现其单向递归和尾递归可直接用迭代实现其非递归过程；非递归过程；n n其他情形必须借助栈实现非递归过程。其他情形必须借助栈实现非递归过程。数据结构课件c语言描述第5章计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 l

13、ong Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 如如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 数据结构课件c语言描述第5章调用次数调用次数 NumCall(k) = 2* *Fib(k+1) - - 1。斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1) Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1) Fib(0)Fib(2)Fib(1) Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)数

14、据结构课件c语言描述第5章Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点栈结点n tagtag = 1, 向左递归；向左递归；tag = 2, 向右递归。向右递归。数据结构课件c语言描述第5章Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 13 14 1 n=1sum=0+12 23 14 1n=2-23 14 1 n=0sum=1+03 24 1n=3-24 1 n=1sum=1+14 2n=4-2数据结构课件c语言描述第5章Fib(1)Fib(0)Fib(2)

15、Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 14 2 n=1sum=2+12 24 2n=2-24 2 n=0sum=3+0数据结构课件c语言描述第5章long Fibnacci ( long n ) Stack S; Node w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w.n = n; w.tag = 1; S.push ( w ); n-; /向左递归到底, 边走边进栈 sum = sum + n; /执行求和 数据结构课件c语言描述第5章 while ( !S.IsEmpty( ) ) w =

16、 S.getTop( ); S.Pop( ); if ( w.tag = 1 ) /改为向右递归 w.tag = 2; S.push ( w ); n = w.n 2; /F(n)右侧为F(n-2) break; while ( !S.IsEmpty( ) );return sum;数据结构课件c语言描述第5章单向递归用迭代法实现单向递归用迭代法实现long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = 0 ) cout An = 0

17、) cout value An endl; n-; 数据结构课件c语言描述第5章递归与回溯递归与回溯 常用于搜索过程常用于搜索过程对对一个包含有许多结点，且每个结点有多一个包含有许多结点，且每个结点有多个分支的问题，可以个分支的问题，可以先选择一个分支进行先选择一个分支进行搜索搜索。当搜索到某一结点，发现无法再继。当搜索到某一结点，发现无法再继续搜索下去时，可以续搜索下去时，可以沿搜索路径回退到前沿搜索路径回退到前一结点，沿另一分支继续搜索一结点，沿另一分支继续搜索。如果回退之后没有其他选择，再沿搜索路如果回退之后没有其他选择，再沿搜索路径回退到更前结点，径回退到更前结点，。依次执行，直到。依

18、次执行，直到搜索到问题的解搜索到问题的解，或，或搜索完全部可搜索的搜索完全部可搜索的分支没有解存在分支没有解存在为止。为止。回溯法与分治法本质相同，可用递归算法回溯法与分治法本质相同，可用递归算法求解。求解。数据结构课件c语言描述第5章n皇后问题皇后问题 在在 n 行行 n 列的国际象棋棋盘上，若列的国际象棋棋盘上，若两两个皇后个皇后位于位于同一行同一行、同一列同一列、同一对角同一对角线线上，则称为它们为上，则称为它们为互相攻击互相攻击。n皇后皇后问题是指问题是指找到这找到这 n 个皇后的互不攻击的个皇后的互不攻击的布局布局。数据结构课件c语言描述第5章1#主对角线主对角线3#主对角线主对角线

19、5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k = i+jk = n+i- -j- -1数据结构课件c语言描述第5章解题思路解题思路n n安放安放第第 i 行行皇后时，需要在列的方向从皇后时，需要在列的方向从 0 到到 n-1 试探试探 ( j = 0, , n-1 ) 。n n在在第第 j 列列安放一个皇后：安放一个皇后：uu如果在如果在列列、主对角线主对角线、次对角线次对角

20、线方向方向有其他皇后，则出现攻击，撤消在有其他皇后，则出现攻击，撤消在第第 j 列列安放的皇后。安放的皇后。uu如果没有出现攻击，在如果没有出现攻击，在第第 j 列列安放的安放的皇后不动，递归安放第皇后不动，递归安放第 i+1行皇后。行皇后。数据结构课件c语言描述第5章n n设置设置 4 个数组个数组u col n ：coli 标识第标识第 i 列是否安放了列是否安放了皇后皇后；u md2n-1 : mdk 标识第标识第 k 条主对角线条主对角线是否安放了皇后；是否安放了皇后；u sd2n-1 : sdk 标识第标识第 k 条次对角线是条次对角线是否安放了皇后；否安放了皇后；u qn : qi

21、 记录第记录第 i 行皇后在第几列。行皇后在第几列。数据结构课件c语言描述第5章void Queen( int i ) for ( int j = 0; j n; j+ ) if ( 第第 i 行第行第 j 列没有攻击列没有攻击 ) 在在第第 i 行第行第 j 列安放皇后列安放皇后； if ( i = n-1 ) 输出一个布局输出一个布局； else Queen ( i+1 ); 撤消撤消第第 i 行第行第 j 列的皇后列的皇后； 数据结构课件c语言描述第5章算法求精算法求精void Queen( int i ) for ( int j = 0; j n; j+ ) if ( !colj &

22、!mdn+i-j-1 & !sdi+j ) /*第第 i 行第行第 j 列没有攻击列没有攻击 */ colj = mdn+i-j-1 = sdi+j = 1; qi = j; /*在在第第 i 行第行第 j 列安放皇后列安放皇后*/ 数据结构课件c语言描述第5章 if ( i = n-1 ) /*输出一个布局输出一个布局*/ for ( k = 0; k n; k+ ) cout qk ,; cout endl; else Queen ( i+1 ); colj = mdn+i-j-1 = sdi+j = 0; qi = 0; /*撤消撤消第第 i 行第行第 j 列的皇后列的皇后*/ 数据结构

23、课件c语言描述第5章迷宫问题迷宫问题小型迷宫小型迷宫 路口路口 动作动作 结果结果 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

24、0 0 0 0 7 0 0 7小小型型迷迷宫宫的的数数据据数据结构课件c语言描述第5章迷宫的类定义迷宫的类定义#include #include #include class Maze private: int MazeSize; int EXIT; Intersection *intsec;public: Maze ( char *filename ); int TraverseMaze ( int CurrentPos );交通路口结构定义交通路口结构定义struct Intersection int left; int forward; int right;数据结构课件c语言描述第5章M

25、aze : Maze ( char *filename ) /构造函数：从文件 filename 中读取各路口/和出口的数据 ifstream fin; fin.open ( filename, ios:in | ios:nocreate ); /为输入打开文件,文件不存在则打开失败 if ( !fin ) cerr “迷宫数据文件” filename “打不开” MazeSize; /输入迷宫路口数数据结构课件c语言描述第5章 intsec = new IntersectionMazeSize+1; /创建迷宫路口数组 for ( int i = 1; i intseci.left ints

26、eci.forward intseci.right; fin EXIT; /输入迷宫出口 fin.close ( );迷宫漫游与求解算法迷宫漫游与求解算法int Maze:TraverseMaze ( int CurrentPos ) if ( CurrentPos 0 ) /路口从 1 开始数据结构课件c语言描述第5章 if ( CurrentPos = EXIT ) /出口处理 cout CurrentPos ; return 1; else /递归向左搜寻可行 if (TraverseMaze(intsecCurrentPos.left ) cout CurrentPos “ ”; re

27、turn 1; else /递归向前搜寻可行 if (TraverseMaze(intsecCurrentPos.forward) cout CurrentPos “ ”; return 1; else /递归向右搜寻可行 if (TraverseMaze(intsecCurrentPos.right) cout CurrentPos 0时，时，表的第一个表元素称为广义表表的第一个表元素称为广义表 的的表头表头(head)，除此之外，其他表元素组除此之外，其他表元素组 成的表称为广义表的成的表称为广义表的表尾表尾(tail)。数据结构课件c语言描述第5章广义表的特性广义表的特性n n有次序性有

28、次序性n n有长度有长度n n有深度有深度n n可共享可共享n n可递归可递归A( )B( 6, 2 ) head(B) = 6, tail(B) =(2)C( a, ( 5, 3, x ) ) D( B, C, A ) head(C) =aE( B, D ) tail(C) = (5,3,x)F( 4, F ) head( (5,3,x) ) = (5,3,x) tail( (5,3,x) ) = ( )数据结构课件c语言描述第5章A AB BC Cu vax y zD Du vax y zB BC CA Au vax y zB BC CA AE ED D空表空表空表空表线性表线性表线性表线

29、性表再入表再入表再入表再入表纯表纯表纯表纯表F F递归表递归表递归表递归表d数据结构课件c语言描述第5章广义表的表示广义表的表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示5232436103914 list25list1 1247as数据结构课件c语言描述第5章广义表结点定义广义表结点定义n n结结点点类类型型 utype = 0, 表表头头；= 1, 整整型型原原子子；= 2, 字符型原子；字符型原子；= 3, 子表。子表。n n值值value utype=0时时, 存存放放引引用用计计数数(re

30、f)；utype=1时时, 存存放放整整数数值值(intinfo)；utype=2时时, 存存放放字字符符型型数数据据(charinfo)；utype=3时时, 存放指向子表表头的指针存放指向子表表头的指针(hlink)。n n尾指针尾指针tlink utype=0时时, 指向该表第一个结指向该表第一个结点；点；utype 0时时, 指向同一层下一个结点。指向同一层下一个结点。 utype value tlink 数据结构课件c语言描述第5章广义表的存储表示广义表的存储表示E EBF F0 11 430 033D 0 11 51 32 x 0 12 a3 C C 0 13330 21 6D D

31、B BBCA1 2 0 1A A 数据结构课件c语言描述第5章广义表的类定义广义表的类定义class GenList; /GenList类的前视声明class GenListNode ; /广义表结点类的前视声明struct Items /仅有结点信息的项friend class GenlistNode;friend class Genlist; int utype; /0 / 1 / 2 / 3 union /联合 数据结构课件c语言描述第5章 int ref; /utype=0, 存放引用计数 int intinfo; /utype=1, 存放整数值 char charinfo; /uty

32、pe =2, 存放字符 GenListNode *hlink; /utype =3, 存放指向子表的指针 value; class GenListNode /广义表结点类定义friend class Genlist;private: int utype; /0 / 1 / 2 / 3数据结构课件c语言描述第5章 GenListNode * tlink;/下一结点指针 union /联合 int ref; /utype=0, 存放引用计数 int intinfo; /utype=1, 存放整数值 char charinfo; /utype=2, 存放字符 GenListNode *hlink;

33、/utype =3, 存放指向子表的指针 value;public: GenListNode ( ) : utype (0), tlink (NULL), ref (0) /构造函数, 建表头结点数据结构课件c语言描述第5章 GenListNode ( int t, GenListNode *next = NULL ) /构造函数：建表结点 Items Info ( ); /返回当前表元素的值 int nodetype ( ) return utype; /返回当前表元素的数据类型 void setInfo ( Items& x ); /将当前表元素中的值修改为x;数据结构课件c语言描述第5章

34、class GenList /广义表类定义 private: GenListNode *first; /广义表头指针 GenListNode *Copy ( GenListNode *ls ); /复制一个 ls 指示的无共享非递归表 int depth ( GenListNode *ls ); /计算由 ls 指示的非递归表的深度 int equal (GenListNode *s, GenListNode *t); /比较以s和t为表头的两个表是否相等 void Remove (GenListNode *ls ); /释放以 ls 为表头结点的广义表数据结构课件c语言描述第5章public

35、: Genlist ( ); /构造函数 GenList ( );/析构函数 Items Head ( ); /返回表头元素 GenList Tail ( ); /返回表尾 GenListNode *First ( ); /返回第一个元素 GenListNode * Next ( GenListNode *elem ); /返回表元素elem的直接后继元素 GenList Addon ( GenList& list, Items x ); /返回一个以x为头，list为尾的新广义表 void GenList : Push ( GenListNode& x ); /将表结点 x 加到表的最前端数

36、据结构课件c语言描述第5章 void setNext ( GenListNode *elem1, GenListNode *elem2 ); /将elem2插到表中元素elem1后 void Copy ( const GenList & l ); /广义表的复制 int depth ( ); /计算一个非递归表的深度 int Createlist ( GenListNode *ls, char * s ); /从广义表的字符串描述 s 出发, /建立一个带表头结点的广义表结构 数据结构课件c语言描述第5章广义表的访问算法广义表的访问算法 广义表结点类的存取成员函数广义表结点类的存取成员函数It

37、ems GenListNode : Info ( ) /返回表元素的值 Items pitem; pitem.utype = utype; pitem.value = value; return pitem;数据结构课件c语言描述第5章void GenListNode : setInfo ( Items& x ) /修改表元素的值为 x utype = x.utype; value = x.value; 广义表类的构造和访问成员函数广义表类的构造和访问成员函数Genlist : GenList ( ) /构造函数 GenListNode *first = new GenListNode; fi

38、rst-utype = 0; first-ref = 0; first-tlink = NULL;数据结构课件c语言描述第5章Items GenList : Head ( ) /若广义表非空，则返回其第一个元素的值，/否则函数没有定义。 if ( first-tlink = NULL ) return NULL; else /非空表 Items temp; temp.utype = frist-tlink-utype; temp.value = frist-tlink-value; return temp; /返回类型及值 数据结构课件c语言描述第5章GenList GenList : Tai

39、l ( ) /若广义表非空，则返回广义表除第一个元/素外其它元素组成的表, 否则函数没有定义 if ( frist-tlink = NULL ) return NULL; GenList temp; temp.first = new GenListNode; temp.first-utype = 0; temp.first-value.ref = 0; temp.first-tlink = Copy ( first-tlink-tlink); return temp; 数据结构课件c语言描述第5章GenListNode * GenList : First ( ) if ( first-tlin

40、k = NULL ) return NULL; else return first-tlink;GenListNode * GenList : Next ( GenListNode *elem ) if ( elem-tlink = NULL ) return NULL; else return elem-tlink;数据结构课件c语言描述第5章GenList& GenList : Addon ( GenList& list, Items x ) /返回一个以x为头，list为尾的新广义表 GenList * newlist; newlist-first = new GenListNode;

41、newlist-first-utype = 0; newlist-first-value.ref = 0; newlist-first-tlink = Copy ( list.first ); newlist-first-tlink-setInfo (x); /将list的表头结点改为newlist的head结点 return newlist; 数据结构课件c语言描述第5章void GenList : Push ( GenListNode& x ) /将表结点 x 加到表的最前端 if ( first-tlink = NULL ) first-tlink = x; else x-tlink =

42、 first-tlink; first-tlink = x; 数据结构课件c语言描述第5章广义表的递归算法广义表的递归算法 广义表的复制算法广义表的复制算法 void GenList : Copy ( const GenList& ls ) first = Copy ( ls.first ); /共有函数GenListNode* GenList : Copy ( GenListNode * ls ) /私有函数 GenListNode *q = NULL; if ( ls != NULL ) q = new GenListNode ( ls-utype, NULL );数据结构课件c语言描述第

43、5章 switch ( ls-utype ) case 0: q-value.ref = ls-value.ref; break; case 1: q-value.intgrinfo = ls-value.intgrinfo; break; case 2: q-value.charinfo = ls-value.charinfo; break; case 3: q-value.hlink = Copy (ls-value.hlink); 数据结构课件c语言描述第5章 q-tlink = Copy (ls-tlink); return q;数据结构课件c语言描述第5章求广义表的深度求广义表的深度

44、例如，对于广义表例如，对于广义表 E (B (a, b), D (B (a, b), C (u, (x, y, z), A ( ) ) )1111234数据结构课件c语言描述第5章int GenList : depth ( GenListNode *ls ) if ( ls-tlink = NULL ) return 1; /空表 GenListNode * temp = ls-tlink; int m = 0; while ( temp != NULL ) /在表顶层横扫 if ( temp-utype = 3 ) /结点为表结点 int n = depth ( temp-value.hli

45、nk ); if ( m tlink; return m+1;数据结构课件c语言描述第5章int GenList : depth ( ) return depth ( first );广义表的删除算法广义表的删除算法0 11 5331 2 0 12 x 0 10 12 yls32 x n n 扫描子链表扫描子链表uu 若结点数据为若结点数据为x, 删除。可能做循环连续删。删除。可能做循环连续删。uu 若结点数据不为若结点数据不为x，不执行删除。不执行删除。uu 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。数据结构课件c语言描述第5章 扫描子链表扫描子链表1) 若结点数据

46、为若结点数据为x, 删除。可能做循删除。可能做循环连续删。环连续删。2) 若结点数据不为若结点数据不为x，不执行删除。不执行删除。3) 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。void delvalue(GenListNode * ls, const value x) /在广义表中删除所有含 x 的结点 if ( ls-tlink != NULL ) /非空表 GenListNode * p = ls-tlink;数据结构课件c语言描述第5章 while ( p != NULL & /横扫链表 ( ( p-utype = 1 & p-value.intinfo =

47、x ) | ( p-utype = 2 & p-value.charinfo = x ) ) ls-tlink = p-tlink; delete p; /删除 p = ls-tlink; /指向同一层后继结点 if ( p != NULL ) if ( p-utype = 3 ) /在子表中删除 delvalue ( p-value.hlink, x ); 数据结构课件c语言描述第5章 delvalue ( p, x ); /在后续链表中删除 GenList : GenList ( ) /析构函数 Remove ( first ); delete (first);void GenList :

48、 Remove ( GenListNode *ls ) /私有函数：释放以 ls 为表头指针的广义表 ls-value.ref -; /引用计数减1数据结构课件c语言描述第5章 if ( ls-value.ref tlink != NULL ) q = ls-tlink; /到第一个结点 if ( q-utype = 3 ) /递归删除子表 Remove ( q-value.hlink ); if ( q-value.hlink-value.ref value.hlink; ls-tlink = q-tlink; delete q; 数据结构课件c语言描述第5章从字符串从字符串s 建立广义表的

49、链表表示建立广义表的链表表示 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 ); /脱去广义表外面的引号 数据结构课件c语言描述第5章 G

50、enListNode* p = ls; while ( strlen (sub) != 0 ) /建立表结点 p = p-tlink = new GenListNode ( ); /创建新结点,向表尾链接 if ( sever ( sub, hsub ) ) /以逗号为界,分离第一个表元素hsub if ( hsub0 != ( & hsub0 != 0 ) /非子表,非字符分界符 p-utype = INTGR; /转换整型结点 p-value.intgrinfo = atoi ( hsub ); else 数据结构课件c语言描述第5章 if ( hsub0 != ( & hsub0 = 0

51、 ) /非子表且是字符分界符 p-utype = CH; p-value.charinfo = hsub; else /是子表,递归建立子表 p-utype = LST; CreateList ( p-value.hlink, hsub ); else return 0; /字符串表达式有错 /循环完成数据结构课件c语言描述第5章 p-tlink = NULL; /封闭最后一个结点 return 1; int Genlist : sever ( char *str1, char *hstr1 ) /对不含外分界符的字符串分离第一个元素 char ch = str10; int n = strl

52、en ( str1 ); int i = 0, k = 0; /检测str1,扫描完或遇到, 且括号配对则停 数据结构课件c语言描述第5章 while ( i n & ( ch != , | k != 0 ) ) if ( ch = ( ) k+; else if ( ch = ) ) k-; i+; ch = str1i; / i 计数计数, 取一字取一字符符 if ( i n ) strncpy ( hstr1, str1, i-1 ); /str1的前 i- -1 个字符传送到hstr1 strncpy ( str1, str1+i, n-i ); /后后n- -i个字符留在str1, 滤去, return 1; 数据结构课件c语言描述第5章 else if ( k != 0 ) return 0; /括号不配对出错 else /括号配对 strcpy ( hstr1, str1 ); str1 = 0; /str1全部传送给hstr1 return 1; 数据结构课件c语言描述第5章设设 str = ( ( 2, ( b, 7 ) ), ( ), ( d ) )得到的广义表链表结构得到的广义表链表结构数据结构课件c语言描述第5章