一 概述
1
2
3
4
| 1.什么是广义表的长度
2.广义表长度的计算
3.广义表长度的图示
4.示例代码
|
二 什么是广义表的长度
1
| 广义表的长度，指的是广义表中所包含的数据元素的个数。
|
三 广义表长度的计算
1
2
3
4
5
6
7
8
9
| 由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，
广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。
例如，在广义表 {a,{b,c,d}} 中，它包含一个原子和一个子表，因此该广义表的长度为 2。
再比如，广义表 {{a,b,c}} 中只有一个子表 {a,b,c}，因此它的长度为 1。
前面我们用LS={a 1 ,a 2 ,...,a n } 来表示一个广义表，其中每个a i都可用来表示一个原子或子表，其实它还可以表示广义表LS的长度为 n。
广义表规定，空表 {} 的长度为 0。
|
四 广义表长度的图示
4.1 图示
1
| 在编程实现求广义表长度时，由于广义表的存储使用的是链表结构，且有以下两种方式（如图 1 所示）：
|
4.2 说明
1
2
3
4
| 对于图 1a) 来说，只需计算最顶层（红色标注）含有的节点数量，即可求的广义表的长度。
同理，对于图 1b) 来说，由于其最顶层（蓝色标注）表示的此广义表，而第二层（红色标注）表示的才是该广义表中包含的数据元素，
因此可以通过计算第二层中包含的节点数量，即可求得广义表的长度。
|
五 示例代码
由于两种算法的实现非常简单，这里只给出计算图 1a) 中广义表长度的 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
| #include <stdio.h>
#include <stdlib.h>
typedef struct GLNode {
int tag;//标志域
union {
char atom;//原子结点的值域
struct {
struct GLNode * hp,*tp;
} ptr; //子表结点的指针域，hp 指向表头；tp 指向表尾
};
}*Glist;
Glist creatGlist(Glist C) {
//广义表 C
C=(Glist)malloc(sizeof(Glist));
C->tag=1;
//表头原子‘a’
C->ptr.hp=(Glist)malloc(sizeof(Glist));
C->ptr.hp->tag=0;
C->ptr.hp->atom='a';
//表尾子表（b,c,d）,是一个整体
C->ptr.tp=(Glist)malloc(sizeof(Glist));
C->ptr.tp->tag=1;
C->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
C->ptr.tp->ptr.tp=NULL;
//开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）
C->ptr.tp->ptr.hp->tag=1;
C->ptr.tp->ptr.hp->ptr.hp=(Glist)malloc(sizeof(Glist));
C->ptr.tp->ptr.hp->ptr.hp->tag=0;
C->ptr.tp->ptr.hp->ptr.hp->atom='b';
C->ptr.tp->ptr.hp->ptr.tp=(Glist)malloc(sizeof(Glist));
//存放子表(c,d)，表头为 c，表尾为 d
C->ptr.tp->ptr.hp->ptr.tp->tag=1;
C->ptr.tp->ptr.hp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag=0;
C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom='c';
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp=(Glist)malloc(sizeof(Glist));
//存放表尾 d
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag=1;
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag=0;
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom='d';
C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp=NULL;
return C;
}
int GlistLength(Glist C) {
int Number=0;
Glist P=C;
while(P) {
Number++;
P=P->ptr.tp;
}
return Number;
}
int main() {
Glist C = creatGlist(C);
printf("广义表的长度为：%d",GlistLength(C));
return 0;
}
|
程序运行结果为：
六 参考