亲宝软件园·资讯

展开

C++实现广义表 C++怎样实现广义表详解

人气:0
想了解C++怎样实现广义表详解的相关内容吗,在本文为您仔细讲解C++实现广义表的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:广义表c语言,广义表的运算c语言,广义表head,tail,运算,下面大家一起来学习吧。

以下给出几种简单的广义表模型:

 

由上图我们可以看到,广义表的节点类型无非headvaluesub三种,这里设置枚举类型,利用枚举变量来记录每个节点的类型:

enum Type
{
  HEAD,  //头节点
  VALUE, //值节点
  SUB,  //子表节点
};

每个节点都有自己的类型以及next指针,除此之外,如果该节点是VALUE类型还要分配空间存储该节点的有效值;但是若该节点是SUB类型,就需定义一个指针指向子表的头。

这里我们可以用联合来解决这个问题。

(联合(或共同体)是一种不同数据类型成员之间共享存储空间的方法,并且联合体对象在同一时间只能存储一个成员值)

构造节点:

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;
    }
  }
};

广义表的定义及基本操作: 

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;  //记录广义表头指针
};

初始化建立广义表进行循环递归。遍历字符串时遇到字符就建立值节点,遇到'('就进行递归并建立子表;遇到')'就结束当前子表的建立,并返回当前子表的头指针。 

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时进行递归,最后不要忘了每打印完一层要打印一个后括号。

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

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节点中深度最大的子表的深度。

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完成后,再回到当前层继续遍历。

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的表尾。

  ④广义表是递归定义的

画图举例:

代码实现:

[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; 
} 

测试代码

[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++如何实现广义表详解的全部内容,希望对有需要的人能有所帮助,如果有疑问欢迎大家留言讨论。

加载全部内容

相关教程
猜你喜欢
用户评论