最近学习了广义表,我们知道广义表也是一种线性表,而顾名思义广义表就是不止一个表,下面来举个栗子:
A=( )
B=(1 , 2,3)
C=(1 ,2 ,3, ( a , b ,c) )
D=(1, 2, 3, (a,( b,c),d),4)
以上A,B,C,D都是广义表,只不过深度不一样,也就是括号的对数不一样,A是个特殊的广义表,即空表。B里面有三个元素,C里面有6个元素,包括一个子表(a,b,c),C也同理,只不过多了一层子表。由此可总结为一句话:表里有表
这样看可能不太直观,下面以广义表C为例来看一下它的结构图:
(图画得有点丑,不要吐槽我)
每当遇到一个前括号,就要创建一个子表,直到遇见收括号。
那么如何创建一个广义表呢,在创建节点结构体的时候,我们要考虑每个节点的类型,有可能是头结
点,也有可能是子表节点,也有可能是普通的值节点,所以在构造节点的时候就要定义一个三元体,由
于是表里有表,我们可以用递归的方法来解决广义表的问题,每个子表都可以递归为一个子问题,就可
以很轻松的解决掉这个问题了。
下面是具体实现的代码:
先构造一个三元结构体:
enum Type { HEAD, VALUE, SUB, }; template<class T> struct GeneralizedNode { Type _type; GeneralizedNode<T>* _next; union { char _value; GeneralizedNode<T>* _sublink; //子表的头结点 }; public: GeneralizedNode(Type type = HEAD,char value = '\0') :_type(type) ,_next(NULL) { if (type == VALUE) { _value = value; } else if (type == SUB) { _sublink = NULL; } } };
下面来构造一个广义表类
template<class T> class GeneralizedList { public: GeneralizedList() :_head(new GeneralizedNode<T>(HEAD)) {} GeneralizedList(const char* str) { _head=_CreateList(str); } GeneralizedList(const GeneralizedList& g) //拷贝构造 { _head = Copy(g._head;) } size_t Size() { return size(_head); } size_t depth() { return Depth(_head); } void print() { Print(_head); } protected: GeneralizedNode<T>* _CreateList(const char*& str) { assert(str && *str == '('); ++str; GeneralizedNode<T>* Head = new GeneralizedNode<T>(HEAD,NULL); GeneralizedNode<T>* cur = Head; while (*str) { if (_IsValue(*str)) { cur->_next = new GeneralizedNode<T>(VALUE,*str); cur = cur->_next; str++; } else if (*str == '(') { GeneralizedNode<T>* newNode= new GeneralizedNode<T>(SUB); //将一个子表结点加入到链表中 cur->_next = newNode; cur = cur->_next; cur->_sublink = _CreateList(str); str++;//递归创建一个子表结点 } else if (*str == ')') //表示一个表已经结束 { str++; return Head; } else { str++; //不需要处理的情况 } } assert(false); return Head; } size_t Depth(GeneralizedNode<T>* head) { GeneralizedNode<T>* cur = head; size_t depth = 1; while (cur) { if (cur->_type == SUB) { size_t subdepth = Depth(cur->_sublink); if (subdepth+1 > depth) { depth=subdepth;//保存较大的深度 } } cur = cur->_next; } return depth; } size_t size(GeneralizedNode<T>* head) { GeneralizedNode<T>* cur = head; size_t count = 0; while (cur) { if (cur->_type != SUB) { count++; } else { count += size(cur->_sublink); } cur = cur->_next; } return count; } void Print(GeneralizedNode<T>* head) { GeneralizedNode<T>* cur = head; while (cur) { if (cur->_type == HEAD) { cout << '('; } else if (cur->_type == VALUE) { cout << cur->_value ; if (cur->_next != NULL) { cout << ',' ; } } else if (cur->_type == SUB) { Print(cur->_sublink); if (cur->_next != NULL) { cout << ','; } } cur = cur->_next; } cout << ')'; } bool _IsValue(char ch) //检查是否为合法值 { if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z')) { return true; } return false; } protected: GeneralizedNode<T>* _head; };
下面给出测试代码:
#include"Generalized.h" void Test() { char* ch = "(a,b,c,(1,2),c)"; GeneralizedList<char> gl1(ch); gl1.print(); cout << endl; cout << "广义表深度为:" << gl1.depth() << endl; cout << "广义表大小为:" << gl1.Size() << endl; } int main() { Test(); getchar(); return 0; }
运行结果:
以上就是C++实现广义表的方法啦,里面也许还存在着一些问题,希望大家能够指正出来,共同促进学习。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。