C++如何實(shí)現(xiàn)廣義表詳解

更新時(shí)間：2016年08月16日 09:43:51 投稿：daisy

廣義表是非線性結(jié)構(gòu)，其定義是遞歸的。那么下面跟著小編一起看看如何用C++實(shí)現(xiàn)廣義表，有需要的可以參考借鑒。

以下給出幾種簡(jiǎn)單的廣義表模型：

由上圖我們可以看到，廣義表的節(jié)點(diǎn)類型無(wú)非head、value、sub三種，這里設(shè)置枚舉類型，利用枚舉變量來(lái)記錄每個(gè)節(jié)點(diǎn)的類型：

enum Type
{
  HEAD,  //頭節(jié)點(diǎn)
  VALUE, //值節(jié)點(diǎn)
  SUB,  //子表節(jié)點(diǎn)
};

每個(gè)節(jié)點(diǎn)都有自己的類型以及next指針，除此之外，如果該節(jié)點(diǎn)是VALUE類型還要分配空間存儲(chǔ)該節(jié)點(diǎn)的有效值；但是若該節(jié)點(diǎn)是SUB類型，就需定義一個(gè)指針指向子表的頭。

這里我們可以用聯(lián)合來(lái)解決這個(gè)問(wèn)題。

（聯(lián)合（或共同體）是一種不同數(shù)據(jù)類型成員之間共享存儲(chǔ)空間的方法，并且聯(lián)合體對(duì)象在同一時(shí)間只能存儲(chǔ)一個(gè)成員值）

構(gòu)造節(jié)點(diǎn)：

struct GeneralizedNode
{
  Type _type;    // 1.類型
  GeneralizedNode* _next; //2.指向同層的下一個(gè)節(jié)點(diǎn)
  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:
  //無(wú)參的構(gòu)造函數(shù),建立空的廣義表
  Generalized();
  //建造廣義表，有參數(shù)的構(gòu)造函數(shù)
  Generalized(const char* str);
  //打印廣義表
  void Print();
  //獲取值節(jié)點(diǎn)的個(gè)數(shù)
  size_t Amount();
  //獲取廣義表的深度
  size_t Depth();
  //拷貝構(gòu)造
  Generalized(const Generalized& g);
  ////賦值運(yùn)算符的重載
  Generalized& operator=(const Generalized& g);
  ////析構(gòu)函數(shù)
  ~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;  //記錄廣義表頭指針
};

初始化建立廣義表進(jìn)行循環(huán)遞歸。遍歷字符串時(shí)遇到字符就建立值節(jié)點(diǎn)，遇到'('就進(jìn)行遞歸并建立子表；遇到')'就結(jié)束當(dāng)前子表的建立，并返回當(dāng)前子表的頭指針?！?/p>

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

打印廣義表：當(dāng)節(jié)點(diǎn)的類型為SUB時(shí)進(jìn)行遞歸，最后不要忘了每打印完一層要打印一個(gè)后括號(hào)。

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

獲取值節(jié)點(diǎn)的個(gè)數(shù)：設(shè)置count變量，遇到值節(jié)點(diǎn)就加1，遇到SUB節(jié)點(diǎn)進(jìn)行遞歸并將返回值加給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;
}

廣義表的深度：設(shè)置變量dp和max分別用來(lái)記錄當(dāng)前子表即當(dāng)前SUB節(jié)點(diǎn)指向的子表深度，以及本層所有的SUB節(jié)點(diǎn)中深度最大的子表的深度。

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

銷毀廣義表：依次遍歷節(jié)點(diǎn)，遇到子表遞歸，將子表的節(jié)點(diǎn)delete完成后，再回到當(dāng)前層繼續(xù)遍歷。

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

實(shí)例演示

定義：

廣義表是n(n≥0)個(gè)元素a1，a2，…，ai，…，an的有限序列。

　　其中：

　　①ai--或者是原子或者是一個(gè)廣義表。

　　②廣義表通常記作：

　　Ls=( a1，a2，…，ai，…，an)。

　?、跮s是廣義表的名字，n為它的長(zhǎng)度。

　?、苋鬭i是廣義表，則稱它為L(zhǎng)s的子表。

　　注意：

　?、?gòu)V義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。

　?、跒榱藚^(qū)分原子和廣義表，書(shū)寫(xiě)時(shí)用大寫(xiě)字母表示廣義表，用小寫(xiě)字母表示原子。

　　③若廣義表Ls非空(n≥1)，則al是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為L(zhǎng)s的表尾。

　?、軓V義表是遞歸定義的

畫(huà)圖舉例：

代碼實(shí)現(xiàn)：

[cpp] view plain copy
#include <iostream> 
 
using namespace std; 
 
//表示廣義表的結(jié)點(diǎn)類型 
enum NodeType 
{ 
  HEAD_TYPE,//頭結(jié)點(diǎn)類型 
  VALUE_TYPE,//值結(jié)點(diǎn)類型 
  SUB_TYPE//子表類型 
}; 
 
//表示廣義表結(jié)點(diǎn)的結(jié)構(gòu)體 
struct GeneraListNode 
{ 
  NodeType _type;//結(jié)點(diǎn)類型 
  GeneraListNode *_next;//存放結(jié)點(diǎn)的下一個(gè)元素的地址 
 
  //一個(gè)結(jié)點(diǎn)要么是值結(jié)點(diǎn)要么是子表，故用聯(lián)合體來(lái)存放節(jié)省一定的空間 
  //若是值結(jié)點(diǎn)則存放的是值，是子表結(jié)點(diǎn)的話存放的是子表結(jié)點(diǎn)頭結(jié)點(diǎn)的地址 
  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;//用來(lái)存放廣義表頭結(jié)點(diǎn)地址 
public: 
  GeneraList(const char *str) 
    :_link(NULL) 
  { 
    _CreateGeneraList(_link, str);//根據(jù)指定序列創(chuàng)建廣義表 
  } 
 
  ~GeneraList() 
  {} 
public: 
  void Print();//對(duì)外提供的打印廣義表的接口 
  int Size();//廣義表中值結(jié)點(diǎn)的數(shù)目的對(duì)外獲取接口 
  int Depth();//廣義表的最深層次的對(duì)外獲取接口 
private: 
  void _CreateGeneraList(GeneraListNode *& link, const char *& str); 
  bool _IsValue(const char ch);//判斷指定字符是否為值結(jié)點(diǎn)所允許的類型 
  int _Size(GeneraListNode *head);//計(jì)算廣義表中值結(jié)點(diǎn)的數(shù)目的實(shí)現(xiàn) 
  int _Depth(GeneraListNode *head);//計(jì)算廣義表的最深層次的實(shí)現(xiàn) 
  void _Print(GeneraListNode *link);//打印廣義表的接口的底層實(shí)現(xiàn) 
}; 
 
//創(chuàng)建廣義表 
void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str) 
{ 
  //廣義表最前端有一個(gè)頭結(jié)點(diǎn)，用來(lái)記錄實(shí)現(xiàn)廣義表鏈表的首地址 
  //故每次調(diào)用該創(chuàng)建廣義表的函數(shù)首先創(chuàng)建一個(gè)頭結(jié)點(diǎn) 
  GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL); 
  head->_next = NULL; 
  link = head; 
  GeneraListNode* cur = link;//用來(lái)記錄創(chuàng)建廣義表鏈表時(shí)當(dāng)前創(chuàng)建出的結(jié)點(diǎn)位置游標(biāo)指針 
  str++;//將廣義表序列后移,相當(dāng)于跳過(guò)了'(' 
   
  while(*str != '\0') 
  { 
    if(_IsValue(*str)){//如果當(dāng)前掃描到的字符是值 
      //創(chuàng)建一個(gè)值結(jié)點(diǎn) 
      GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str); 
      newNode->_next = NULL; 
      cur->_next = newNode;//將該值結(jié)點(diǎn)加入到鏈表中 
      cur = cur->_next;//游標(biāo)后移 
      str++;//將廣義表序列后移 
    }else if(*str == '('){//如果掃描到'('創(chuàng)建子表結(jié)點(diǎn) 
      GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL); 
      subLink->_next = NULL; 
      cur->_next = subLink;//將子表結(jié)點(diǎn)加入到鏈表中 
      cur = cur->_next; 
      _CreateGeneraList(cur->_subLink, str);//遞歸創(chuàng)建子表 
    }else if(*str == ')'){ 
      str++; 
      return;//若掃描到')'表示廣義表創(chuàng)建結(jié)束 
    }else{ 
      str++;//空格等其他無(wú)效字符跳過(guò) 
    } 
  } 
} 
 
int GeneraList::Size() 
{ 
  return _Size(_link); 
} 
 
//計(jì)算廣義表值結(jié)點(diǎn)的個(gè)數(shù) 
int GeneraList::_Size(GeneraListNode *head) 
{ 
  int size = 0; 
  GeneraListNode *cur = head; 
  while(cur != NULL){ 
    if(cur->_type == VALUE_TYPE){ 
      ++size;//遇到值結(jié)點(diǎn)則將size加一 
    }else if(cur->_type == SUB_TYPE){ 
      size += _Size(cur->_subLink);//遇到子表進(jìn)行遞歸 
    } 
    cur = cur->_next; 
  } 
  return size; 
} 
 
int GeneraList::Depth() 
{ 
  return _Depth(_link); 
} 
int GeneraList::_Depth(GeneraListNode *head) 
{ 
  int depth = 1,maxDepth = 1;//depth表示當(dāng)前表的深度，maxDepth表示目前最大的深度 
  GeneraListNode *cur = head; 
  while(cur != NULL){ 
    if(cur->_type == SUB_TYPE){ 
      depth += _Depth(cur->_subLink); 
    } 
    if(depth > maxDepth){//更新最大深度 
      maxDepth = depth; 
      depth = 1;//將當(dāng)前深度復(fù)位 
    } 
    cur = cur->_next; 
  } 
  return maxDepth; 
} 
 
void GeneraList::Print() 
{ 
  _Print(_link); 
  cout<<endl; 
} 
 
//打印廣義表 
void GeneraList::_Print(GeneraListNode *link) 
{ 
  GeneraListNode *cur = link;//遍歷廣義表的游標(biāo) 
  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)//如果打印完子表后廣義表未結(jié)束則打印',' 
      { 
        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; 
}

測(cè)試代碼

[cpp] view plain copy
#include"GeneraList.hpp" 
 
//測(cè)試空表 
void Test1() 
{ 
  GeneraList genList("()"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//測(cè)試單層表 
void Test2() 
{ 
  GeneraList genList("(a,b)"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//測(cè)試雙層表 
void Test3() 
{ 
  GeneraList genList("(a,b,(c,d))"); 
  genList.Print(); 
  cout<<"Size is :"<<genList.Size()<<endl; 
  cout<<"Depth is :"<<genList.Depth()<<endl<<endl; 
} 
//測(cè)試多層表 
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; 
} 
//測(cè)試多層空表 
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; 
}

運(yùn)行結(jié)果