数据结构之递归算法和广义表

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 4.1k 阅读时长 ≈ 4 分钟

第六章递归算法和广义表

第一节递归算法

1.递归算法概念

​ 是一种直接或者间接调用自身函数或者方法的算法。说简单点就是程序自身的调用。

2.递归算法设计

（1）阶乘

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int fac(int n){
    if(n == 1)
        return 1;
    return n*f(n-1);
}
int main(){
    cout<<f(5)<<endl;
}
//120

（2）斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int fib(int n){
    if(n == 1 || n == 2)
        return 1;
    return fib(n-1)+fib(n-2);
}
int main(){
    cout<<fib(10)<<endl;
}
//55

（3）杨辉三角的取值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
//递归函数
int func(int m,int n)
{
    if(n == 0||n == m )//递归终止条件
        return 1;
    return func(m-1,n)+func(m-1,n-1);//核心代码
}
int main(void) {
    int m,i,j;
    m=6;//打印前6行杨辉三角
    for(i=0;i<=m;i++)
    {
        for(j=0;j<m-i;j++)
            printf("   ");
        for(j=0;j<=i;j++)
            printf("%6d",func(i,j));
        printf("\n");
    }
    return 0;
}

（4）汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
void Move(int n, char A, char B, char C){
    if (n == 1){
        //圆盘只有一个时，只需将其从A塔移到C塔
        cout << "move " << n << " from " << A << " to " << C << endl;
    }
    else{
        Move(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
        cout << "move " << n << " from " << A << " to " << C << endl;//把A塔上编号为n的圆盘移到C上
        Move(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
    }
}

int main(){
    Move(3, 'A', 'B', 'C');
    return 0;
}

第二节广义表

1.广义表概念

​ 是一种非线性的数据结构，它的表元素可以是原子或者广义表的一种线性表的扩展结构。

  • ​ 广义表的长度：表中最上层元素的个数
  • ​ 广义表的深度：表中括号的最大层数
  • ​ 表头和表尾：当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾
1
2
3
4
5
6
E=()	//E是一个空表，其长度为0，其深度为1
L=(a，b)	//L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表，其深度为1
A=(x，L)=(x，(a，b))	//A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L，其深度为2
B=(A，y)=((x，(a，b))，y)	//B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y，其深度为3
C=(A，B)=((x，(a，b))，((x，(a，b))，y))	//C的长度为2，两个元素都是子表，其深度为4
D=(a，D)=(a，(a，(a，(…))))	//D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表，其深度为∞

2.广义表存储结构和操作实现

（1）广义表结点的代码结构

1
2
3
4
5
6
7
8
9
//定义广义表的数据结构
typedef struct GList{
	NodeTag tag; //用以区分是原子结点还是子表结点
	union{
		DataType data; //用以存放原子结点值，其类型由用户自定义
		GList *slink; //指向子表的指针
	};
	GList *next; //指向下一个表结点
} *GListPtr;

（2）求表头、表尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*求广义表L的表头，并返回表头指针*/
GList Head(GList L) {
	if (L == NULL)					//空表无表头
		return NULL;
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	else
		return L->atom_htp.htp.hp;	//返回表头指针
}

/*求广义表L的表尾，并返回表尾指针*/
GList Tail(GList L) {
	if (L == NULL)					//空表无表尾
		return NULL;
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	else
		return L->atom_htp.htp.tp;	//返回表尾指针
}

（3）求长度、深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*求广义表长度*/
int Length(GList L) {
	int k = 0;
	GLNode* s;
	if (L == NULL)
		return 0;					//空表长度为0
	if (L->tag == ATOM)				//原子不是表
		exit(0);
	s = L;
	while (s != NULL) {				//统计最上层表的长度
		k++;
		s = s->atom_htp.htp.tp;
	}
	return k;
}

/*求广义表的深度*/
int Depth(GList L) {
	int d, max;
	GLNode* s;
	if (L == NULL)
		return 1;					//空表深度为1
	if (L->tag == ATOM)
		return 0;					//原子深度为0
	s = L;
	while (s != NULL) {				//求每个子表的深度的最大值
		d = Depth(s->atom_htp.htp.hp);
		if (d > max)
			max = d;
		s = s->atom_htp.htp.tp;
	}
	return (max + 1);				//表的深度等于最深子表的深度+1
}
void PrintGList(GListPtr gl){
	if(gl != NULL){
		if(gl->tag == list){
			printf("(");
			if(gl->slink == NULL){
				printf("");
			}else{
				PrintGList(gl->slink); //递归调用输出子表
			}
		}else{
			printf("%c", gl->data); //输出结点数据域值
		}
 
		if(gl->tag == list){
			printf(")");
		}
 
		if(gl->next != NULL){
			printf(",");
			PrintGList(gl->next); //递归调用输出下一个节点
		}
	}
}

（4）统计原子个数

1
2
3
4
5
6
7
8
9
10
11
/*统计广义表中原子结点数目*/
int CountAtom(GList L) {
	int n1, n2;
	if (L == NULL)
		return 0;							//空表中没有原子
	if (L->tag == ATOM)
		return 1;							//L指向单个原子
	n1 = CountAtom(L->atom_htp.htp.hp);		//统计表头中的原子数目
	n2 = CountAtom(L->atom_htp.htp.tp);		//统计表尾中的原子数目
	return (n1 + n2);
}

（5）广义表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*复制广义表*/
int CopyGList(GList S, GList* T) {
	if (S == NULL) {				//复制空表
		*T = NULL;
		return OK;
	}
	*T = (GLNode*)malloc(sizeof(GLNode));
	if (*T == NULL)
		return ERROR;
	(*T)->tag = S->tag;
	if (S->tag == ATOM)
		(*T)->atom_htp.atom = S->atom_htp.atom;		//复制单个原子
	else {
		/*复制表头*/
		CopyGList(S->atom_htp.htp.hp, &((*T)->atom_htp.htp.hp));
		/*复制表尾*/
		CopyGList(S->atom_htp.htp.tp, &((*T)->atom_htp.htp.tp));
	}
	return OK;
}