廣義表的實現

廣義表是一種非線性表的數據結構，是線性表的一種推廣。他放松了對原子的控制，容許原子有自身的結構。其實現如下：

#include<iostream>
using namespace std;
#include<assert.h>

enum Type????? //原子類型有三種:頭結點，子表節點和值節點
{
?? ?HEAD,
?? ?SUB,
?? ?VALUE
};
template<class T>
struct GeneralListNode?????? //廣義表節點
{
?? ?Type _type;?????????? //節點類型
?? ?GeneralListNode* _next;??? //節點的下一個
?? ?union????????????????? //當節點的類型不是值節點就是子表節點
?? ?{
?? ??? ?T _value;
?? ??? ?GeneralListNode* _SubLink;
?? ?};

?? ?GeneralListNode(Type type, char s)?? //當節點值節點時的構造函數
?? ??? ?:_type(type)
?? ??? ?, _value(s)
?? ??? ?, _next(NULL)
?? ?{}

?? ?GeneralListNode(Type type)?? //當節點為子表節點或頭結點時的構造函數
?? ??? ?:_type(type)
?? ??? ?, _next(NULL)
?? ??? ?, _SubLink(NULL)
?? ?{}
};

template<class T>
class GeneralList
{
public:
?? ?GeneralList()?????? //構造函數
?? ??? ?:_head(NULL)
?? ?{}

?? ?GeneralList(char* s)??? //構造函數
?? ?{
?? ??? ?_head = _CreateList(s);
?? ?}

?? ?~GeneralList()?? //析構函數
?? ?{
?? ??? ?_Destory(_head);
?? ?}

?? ?GeneralList(const GeneralList<T>& t)?? //拷貝構造函數
?? ?{
?? ??? ?_head = _Copy(t._head);
?? ?}

?? ?GeneralList& operator=(GeneralList<T> t)??? //賦值運算符的重載
?? ?{
?? ??? ?swap(t._head, _head);
?? ??? ?return *this;
?? ?}

?? ?void Print()?? //打印函數
?? ?{
?? ??? ?_Print(_head);
?? ??? ?cout << endl;
?? ?}

?? ?size_t Size()?? //求廣義表節點的個數
?? ?{
?? ??? ?return _Size(_head);
?? ??? ?cout << endl;
?? ?}

?? ?size_t Depth()?? //求廣義表的深度
?? ?{
?? ??? ?return _Depth(_head);
?? ?}
protected:
?? ?size_t _Depth(GeneralListNode<T>* head)
?? ?{
?? ??? ?GeneralListNode<T>* cur = head;
?? ??? ?size_t Maxdepth = 1;
?? ??? ?while (cur)
?? ??? ?{
?? ??? ??? ?if (cur->_type == SUB)
?? ??? ??? ?{
?? ??? ??? ??? ?size_t depth = _Depth(cur->_SubLink);
?? ??? ??? ??? ?if (depth+1>Maxdepth)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?Maxdepth = depth+1;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?cur = cur->_next;
?? ??? ?}
?? ??? ?return Maxdepth;
?? ?}

?? ?GeneralListNode<T>* _Copy(GeneralListNode<T>* head)
?? ?{
?? ??? ?assert(head);
?? ??? ?GeneralListNode<T>* Newhead = new GeneralListNode<T>(HEAD);
?? ??? ?GeneralListNode<T>* cur = head->_next;
?? ??? ?GeneralListNode<T>* newcur = Newhead;
?? ??? ?while (cur)
?? ??? ?{
?? ??? ??? ?if (cur->_type == VALUE)
?? ??? ??? ?{
?? ??? ??? ??? ?newcur->_next = new GeneralListNode<T>(VALUE, cur->_value);
?? ??? ??? ??? ?newcur = newcur->_next;
?? ??? ??? ?}
?? ??? ??? ?if (cur->_type == SUB)
?? ??? ??? ?{
?? ??? ??? ??? ?newcur->_next = new GeneralListNode<T>(SUB);
?? ??? ??? ??? ?newcur = newcur->_next;
?? ??? ??? ??? ?newcur->_SubLink = _Copy(cur->_SubLink);
?? ??? ??? ?}
?? ??? ??? ?cur = cur->_next;
?? ??? ?}
?? ??? ?return Newhead;
?? ?}

?? ?int _Size(GeneralListNode<T>* head)
?? ?{
?? ??? ?GeneralListNode<T>* cur = head;
?? ??? ?size_t Count=0;
?? ??? ?while (cur)
?? ??? ?{
?? ??? ??? ?if (cur->_type==VALUE)
?? ??? ??? ?{
?? ??? ??? ??? ?Count++;
?? ??? ??? ?}
?? ??? ??? ?if (cur->_type == SUB)
?? ??? ??? ?{
?? ??? ??? ??? ?Count += _Size(cur->_SubLink);
?? ??? ??? ?}
?? ??? ??? ?cur = cur->_next;
?? ??? ?}
?? ??? ?return Count;
?? ?}

?? ?void _Print(GeneralListNode<T>* head)
?? ?{
?? ??? ?GeneralListNode<T>* cur = head;
?? ??? ?while (cur)
?? ??? ?{
?? ??? ??? ?if (cur->_type == HEAD)
?? ??? ??? ?{
?? ??? ??? ??? ?cout << '(';
?? ??? ??? ?}
?? ??? ??? ?else if (cur->_type == VALUE)
?? ??? ??? ?{
?? ??? ??? ??? ?cout << cur->_value << " ";
?? ??? ??? ??? ?if (cur->_next)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?cout << ',';
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else? //cur->_type==SUB
?? ??? ??? ?{
?? ??? ??? ??? ?_Print(cur->_SubLink);
?? ??? ??? ??? ?if (cur->_next)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?cout << ')';
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?cur = cur->_next;
?? ??? ?}
?? ??? ?cout << ')';
?? ?}

?? ?bool Isvalue(char ch)
?? ?{
?? ??? ?return (ch >= '0'&&ch <= '9') || (ch >= 'a'&&ch <= 'z') || (ch >= 'A'&&ch <= 'Z');
?? ?}

?? ?GeneralListNode<T>* _CreateList(char*& s)
?? ?{
?? ??? ?assert(*s == '(');
?? ??? ?GeneralListNode<T>* head = new GeneralListNode<T>(HEAD);
?? ??? ?++s;
?? ??? ?GeneralListNode<T>* cur = head;
?? ??? ?while (*s)
?? ??? ?{
?? ??? ??? ?if (*s == '(')
?? ??? ??? ?{
?? ??? ??? ??? ?GeneralListNode<T>* SubNode = new GeneralListNode<T>(SUB);
?? ??? ??? ??? ?cur->_next = SubNode;
?? ??? ??? ??? ?cur = cur->_next;

?? ??? ??? ??? ?SubNode->_SubLink = _CreateList(s);
?? ??? ??? ?}
?? ??? ??? ?else if (*s == ')')
?? ??? ??? ?{
?? ??? ??? ??? ?++s;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?else if ( Isvalue(*s))
?? ??? ??? ?{
?? ??? ??? ??? ?GeneralListNode<T>* ValueNode = new GeneralListNode<T>(VALUE, *s);
?? ??? ??? ??? ?cur->_next = ValueNode;
?? ??? ??? ??? ? cur = cur->_next;
?? ??? ??? ??? ?++s;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?++s;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return head;
?? ?}

?? ?void _Destory(GeneralListNode<T>* head)
?? ?{
?? ??? ?GeneralListNode<T>* cur = head;
?? ??? ?while (cur)
?? ??? ?{
?? ??? ??? ?GeneralListNode<T>* del = cur;
?? ??? ??? ?cur = cur->_next;
?? ??? ??? ?if (del->_type ==SUB)
?? ??? ??? ?{
?? ??? ??? ??? ?_Destory(del->_SubLink);
?? ??? ??? ?}
?? ??? ??? ?delete del;
?? ??? ?}
?? ?}
private:
?? ?GeneralListNode<T>* _head;
};

?

/

主函數：

#include"GeneralList.h"
void main()
{
?? ??? ?GeneralList<char> g1("()");
?? ??? ?GeneralList<char> g2("(a,b)");
?? ??? ?GeneralList<char> g3("(a,b,(c,d))");
?? ??? ?GeneralList<char> g4("(a,b,(c,d),(e,(f),h))");
?? ??? ?GeneralList<char> g5;
?? ??? ?g5 = g4;

?? ??? ?g4.Print();
?? ??? ?cout << g4.Size() << endl;
?? ??? ?cout << g4.Depth() << endl;
?? ??? ?g5.Print();
}