数据结构与算法——第5章-数组和广义表-广义表的复制详解(5.14)

发表于 分类于 ， ， 阅读时长 ≈ 6 分钟

一 概述

1
2
3
1.广义表的复制
2.广义表的复制方式1
3.广义表的复制方式2

二 广义表的复制

1
2
3
4
5
6
7
8
9
对于任意一个非空广义表来说，都是由两部分组成：表头和表尾。
也就是说，只要确定了广义表的表头和表尾，就可以唯一确定这个广义表。

复制一个广义表，其实就是复制广义表中的表头和表尾。
如果表头或者表尾同样是一个广义表，就继续复制子表的表头和表尾。

因此，复制广义表的过程，就是以递归的方式复制广义表中的原子和子表。递归的出口有两个：
1.如果当前遍历的元素为空表，则直接返回空表。
2.如果当前遍历的元素为该表的一个原子，那么直接复制，返回即可。

三 广义表的复制方式1

3.1 图示

前面章节，给大家介绍了两种存储广义表的方式。采用图 1 所示的方式存储广义表

3.2 示例代码

复制广义表的 C 语言程序如下：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int tag;//标志域
	union {
		char atom;//原子结点的值域
		struct {
			struct Node* hp, * tp;
		} ptr; //子表结点的指针域，hp指向表头；tp指向表尾
	} un;
} GLNode, * Glist;

Glist creatGlist(Glist C) {
	//广义表C
	C = (Glist)malloc(sizeof(GLNode));
	C->tag = 1;
	//表头原子‘a’
	C->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.hp->tag = 0;
	C->un.ptr.hp->un.atom = 'a';
	//表尾子表(b,c,d),是一个整体
	C->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->tag = 1;
	C->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.tp = NULL;
	//开始存放下一个数据元素(b,c,d),表头为‘b’，表尾为(c,d)
	C->un.ptr.tp->un.ptr.hp->tag = 1;
	//存储 'b'
	C->un.ptr.tp->un.ptr.hp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.hp->un.ptr.hp->tag = 0;
	C->un.ptr.tp->un.ptr.hp->un.ptr.hp->un.atom = 'b';
	//存放子表(c,d)，表头为c，表尾为(d)
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->tag = 1;
	//存储原子 'c'
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp->tag = 0;
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp->un.atom = 'c';
	//存放表尾(d)
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->tag = 1;
	//存储 'd'
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp->tag = 0;
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp->un.atom = 'd';
	C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.tp = NULL;
	return C;
}

void copyGlist(Glist C, Glist* T) {
	//如果C为空表，那么复制表直接为空表
	if (!C) {
		*T = NULL;
	} else {
		*T = (Glist)malloc(sizeof(GLNode));//C不是空表，给T申请内存空间
		//申请失败，程序停止
		if (!*T) {
			exit(0);
		}
		(*T)->tag = C->tag;//复制表C的tag值
		//判断当前表元素是否为原子，如果是，直接复制
		if (C->tag == 0) {
			(*T)->un.atom = C->un.atom;
		} else { //运行到这，说明复制的是子表
			copyGlist(C->un.ptr.hp, &((*T)->un.ptr.hp));//复制表头
			copyGlist(C->un.ptr.tp, &((*T)->un.ptr.tp));//复制表尾
		}
	}
}

//递归删除广义表占用的堆内存
void delGlist(Glist C) {
	if (C != NULL) {
		//如果是子表结点，继续查找它的 hp 和 tp 方向，直至它的 hp 和 tp 方向都没有可释放的堆空间之后，释
		放当前结点的空间
		if (C->tag == 1) {
			delGlist(C->un.ptr.hp);
			delGlist(C->un.ptr.tp);
			free(C);
			return;
		}
		//删除原子结点
		else {
			free(C);
			return;
		}
	}
}
//递归输出广义表中的子表
void pri_SubGlist(Glist C) {
	if (C) {
		//如果表头结点的 hp 为 NULL，表示这是一个空表
		if (!C->un.ptr.hp) {
			printf("()");
		} else {
			//如果表头是原子，直接输出
			if (C->un.ptr.hp->tag == 0) {
				putchar(C->un.ptr.hp->un.atom);
			}
			//如果表头是子表，继续遍历该子表
			else {
				putchar('(');
				pri_SubGlist(C->un.ptr.hp);
				putchar(')');
			}
		}
		//如果表尾不是空表，以同样的方式处理表尾
		if (C->un.ptr.tp) {
			putchar(',');
			pri_SubGlist(C->un.ptr.tp);
		}
	}
}
//输出广义表
void priGlist(Glist C) {
	putchar('(');
	pri_SubGlist(C);
	putchar(')');
}

int main(int argc, const char* argv[]) {
	Glist C = NULL, T = NULL;
	C = creatGlist(C);
	printf("C=");
	priGlist(C);

	copyGlist(C, &T);

	printf("\nT=");
	priGlist(T);

	//删除 C 和 T
	delGlist(C);
	delGlist(T);
	return 0;
}

运行结果：

1
2
C=(a,(b,c,d))
T=(a,(b,c,d))

四 广义表的复制方式2

4.1 图示

对于采用图 2 所示的方式存储的广义表：

4.2 示例代码

复制广义表的 C 语言程序如下：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
	int tag;//标志域
	union {
		char atom;//原子结点的值域
		struct Node* hp;//子表结点的指针域，hp指向表头
	} un;
	struct Node* tp;//这里的tp相当于链表的next指针，用于指向下一个数据元素
} GLNode, * Glist;

Glist creatGlist(Glist C) {
	C = (Glist)malloc(sizeof(GLNode));
	C->tag = 1;
	C->un.hp = (Glist)malloc(sizeof(GLNode));
	C->tp = NULL;
	//存储 'a'
	C->un.hp->tag = 0;
	C->un.hp->un.atom = 'a';
	//存储(b,c,d)
	C->un.hp->tp = (Glist)malloc(sizeof(GLNode));
	C->un.hp->tp->tag = 1;
	C->un.hp->tp->un.hp = (Glist)malloc(sizeof(GLNode));
	C->un.hp->tp->tp = NULL;
	//存储'b'
	C->un.hp->tp->un.hp->tag = 0;
	C->un.hp->tp->un.hp->un.atom = 'b';
	C->un.hp->tp->un.hp->tp = (Glist)malloc(sizeof(GLNode));
	//存储'c'
	C->un.hp->tp->un.hp->tp->tag = 0;
	C->un.hp->tp->un.hp->tp->un.atom = 'c';
	C->un.hp->tp->un.hp->tp->tp = (Glist)malloc(sizeof(GLNode));
	//存储'd'
	C->un.hp->tp->un.hp->tp->tp->tag = 0;
	C->un.hp->tp->un.hp->tp->tp->un.atom = 'd';
	C->un.hp->tp->un.hp->tp->tp->tp = NULL;
	return C;
}

void copyGlist(Glist C, Glist* T) {
	//如果 C 为 NULL，直接返回
	if (C) {
		//复制表头
		(*T) = (Glist)malloc(sizeof(GLNode));
		if (!*T) {
			exit(0);
		}
		(*T)->tag = C->tag;
		//如果当前遍历的是原子结点，直接赋值
		if (C->tag == 0) {
			(*T)->un.atom = C->un.atom;
		} else {
			//如果当前遍历的是子表，继续递归复制这个子表
			copyGlist(C->un.hp, &((*T)->un.hp));
		}

		//复制表尾
		if (C->tp == NULL) {
			(*T)->tp = C->tp;
		} else {
			copyGlist(C->tp, &((*T)->tp));
		}
	}
}

void priGlist(Glist C) {
	Glist cur = C;
	while (cur != NULL) {
		//如果是原子，直接输出
		if (cur->tag == 0) {
			printf("%c", cur->un.atom);
		}
		//如果是广义表或者子表，递归输出表头和表尾
		else {
			printf("(");
			priGlist(cur->un.hp);
			printf(")");
		}
		if (cur->tp != NULL) {
			printf(",");
		}
		cur = cur->tp;
	}
}

//递归释放广义表占用的堆空间
void delGlist(Glist C) {
	Glist cur = C;
	while (cur != NULL) {
		Glist del = cur;
		if (cur->tag == 1) {
			delGlist(cur->un.hp);
		}
		cur = cur->tp;
		free(del);
	}
}

int main(int argc, const char* argv[]) {
	Glist C = NULL, T = NULL;
	C = creatGlist(C);
	printf("C=");
	priGlist(C);
	copyGlist(C, &T);
	printf("\nT=");
	priGlist(T);
	//删除 C 和 T
	delGlist(C);
	delGlist(T);
	return 0;
}

运行结果为：

1
2
C=(a,(b,c,d))
T=(a,(b,c,d))

五 总结

1
2
3
4
5
6
本节，我们针对广义表的两种存储结构，分别给出了复制广义表的实现代码：
void copyGlist(Glist C, Glist *T);

其中 Glist *T 等同 struct GLNode* *T，此为二级指针而非一级指针。在主函数中调用此函数，需要传入指针 T 的地址，而不是 T 本身。
C 语言中，函数参数传递的方式有两种，分别是值传递和地址传递，
本节中的 copyGlist() 函数中的参数 C 采用的是值传递，参数 T 采用的是地址传递。

六 参考

  • C语言中文网—广义表的复制详解