登录
当前位置： 首页 > 编程笔记 >

C++如何实现广义表详解

景阳曜
2023-03-14
本文向大家介绍C++如何实现广义表详解，包括了C++如何实现广义表详解的使用技巧和注意事项，需要的朋友参考一下

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

 

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

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

 类似资料：
  • C++如何实现简单的计时器详解

    本文向大家介绍C++如何实现简单的计时器详解，包括了C++如何实现简单的计时器详解的使用技巧和注意事项，需要的朋友参考一下 实现分析 首先我们先分析一下计时器的一些功能，简单一点的计时器包括开始、暂停、停止和显示基本功能，这些功能以C++面向对象的编程思想（OOP）进行抽象，就是计时器类（Timer）的4个成员函数，当然我们要把这些函数作为公有的，因为它们是留给外部的接口（interface）。

  • C语言单链表实现方法详解

    本文向大家介绍C语言单链表实现方法详解，包括了C语言单链表实现方法详解的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了C语言单链表实现方法。分享给大家供大家参考，具体如下： slist.h slist.cpp main.cpp 附：单链表优化版本 slist.h slist.cpp main.cpp 希望本文所述对大家C语言程序设计有所帮助。

  • C语言栈的表示与实现实例详解

    本文向大家介绍C语言栈的表示与实现实例详解，包括了C语言栈的表示与实现实例详解的使用技巧和注意事项，需要的朋友参考一下 1.基本概念： C语言的栈是指限定仅在表尾进行插入和删除操作的线性表。 栈作为C语言中一种常用的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一

  • C语言双向链表的表示与实现实例详解

    本文向大家介绍C语言双向链表的表示与实现实例详解，包括了C语言双向链表的表示与实现实例详解的使用技巧和注意事项，需要的朋友参考一下 1.概述： C语言中一种更复杂的链表是“双向链表”或“双面链表”。其表中的每个节点有两个连接：一个指向前一个节点，（当这个“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当这个“连接”为最后一个“连接”时，指向空值或者空列表） 一个双向链表

  • C语言单向链表的表示与实现实例详解

    本文向大家介绍C语言单向链表的表示与实现实例详解，包括了C语言单向链表的表示与实现实例详解的使用技巧和注意事项，需要的朋友参考一下 1.概述： C语言中的单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。 链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。 如下图所示

  • C++实现广度优先搜索实例

    本文向大家介绍C++实现广度优先搜索实例，包括了C++实现广度优先搜索实例的使用技巧和注意事项，需要的朋友参考一下 本文主要叙述了图的遍历算法中的广度优先搜索（Breadth-First-Search）算法，是非常经典的算法，可供C++程序员参考借鉴之用。具体如下： 首先，图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，

相关阅读

C语言单向链表的表示与实现实例详解C++实现广度优先搜索实例C语言单循环链表的表示与实现实例详解asp.net中c#自定义事件的实现方法详解C#实现绘制面形图表的方法详解

相关文章

广联达C++一面广立微 凉经 C++/Qt广联达C++一面面经MySQL 是如何实现 ACID 的详解MySQL/Redis/ZooKeeper实现分布式锁

相关问答

如何实现mpeg-dash实时播放列表？node.js - mongodb 如何实现多表连改？如何用RecyclerView实现无尽列表？Apache Flink-如何实现自定义反序列化器实现DeserializationSchemac - 按广义表表示二叉树结构生成二叉链表的算法问题？

相关工具

自定义表情键盘流媒体广播广电融合 CDN简单的广告栏《Redis 设计与实现》

相关文档

如何实现自己的 jQueryGRUB2 配置文件 grub.cfg 详解 / GRUB2 实战手册Redis 设计与实现通过实例学习 C 语言深入理解 OpenStack 网络实现 Neutron
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.