【代碼】C++實現(xiàn)廣義表及其測試用例

    廣義表是我第一次用遞歸接觸鏈式的數(shù)據(jù)結構，其結構如下：

為城東等地區(qū)用戶提供了全套網(wǎng)頁設計制作服務，及城東網(wǎng)站建設行業(yè)解決方案。主營業(yè)務為成都網(wǎng)站設計、成都網(wǎng)站制作、城東網(wǎng)站設計，以傳統(tǒng)方式定制建設網(wǎng)站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

    HEAD->VAL->VAL->LINK(->HEAD.....)->VAL->......

    在這里，我們的頭結點與link節(jié)點是不存儲數(shù)據(jù)的，由此我們便可以定義出節(jié)點的數(shù)據(jù)結構：

typedef int DataType;
enum NodeType//枚舉類型定義節(jié)點類型
{
	HEAD,
	VALUE,
	SUB,
};
struct GeneralizedNode
{
public:
	GeneralizedNode()
		:_next(NULL)
		, _link(NULL)
	{}
	NodeType _type;
	GeneralizedNode* _next;
	union//因為link與value是不可能同時存在的，故用共同體節(jié)省空間
	{
		GeneralizedNode* _link;
		DataType _value;
	};
};

    因為廣義表是鏈式的嵌套結構，所以我們必須用遞歸來進行遍歷，這里面遞歸的方式有很多種，可以循環(huán)套遞歸，也可以遞歸套遞歸，也可以遞歸套循環(huán)，根據(jù)我們不同的需求，可以吧這三種方法都運用在合適的地方，這里，我簡單的實現(xiàn)了，返回對象的層數(shù)，數(shù)據(jù)個數(shù)，以及一些常用的成員函數(shù)，其代碼如下：

class Generalized
{
public:
	Generalized()
		:_head(NULL)
	{}
	Generalized(const char *str)//構造函數(shù)是用字符串來體現(xiàn)廣義表如（1,2，（2,3））
	{                           //這樣可以更好的體現(xiàn)出廣義表的結構
		_head = _CreatList(str);
	}
	~Generalized()
	{
		_Destory(_head);
	}
	void Print()//控制臺打印廣義表，也是打印出字符串類型
	{
		_Print(_head);
	}
	Generalized(const Generalized &g)
	{
		_head = _Copy(g._head);
	}
	Generalized&operator = (Generalized g)
	{
		swap(_head, g._head);
		return *this;
	}
	size_t Depth()
	{
		return _Depth(_head);
	}
	size_t Size()
	{
		size_t size = 0;
		_Size(_head, size);
		return size;
	}
protected:
	size_t _Depth(GeneralizedNode* head)
	{
		size_t depth = 1;
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type == SUB)
			{
				size_t newdepth = _Depth(cur->_link) + 1;
				depth = depth < newdepth ? newdepth : depth;
			}
			cur = cur->_next;
		}
		return depth;
	}
	void _Size(GeneralizedNode* head, size_t &size)
	{
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type == VALUE)
				++size;
			else if (cur->_type == SUB)
				_Size(cur->_link, size);
			cur = cur->_next;
		}
	}
	GeneralizedNode* _Copy(GeneralizedNode *head)
	{
		GeneralizedNode* cur = head;
		GeneralizedNode* newHead = new GeneralizedNode;
		GeneralizedNode*tail = newHead;
		tail->_type = HEAD;
		while (cur)
		{
			if (cur->_type == SUB)
			{

				tail->_next = new GeneralizedNode;
				tail = tail->_next;
				tail->_type = SUB;
				tail->_link = _Copy(cur->_link);

			}
			else if (cur->_type == VALUE)
			{
				tail->_next = new GeneralizedNode;
				tail = tail->_next;
				tail->_type = VALUE;
				tail->_value = cur->_value;
			}
			cur = cur->_next;
		}
		return newHead;
	}
	void _Print(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << "(";
			}
			else if (cur->_type == VALUE)
			{
				cout << cur->_value;
				if (cur->_next!=NULL&&
					cur->_next->_type == VALUE)
					cout << ",";
			}
			else
				_Print(cur->_link);
			cur = cur->_next;
		}
		cout << ")";
	}
	GeneralizedNode* _CreatList(const char* &str)
	{

		assert('(' == *str);
		GeneralizedNode* head = new GeneralizedNode;
		GeneralizedNode* cur = head;
		head->_type = HEAD;

		while (*++str)
		{
			if (IsValue(str))
			{
				cur->_next = new GeneralizedNode;
				cur = cur->_next;
				cur->_type = VALUE;
				cur->_value = *str;
				str++;
			}
			else if (')' == *str)
			{
				return head;
			}
			else if ('(')
			{
				cur->_next = new GeneralizedNode;
				cur = cur->_next;
				cur->_type = SUB;
				cur->_link = _CreatList(str);
			}
			cur->_next = NULL;
			*str++;
		}
		return head;


	}
	bool IsValue(const char *str)//判斷表內存儲數(shù)據(jù)是否為所需數(shù)據(jù)類型
	{
		if (*str <= '9'&&
			*str >= '0')
			return true;
		return false;
	}
	void _Destory(GeneralizedNode*head)
	{
		GeneralizedNode*cur = head;
		if (cur->_value == SUB)
			_Destory(cur->_link);
		else if (cur->_next != NULL)
			_Destory(cur->_next);
		delete cur;
	}
protected:
	GeneralizedNode* _head;
};

    如有什么不足或疑問希望提出。

本文標題：【代碼】C++實現(xiàn)廣義表及其測試用例
文章路徑：http://m.jiaotiyi.com/article/jiopgi.html