本文共 2786 字，大约阅读时间需要 9 分钟。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream> #include<assert.h> using namespace std; enum NODETYPE { HEAD, VALUE, SUB }; struct GeneralizedNode { NODETYPE _type; GeneralizedNode* _next; union { char _value; GeneralizedNode* _sublist; }; GeneralizedNode(NODETYPE type = HEAD, char value = 0) :_type(type) , _next(NULL) { if (_type == VALUE) { _value = value; } else if (_type == SUB) { _sublist = NULL; } } }; class GeneralizedList { public: GeneralizedList(const char* str) { _head = _CreateList(str); } ~GeneralizedList() { _Clean(_head); } void Print() { _Print(_head); cout << endl; } void Size() { cout<<_Size(_head)<<endl; } protected: GeneralizedNode* _CreateList(const char*& str) //这里的str为二级指针 所以要用引用 { assert(*str == '('); GeneralizedNode* head = new GeneralizedNode(HEAD); GeneralizedNode* cur = head; str++; //方便处理 开始 和 字链表 这两种情况 // 一搬情况： // (a,b,c) // (a,(b,c),d) // (a, b,c) // () // (()) // 1:值 2：‘（’ 3：‘）’ 4：逗号 空格等等无关符号 while (*str != NULL) { if (_IsValue(*str)) // 是值的情况 { GeneralizedNode* tem = new GeneralizedNode(VALUE, *str); cur->_next = tem; cur = tem; str++; } else if (*str == '(') // 是子链表的情况 { GeneralizedNode* sub = new GeneralizedNode(SUB); cur->_next = sub; cur = sub; sub->_sublist = _CreateList(str);//循环构造子链 } else if (*str == ')') //子表结束的情况 { str++; return head; } else //逗号 空格等等无关符号的情况 { str++; } } return head; } bool _IsValue(char ch) { if ((ch >= '0' && ch <= '9') || \ (ch >= 'a' && ch <= 'z') || \ (ch >= 'A' && ch <= 'Z')) { return true; } else { return false; } } void _Print(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur != NULL) { if (cur->_type == HEAD) { cout << "("; } else if (cur->_type == VALUE) { cout << cur->_value; if (cur->_next != NULL) { cout << ","; } } else { _Print(cur->_sublist); cout << ","; //注意子链打印完了也要打印一个 ， } cur = cur->_next; } cout << ")"; } int _Size(GeneralizedNode* head) { //assert(head); int count = 0; GeneralizedNode* cur = head; while (cur != NULL) { //if (cur->_type == HEAD) //{ // cur = cur->_next; //下面有这个操作 可以合并 //} if (cur->_type == VALUE) { count++; } else if (cur->_type == SUB) { count += _Size(cur->_sublist); } cur = cur->_next; } return count; } void _Clean(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur != NULL) { GeneralizedNode* del = cur; if (cur->_type == HEAD || cur->_type == VALUE) { cur = cur->_next; delete(del); } else { _Clean(cur->_sublist); cur = cur->_next; } } } protected: GeneralizedNode* _head; }; void Test1() { char* s1 = "(a,b,c,d)"; char* s2 = "(a,(b,c),d)"; char* s3 = "(())"; GeneralizedList L1(s1); GeneralizedList L2(s2); GeneralizedList L3(s3); L1.Print(); L2.Print(); L3.Print(); L1.Size(); L2.Size(); L3.Size(); } int main() { Test1(); return 0; }