Generalized------廣義表

廣義表是非線性結(jié)構(gòu)，是線性表的一種擴(kuò)展，是有N個(gè)元素組成的有限序列。

廣義表的定義是遞歸的，因?yàn)樵诒淼拿枋鲋杏值玫搅吮?，允許表中有表。

<1>A=（）；

<2>B=（a, b）;

<3>C=（a, b,（c, d））;

<4>D=（a, b,（c, d），（e, （f）, h））

<5>E = （（（），（）））

那么廣義表如何實(shí)現(xiàn)呢？

我們使用遞歸來實(shí)現(xiàn)它~~~~

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

enum Type
{
	HEAD,
	VALUE,
	SUB,
};

struct GeneralizedNode
{
	Type _type;                     //結(jié)點(diǎn)類型
	GeneralizedNode* _next;
	union
	{
		char _value;                //若為值類型結(jié)點(diǎn)，則存儲(chǔ)值
		GeneralizedNode* _sublink;  
	};

	GeneralizedNode(Type type = HEAD,char value=0)
		:_type(type)
		, _next(NULL)
	{
		if (_type == VALUE)
		{
			_value = value;
		}
		else if (_type == SUB)
		{
			_sublink = NULL;
		}
	}
};

class Generalized
{
public:
	Generalized()
	    :_head(NULL)
	{}

	Generalized(const char* str)
		:_head(NULL)
	{
		_head = _CreateLized(str);   
	}

	Generalized(const Generalized& g)
	{
		_head = _Copy(g._head);
	}

	Generalized& operator=(const Generalized& g)
	{
		if (_head != g._head)
		{
			GeneralizedNode* cur = _head;
			_Destory(_head);
			_head = _Copy(g._head);
			return *this;
		}
	}

	~Generalized()
	{
		_Destory(_head);
	}
public:
	void Print()
	{
		_Print(_head);
		cout << endl;
	}
	size_t Size()
	{
		size_t count = _Size(_head);
		return count;
	}

	size_t Depth()
	{
		size_t dep = _Depth(_head);
		return dep;
	}

protected:
	//創(chuàng)建表
	GeneralizedNode* _CreateLized(const char*& str)//傳參用引用是為了防止str在退出一層
	{                                              //遞歸時(shí)發(fā)生回退
		assert(str&&*str == '(');     //若當(dāng)前str是不為‘（’，則傳參錯(cuò)誤
		str++;                       

		GeneralizedNode* head = new GeneralizedNode(HEAD);
		GeneralizedNode* cur = head;
		while (*str != '\0')
		{
			if (_Isvalue(*str))
			{
				GeneralizedNode* tmp = new GeneralizedNode(VALUE, *str);
				cur->_next = tmp;
				cur = cur->_next;
				str++;
				continue;
			}
			else if (*str == '(')   //遇到子表
			{
				GeneralizedNode* sub = new GeneralizedNode(SUB);
				cur->_next = sub;
				cur = cur->_next;
				sub->_sublink = _CreateLized(str);  //進(jìn)入遞歸創(chuàng)建子表
				continue;
			}
			else if (*str == ')')  //一個(gè)表的結(jié)束
			{
				str++;
				return head;
			}
			else
			{
				str++;
				continue;
			}
			assert(false);  //強(qiáng)制判斷程序是否出錯(cuò)
			return head;
		}
	}

	//判斷當(dāng)前值是否為有效值
	bool _Isvalue(const char c)
	{
		if ((c <= '9'&&c >= '0') || (c <= 'z'&&c >= 'a') || (c <= 'Z'&&c >= 'A'))
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//拷貝一個(gè)表
	GeneralizedNode* _Copy(GeneralizedNode* head)
	{
		GeneralizedNode* Head = new GeneralizedNode(HEAD);
		//_head = Head;
		GeneralizedNode* cur = head->_next;
		GeneralizedNode* tmp = Head;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				tmp->_next = new GeneralizedNode(VALUE, cur->_value);
				cur = cur->_next;
				tmp = tmp->_next;
			}
			else if (cur->_type == SUB)
			{
				tmp->_next = new GeneralizedNode(SUB);
				//cur = cur->_next;
				tmp = tmp->_next;
				tmp->_sublink = _Copy(cur->_sublink);  //進(jìn)入拷貝表的遞歸
				cur = cur->_next;
			}
		}
		return Head;
	}

	//打印表
	void _Print(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << "(" << " ";
				cur = cur->_next;
				continue;
			}
			else if ((cur->_type == VALUE) && (cur->_next != NULL))
			{
				cout << cur->_value << " " << ",";
				cur = cur->_next;
				continue;
			}
			else if ((cur->_type == VALUE) && (cur->_next == NULL))//遇到一個(gè)表的最后一個(gè)節(jié)點(diǎn)
			{
				cout << cur->_value << " ";
				cur = cur->_next;
				continue;
			}
			else if (cur->_type == SUB)
			{
				_Print(cur->_sublink);                //進(jìn)入打印表的遞歸
				cur = cur->_next;
				if (cur != NULL)      //說明此時(shí)的表并不是最外層的表，需要打印‘，’
				{
				   cout << ",";
				}	
				continue;
			}			
		}
		if (cur == NULL)
		{
			cout << ")";
			return;
		}
	}

	//銷毀表
	void _Destory(GeneralizedNode* head)
	{
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type  == SUB)
			{
				_Destory(cur->_sublink);  //進(jìn)入銷毀表的遞歸
			}
			GeneralizedNode* del = cur;
			cur = cur->_next;
			delete del;
		}
		return;
	}

	//求表的大小
	size_t _Size(GeneralizedNode* head)
	{
		size_t count = 0;
		GeneralizedNode* cur = head;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				count++;
				cur = cur->_next;
				continue;
			}
			if (cur->_type == SUB)
			{
				count += _Size(cur->_sublink); //進(jìn)入遞歸
				cur = cur->_next;
				continue;
			}
			cur = cur->_next;
		}
		return count;
	}

	//求表的深度
	size_t _Depth(GeneralizedNode* head)
	{
		assert(head);
		size_t dep = 1;
		size_t Dep = 0;
		GeneralizedNode* cur = head;
		while (cur)
		{	
			if (cur->_type == SUB)
			{
				dep += _DepthSUB(cur->_sublink); 
			}
			cur = cur->_next;
			if (Dep < dep)   //用Dep來保存最深的深度
			{
				Dep = dep;
				dep = 1;
			}
		}
		
		return Dep;
	}
	//求子表長度
	size_t _DepthSUB(GeneralizedNode* sub)
	{
		GeneralizedNode* cur = sub;
		size_t dep = 1;
		while (cur)
		{
			if (cur->_type == SUB)
			{
				dep = dep + _DepthSUB(cur->_sublink);
			}
			cur = cur->_next;
		}
		return dep;
	}

protected:
	GeneralizedNode* _head;
};

廣義表的函數(shù)都用了遞歸，所以會(huì)比較繞。小伙伴們好好看，不懂可以來交流啊。寫的不好多多指教~~~~