C++如何實現(xiàn)廣義表詳解
更新時間：2016年08月16日 09:43:51 投稿：daisy
廣義表是非線性結構，其定義是遞歸的。那么下面跟著小編一起看看如何用C++實現(xiàn)廣義表，有需要的可以參考借鑒。
以下給出幾種簡單的廣義表模型：
由上圖我們可以看到，廣義表的節(jié)點類型無非head、value、sub三種，這里設置枚舉類型，利用枚舉變量來記錄每個節(jié)點的類型：
enum Type
{
HEAD, //頭節(jié)點
VALUE, //值節(jié)點
SUB, //子表節(jié)點
};
每個節(jié)點都有自己的類型以及next指針，除此之外，如果該節(jié)點是VALUE類型還要分配空間存儲該節(jié)點的有效值；但是若該節(jié)點是SUB類型，就需定義一個指針指向子表的頭。
這里我們可以用聯(lián)合來解決這個問題。
（聯(lián)合（或共同體）是一種不同數(shù)據(jù)類型成員之間共享存儲空間的方法，并且聯(lián)合體對象在同一時間只能存儲一個成員值）
構造節(jié)點：
struct GeneralizedNode
{
Type _type; // 1.類型
GeneralizedNode* _next; //2.指向同層的下一個節(jié)點
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:
//無參的構造函數(shù),建立空的廣義表
Generalized();
//建造廣義表，有參數(shù)的構造函數(shù)
Generalized(const char* str);
//打印廣義表
void Print();
//獲取值節(jié)點的個數(shù)
size_t Amount();
//獲取廣義表的深度
size_t Depth();
//拷貝構造
Generalized(const Generalized& g);
////賦值運算符的重載
Generalized& operator=(const Generalized& g);
////析構函數(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; //記錄廣義表頭指針
};
初始化建立廣義表進行循環(huán)遞歸。遍歷字符串時遇到字符就建立值節(jié)點，遇到'('就進行遞歸并建立子表；遇到')'就結束當前子表的建立，并返回當前子表的頭指針?！?/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;
}
打印廣義表：當節(jié)點的類型為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 << ')';
}
獲取值節(jié)點的個數(shù)：設置count變量，遇到值節(jié)點就加1，遇到SUB節(jié)點進行遞歸并將返回值加給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節(jié)點指向的子表深度，以及本層所有的SUB節(jié)點中深度最大的子表的深度。
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é)點，遇到子表遞歸，將子表的節(jié)點delete完成后，再回到當前層繼續(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;
}
}
實例演示
定義：
廣義表是n(n≥0)個元素a1，a2，…，ai，…，an的有限序列。
其中：
?、賏i--或者是原子或者是一個廣義表。
?、趶V義表通常記作：
Ls=( a1，a2，…，ai，…，an)。
?、跮s是廣義表的名字，n為它的長度。
?、苋鬭i是廣義表，則稱它為Ls的子表。
注意：
①廣義表通常用圓括號括起來，用逗號分隔其中的元素。
?、跒榱藚^(qū)分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。
?、廴魪V義表Ls非空(n≥1)，則al是LS的表頭，其余元素組成的表(a1，a2，…，an)稱為Ls的表尾。
?、軓V義表是遞歸定義的
畫圖舉例：
代碼實現(xiàn)：
[cpp] view plain copy
#include <iostream>
using namespace std;
//表示廣義表的結點類型
enum NodeType
{
HEAD_TYPE,//頭結點類型
VALUE_TYPE,//值結點類型
SUB_TYPE//子表類型
};
//表示廣義表結點的結構體
struct GeneraListNode
{
NodeType _type;//結點類型
GeneraListNode *_next;//存放結點的下一個元素的地址
//一個結點要么是值結點要么是子表，故用聯(lián)合體來存放節(jié)省一定的空間
//若是值結點則存放的是值，是子表結點的話存放的是子表結點頭結點的地址
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);//根據(jù)指定序列創(chuàng)建廣義表
}
~GeneraList()
{}
public:
void Print();//對外提供的打印廣義表的接口
int Size();//廣義表中值結點的數(shù)目的對外獲取接口
int Depth();//廣義表的最深層次的對外獲取接口
private:
void _CreateGeneraList(GeneraListNode *& link, const char *& str);
bool _IsValue(const char ch);//判斷指定字符是否為值結點所允許的類型
int _Size(GeneraListNode *head);//計算廣義表中值結點的數(shù)目的實現(xiàn)
int _Depth(GeneraListNode *head);//計算廣義表的最深層次的實現(xiàn)
void _Print(GeneraListNode *link);//打印廣義表的接口的底層實現(xiàn)
};
//創(chuàng)建廣義表
void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str)
{
//廣義表最前端有一個頭結點，用來記錄實現(xiàn)廣義表鏈表的首地址
//故每次調用該創(chuàng)建廣義表的函數(shù)首先創(chuàng)建一個頭結點
GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL);
head->_next = NULL;
link = head;
GeneraListNode* cur = link;//用來記錄創(chuàng)建廣義表鏈表時當前創(chuàng)建出的結點位置游標指針
str++;//將廣義表序列后移,相當于跳過了'('
while(*str != '\0')
{
if(_IsValue(*str)){//如果當前掃描到的字符是值
//創(chuàng)建一個值結點
GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str);
newNode->_next = NULL;
cur->_next = newNode;//將該值結點加入到鏈表中
cur = cur->_next;//游標后移
str++;//將廣義表序列后移
}else if(*str == '('){//如果掃描到'('創(chuàng)建子表結點
GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL);
subLink->_next = NULL;
cur->_next = subLink;//將子表結點加入到鏈表中
cur = cur->_next;
_CreateGeneraList(cur->_subLink, str);//遞歸創(chuàng)建子表
}else if(*str == ')'){
str++;
return;//若掃描到')'表示廣義表創(chuàng)建結束
}else{
str++;//空格等其他無效字符跳過
}
}
}
int GeneraList::Size()
{
return _Size(_link);
}
//計算廣義表值結點的個數(shù)
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++如何實現(xiàn)廣義表詳解的全部內容，希望對有需要的人能有所幫助，如果有疑問歡迎大家留言討論。
相關文章
數(shù)據(jù)結構之數(shù)組Array實例詳解
這篇文章主要介紹了數(shù)據(jù)結構之數(shù)組Array實例詳解的相關資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了C++ boost::asio編程-域名解析詳細介紹的相關資料,這里附有實例代碼，幫助大家學習理解這部分知識，需要的朋友可以參考下2016-11-11
這篇文章主要介紹了C++深淺拷貝及簡易string類實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)仿QQ設置面板功能，文中的示例代碼講解詳細，具有一定的借鑒價值，感興趣的小伙伴可以了解一下2022-12-12
本文主要介紹了C++中map和set的簡介及使用詳解，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
C語言是一門通用計算機編程語言,廣泛應用于底層開發(fā),這篇文章主要給大家介紹了關于利用C語言實現(xiàn)經(jīng)典多級時間輪定時器的相關資料,需要的朋友可以參考下2021-07-07
Windows下ncnn環(huán)境配置教程詳解（VS2019）
這篇文章主要介紹了Windows下ncnn環(huán)境配置（VS2019）,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-03-03
當文件見過編譯后就需要進行一個鏈接的操作接下來我們就說說什么是鏈接,本文給大家介紹了C++鏈接器是如何工作的,文章通過代碼示例和圖文介紹的非常詳細,需要的朋友可以參考下2024-02-02
這篇文章主要為大家詳細介紹了C++的原生數(shù)組，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C語言中對于循環(huán)結構優(yōu)化的一些入門級方法簡介
這篇文章主要介紹了C語言中對于循環(huán)結構優(yōu)化的一些入門級方法,包括算法設計的改進來提高一些并行性等方法,要的朋友可以參考下2015-12-12