廣義表是什么？如何實現(xiàn)廣義表的遞歸？這篇文章運(yùn)用了實例代碼展示，代碼非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下。
在云安等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計制作定制網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計,網(wǎng)絡(luò)營銷推廣,外貿(mào)網(wǎng)站建設(shè),云安網(wǎng)站建設(shè)費(fèi)用合理。
廣義表的定義
廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴(kuò)展，是有n個元素組成有限序列。
廣義表的定義是遞歸的，因為在表的描述中又得到了表，允許表中有表。
例如
<1> A = ()
<2> B = (a,b)
<3> C = (a,b,(c,d))
<4> D = (a,b,(c,d),(e,(f),h))
<5> E = (((),())
廣義表的節(jié)點(diǎn)結(jié)構(gòu)定義：
重慶分公司
重慶分公司
enum Type
{
HEAD,//頭結(jié)點(diǎn)
VALUE,//數(shù)據(jù)
SUB,//子表
};
//廣義表結(jié)構(gòu)
struct GeneralizedNode
{
public:
//無參構(gòu)造函數(shù)
GeneralizedNode()
:_type(HEAD)
,_next(NULL)
{}
//有參的構(gòu)造函數(shù)
GeneralizedNode(Type type, char ch);
public:
Type _type;
GeneralizedNode* _next;
//因為節(jié)點(diǎn)類型不可能既是數(shù)據(jù)節(jié)點(diǎn)又是子表結(jié)點(diǎn)，所以采用聯(lián)合結(jié)構(gòu)，
//節(jié)省空間，便于管理。
union
{
char _value;//數(shù)據(jù)結(jié)點(diǎn)
GeneralizedNode* _subLink;//子表結(jié)點(diǎn)
};
};
//有參的構(gòu)造函數(shù)
GeneralizedNode::GeneralizedNode(Type type, char ch = 0)
:_type(type)
, _next(NULL)
{
//數(shù)據(jù)節(jié)點(diǎn)則為數(shù)據(jù)初始化
if (_type == VALUE)
{
_value = ch;
}
//子表結(jié)點(diǎn)的初始化
else if (_type == SUB)
{
_subLink = NULL;
}
}廣義表的定義：
注意：由于廣義表的采用的是用遞歸實現(xiàn)。但構(gòu)造函數(shù)，等成員函數(shù)不能夠采用遞歸，而且在函數(shù)內(nèi)部需要不斷的傳子表的head，對于成員函數(shù)直接使用成員變量_head,則無法遞歸下去。
//廣義表類
class Generalized
{
public:
//無參構(gòu)造函數(shù)
Generalized()
:_head(new GeneralizedNode(HEAD))
{}
//有參構(gòu)造函數(shù)
Generalized(const char* str)
:_head(NULL)
{
_head = CreateList(str);
}
//拷貝構(gòu)造函數(shù)
Generalized(const Generalized& g)
{
_head=_CopyList(g._head);
}
GeneralizedNode* _CopyList(GeneralizedNode* head);
//賦值運(yùn)算符的重載
Generalized& operator=(Generalized g)
{
swap(_head, g._head);
return *this;
}
//析構(gòu)函數(shù)
~Generalized()
{
_Delete(_head);
}
void _Delete(GeneralizedNode* head);
public:
//打印廣義表
void Print()
{
_Print(_head);
}
//求廣義表的大小
size_t Size()
{
return _Size(_head);
}
//求廣義表的深度
size_t Depth()
{
return _Depth(_head);
}
protected:
//判斷數(shù)據(jù)是否有效
bool IsVaild(const char ch);
//創(chuàng)建廣義表
GeneralizedNode* CreateList(const char* &str);
void _Print(GeneralizedNode* head);
size_t _Size(GeneralizedNode* head);
size_t _Depth(GeneralizedNode* head);
private:
GeneralizedNode* _head;
};函數(shù)的實現(xiàn)
GeneralizedNode* Generalized::_CopyList(GeneralizedNode* head)
{
GeneralizedNode* cur = head;//需要拷貝的廣義表的當(dāng)前節(jié)點(diǎn)
GeneralizedNode* _head = new GeneralizedNode();//拷貝廣義表的頭結(jié)點(diǎn)
GeneralizedNode* index = _head;//拷貝廣義表的當(dāng)前節(jié)點(diǎn)
while (cur)
{
//數(shù)據(jù)結(jié)點(diǎn)
if (cur->_type == VALUE)
{
index->_next = new GeneralizedNode(VALUE, cur->_value);
index = index->_next;
}
//子表結(jié)點(diǎn)，遞歸復(fù)制
else if (cur->_type == SUB)
{
GeneralizedNode*SubNode = new GeneralizedNode(SUB);
index->_next = SubNode;
SubNode->_subLink= _CopyList(cur->_subLink);
index = index->_next;
}
cur = cur->_next;
}
return _head;
}
void Generalized::_Delete(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
while (cur)
{
GeneralizedNode* del = cur;
//遞歸刪除子表
if (cur->_type == SUB)
{
_Delete(cur->_subLink);
}
cur = cur->_next;
delete del;
}
}
//判斷廣義表的數(shù)據(jù)是否合法
bool Generalized::IsVaild(const char ch)
{
if ((ch >= '0'&&ch <= '9')
|| (ch >= 'a'&&ch <= 'z')
|| (ch >= 'A'&&ch <= 'Z'))
{
return true;//合法
}
return false;//非法
}
GeneralizedNode* Generalized::CreateList(const char* &str)
{
assert(str &&*str == '(');//斷言防止傳的廣義表格式不對，或者為空
str++;//跳過第一個(
GeneralizedNode* head = new GeneralizedNode();//創(chuàng)建頭結(jié)點(diǎn)
GeneralizedNode* cur = head;
while (*str)
{
if (IsVaild(*str))
{
cur->_next = new GeneralizedNode(VALUE, *str);
cur = cur->_next;
str++;
}
else if (*str == '(')//新的子表
{
GeneralizedNode* SubNode = new GeneralizedNode(SUB);
SubNode->_subLink = CreateList(str);
cur->_next = SubNode;
cur = cur->_next;
}
else if (*str == ')')//廣義表結(jié)束
{
str++;//返回之前需要給str++指向下一個
return head;
}
else//空格或者逗號
{
str++;
}
}
assert(false);
return NULL;
}
void Generalized::_Print(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
if (cur == NULL)
{
cout << "()" << endl;
return;
}
while (cur)
{
if (cur->_type == HEAD)
{
cout << "(";
}
else if (cur->_type == VALUE)
{
cout << cur->_value;
//_value不是最后一個值
if (cur->_next)
{
cout << ",";
}
}
else if (cur->_type == SUB)
{
_Print(cur->_subLink);
if (cur->_next)
{
cout << ",";
}
}
cur = cur->_next;
}
//輸出每個表最后一個(
cout << ")";
}
size_t Generalized::_Size(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
size_t count = 0;
while (cur)
{
if (cur->_type == VALUE)
{
count++;
}
//遞歸求取子表的大小
if (cur->_type == SUB)
{
count = count + _Size(cur->_subLink);
}
cur = cur->_next;
}
return count;
}
size_t Generalized::_Depth(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
size_t depth = 1;//空表深度為1
while (cur)
{
if (cur->_type == SUB)
{
size_t newDepth = _Depth(cur->_subLink);
//如果子表的深度+1大于當(dāng)前廣義表的最大深度，則更新廣義表的深度
if (newDepth +1 > depth)
{
depth = newDepth + 1;
}
}
cur = cur->_next;
}
return depth;
}測試代碼
#include"Generalized.h"
void TestGeneralized()
{
Generalized l("(a,b,(c,d),(e,(f),h))");
Generalized l1;
l1 = l;
l.Print();
cout << endl;
cout << "size:" << l.Size() << endl;
cout << "depth:" << l.Depth() << endl;
l1.Print();
cout << endl;
cout << "size:" << l1.Size() << endl;
cout << "depth:" << l1.Depth() << endl;
}
int main()
{
TestGeneralized();
getchar();
return 0;
}測試結(jié)果
以上就是實現(xiàn)廣義表的遞歸的具體操作，代碼應(yīng)該是足夠清楚的，而且我也相信有相當(dāng)?shù)囊恍├涌赡苁俏覀內(nèi)粘９ぷ骺赡軙姷玫降?。通過這篇文章，希望你能收獲更多。
