遞歸實現廣義表

    廣義表是非線性的結構，是線性表的一種擴展，是有n個元素組成有限序列。由于在表的描述中可以嵌套表，允許表中有表，所以可以通過遞歸實現廣義表。

具體實現如下：

頭文件

#pragma once
//實現廣義表的結構
enum Type//枚舉類型
{
	HEAD,
	VALUE,
	SUB,
};

struct GeneralizedNode//廣義表的結點
{
	Type _type;//類型
	GeneralizedNode* _next;//值相同層的下一個節點
	union//共用體/聯合
	{
		int _value;//值節點
		GeneralizedNode* _SubLink;//指向字表的指針
	};
	GeneralizedNode();
	GeneralizedNode(Type type, int value); //全缺省構造函數
};

class Generalized
{
public:
	Generalized();
	Generalized(const char* str);//構造
	Generalized(const Generalized& g);//拷貝構造
	Generalized& operator=(const Generalized& g);
	~Generalized();
	void Print();
	size_t Size();
	size_t Depth();
protected:
	GeneralizedNode* _CreatList(const char*& str);
	GeneralizedNode* _Copy(GeneralizedNode* head);
	bool _isValue(char ch);//判斷是否為字母或數字
	void _Distory(GeneralizedNode* head);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
protected:
	GeneralizedNode* _head;
};

各函數的具體實現

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

GeneralizedNode::GeneralizedNode()
:_next(NULL)
{}
GeneralizedNode::GeneralizedNode(Type type, int value)
: _type(type)
, _next(NULL)
{
	if (_type == VALUE)
	{
		_value = value;
	}
	if (_type == SUB)
	{
		_SubLink = NULL;
	}
}
Generalized::Generalized()
:_head(NULL)
{}
Generalized::Generalized(const char* str)//構造函數
: _head(NULL)
{
	_head = _CreatList(str);
}
GeneralizedNode* Generalized::_CreatList(const char*& str)
{//廣義表：(a, (b, c))
	assert('(' == *str); 
	str++;
	GeneralizedNode* head = new GeneralizedNode(HEAD, 0);//建立表的頭結點
	GeneralizedNode* cur = head;
	while (str)
	{
		if (_isValue(*str))//*str為字母或數字
		{
			cur->_next = new GeneralizedNode(VALUE, *str);//建立value結點
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')//如果為（，則出現字表，進行遞歸調用
		{
			GeneralizedNode* subNode = new GeneralizedNode(SUB, 0);//建立子表結點
			cur->_next = subNode;
			cur = cur->_next;
			subNode->_SubLink = _CreatList(str);//_SubLink指向子表構造子表
		}
		else if (*str == ')')//表示表的結束（包括子表）,返回表的頭結點
		{
			str++;
			return head;
		}
		else
		{
			str++;
		}
	}
	assert(false);
	return head;
}
bool Generalized::_isValue(char ch)//判斷是否為字母或數字
{
	if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')
	{
		return true;
	}
	return false;
}
Generalized::Generalized(const Generalized& g)//拷貝構造函數
{
	_head = _Copy(g._head);
}
GeneralizedNode* Generalized::_Copy(GeneralizedNode* head)
{
	GeneralizedNode* newhead = new GeneralizedNode(HEAD, 0);
	GeneralizedNode* cur = head;
	GeneralizedNode* newcur = newhead;
	while (cur)
	{
		if (cur->_type == VALUE)//cur._type為VALUE或SUB時建立結點，newcur才存在指向下一個結點
		{
			newcur->_next = new GeneralizedNode(VALUE, cur->_value);
			newcur = newcur->_next;
		}
		if (cur->_type == SUB)
		{
		    newcur->_next= new GeneralizedNode(SUB, 0);
			newcur = newcur->_next;
			newcur->_SubLink = _Copy(cur->_SubLink);//遞歸調用_Copy進行復制
		}
		cur = cur->_next;
	}
	return newhead;
}
Generalized& Generalized::operator=(const Generalized& g)//傳統寫法
{
	if (this != &g)
	{
		GeneralizedNode* tmp = _Copy(g._head);
		_Distory(_head);
		_head = tmp;
	}
	return *this;
}
Generalized::~Generalized()
{
	_Distory(_head);
}
void Generalized::_Distory(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		GeneralizedNode* del = cur;
		if (cur->_type == SUB)
		{
			_Distory(cur->_SubLink);//釋放cur結點的字表
		}
		cur = cur->_next;
		delete del;
	}
}
void Generalized::Print()
{
	_Print(_head);
	cout << endl;
}
void Generalized::_Print(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	while (cur)
	{
		if (cur->_type == HEAD)
		{
			cout << "(";
		}
		if (cur->_type == VALUE)
		{
			cout << (char)cur->_value;//強轉為char類型
			if (cur->_next)//如果cur->_next不為空打印“,”
				cout << ",";
		}
		if (cur->_type == SUB)
		{
			_Print(cur->_SubLink);
			if (cur->_next)
				cout << ",";
		}
		cur = cur->_next;
	}
	cout << ")";
}
size_t Generalized::Size()
{
	return _Size(_head);
}
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 += _Size(cur->_SubLink);
		}
		cur = cur->_next;
	}
	return count;
}
size_t Generalized::Depth()
{
	return _Depth(_head);
}
size_t Generalized::_Depth(GeneralizedNode* head)
{
	GeneralizedNode* cur = head;
	size_t depth = 1;
	while (cur)
	{
		if (cur->_type == SUB)
		{
			size_t cdepth = _Depth(cur->_SubLink);
			if (cdepth + 1 > depth)//比較子表深度，保存較大的
			{
				depth = cdepth + 1;
			}
		}
		cur = cur->_next;
	}
	return depth;
}

測試用例如下：

void Test()
{
	//Generalized g1("(a)");
	//Generalized g2("(a,b)");
	Generalized g3("(a,(a,b))");
	Generalized g4("(a,(a,(b),c),d)");
	Generalized g5 = g4;
	g5 = g3;
	//g1.Print();
	//g2.Print();
	g3.Print();
	g4.Print();
	g5.Print();
	cout << "g3.Size():" << g3.Size() << endl;
	cout << "g4.Size():" << g4.Size() << endl;
	cout << "g3.Depth():" << g3.Depth() << endl;
	cout << "g4.Depth():" << g4.Depth() << endl;
}