? 递归 (Recurve)的概念
迷宫 (Maze)问题
递归过程与递归工作栈
广义表 (General Lists )
递归的概念
递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。
在以下三种情况下，常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的定义是递归的求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
例如，阶乘函数
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 n! 的过程计算斐波那契数列的函数 Fib(n)的定义求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1),2()1(
0,1,
)(
nnF i bnF i b
nn
nF i b
数据结构是递归的搜索链表最后一个结点并打印其数值
template <class Type>
void Find ( ListNode<Type> *f ) {
if ( f → link == NULL )
cout << f → data << endl;
else Find ( f → link );
}
例如，单链表结构在链表中寻找等于给定值的结点并打印其数值
template <class Type> void Print
( ListNode<Type> *f ) {
if ( f != NULL)
if ( f → data == x )
cout << f→ data << endl;
else Print ( f→ link );
}
问题的解法是递归的例如，汉诺塔 (Tower of Hanoi)问题
#include <iostream.h>
#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 );
}
}
迷宫问题 小型迷宫路口 动作 结果
1 (入口 ) 正向走 进到 2
2 左拐弯 进到 3
3 右拐弯 进到 4
4 (堵死 ) 回溯 退到 3
3 (堵死 ) 回溯 退到 2
2 正向走 进到 5
5 (堵死 ) 回溯 退到 2
2 右拐弯 进到 6
6 左拐弯 进到 7
(出口 )
4
3
5
2
1
7
6
6
左 0 直 2 右 0
行 3 行 5 行 6
0 0 4
0 0 0
0 0 0
7 0 0
7
小型迷宫的数据迷宫的类定义
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
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;
}
Maze::Maze ( char *filename ) {
//构造函数：从文件 filename 中读取各路口
//和出口的数据
ifstream fin;
fin.open ( filename,ios::in | ios::nocreate );
//为输入打开文件,文件不存在则打开失败
if ( !fin ) {
cout <<,迷宫数据文件,<< filename
<<,打不开,<< endl;
exit (1);
}
fin >> MazeSize; //输入迷宫路口数
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 开始
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;
}
递归过程与递归工作栈
递归过程在实现时，需要自己调用自己。
每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
层层向下递归，退出时的次序正好相反：
递归次序
n! (n-1)! (n-2)! 1! 0!=1
返回次序
因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。
函数递归时的活动记录
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
}
计算 Factorial时活动记录的内容调用次数 NumCall(k) = 2*Fib(k+1) - 1。
斐波那契数列的递归调用树打印数组 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
void iterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
cout << "value " << A[n] << endl;
n--;
}
}
广义表 (General Lists )
广义表的概念 n (? 0 )个表元素组成的有限序列,记作
LS = (a0,a1,a2,…,an-1)
LS是表名,ai是表元素，它可以是表 (称为 子表 )，可以是数据元素 (称为 原子 )。
n为表的长度。 n = 0 的广义表为空表。
n > 0时,表的 第一个表元素 称为广义表的 表头 (head)，除此之外,其它表元素组成的 表 称为广义表的 表尾 (tail)。
广义表的特性
有次序性
有长度
有深度
可递归
可共享
A = ( )
B = ( 6,2 )
C = ( ‘a’,( 5,3,‘x’ ) )
D = ( B,C,A )
E = ( B,D )
F = ( 4,F )
各种广义表的示意图广义表的表示只包括整数和字符型数据的广义表链表表示表中套表情形下的广义表链表表示广义表结点定义
标志域 utype,表明结点类型。 0为表头结点,1
为整型原子结点,2为字符型原子结点,3为子表结点。
值域 value。当 utype = 0 时为 表引用计数,= 1
时为 整数值,= 2 时为 字符值,= 3 时为 指向子表的表头结点的指针 。
尾指针域 tlink。当 utype = 0 时为指向该表表头元素的指针；当 utype? 0 时为指向同一层下一个表结点的指针。
utype = 0/1/2/3 value = ref /intgrinfo /charinfo / hlink tlink
广义表的带表头结点的存储表示广义表的类定义
#define HEAD 0
#define INTGR 1
#define CH 2
#define LST 3
class GenList;
class GenListNode {
friend class Genlist;
private:
int utype;
GenListNode * tlink;
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 );
};
class GenList {
private:
GenListNode *first;
GenListNode* GenList::Copy ( GenListNode
*ls );
int depth ( GenListNode *ls );
int equal ( GenListNode *s,GenListNode *t );
void GenList::Remove (GenListNode *ls );
public:
Genlist ( );
~GenList ( );
GenListNode &Head ( );
GenListNode *Tail ( );
GenListNode *First ( );
GenListNode * Next ( GenListNode *elem );
void Push ( GenListNode &x );
GenList & Addon ( GenList & list,
GenListNode & x );
void setHead ( GenListNode &x );
viod setNext ( GenListNode *elem1,
GenListNode *elem2 );
void setTail ( GenList & list );
void Copy ( const GenList & l );
int depth ( );
int Createlist ( GenListNode *ls,char * s );
}
广义表的访问算法广义表结点类的存取成员函数
GenListNode &GenListNode::
Info (GenListNode *elem ) {
//提取广义表中指定表元素 elem的值
GenListNode * pitem = new GenListNode;
pitem→ utype = elem→ utype;
pitem→ value = elem→ value;
return & pitem;
}
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 = 0;
first→ tlink = NULL; //仅建立表头结点
}
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;
}
}
void GenList::Push ( GenListNode &x ) {
//将表结点 x 加到表的最前端
if ( first→ tlink == NULL ) first→ tlink = x;
else {
x→ tlink = first→ tlink; first→ tlink = x;
}
}
GenList & GenList::Addon ( GenList & list,
GenListNode &x ) {
//返回一个以 x为头,list为尾的新广义表
GenList newlist = new GenList;
newlist.first→ tlink = Copy ( list.first );
x→ tlink = newlist.frist→ tlink;
newlist.frist→ tlink = x;
return & newlist;
}
广义表的递归算法广义表的复制算法
void GenList::Copy ( const GenList & l ) {
first→ tlink = Copy ( l.first );
}
GenListNode* GenList::Copy(GenListNode *ls)
{
GenListNode *q = NULL;
if ( ls != NULL ) {
q = new GenListNode; //创建表结点
q→ utype = ls→ utype; //复制 utype
switch ( ls→ utype ) {
case HEAD,q→ ref = ls→ ref; break;
case INTGR,
q→ intgrinfo = ls→ intgrinfo;
break;
case CH,q→ charinfo = ls→ charinfo;
break;
case LST,q→ hlink = Copy ( ls→ hlink );
break;
}
q→ tlink = Copy ( ls→ tlink );
}
return q;
}
图 5.16 广义表 ls的链表结构递归顺序 s0→ tlink s1→ hlink t0→ tlink
t1→ tlink t2→ tlink NULL 回退 t2 回退
t1回退 t0回退 s1→ tlink s2→ hlink
u0→ tlink u1→ hlink v0→ tlink v1→ tlink
v2→ tlink NULL 回退 v2 回退 v1 回退
v0 回退 u1→ tlink u2→ tlink NULL 回退
u2 回退 u1 回退 u0 回退 s2→ tlink
NULL 回退 s2 回退 s1回退 s0 回退求广义表的深度
1) },({1
,0
,1
)(
10
naD e p t h
LS
LS
LSD e p t h
i
ni
，其它为原子时当为空表时当
m a x
例如，对于广义表
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)}
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} = 4
E ( B (a,b),D ( B (a,b),C (u,(x,y,z)),A ( ) ) )
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→ hlink );
if ( m < n ) m = n;
} //不是子表不加深度
temp = temp→ tlink;
}
return m+1;
}
int GenList::depth ( ) {
return depth ( first );}
广义表的删除算法删除 'x'前的广义表链表结构
扫描子链表
若结点数据为‘ x’,删除。可能做循环连续删。
若结点数据不为‘ x’，不执行删除。
若结点为子表，递归在子表执行删除。
void delvalue (GenListNode * ls,const value x)
{ //在广义表中删除所有含 x的结点
if ( ls→ tlink != NULL ) {
GenListNode * p = ls→ tlink; //横扫链表
while ( p != NULL &&
(p→ utype==INTGR || p→ utype==CH )
&& p→ value == x ) {
ls→ tlink = p→ tlink; delete p; //删除
p = ls→ tlink; // p指向同层下一结点
}
//链表检测完或遇到子表或走到子表表
//头 结点或不是含 x结点,转出循环
if ( p != NULL ) {
if ( p→ utype == LST ) //到子表中删除
delvalue ( p→ hlink,x );
delvalue ( p,x ); //向后 递归删除
}
}
}
GenList::~GenList ( ) { //析构函数
Remove ( first );
}
void GenList::Remove (GenListNode *ls ) {
ls→ ref --; //引用计数减一
if ( !ls→ ref ) { //引用计数减至 0才能删除
GenListNode *y = ls;
while ( y→ tlink != NULL ) { //横扫链表
y = y→ tlink;
if ( y→ utype == LST ) //遇到子表
Remove ( y→ hlink ); //递归删除
}
y→ tlink = av; av = ls;
//扫描完后,回收到可利用空间表
}
}
从字符串 s建立广义表的链表表示 ls
int Genlist::
CreateList ( GenListNode *ls,char * s ) {
char *sub,*hsub; int tag;
ls = new GenListNode ( ); //建立表头结点
ls→ utype = HEAD; ls→ ref = 1;
if ( strlen (s) == 0 || !strcmp ( s,"( )" ) )
ls→ tlink = NULL; //空表
else {
strncpy ( sub,s+1,strlen (s)-2 );
//脱去广义表外面的引号
GenListNode* p = ls;
while ( strlen (sub) != 0 ) { //建立表结点
p = p→ tlink = new GenListNode ( );
//创建新结点,向表尾链接
if ( sever ( sub,hsub ) ) {
//以逗号为界,分离第一个表元素 hsub
if ( hsub[0] != '(' && hsub[0] != ''' ) {
//非子表,非字符分界符
p→ utype = INTGR; //转换整型结点
p→ intgrinfo = atoi ( hsub );
}
else
if ( hsub[0] != '(' && hsub[0] == ''' ) {
//非子表且是字符分界符
p→ utype = CH;
p→ charinfo = hsub;
}
else { //是子表,递归建立子表
p→ utype = LST;
CreateList ( p→ hlink,hsub );
}
}
else return 0; //字符串表达式有错
} //循环完成
p→ tlink = NULL; //封闭最后一个结点
}
return 1;
}
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 ) ) {
ch = str1[i]; i++; //取一字符,i计数
if ( ch == '(' ) k++;
else if ( ch == ')' ) k--;
}
if ( i < n ) {
strncpy ( hstr1,str1,i-2 );
//str1的前 i-2个字符传送到 hstr1
strncpy ( str1,str1+i-1,n-i+1 );
//后 n-i+1个字符留在 str1,滤去 ‘,’
return 1;
}
else if ( k != 0 ) return 0; //括号不配对出错
else { //括号配对
strcpy ( hstr1,str1 ); str1 = 0;
//str1全部传送给 hstr1
return 1;
}
}
设 str = ‘( ( 2,( ‘b’,7 ) ),( ),( ‘d’ ) )’
得到的广义表链表结构
迷宫 (Maze)问题
递归过程与递归工作栈
广义表 (General Lists )
递归的概念
递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。
在以下三种情况下，常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的定义是递归的求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n*Factorial (n-1);
}
例如，阶乘函数
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 n! 的过程计算斐波那契数列的函数 Fib(n)的定义求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1),2()1(
0,1,
)(
nnF i bnF i b
nn
nF i b
数据结构是递归的搜索链表最后一个结点并打印其数值
template <class Type>
void Find ( ListNode<Type> *f ) {
if ( f → link == NULL )
cout << f → data << endl;
else Find ( f → link );
}
例如，单链表结构在链表中寻找等于给定值的结点并打印其数值
template <class Type> void Print
( ListNode<Type> *f ) {
if ( f != NULL)
if ( f → data == x )
cout << f→ data << endl;
else Print ( f→ link );
}
问题的解法是递归的例如，汉诺塔 (Tower of Hanoi)问题
#include <iostream.h>
#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 );
}
}
迷宫问题 小型迷宫路口 动作 结果
1 (入口 ) 正向走 进到 2
2 左拐弯 进到 3
3 右拐弯 进到 4
4 (堵死 ) 回溯 退到 3
3 (堵死 ) 回溯 退到 2
2 正向走 进到 5
5 (堵死 ) 回溯 退到 2
2 右拐弯 进到 6
6 左拐弯 进到 7
(出口 )
4
3
5
2
1
7
6
6
左 0 直 2 右 0
行 3 行 5 行 6
0 0 4
0 0 0
0 0 0
7 0 0
7
小型迷宫的数据迷宫的类定义
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
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;
}
Maze::Maze ( char *filename ) {
//构造函数：从文件 filename 中读取各路口
//和出口的数据
ifstream fin;
fin.open ( filename,ios::in | ios::nocreate );
//为输入打开文件,文件不存在则打开失败
if ( !fin ) {
cout <<,迷宫数据文件,<< filename
<<,打不开,<< endl;
exit (1);
}
fin >> MazeSize; //输入迷宫路口数
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 开始
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;
}
递归过程与递归工作栈
递归过程在实现时，需要自己调用自己。
每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
层层向下递归，退出时的次序正好相反：
递归次序
n! (n-1)! (n-2)! 1! 0!=1
返回次序
因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。
函数递归时的活动记录
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
}
计算 Factorial时活动记录的内容调用次数 NumCall(k) = 2*Fib(k+1) - 1。
斐波那契数列的递归调用树打印数组 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
void iterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
cout << "value " << A[n] << endl;
n--;
}
}
广义表 (General Lists )
广义表的概念 n (? 0 )个表元素组成的有限序列,记作
LS = (a0,a1,a2,…,an-1)
LS是表名,ai是表元素，它可以是表 (称为 子表 )，可以是数据元素 (称为 原子 )。
n为表的长度。 n = 0 的广义表为空表。
n > 0时,表的 第一个表元素 称为广义表的 表头 (head)，除此之外,其它表元素组成的 表 称为广义表的 表尾 (tail)。
广义表的特性
有次序性
有长度
有深度
可递归
可共享
A = ( )
B = ( 6,2 )
C = ( ‘a’,( 5,3,‘x’ ) )
D = ( B,C,A )
E = ( B,D )
F = ( 4,F )
各种广义表的示意图广义表的表示只包括整数和字符型数据的广义表链表表示表中套表情形下的广义表链表表示广义表结点定义
标志域 utype,表明结点类型。 0为表头结点,1
为整型原子结点,2为字符型原子结点,3为子表结点。
值域 value。当 utype = 0 时为 表引用计数,= 1
时为 整数值,= 2 时为 字符值,= 3 时为 指向子表的表头结点的指针 。
尾指针域 tlink。当 utype = 0 时为指向该表表头元素的指针；当 utype? 0 时为指向同一层下一个表结点的指针。
utype = 0/1/2/3 value = ref /intgrinfo /charinfo / hlink tlink
广义表的带表头结点的存储表示广义表的类定义
#define HEAD 0
#define INTGR 1
#define CH 2
#define LST 3
class GenList;
class GenListNode {
friend class Genlist;
private:
int utype;
GenListNode * tlink;
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 );
};
class GenList {
private:
GenListNode *first;
GenListNode* GenList::Copy ( GenListNode
*ls );
int depth ( GenListNode *ls );
int equal ( GenListNode *s,GenListNode *t );
void GenList::Remove (GenListNode *ls );
public:
Genlist ( );
~GenList ( );
GenListNode &Head ( );
GenListNode *Tail ( );
GenListNode *First ( );
GenListNode * Next ( GenListNode *elem );
void Push ( GenListNode &x );
GenList & Addon ( GenList & list,
GenListNode & x );
void setHead ( GenListNode &x );
viod setNext ( GenListNode *elem1,
GenListNode *elem2 );
void setTail ( GenList & list );
void Copy ( const GenList & l );
int depth ( );
int Createlist ( GenListNode *ls,char * s );
}
广义表的访问算法广义表结点类的存取成员函数
GenListNode &GenListNode::
Info (GenListNode *elem ) {
//提取广义表中指定表元素 elem的值
GenListNode * pitem = new GenListNode;
pitem→ utype = elem→ utype;
pitem→ value = elem→ value;
return & pitem;
}
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 = 0;
first→ tlink = NULL; //仅建立表头结点
}
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;
}
}
void GenList::Push ( GenListNode &x ) {
//将表结点 x 加到表的最前端
if ( first→ tlink == NULL ) first→ tlink = x;
else {
x→ tlink = first→ tlink; first→ tlink = x;
}
}
GenList & GenList::Addon ( GenList & list,
GenListNode &x ) {
//返回一个以 x为头,list为尾的新广义表
GenList newlist = new GenList;
newlist.first→ tlink = Copy ( list.first );
x→ tlink = newlist.frist→ tlink;
newlist.frist→ tlink = x;
return & newlist;
}
广义表的递归算法广义表的复制算法
void GenList::Copy ( const GenList & l ) {
first→ tlink = Copy ( l.first );
}
GenListNode* GenList::Copy(GenListNode *ls)
{
GenListNode *q = NULL;
if ( ls != NULL ) {
q = new GenListNode; //创建表结点
q→ utype = ls→ utype; //复制 utype
switch ( ls→ utype ) {
case HEAD,q→ ref = ls→ ref; break;
case INTGR,
q→ intgrinfo = ls→ intgrinfo;
break;
case CH,q→ charinfo = ls→ charinfo;
break;
case LST,q→ hlink = Copy ( ls→ hlink );
break;
}
q→ tlink = Copy ( ls→ tlink );
}
return q;
}
图 5.16 广义表 ls的链表结构递归顺序 s0→ tlink s1→ hlink t0→ tlink
t1→ tlink t2→ tlink NULL 回退 t2 回退
t1回退 t0回退 s1→ tlink s2→ hlink
u0→ tlink u1→ hlink v0→ tlink v1→ tlink
v2→ tlink NULL 回退 v2 回退 v1 回退
v0 回退 u1→ tlink u2→ tlink NULL 回退
u2 回退 u1 回退 u0 回退 s2→ tlink
NULL 回退 s2 回退 s1回退 s0 回退求广义表的深度
1) },({1
,0
,1
)(
10
naD e p t h
LS
LS
LSD e p t h
i
ni
，其它为原子时当为空表时当
m a x
例如，对于广义表
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)}
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} = 4
E ( B (a,b),D ( B (a,b),C (u,(x,y,z)),A ( ) ) )
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→ hlink );
if ( m < n ) m = n;
} //不是子表不加深度
temp = temp→ tlink;
}
return m+1;
}
int GenList::depth ( ) {
return depth ( first );}
广义表的删除算法删除 'x'前的广义表链表结构
扫描子链表
若结点数据为‘ x’,删除。可能做循环连续删。
若结点数据不为‘ x’，不执行删除。
若结点为子表，递归在子表执行删除。
void delvalue (GenListNode * ls,const value x)
{ //在广义表中删除所有含 x的结点
if ( ls→ tlink != NULL ) {
GenListNode * p = ls→ tlink; //横扫链表
while ( p != NULL &&
(p→ utype==INTGR || p→ utype==CH )
&& p→ value == x ) {
ls→ tlink = p→ tlink; delete p; //删除
p = ls→ tlink; // p指向同层下一结点
}
//链表检测完或遇到子表或走到子表表
//头 结点或不是含 x结点,转出循环
if ( p != NULL ) {
if ( p→ utype == LST ) //到子表中删除
delvalue ( p→ hlink,x );
delvalue ( p,x ); //向后 递归删除
}
}
}
GenList::~GenList ( ) { //析构函数
Remove ( first );
}
void GenList::Remove (GenListNode *ls ) {
ls→ ref --; //引用计数减一
if ( !ls→ ref ) { //引用计数减至 0才能删除
GenListNode *y = ls;
while ( y→ tlink != NULL ) { //横扫链表
y = y→ tlink;
if ( y→ utype == LST ) //遇到子表
Remove ( y→ hlink ); //递归删除
}
y→ tlink = av; av = ls;
//扫描完后,回收到可利用空间表
}
}
从字符串 s建立广义表的链表表示 ls
int Genlist::
CreateList ( GenListNode *ls,char * s ) {
char *sub,*hsub; int tag;
ls = new GenListNode ( ); //建立表头结点
ls→ utype = HEAD; ls→ ref = 1;
if ( strlen (s) == 0 || !strcmp ( s,"( )" ) )
ls→ tlink = NULL; //空表
else {
strncpy ( sub,s+1,strlen (s)-2 );
//脱去广义表外面的引号
GenListNode* p = ls;
while ( strlen (sub) != 0 ) { //建立表结点
p = p→ tlink = new GenListNode ( );
//创建新结点,向表尾链接
if ( sever ( sub,hsub ) ) {
//以逗号为界,分离第一个表元素 hsub
if ( hsub[0] != '(' && hsub[0] != ''' ) {
//非子表,非字符分界符
p→ utype = INTGR; //转换整型结点
p→ intgrinfo = atoi ( hsub );
}
else
if ( hsub[0] != '(' && hsub[0] == ''' ) {
//非子表且是字符分界符
p→ utype = CH;
p→ charinfo = hsub;
}
else { //是子表,递归建立子表
p→ utype = LST;
CreateList ( p→ hlink,hsub );
}
}
else return 0; //字符串表达式有错
} //循环完成
p→ tlink = NULL; //封闭最后一个结点
}
return 1;
}
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 ) ) {
ch = str1[i]; i++; //取一字符,i计数
if ( ch == '(' ) k++;
else if ( ch == ')' ) k--;
}
if ( i < n ) {
strncpy ( hstr1,str1,i-2 );
//str1的前 i-2个字符传送到 hstr1
strncpy ( str1,str1+i-1,n-i+1 );
//后 n-i+1个字符留在 str1,滤去 ‘,’
return 1;
}
else if ( k != 0 ) return 0; //括号不配对出错
else { //括号配对
strcpy ( hstr1,str1 ); str1 = 0;
//str1全部传送给 hstr1
return 1;
}
}
设 str = ‘( ( 2,( ‘b’,7 ) ),( ),( ‘d’ ) )’
得到的广义表链表结构
