C++數(shù)據(jù)結(jié)構(gòu)廣義表
GeneralList-廣義表
站在用戶的角度思考問題，與客戶深入溝通，找到陽原網(wǎng)站設(shè)計與陽原網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都做網(wǎng)站、網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名與空間、網(wǎng)頁空間、企業(yè)郵箱。業(yè)務(wù)覆蓋陽原地區(qū)。
廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴展，是有n個元素組成有限序列。
廣義表的定義是遞歸的，因為在表的描述中又得到了表，允許表中有表。
<1> A = ()
<2> B = (a,b)
<3> C = (a,b,(c,d))
<4> D = (a,b,(c,d),(e,(f),h))
<5> E = (((),()))
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <assert.h>
using namespace std;
enum Type
{
HEAD,
VALUE,
SUB
};
struct GeneralizedNode
{
Type _type;//類型
GeneralizedNode* _next;//指向同層下一個結(jié)點
union
{
//int _value;
char _value;
GeneralizedNode* _subLink;//指向子表的指針
};
GeneralizedNode(Type type = VALUE, const int value = 0)
:_type(type)
,_next(NULL)
,_value(value)
{}
};
class Generalized
{
public:
Generalized()
:_head(NULL)
{}
Generalized(const char* str)
:_head(NULL)
{
_head = _CreateList(str);
}
void Print() const
{
_Print(_head);
cout<<endl;
}
size_t Size() const
{
return _Size(_head);
}
size_t Depth() const
{
return _Depth(_head);
}
//===========新加的
Generalized(const Generalized& g);
Generalized& operator=(Generalized g); // 現(xiàn)代寫法
~Generalized();
protected:
GeneralizedNode* _CreateList(const char*& str);
void _Print(GeneralizedNode* head) const;
bool _IsValue(char ch);
size_t _Size(GeneralizedNode* head) const;
size_t _Depth(GeneralizedNode* head) const;
GeneralizedNode* _Copy(const GeneralizedNode* head);
void _Destory(GeneralizedNode* head);
protected:
GeneralizedNode* _head;
};
bool Generalized:: _IsValue(char ch)
{
if ((ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z'))
{
return true;
}
else
{
return false;
}
}
GeneralizedNode* Generalized::_CreateList(const char*& str)//注意&
{
assert(str);
assert(*str == '(');
// D = (a,b,(c,d),(e,(f),h))
GeneralizedNode* head = new GeneralizedNode(HEAD);
GeneralizedNode* cur = head;
++str;
while (*str != '\0')
{
if (*str == '(')// 有子層
{
cur->_next = new GeneralizedNode(SUB);
cur = cur->_next;
cur->_subLink = _CreateList(str);//下一層
}
else if(_IsValue(*str))
{
cur->_next = new GeneralizedNode(VALUE, *str);
cur = cur->_next;
++str;
}
else if (*str == ')')
{
++str;// **********更新上一層的str
break;
}
else // 其他情況 *str為 逗號 空格 制表符 等
{
++str;
}
}
return head;
}
void Generalized::_Print(GeneralizedNode* head)const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
cout<<"(";
while(cur)
{
if (cur->_type == VALUE)
{
cout<<cur->_value;
cur = cur->_next;
if (cur != NULL)
{
cout<<",";
}
}
else if (cur->_type == SUB)
{
_Print(cur->_subLink);
cur = cur->_next;
if (cur != NULL)
{
cout<<",";
}
}
}
cout<<")";
}
size_t Generalized::_Size(GeneralizedNode* head) const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
size_t count = 0;
while(cur)
{
if (cur->_type == VALUE)
{
count++;
}
else if(cur->_type == SUB)
{
count += _Size(cur->_subLink);
}
cur = cur->_next;
}
return count;
}
// 有問題
//size_t Generalized::_Depth(GeneralizedNode* head) const
//{
//assert(head && head->_type == HEAD);
//GeneralizedNode* cur = head->_next;
//size_t depth = 1;
//while(cur)
//{
//if (cur->_type == SUB)
//{
//depth += _Depth(cur->_subLink);
//}
//
//cur = cur->_next;
//}
//
//return depth;
//}
size_t Generalized::_Depth(GeneralizedNode* head) const
{
assert(head && head->_type == HEAD);
GeneralizedNode* cur = head->_next;
size_t depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
size_t SubDepth = _Depth(cur->_subLink);
if (depth < 1 + SubDepth) // 找最大的 depth 注意 不要用 depth = depth + SubDepth
{
depth = 1 + SubDepth;
}
}
cur = cur->_next;
}
return depth;
}
Generalized:: Generalized(const Generalized& g)
{
_head = _Copy(g._head);
}
GeneralizedNode* Generalized::_Copy(const GeneralizedNode* head)
{
assert(head && head->_type == HEAD);
const GeneralizedNode* cur = head->_next;
GeneralizedNode* retHead = new GeneralizedNode(HEAD);
GeneralizedNode* newNode = retHead;
while (cur)
{
if (cur->_type == VALUE)
{
newNode->_next = new GeneralizedNode(VALUE, cur->_value);
newNode = newNode->_next;
}
else if (cur->_type == SUB)
{
newNode->_next = new GeneralizedNode(SUB);
newNode = newNode->_next;
newNode->_subLink = _Copy(cur->_subLink);
}
cur = cur->_next;
}
return retHead;
}
Generalized& Generalized::operator=(Generalized g) // 現(xiàn)代寫法
{
swap(_head, g._head);
return *this;
}
Generalized::~Generalized()
{
_Destroy(_head);
}
void Generalized::_Destory(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
while (cur)
{
GeneralizedNode* del = cur;
cur = cur->_next;
if (del->_type == SUB)
{
_Destory(del->_subLink);
}
delete del;
del = NULL;
}
}
void test_G_chuangjian()
{
char* str = "(a,b,(c,d))";
Generalized g(str);
g.Print();
cout<<g.Size()<<endl;
cout<<g.Depth()<<endl;
cout<<"============"<<endl;
char* str2 = "(a,b,(c,d),(e,(f),h))";
Generalized g2(str2);
g2.Print();
cout<<g2.Size()<<endl;
cout<<g2.Depth()<<endl;
cout<<"============"<<endl;
Generalized g3(g2);
g3.Print();
cout<<g3.Size()<<endl;
cout<<g3.Depth()<<endl;
cout<<"============"<<endl;
Generalized g4;
g4 = g2;
g4.Print();
cout<<g4.Size()<<endl;
cout<<g4.Depth()<<endl;
}
int main()
{
test_G_chuangjian();
return 0;
}
文章標題：C++數(shù)據(jù)結(jié)構(gòu)廣義表
本文網(wǎng)址：http://muchs.cn/article4/pisooe.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、網(wǎng)站收錄、建站公司、網(wǎng)站維護、云服務(wù)器、
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)
