其中包括广义表的创建、输出、拷贝构造、赋值运算符重载、析构、有效数据个数以及广义表深度

#pragma once#include
     
      #include
      
       #include
       
        using namespace std;enum Type{ HEAD, VALUE, SUB};//头结点、值、子表struct GeneralizedNode{ Type _type;  //广义表结点类型 GeneralizedNode* _next;  //广义表结点指针 union {  int _value;  //广义表结点存储的数据  GeneralizedNode* _subLink; //存储的指向子表的指针 }; GeneralizedNode(Type type = HEAD, int value = 0)//构造  :_type(type)  , _next(NULL) {  if (type == VALUE)  {   _value = value;  } }};class GeneralizedList{public: GeneralizedList()  :_head(NULL) {} GeneralizedList(const char* str) //创建表 {  _head = _CreateList(str); } //拷贝构造 GeneralizedList(const GeneralizedList& s) {  _head = _copy(s._head); } //赋值运算符重载 GeneralizedNode* operator=(GeneralizedList s) {  swap(_head, s._head);  return _head; } //析构函数 ~GeneralizedList() {  _Dele(_head); } void PrintList()//输出 {  _PrintNode(_head); } size_t size() {  size_t num = 0;  _size(_head, num);  return num; } size_t Depth() {  return _depth(_head); }private: GeneralizedNode* _CreateList(const char*& str) {  //  GeneralizedList b2("(a,(b,c))");  assert('(' == *str);  ++str; //跳过'('  GeneralizedNode* head = new GeneralizedNode(HEAD);  GeneralizedNode* cur = head;  //除数字字符与')'其他字符都不需要考虑，直接跳过就可以  while (')' != *str)  {   if ((*str >= '0'&&*str <= '9') || /*也可以使用数字字符判别函数 isdigit(*str)==-1*/    (*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, *str);    cur->_next->_subLink = _CreateList(str);    cur = cur->_next;   }   else   {    str++;   }  }  str++;//跳过 ')'  return head; } GeneralizedNode* _copy(GeneralizedNode* head) {  GeneralizedNode* dst = new GeneralizedNode(HEAD);  GeneralizedNode* cur = dst;  if (head == NULL)   return NULL;  while (head != NULL)  {   if (head->_type == VALUE)   {    cur->_next = new GeneralizedNode(VALUE, head->_value);    cur = cur->_next;   }   else if (head->_type == SUB)   {    cur->_next = new GeneralizedNode(SUB);    cur->_next->_subLink = _copy(head->_subLink);    cur = cur->_next;   }   head = head->_next;   //cur->_next = new GeneralizedNode(VALUE, head->_value);  }  return dst; } void _PrintNode(GeneralizedNode* head) {  //  GeneralizedList b2("(a,(b,c))");  GeneralizedNode* tmp = head;  while (tmp != NULL)  {   if (HEAD == tmp->_type)   {    cout << "(";    tmp = tmp->_next;   }   else if (VALUE == tmp->_type)   {    cout << (char)tmp->_value;    tmp = tmp->_next;    if (tmp != NULL)    {     cout << ", ";    }   }   else   {    _PrintNode(tmp->_subLink);    if (tmp->_next != NULL)    {     cout << ", ";    }    tmp = tmp->_next;   }  }  cout << ")"; } void _size(GeneralizedNode* head, size_t& size) {  GeneralizedNode* tmp = head;  while (tmp != NULL)  {   if (HEAD == tmp->_type)   {    tmp = tmp->_next;   }   else if (VALUE == tmp->_type)   {    ++size;    tmp = tmp->_next;   }   else   {    _size(tmp->_subLink, size);    tmp = tmp->_next;   }  } } size_t _depth(GeneralizedNode* head) {  size_t depth = 1;  size_t count = 0;  GeneralizedNode* tmp = head;  while (tmp != NULL)  {   if (SUB == tmp->_type)   {    size_t subdep = _depth(tmp->_subLink);    if (subdep + 1 > depth)    {     depth = subdep + 1;    }   }   tmp = tmp->_next;  }  return depth; } void _Dele(GeneralizedNode* head) {  if (head == NULL)   return;  else if (head->_type == SUB)  {   _Dele(head->_subLink);   _Dele(head->_next);//注意 在删除SUB结点后紧接着删除下一结点   //cout << "dele" << " ";   delete head;  }  else  {   _Dele(head->_next);   //cout << "dele" << " ";   delete head;  } }private: GeneralizedNode* _head;};#include"GeneralizedList.h"void test(){ GeneralizedList b1("(a,b)"); b1.PrintList(); cout << endl; GeneralizedList b2("(a,(b,c))"); b2.PrintList(); cout << endl; GeneralizedList b3("(a,(b,c),d)"); b3.PrintList(); cout << endl; GeneralizedList b4("(a,(b,c),(d,(e),f),(h,i))"); b4.PrintList(); cout << "\n" << endl; cout << "b1.size = " << b1.size() << endl; cout << "b2.size = " << b2.size() << endl; cout << "b3.size = " << b3.size() << endl; cout << "b4.size = " << b4.size() << endl; cout << "b1.Depth = " << b1.Depth() << endl; cout << "b2.Depth = " << b2.Depth() << endl; cout << "b3.Depth = " << b3.Depth() << endl; cout << "b4.Depth = " << b4.Depth() << endl; GeneralizedList b5("(a,(b,c),(h,i),(d,(e),f))"); cout << "b5.Depth = " << b5.Depth() << endl; GeneralizedList b6(b2); b6.PrintList(); cout << endl; GeneralizedList b7(b3); b7.PrintList(); GeneralizedList b8; b8 = b7; b8.PrintList(); b7.PrintList();}int main(){ test(); system("pause"); return 0;}