以下給出幾種簡單的廣義表模型：
由上圖我們可以看到，廣義表的節點類型無非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++如何實現廣義表詳解的全部內容，希望對有需要的人能有所幫助，如果有疑問歡迎大家留言討論。
新聞熱點
疑難解答
