以下给出几种简单的广义表模型：
由上图我们可以看到，广义表的节点类型无非head、value、sub三种，这里设置枚举类型，利用枚举变量来记录每个节点的类型：
|
1
2
3
4
5
6
|
enum Type{ HEAD, //头节点 VALUE, //值节点 SUB, //子表节点}; |
每个节点都有自己的类型以及next指针，除此之外，如果该节点是VALUE类型还要分配空间存储该节点的有效值；但是若该节点是SUB类型，就需定义一个指针指向子表的头。
这里我们可以用联合来解决这个问题。
（联合（或共同体）是一种不同数据类型成员之间共享存储空间的方法，并且联合体对象在同一时间只能存储一个成员值）
构造节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
struct GeneralizedNode{ Type _type; // 1.类型 GeneralizedNode* _next; //2.指向同层的下一个节点 union { char _value; // 3.有效值 GeneralizedNode* _subLink; // 3.指向子表的指针 }; GeneralizedNode(Type type = HEAD, char value = '0') :_value(value) ,_type(type) , _next(NULL) { if (_type == SUB) { _subLink = NULL; } }}; |
广义表的定义及基本操作：
|
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
|
class Generalized{public: //无参的构造函数,建立空的广义表 Generalized(); //建造广义表，有参数的构造函数 Generalized(const char* str); //打印广义表 void Print(); //获取值节点的个数 size_t Amount(); //获取广义表的深度 size_t Depth(); //拷贝构造 Generalized(const Generalized& g); ////赋值运算符的重载 Generalized& operator=(const Generalized& g); ////析构函数 ~Generalized(); protected: void _Print(GeneralizedNode* head); GeneralizedNode* _CreatList(const char*& str); size_t _Amount(GeneralizedNode* head); GeneralizedNode* _Copy(GeneralizedNode* head); void _Destory(GeneralizedNode* head);protected: GeneralizedNode* _head; //记录广义表头指针}; |
初始化建立广义表进行循环递归。遍历字符串时遇到字符就建立值节点，遇到'('就进行递归并建立子表；遇到')'就结束当前子表的建立，并返回当前子表的头指针。
|
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
|
GeneralizedNode* _CreatList(const char*& str){ assert(*str == '('); GeneralizedNode* head = new GeneralizedNode(HEAD,'0'); GeneralizedNode* cur = head; str++; while (str != '\0') { if ((*str >= '0'&&*str <= '9') || (*str >= 'a'&&*str <= 'z') || (*str >= 'A'&&*str <= 'Z')) { cur->_next = new GeneralizedNode(VALUE, *str); cur = cur->_next; } else if (*str == '(') { cur->_next = new GeneralizedNode(SUB); cur = cur->_next; cur->_subLink = _CreatList(str); } else if (*str == ')') { return head; } str++; } return head;} |
打印广义表：当节点的类型为SUB时进行递归，最后不要忘了每打印完一层要打印一个后括号。
|
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
|
void _Print(GeneralizedNode* head){ if (head == NULL) { cout << "Generalized table is NULL" << endl; return; } GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << '('; } else if (cur->_type == VALUE) { cout << cur->_value; if (cur->_next) { cout << ','; } } else if (cur->_type == SUB) { _Print(cur->_subLink); if (cur->_next) { cout << ','; } } cur = cur->_next; } cout << ')';} |
获取值节点的个数：设置count变量，遇到值节点就加1，遇到SUB节点进行递归并将返回值加给count
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
size_t _Amount(GeneralizedNode* head){ GeneralizedNode* begin = head; size_t count = 0; while (begin) { if (begin->_type == VALUE) { count++; } if (begin->_type == SUB) { count += _Amount(begin->_subLink); } begin = begin->_next; } return count;} |
广义表的深度：设置变量dp和max分别用来记录当前子表即当前SUB节点指向的子表深度，以及本层所有的SUB节点中深度最大的子表的深度。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
size_t _Depth(GeneralizedNode* head){ if (_head == NULL) { return 0; } size_t dp=0; GeneralizedNode* cur = head; size_t max = 0; while (cur) { if (cur->_type == SUB) { dp=_Depth(cur->_subLink); if (max < dp) { max = dp; } } cur = cur->_next; } return max+1;} |
销毁广义表：依次遍历节点，遇到子表递归，将子表的节点delete完成后，再回到当前层继续遍历。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void _Destory(GeneralizedNode* head){ if (head == NULL) { return; } while (head) { GeneralizedNode* begin = head->_next; if (head->_type == SUB) { _Destory(head->_subLink); } delete head; head = begin; }} |
实例演示
定义：
广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
其中：
①ai--或者是原子或者是一个广义表。
②广义表通常记作：
Ls=( a1，a2，…，ai，…，an)。
③Ls是广义表的名字，n为它的长度。
④若ai是广义表，则称它为Ls的子表。
注意：
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。
④广义表是递归定义的
画图举例：
代码实现：
|
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
[cpp] view plain copy#include <iostream> using namespace std; //表示广义表的结点类型 enum NodeType { HEAD_TYPE,//头结点类型 VALUE_TYPE,//值结点类型 SUB_TYPE//子表类型 }; //表示广义表结点的结构体 struct GeneraListNode { NodeType _type;//结点类型 GeneraListNode *_next;//存放结点的下一个元素的地址 //一个结点要么是值结点要么是子表，故用联合体来存放节省一定的空间 //若是值结点则存放的是值，是子表结点的话存放的是子表结点头结点的地址 union{ char _value; GeneraListNode *_subLink; }; GeneraListNode(NodeType type = HEAD_TYPE, char value = '\0') :_type(type) ,_next(NULL) { if (type == VALUE_TYPE) { _value = value; }else if(type == SUB_TYPE) { _subLink = NULL; } } }; class GeneraList { private: GeneraListNode *_link;//用来存放广义表头结点地址 public: GeneraList(const char *str) :_link(NULL) { _CreateGeneraList(_link, str);//根据指定序列创建广义表 } ~GeneraList() {} public: void Print();//对外提供的打印广义表的接口 int Size();//广义表中值结点的数目的对外获取接口 int Depth();//广义表的最深层次的对外获取接口 private: void _CreateGeneraList(GeneraListNode *& link, const char *& str); bool _IsValue(const char ch);//判断指定字符是否为值结点所允许的类型 int _Size(GeneraListNode *head);//计算广义表中值结点的数目的实现 int _Depth(GeneraListNode *head);//计算广义表的最深层次的实现 void _Print(GeneraListNode *link);//打印广义表的接口的底层实现 }; //创建广义表 void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str) { //广义表最前端有一个头结点，用来记录实现广义表链表的首地址 //故每次调用该创建广义表的函数首先创建一个头结点 GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL); head->_next = NULL; link = head; GeneraListNode* cur = link;//用来记录创建广义表链表时当前创建出的结点位置游标指针 str++;//将广义表序列后移,相当于跳过了'(' while(*str != '\0') { if(_IsValue(*str)){//如果当前扫描到的字符是值 //创建一个值结点 GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str); newNode->_next = NULL; cur->_next = newNode;//将该值结点加入到链表中 cur = cur->_next;//游标后移 str++;//将广义表序列后移 }else if(*str == '('){//如果扫描到'('创建子表结点 GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL); subLink->_next = NULL; cur->_next = subLink;//将子表结点加入到链表中 cur = cur->_next; _CreateGeneraList(cur->_subLink, str);//递归创建子表 }else if(*str == ')'){ str++; return;//若扫描到')'表示广义表创建结束 }else{ str++;//空格等其他无效字符跳过 } } } int GeneraList::Size() { return _Size(_link); } //计算广义表值结点的个数 int GeneraList::_Size(GeneraListNode *head) { int size = 0; GeneraListNode *cur = head; while(cur != NULL){ if(cur->_type == VALUE_TYPE){ ++size;//遇到值结点则将size加一 }else if(cur->_type == SUB_TYPE){ size += _Size(cur->_subLink);//遇到子表进行递归 } cur = cur->_next; } return size; } int GeneraList::Depth() { return _Depth(_link); } int GeneraList::_Depth(GeneraListNode *head) { int depth = 1,maxDepth = 1;//depth表示当前表的深度，maxDepth表示目前最大的深度 GeneraListNode *cur = head; while(cur != NULL){ if(cur->_type == SUB_TYPE){ depth += _Depth(cur->_subLink); } if(depth > maxDepth){//更新最大深度 maxDepth = depth; depth = 1;//将当前深度复位 } cur = cur->_next; } return maxDepth; } void GeneraList::Print() { _Print(_link); cout<<endl; } //打印广义表 void GeneraList::_Print(GeneraListNode *link) { GeneraListNode *cur = link;//遍历广义表的游标 while(cur != NULL){ if(cur->_type == VALUE_TYPE){ cout<<cur->_value; if(cur->_next != NULL) { cout<<','; } }else if(cur->_type == HEAD_TYPE){ cout<<"("; }else if(cur->_type == SUB_TYPE){ _Print(cur->_subLink);//遇到子表递归打印 if(cur->_next != NULL)//如果打印完子表后广义表未结束则打印',' { cout<<","; } } cur = cur->_next; } cout<<")"; } bool GeneraList::_IsValue(const char ch) { if(ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '(') { return true; } return false; } |
测试代码
|
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
|
[cpp] view plain copy#include"GeneraList.hpp" //测试空表 void Test1() { GeneraList genList("()"); genList.Print(); cout<<"Size is :"<<genList.Size()<<endl; cout<<"Depth is :"<<genList.Depth()<<endl<<endl; } //测试单层表 void Test2() { GeneraList genList("(a,b)"); genList.Print(); cout<<"Size is :"<<genList.Size()<<endl; cout<<"Depth is :"<<genList.Depth()<<endl<<endl; } //测试双层表 void Test3() { GeneraList genList("(a,b,(c,d))"); genList.Print(); cout<<"Size is :"<<genList.Size()<<endl; cout<<"Depth is :"<<genList.Depth()<<endl<<endl; } //测试多层表 void Test4() { GeneraList genList("(a,b,(c,d),(e,(f),h))"); genList.Print(); cout<<"Size is :"<<genList.Size()<<endl; cout<<"Depth is :"<<genList.Depth()<<endl<<endl; } //测试多层空表 void Test5() { GeneraList genList("(((),()),())"); genList.Print(); cout<<"Size is :"<<genList.Size()<<endl; cout<<"Depth is :"<<genList.Depth()<<endl<<endl; } int main() { Test1(); Test2(); Test3(); Test4(); Test5(); return 0; } |
运行结果
总结
以上就是关于C++如何实现广义表详解的全部内容，希望对有需要的人能有所帮助，如果有疑问欢迎大家留言讨论。
