《数据结构》第五章：递归

5.1 递归基础

函数直接或间接地调用自身，称为递归调用。含有递归调用地函数称为递归函数。递归调用用的是相同地策略去解决规模更小的问题，直至问题规模小于或等于某个边界条件时，不再进行递归调用，而是直接处理。

5.1.1汉诺塔问题

有3根柱子A、B、C，啊hi有一组数量为n、大小不一的圆盘。开始时，所有圆盘从大到小叠放在A柱上。游戏任务是将所有圆盘从A移动的任何时刻都不允许大盘子在小盘子之上，每次移动只能移动最上面的一个盘子

现从1开始对圆盘从小到大编号。圆盘数量决定了汉诺塔问题的复杂程度。

当n=1时，可直接将盘子从A移动到C。

当n=2时，由于规则限制，既不能将两个盘子立即从A移动到C，也不能直接把2号盘抽出来移动到C，所以为了移动2号盘，唯有先把1

号盘从A移动到B，然后将2号盘从A移到C，最后将1号盘B移到C。

当n=3时，仍然可以沿用n=2时的思路，为了移动3号盘，先将1号盘和2号盘从A移动到B，剩余步骤也类似。

由上述分析可以得到n>1时的一般求解步骤。

1. 将1至n-1号盘从A柱移动到B柱。
2. 然后将n号盘从A柱移动带C柱。
3. 将1至n-1号盘从B移动到C柱。

其中步骤（1）和（3）是求解n-1规模的汉诺塔问题，可用递归调用实现。

算法：汉诺塔

void hanoi(int n,char x,char y,char z){

    //以y为中转柱，将n个盘从x移动到目标柱z

    if(n==1)

    {
    
    move(x,1,z);//将1号盘从x移动到z柱

    }

    else{

    hanoi(n-1,x,z,y)//将1至n-1号盘从x柱移动到y柱，z为中转柱

    move(x,n,z);//将n号盘从x柱移动到z柱

    hanoi(n-1,y,x,z);//将1至n-1号盘从y柱移动到z柱，x为中转柱

    }

}

5.1.2递归函数执行过程

在程序执行过程中，递归函数调用与一般函数调用的处理相同。但在递归函数执行过程中，每次递归调用时，总会跳转至函数的入口处执行，造成重新执行的假象。实际上在递归调用中，虽然代码被重复执行，但每次执行时程序的运行空间（包括局部变量、传递参数和返回结果）并不相同，所以两次递归调用的执行过程其实是完全不同的。

函数递归调用的嵌套层数称为递归层次。其他函数对递归函数的调用称为第0层调用。

函数调用时的执行过程可以借助函数调用栈来完成。但函数M调用函数F时，暂停执行M，转去执行F。当F执行结束，则返回M继续执行，继续执行的指令地址称为返回地址RA。每次发生函数调用时，在栈顶开辟一段称之为栈帧的存储空间，用于存放实参、局部变量和返回地址等。

在执行F的代码之前，系统需要完成以下工作：

1. 将所有实参、返回地址等信息传给F。
2. 为F中的局部变量分配存储空间。
3. 转到F的第一条将要被执行的代码（入口代码）处，准备开始执行。

当F的代码执行完毕，在返回M之前，系统需要进行以下工作。

1. 保存F的计算结果（如果有）。
2. 释放F使用的栈帧，包括实参和局部变量占用的空间等。
3. 转到返回地址RA，继续执行。

如果函数M对自身递归调用，相当于函数M与F是同一个函数。假设主函数main在第i行调用了汉诺塔函数hanoi(3,A,B,C):

void main(){

...

hanoi(3,A,B,C);//第i行

...

}

调用hanoi(3,A,B,C)时，在函数调用栈中压入栈帧“i+1，3，A，B，C”，其中i+1是返回地址，3，A，B，C是传递的实参。当hanoi(3,A,B,C)执行到第4行时，进入第1层递归调用hanoi(2,A,B,C)，此时压入栈帧“5，2，A，C，B”，返回地址为5.同理hanoi(2,A,C,B)执行至第4行时发生第2层调用hanoi（1，A，B，C），并压入栈帧“5，1，A，B，C”。

当hanoi(1,A,B,C)执行完毕，则栈帧“5，1，A，B，C”出栈，返回执行第1层hanoi(2,A,C，B)的第5行继续执行，到第6行时又发生第二层调用hanoi(1,C,A,B)，压入的栈帧为“7，1，C，A，B”。这两次进入第二层的返回地址和实参都不同，是两次不同的函数调用。

5.2 递归与分治

分治是指将一个难以直接解决的大问题，递归分割成一些规模较小的相同问题，以便逐个解决。

5.2.1 分治法

具有以下特征问题可用分治法求解。

1. 当问题规模小到一定程度，可以直接求解。
2. 当问题规模较大时，可以分解为若干个相互独立的子问题，这些子问题与原问题具有相同的特征。若不能直接求解，则可分为递归求解。
3. 原问题的解时子问题解的组合，其组合方法根据问题的具体情况而定。

分治法的基本思路是，把规模为n的输入分割成k（2≤k≤n）个子集，从而产生l个子问题（一般情况下l≥k），分别求解得到l个子问题的解，并将子解组合成原问题的解。

例如：利用分治法求解汉诺塔问题的要点如下：

1. 需要求解的问题：将n个圆盘从源柱移动至目标柱。
2. 输入：规模为n的圆盘
3. 规模分割：k=2，其中一个自己规模为1，另一个为n-1.
4. 问题分解：l=3,即产生了3个子问题（将1～n-1圆盘从源柱移至中转柱，将n号盘子从源柱移动到目标柱，将1～n-1圆盘从中转柱移至目标柱）。
5. 解的组合：子问题的求解次序即圆盘移动的次序构成了解的组合。

在采用分治法设计递归算法时，需要注意：
（1）规模为n的输入是被处理的对象，将其分割为k个子集后，需要分别对这些子集进行处理，其中有些子集可能对应多个子问题，因而最终产生的子问题数l会大于等于k。例如汉诺塔问题，“1～n-1圆盘”这个子集对应了2个子问题：“将1～n-1圆盘从源柱移至中转柱”和“将1～n-1圆盘从中转柱移至目标柱”。

（2）确定递归边界，即确定问题规模小到什么程度时，可以直接求解。在汉诺塔问题中，递归边界是圆盘数量为1，此时只需直接将圆盘从源柱移到目标柱，而无须递归处理。

（3）在问题规模大于递归边界时，由于处理策略是相同的，所以应“信任”递归调用可以处理子问题，无需关注子问题的求解细节。例如在hanoi（n,x,y,z）调用执行程序中，应信任hanoi(n-1,x,z,y)可以将1～n-1号圆盘移至中转柱y。

（4）要根据问题的特点决定解的组合问题。例如：汉诺塔问题的解的形式是move函数的调用序列。

5.2.2 折半查找

从分治的角度看，顺序查找每次将顺序表分解为1和n-1两个子集，首先在规模为1的子集中查找，若不成功，则继续在规模为n-1的子集中递归查找。这种方法导致子集规模缩减较慢，其时间复杂度为O（n）。

如果顺序表有序，则可采用折半查找的策略，将有序表分解为3个查找区间：前后两个区间的规模大致相等，中间区间长度为1，由于待查找关键字只可能落在这3个区间之一，所以在每次递归查找时，可以将区间规模大致缩减一半，从而大大加快查找效率。

例：在有序表的关键字序列(06，10，20，21，49，51，69，79，82，88，94)中折半查找21。

假设该有序表的记录存储在数组rcd，设立两个位标low和high，用于指示当前查找区间rcd[low,high]，取中间点mid[(low+high)/2]为界，将区间折半为rcd[low..mid-1]和rcd[mid+1..high]的前、后两个半区。在第一次查找中，首先取中间关键字rcd[mid],key=51，与目标关键字key=21作比较，发现21<51，于是将有序序列第一次折半为前半区rcd[0..4]和后半区rcd[6..10]，并且只需搜索前半区rcd[0..4]，即high向前移动至mid-1，查找区间大约缩小一半。继续在rcd[0..4]中取中间关键字rcd[2].key=20，有21＞20，于是第二次折半，low向后移动至mid+1，仅在后半区rcd[3..4]中搜索，此时rcd[3..4]中的中间关键字为rcd[3].key=21，与目标关键字相等，于是直接返回当前中间关键字的位标，即3。

查找另一个关键字85，考察第三次折半之后的情况，此时中间关键字rcd[9].key=88，目标关键字85＜88，所以当前区间rcd[9..10]平分，并且取前半区继续进行搜索。但此时移动high至mid-1后出现low＞high的情况，说明关键字在整个有序序列中不存在，查找失败。

折半查找算法可用递归实现，其算法思路如下：

1. 记录按关键字有序存储在数组rcd[low..high]中，待查找目标关键字为key。如果high<low，则序列为空，查找失败，结束；否则以中间位置mid=（low+high）/2为界，将rcd[low..high]分为三个子序列：低半区rcd[low,mid-1]、中间关键字rcd[mid]和高半区rcd[mid+1..high]。
2. 将rcd[mid]与key比较，产生以下三个子问题：

• 如果rcd[mid]==key，则查找成功，结束。
• 如果rcd[mid]<key，则key位于后半区，在rcd[mid+1..high]内进行折半查找。
• 如果rcd[mid]>key，则key位于前半区，在rcd[low..mid-1]内进行折半查找。

在这3个子问题中，如果求解①成功，则整个问题求解成功；否则只需在②或③中选取一个子问题进行求解。

算法：递归实现的折半查找

int BinSearch(RcdType rcd[],KeyType key,int low,int high)
{
	//在有序序列rcd[low..high]中折半查找目标关键字key
	int mid=(low+high)/2;
	if(low>high)
	{
		return -1;//没有查找到 
	}
	if(rcd[mid].key==key)
	{
		return mid;//关键字和中间关键字相同 
	}
	else if(rcd[mid].key>key)
	{
		return BinSearch(rcd,key,low,mid-1);//继续查找前半区 
	}
	else
	{
		return BinSearch(rcd,key,mid+1,high);//继续查找后半区 
	} 
}

在折半查找算法中，问题的解要么是其中一个子问题的解，要么无解，所以无需进行子解的组合。

5.2.3 归并排序

归并是将两个或两个以上的有序序列组合成一个新的有序序列。归并是指把无序的待排序序列递归分解成若干个长度大致相同的有序子序列，并把有序子序列合并为整体有序序列的过程。采用两两分解和归并的策略简单易行，这样的归并排序称为2-路归并排序。

例：设有待排序记录个数为7，其对应的关键字序列为（42，30，68，98，86，15，57）。

在2-路归并排序中，可以清晰划分问题的分解过程及子解的组和过程。每一层分解都将当前序列分成两个长度大致相同的子序列，直至最底层子序列长度为1.此分解过程可递归进行，并在递归返回时逐层进行归并。最底层归并将长度为1的有序序列进行两两归并；倒数第二层及之上的归并类似。

算法：2-路归并

void Merge(rcdType SR[],RcdType TR[],int i,int m,int n){
	//将响铃的有序区见SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
	int k,j;
	for(j=m+1,k=1;i<=m&&j<=n;++k)
	{
		//将SR中的记录按关键字从小到大地赋值到TR中
		if(SR[i].key<=SR[j].key)//注意：若"<="改为"<"，则归并排序不稳定
		{
			TR[k]=SR[i++];
		}
		else
		{
			TR[k]==SR[j++];
		} 
	}
	while(i<=m)
	{
		TR[k++]=SR[i++];//将剩余地SR[i..m]复制到TR 
	}
	while(j<=n)
	{
		TR[k++]=SR[j++];//将剩余得SR[m+1..n]复制到TR 
	}
}

归并排序算法中，MSort函数中，参数s和t分别为待排序列的上界和下界，R1[s..t]和R2[s..t]相互交替归并，参数i则用于指示MSort当前调用层次中R1和R2的具体作用；当i为奇数时，则从R1[s..t]归并至R2[s..t]；否则从R2[s..t]归并至R1[s..t]。MergeSort函数调用MSort函数时，参数s和t的初值应分别置为1和L.length。排序结果存放会L.rcd，所以需要将MSort中参数i的初值置为0。

算法：递归归并排序

void MSort(RcdType R1[],RcdType R2[],int i,int s,int t){
	//对R1[s..t]归并排序，若i%2==1，则排序后的记录存入R2[s..t]，否则存入R1[s..t]
	int m;
	if(s==t)
	{
		if(1==i%2)
		{
			R2[s]=R1[s];
		}
	}
	else
	{
		m=(s+t)/2;//将区间[s..t]平分为[s..m]和[m+1..t]
		MSort(R1,R2,i+1,s,m);//对区间[s..m]递归
		MSort(R1,R2,i+1,m+1,t);;//对区间[m+1,t]递归
		if(1==i%2)//将R1[s..m]和R1[m+1..t]归并到R2[s..t]
		{
			Merge(R1,R2,s,m,t); 
		}
		else//将R2[s..m]和R12[m+1..t]归并到R1[s..t]
		{
			Merge(R2,R1,s,m,t); 
		} 
	} 
}
void MergeSort(RcdSqList &L){//对顺序表L作2-路归并排序
	RcdType *R;
	R=(RcdType*)malloc((L.length+1)sizeof(RcdType));//分配辅助空间 
	MSort(L.rcd,R,0,1,L.length);//对L.rcd[1..L.length]归并排序
	free(R); 
}

在归并排序过程中，每一层归并排序是将区间[s..t]划分为相邻且长度大致相等的两个有序子序列，然后进行归并，存放进辅助空间R中，整个归并排序过程需进行[logn]层（取上）的递归分解和归并，由此得归并排序得算法时间复杂度为O(nlog n)。此算法只在归并排序前分配大小为n得辅助空间R，并在归并过程中与L.rcd交替归并，所以空间复杂度仅为O(n)。归并排序是一种稳定得排序算法。

5.2.4 快速排序

最简单的排序是冒泡排序。在第一趟冒泡过程中，首先比较第一和第二个记录，若为逆序（即L.rcd[1].key>L.rcd[2].key）则交换位置。然后一直比较。

快速排序是对冒泡排序的改进，简称为快排。他的基本思路是，首先现从待排序列中选定一个记录，称之为枢轴，通过关键字与枢轴的比较将待排序的序列划分成位于枢轴前后的两个子序列，其中枢轴之前的子序列的所有关键字都不大于枢轴，枢轴之后的子序列的所有关键字都不小于枢轴；此时枢轴已到位，再按相同的方法对两个子序列分别递归进行快速排序，最终使得整个序列有序。

每趟冒泡排序将无序序列划分为两部分：最大记录和其余记录。对于快速排序，为简单起见，不妨选定第一个记录为枢轴。这样原始序列分为枢轴和其余部分。一次划分之后，序列变成了“比枢轴小”和“比枢轴大”两个子序列，以及已排序到位的枢轴。然后，对两个子序列分别递归进行快速排序。

快速排序的一次划分具体过程是，将位标low指向待排序记录的第一个记录（枢轴），high指向最后一个记录，并将枢轴复制至pivotkey指向的0号空闲单元。首先将high所指位置向前移动，直至找到第一个比枢轴关键字小的记录，并复制至low所指的位置。然后将low向后移动，找到第一个比枢轴关键字大的记录，并将其复制至high所指的位置。如此反复移动位标high和low，直至low与high相等，将枢轴复制至low或high所指的位置。

算法：划分算法

int Partition(RcdType[],int low,int high){
	//对子序列rcd[low..high]进行一次划分，并返回枢轴所在的位置
	//使得在枢轴之前的关键字均不大于它的关键字，枢轴之后的关键字均不下于它的关键字
	rcd[0]=rcd[low];//将枢轴移至数组的空闲单元
	while(low<high)//从待排序列的两端交替地向中间移动 
	{
		while(low<high&&rcd[high].key>=rcd[0].key)
		{
			--high;
		}
		rcd[low]=rcd[high]; //将比枢轴小的关键字移到低端 
		while(low<high&&rcd[low].key<=rcd[0].key)
		{
			++low;
		}
		rcd[high]=rcd[low];//将比枢轴大的关键字移到高端 
	}
	rcd[low]=rcd[0];//枢轴关键字移到正确位置，low改成high也行
	return low;//或high 
}

算法：快速排序

void QSort(RcdType rcd[],int s,int t){
	//对记录序列rcd[s..t]进行快速排序
	int pivotloc;
	if(s<t)//长度大于1 
	{
		pivotloc=Partition(rcd,s,t);//对rcd[s..t]进行划分并返回枢轴位置 
		QSort(rcd,s,pivotoloc-1);//对枢轴之前的子序列递归排序
		QSort(rcd,pivotoloc+1,t);//对枢轴之后的子序列递归排序
	}
}
void QuickSort(RcdType &L){//对记录的顺序表L进行快速排序
	QSort(L.rcd,1,L.length); 
}

为避免枢轴关键字为最大或最小的情况，可采用“三者取中”的方法，即以rcd[s]、rcd[t]和rcd[（s+t）/2]三者中关键字的大小居中的记录为枢轴，并与rcd[s]交换。

5.3 递归与迭代

迭代法是一种反复利用变量的旧值递推出新值，从而完成问题求解的计算方法。在每次计算中，都至少有一个变量需要使用该变量在上一轮中的旧值结果作为输出。迭代和递归存在相似之处，再某种情况下甚至可以相互转换。

5.3.1 迭代三要素

对于折半查找法，也可以用迭代的方法实现。当有序序列长度大于1时，可能需要多轮折半迭代。

算法：迭代法实现折半查找

int BinSearch_ite(RcdType rcd[],KeyType key,int low,int high)
{
	//在有序序列rcd[]中折半查找目标关键字key
	int mid;
	while(low<=high){
		mid=(low+high)/2;
		if(rcd[mid].key==key){
			return mid;//中间关键字与key匹配，返回其下标 
		}
		else if(rcd[mid].key>key){
			high=mid-1;//在前半区查找 
		}
		else{
			low=mid+1;//在后半区查找 
		}
		return -1;//查找失败，返回-1 
	} 
}

迭代法有三要素：

1. 确定迭代变量，迭代变量可有多个，并在迭代中可由旧值直接或间接地推出新值。在某些问题中，迭代变量是最终地计算结果，例如自然数n的阶乘n！。
2. 建立迭代关系式，迭代关系式也称为递推关系式，是指迭代变量的旧值与新值之间的变化规律。在折半查找算法中，如果key与rcd[mid].key不相等，则仅需在划分得到前后子区间中选择一个继续求解。由此得到迭代关系式：

mid=(low+high)/2;high=mid-1;

或

mid=(low+high)/2;low=mid+1;

1. 确定迭代结束条件。迭代结束条件通常有两种：一种是可指定迭代次数，例如，求n！的迭代次数是n-1；另一种是无法预知迭代次数，结束条件由实际情况确定，折半查找的迭代条件是low>high。

具有迭代三要素的问题可用迭代法求解。归并排序的实现也可以用迭代法，其基本思路是，将待排序列划分成长度为k(k=2,22，…)的若干子区间，在各自子区间内的左、右半区间归并完成后，再取两两相邻的子区间继续归并，直至达到需归并的趟数为止。在该算法中，迭代结束条件是归并趟数达到[log2n]（取上），因而归并趟数变量d是最主要的迭代变量。另一个重要的迭代变量是待归并区间长度变量k，它每次以自身区间长度的2倍增长。变量k和d的循环迭代过程形成了程序的主要框架。其他迭代变量还包括待归并区间的左边界变量j、待归并区间的右边界变量jk和待归并区间的中点变量m。

算法：迭代实现2-路归并排序

void MSort_ite(RcdType R1[],RcdType R2[],int n){
	//对R1[1..n]进行归并排序，R2作为辅助空间
	int d,i,j,jk,m;//d:归并层数；k:当前区间长度；j:区间左边界；jk：区间右边界；m：区间中点
	d=ceil(log(n)/log(2));//求以2为底的对数，即归并趟数
	if(1==d%2)//若归并趟数为奇数，则首次归并时需置R2为原始的待排序列的存储空间
	{
		for(i=1;i<=n;i++)
		{
			R2[i]=R1[i];
		}
		for(k=2;d>0;K*=2,d--)
		{
			for(j=1;j<=n;j+=k){//逐个归并区间为k的区间 
				if((m=j+(k-1)/2)>n)//求区间中点m
				{
					m=n;//最后区间长度小于k/2时，置区间中点m为n 
				}
				if((jk=j+k-1)>n)//求区间右边界 
				{
					jk=n; 
				}
				if(1==d%2)//将R2[j..m]和R2[m+1..jk]归并到R2[j..jk] 
				{
					Merge(R2,R1,j,m,jk);
				}
				else//将R1[j..m]和R1[m+1..jk]归并到R2[j..jk] 
				{
					Merge(R1,R2,j,m,jk);
				} 
			}
		}
	} 
}
void MergeSort(RcdSqList &L){//对顺序表L做2—路归并排序
	RcdType*R;
	R=(RcdType*)malloc((L.length+1)*sizeof(RcdType));//分配辅助空间 
	MSort_ite(L.rcd,R,L.length);
	free(R);
}

对于待归并区间，以m为分界分为左半区[j..m]和右半区[m+1..jk]，调用算法中的Merge函数对其进行合并。由于k不一定整除L.length，所以需要对最后一个区间进行专门处理。

两种典型情况：

1. k=4，最后一个区间长度3<k，如果右半区的右边界jk=17+4-1=20则大于L.length，所以应置jk为L.length即19.
2. k=8，最后一个区间长度为3<k/2，如果取中点m=17+(8-1)/2=20则大于L.length，无法划分左半区和右半区。此时区间[17..19]已经有序，所以应置m为L.length即19，且也置jk为19.由于右半区为空（m=jk）,则在Merge函数内无需进行区间左右半区的合并，而是直接将区间[17..19]作为排序后的结果保存即可。

5.3.2 迭代与递归的联系与区别

如果一个问题可以分解成若干个与初始问题形式相似的子问题，并且分解次数是有限的，则该问题可递归求解。这类问题只要满足迭代三要素，则也可能用迭代方式求解。对于同一个问题，其迭代和递归的求解思路可以不一致。

递归的优点在于程序代码简洁，容易编程理解，可读性较好，而后者需要仔细确定跌打三要素，可读性较差。

在递归过程中可能产生大量函数调用，既耗费较多程序运行时间，也占有了大量的函数调用栈空间，极端情况下甚至导致栈溢出。如果迭代和递归求解的时间复杂度相同，可优先考虑采用迭代。

递归不能被迭代完全替代：

1. 某些问题的迭代实现的代价远高于递归，例如汉诺塔问题，迭代实现过程相当复杂，需要做许多专门化的处理，代码量是递归实现的好几倍，其原因往往是迭代关系式极其复杂甚至不易求得，或者将其代码实现的复杂度极高；或者解的组合不易实现。
2. 对具有递归特性的数据结果的问题求解，很自然使用递归思想设计算法。例如：广义表、二叉树、树和图的遍历操作。

5.4 广义表

线性表的元素定义进行扩展，每个元素也可以是一个表，得到一种“表中表”的递归数据结构，称为广义表。

在常用的操作系统种，文件系统的组织结构是一个典型的广义表应用。在某个文件夹下，既可能存在文件，也可能存在文件夹。例子：在C:\program Files\Wandoujia文件夹的情况。Wandoujia文件夹是一个广义表，图左边的树形组织结构可以看出，其包含了三个子文件夹：App、CrashReports和Update，它们也都是广义表。在图右边展开的Update文件夹包含4个子文件夹和1个文件1.1.0.3、Download、Install、Offiline和wandoujia_update.exe，而Download文件夹继续包含了其他文件，形成了表中有表的结构。

5.4.1 广义表的定义

广义表（Generalized?List）一般记作

L=（α1，α2，…,αn）

其中，α1既可以是不再细分的元素，也是广义表，分别称为广义表L的原子和子表。

有以下广义表的概念：

1. 表头和表尾：对于非空广义表L，第一个元素α1称为L的表头。表头既有可能是原子，也有可能是表。除表头之外的元素序列（α2，α3，…，αn）构成了L的表尾。表尾必定是一个广义表。
2. 长度（Length）:广义表的元素个数。空表的长度为0.
3. 深度（Depth）:广义表括弧的最大嵌套层数。空表的深度为1，原子深度为0。

?

5.4.2 广义表的存储结构

由于广义表的每个元素既可以是原子，也可以是表，导致不能统一规定每个元素所需的内存空间。如果采用顺序存储结构，则无法在初始化时确定所需的内存空间，因此，广义表通常采用链式存储结构，以便于进行存储空间的管理。

广义表的结点分为两种，分别为原子结点和表结点。表结点用于表示一个广义表，含有值为LIST的标志域tag、指向表头的指针域hp和指向表尾的指针域tp。原子结点用于表示一个原子，含有值为ATOM的标志域tag和存放原子的值域atom。

存储结构的类型定义如下：

typedef char AtomType;
typedef enum{
	ATOM,LIST;//ATOM值为0表示原子；LIST值为1表示表结点 
}ElemTag;
typedef struct GLNOde{
	ElemTag tag;//区分原子结点和表结点 
	union{//原子结点和表结点公用存储空间 
		AtomType atom;//当tag==ATOM时，本项有意义，存放原子结点值 
		struct{//当tag==LIST时，本项有意义
			struct GLNode *hp;
			struct GLNode *tp''
		}ptr;//表结点的指针域，其中ptr.hp指向表头；ptr.tp指向表尾 
	}un;
}GLNode,*GList;//广义表

对于广义表L=((),(a),(b,(c,(d),e)))其广义表结构示意图为：

广义表是一种具有递归特性的数据结构，其相关问题往往可以分治法求解，长度为n的广义表有两种不同的分解方式：

1. 分解表头和表尾两个子集，并用递归求解，直至原子或空表位置。对于广义表L=（f，(g),h），其分解过程如下：

1. 每个元素为一个子集，共分解为n个子集，并分别用递归求解。L=（f,(g),h）,其分解过程如下：

（2）比（1）的分解层数少。（1）每次将问题规模分为1和n-1，而方式二则将问题规模划分为n个子问题，每个子问题规模为1.

广义表的递归边界条件为空表或原子。

广义表的接口定义如下：

GLNode *MakeAtom(AtomType e);//创建一个原子结点e
void InitGList(GList &L);//创建一个空的广义表
Status DestroyGList(GList &L);;//销毁一个广义表
GLNode *GetHead(GList L);//求广义表表头
GList GetTail(GList L);//求广义表表尾
Status InsertHead(GList &L,GLNode *p);//在广义表L的表头插入元素p
Status Append(GList &L,GLNode *p);//在广义表L的表尾添加元素p
Status DeleteHead(GList L,GList &p);//删除一个广义表L的表头，并用p返回
int GListHead(GList L);//求广义表的深度
GList CopyGList(GList L);//复制一个广义表
int GListLength(GList L);//求广义表的长度 
Status GListEmpty(GList L);//判断广义表L是否为空
Status GListTraverse(GList L,Status(*visit)(ELemType e));//遍历广义表

5.4.3 广义表常用操作的实现

1.求广义表的深度

根据分解方法1，非空广义表可分解为表头和表尾，求广义表深度操作的实现的要点：

1. 如果是空表或原子，直接求得深度为1或0。
2. 如果是非空表，则分别对表头和表尾递归求解。
3. 广义表的深度是表头深度加1和表尾深度的较大值。

算法：求广义表的深度

算法：求广义表的深度
int GListHead(GList L){//求广义表的深度
	int h1,h2;
	if(NULL==L)
	{
		return 1;
	}
	if(ATOM==L->tag)
	{
		return 0;
	}
	h1=GListDepth(L->un.ptr.hp)+1;//表头深度加1
	h2=GListDepth(L->un.ptr.tp);//表尾的深度与原表相同；
	return h1>=h2?h1:h2; 
}

2.在表尾添加元素

Status Append(GList &L,GLNode *p){//在广义表L的表尾添加元素p
	GLNode *pp;
	GList tail;
	tail=(GList)malloc(sizeof(GLNode));
	if(NULL==tail)
	{
		return OVERFLOW;
	}
	tail->tag=LIST;
	tail->un.ptr.hp=p;//表头元素为1 
	tail->un.ptr.tp=NULL;
	if(NULL==L)
	{
		L=tail;
	}
	else
	{
		for(pp=L;pp->un.ptr.tp!=NULL;pp=pp->un.ptr.tp);
		//定位最后一个结点
		pp->un.ptr.tp =tail;
	}
	return OK;
}