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

創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設計、成都做網(wǎng)站和達州主機托管的網(wǎng)絡公司，有著豐富的建站經驗和案例。

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

頭文件

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

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

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);//判斷是否為字母或數(shù)字
	void _Distory(GeneralizedNode* head);
	void _Print(GeneralizedNode* head);
	size_t _Size(GeneralizedNode* head);
	size_t _Depth(GeneralizedNode* head);
protected:
	GeneralizedNode* _head;
};

各函數(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)//構造函數(shù)
: _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為字母或數(shù)字
		{
			cur->_next = new GeneralizedNode(VALUE, *str);//建立value結點
			cur = cur->_next;
			str++;
		}
		else if (*str == '(')//如果為（，則出現(xiàn)字表，進行遞歸調用
		{
			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)//判斷是否為字母或數(shù)字
{
	if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')
	{
		return true;
	}
	return false;
}
Generalized::Generalized(const Generalized& g)//拷貝構造函數(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時建立結點，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)//傳統(tǒng)寫法
{
	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;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

網(wǎng)站欄目：遞歸實現(xiàn)廣義表-創(chuàng)新互聯(lián)
標題URL：http://chinadenli.net/article38/gsjpp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、手機網(wǎng)站建設、做網(wǎng)站、網(wǎng)站建設、營銷型網(wǎng)站建設、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)