遞歸實(shí)現(xiàn)廣義表

    廣義表是非線性的結(jié)構(gòu)，是線性表的一種擴(kuò)展，是有n個(gè)元素組成有限序列。由于在表的描述中可以嵌套表，允許表中有表，所以可以通過(guò)遞歸實(shí)現(xiàn)廣義表。

具體實(shí)現(xiàn)如下：

頭文件

#pragma once
//實(shí)現(xiàn)廣義表的結(jié)構(gòu)
enum Type//枚舉類型
{
	HEAD,
	VALUE,
	SUB,
};

struct GeneralizedNode//廣義表的結(jié)點(diǎn)
{
	Type _type;//類型
	GeneralizedNode* _next;//值相同層的下一個(gè)節(jié)點(diǎn)
	union//共用體/聯(lián)合
	{
		int _value;//值節(jié)點(diǎn)
		GeneralizedNode* _SubLink;//指向字表的指針
	};
	GeneralizedNode();
	GeneralizedNode(Type type, int value); //全缺省構(gòu)造函數(shù)
};

class Generalized
{
public:
	Generalized();
	Generalized(const char* str);//構(gòu)造
	Generalized(const Generalized& g);//拷貝構(gòu)造
	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);//判斷是否為字母或數(shù)字
	void _Distory(GeneralizedNode* head);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
protected:
	GeneralizedNode* _head;
};

各函數(shù)的具體實(shí)現(xiàn)

#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)//構(gòu)造函數(shù)
: _head(NULL)
{
	_head = _CreatList(str);
}
GeneralizedNode* Generalized::_CreatList(const char*& str)
{//廣義表：(a, (b, c))
	assert('(' == *str); 
	str++;
	GeneralizedNode* head = new GeneralizedNode(HEAD, 0);//建立表的頭結(jié)點(diǎn)
	GeneralizedNode* cur = head;
	while (str)
	{
		if (_isValue(*str))//*str為字母或數(shù)字
		{
			cur->_next = new GeneralizedNode(VALUE, *str);//建立value結(jié)點(diǎn)
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')//如果為（，則出現(xiàn)字表，進(jìn)行遞歸調(diào)用
		{
			GeneralizedNode* subNode = new GeneralizedNode(SUB, 0);//建立子表結(jié)點(diǎn)
			cur->_next = subNode;
			cur = cur->_next;
			subNode->_SubLink = _CreatList(str);//_SubLink指向子表構(gòu)造子表
		}
		else if (*str == ')')//表示表的結(jié)束（包括子表）,返回表的頭結(jié)點(diǎn)
		{
			str++;
			return head;
		}
		else
		{
			str++;
		}
	}
	assert(false);
	return head;
}
bool Generalized::_isValue(char ch)//判斷是否為字母或數(shù)字
{
	if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')
	{
		return true;
	}
	return false;
}
Generalized::Generalized(const Generalized& g)//拷貝構(gòu)造函數(shù)
{
	_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時(shí)建立結(jié)點(diǎn)，newcur才存在指向下一個(gè)結(jié)點(diǎn)
		{
			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);//遞歸調(diào)用_Copy進(jìn)行復(fù)制
		}
		cur = cur->_next;
	}
	return newhead;
}
Generalized& Generalized::operator=(const Generalized& g)//傳統(tǒng)寫(xiě)法
{
	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結(jié)點(diǎn)的字表
		}
		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;//強(qiáng)轉(zhuǎn)為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;
}

測(cè)試用例如下：

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;
}