递归实现广义表
广义表是非线性的结构,是线性表的一种扩展,是有n个元素组成有限序列。由于在表的描述中可以嵌套表,允许表中有表,所以可以通过递归实现广义表。
创新互联-专业网站定制、快速模板网站建设、高性价比金口河网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式金口河网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖金口河地区。费用合理售后完善,十年实体公司更值得信赖。
具体实现如下:
头文件
#pragma once //实现广义表的结构 enum Type//枚举类型 { HEAD, VALUE, SUB, }; struct GeneralizedNode//广义表的结点 { Type _type;//类型 GeneralizedNode* _next;//值相同层的下一个节点 union//共用体/联合 { int _value;//值节点 GeneralizedNode* _SubLink;//指向字表的指针 }; GeneralizedNode(); GeneralizedNode(Type type, int value); //全缺省构造函数 }; class Generalized { public: Generalized(); Generalized(const char* str);//构造 Generalized(const Generalized& g);//拷贝构造 Generalized& operator=(const Generalized& g); ~Generalized(); void Print(); size_t Size(); size_t Depth(); protected: GeneralizedNode* _CreatList(const char*& str); GeneralizedNode* _Copy(GeneralizedNode* head); bool _isValue(char ch);//判断是否为字母或数字 void _Distory(GeneralizedNode* head); void _Print(GeneralizedNode* head); size_t _Size(GeneralizedNode* head); size_t _Depth(GeneralizedNode* head); protected: GeneralizedNode* _head; };
各函数的具体实现
#include#include #include using namespace std; #include"Generalized.h" GeneralizedNode::GeneralizedNode() :_next(NULL) {} GeneralizedNode::GeneralizedNode(Type type, int value) : _type(type) , _next(NULL) { if (_type == VALUE) { _value = value; } if (_type == SUB) { _SubLink = NULL; } } Generalized::Generalized() :_head(NULL) {} Generalized::Generalized(const char* str)//构造函数 : _head(NULL) { _head = _CreatList(str); } GeneralizedNode* Generalized::_CreatList(const char*& str) {//广义表:(a, (b, c)) assert('(' == *str); str++; GeneralizedNode* head = new GeneralizedNode(HEAD, 0);//建立表的头结点 GeneralizedNode* cur = head; while (str) { if (_isValue(*str))//*str为字母或数字 { cur->_next = new GeneralizedNode(VALUE, *str);//建立value结点 cur = cur->_next; str++; } else if (*str == '(')//如果为(,则出现字表,进行递归调用 { GeneralizedNode* subNode = new GeneralizedNode(SUB, 0);//建立子表结点 cur->_next = subNode; cur = cur->_next; subNode->_SubLink = _CreatList(str);//_SubLink指向子表构造子表 } else if (*str == ')')//表示表的结束(包括子表),返回表的头结点 { str++; return head; } else { str++; } } assert(false); return head; } bool Generalized::_isValue(char ch)//判断是否为字母或数字 { if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') { return true; } return false; } Generalized::Generalized(const Generalized& g)//拷贝构造函数 { _head = _Copy(g._head); } GeneralizedNode* Generalized::_Copy(GeneralizedNode* head) { GeneralizedNode* newhead = new GeneralizedNode(HEAD, 0); GeneralizedNode* cur = head; GeneralizedNode* newcur = newhead; while (cur) { if (cur->_type == VALUE)//cur._type为VALUE或SUB时建立结点,newcur才存在指向下一个结点 { newcur->_next = new GeneralizedNode(VALUE, cur->_value); newcur = newcur->_next; } if (cur->_type == SUB) { newcur->_next= new GeneralizedNode(SUB, 0); newcur = newcur->_next; newcur->_SubLink = _Copy(cur->_SubLink);//递归调用_Copy进行复制 } cur = cur->_next; } return newhead; } Generalized& Generalized::operator=(const Generalized& g)//传统写法 { if (this != &g) { GeneralizedNode* tmp = _Copy(g._head); _Distory(_head); _head = tmp; } return *this; } Generalized::~Generalized() { _Distory(_head); } void Generalized::_Distory(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; if (cur->_type == SUB) { _Distory(cur->_SubLink);//释放cur结点的字表 } cur = cur->_next; delete del; } } void Generalized::Print() { _Print(_head); cout << endl; } void Generalized::_Print(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << "("; } if (cur->_type == VALUE) { cout << (char)cur->_value;//强转为char类型 if (cur->_next)//如果cur->_next不为空打印“,” cout << ","; } if (cur->_type == SUB) { _Print(cur->_SubLink); if (cur->_next) cout << ","; } cur = cur->_next; } cout << ")"; } size_t Generalized::Size() { return _Size(_head); } size_t Generalized::_Size(GeneralizedNode* head) { GeneralizedNode* cur = head; size_t count = 0; while (cur) { if (cur->_type == VALUE) { ++count; } if (cur->_type == SUB) { count += _Size(cur->_SubLink); } cur = cur->_next; } return count; } size_t Generalized::Depth() { return _Depth(_head); } size_t Generalized::_Depth(GeneralizedNode* head) { GeneralizedNode* cur = head; size_t depth = 1; while (cur) { if (cur->_type == SUB) { size_t cdepth = _Depth(cur->_SubLink); if (cdepth + 1 > depth)//比较子表深度,保存较大的 { depth = cdepth + 1; } } cur = cur->_next; } return depth; }
测试用例如下:
void Test() { //Generalized g1("(a)"); //Generalized g2("(a,b)"); Generalized g3("(a,(a,b))"); Generalized g4("(a,(a,(b),c),d)"); Generalized g5 = g4; g5 = g3; //g1.Print(); //g2.Print(); g3.Print(); g4.Print(); g5.Print(); cout << "g3.Size():" << g3.Size() << endl; cout << "g4.Size():" << g4.Size() << endl; cout << "g3.Depth():" << g3.Depth() << endl; cout << "g4.Depth():" << g4.Depth() << endl; }
文章标题:递归实现广义表
文章地址:http://scyanting.com/article/ieehdc.html