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

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

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

<4> D = (a,b,(c,d),(e,(f),h))

<5> E = (((),()))

如下圖所示：

廣義表主要使用遞歸實(shí)現(xiàn)，表與表之間使用鏈?zhǔn)浇Y(jié)構(gòu)來存儲。下面就來看看代碼怎樣實(shí)現(xiàn)的：

#pragma once

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

//節(jié)點(diǎn)類型
enum Type
{
	HEAD,//頭節(jié)點(diǎn)
	VALUE,//數(shù)據(jù)項(xiàng)
	SUB,//子表的頭節(jié)點(diǎn)
};

//廣義表結(jié)構(gòu)
struct GeneralizedNode
{
public:
	GeneralizedNode()//無參構(gòu)造函數(shù)
		:_type(HEAD)
		, _next(NULL)
	{}

	GeneralizedNode(Type type, char ch = 0)
		:_type(type)
		,_next(NULL)
	{
		if (_type == VALUE)
		{
			_value = ch;//數(shù)據(jù)節(jié)點(diǎn)
		}
		if (_type == SUB)
		{
			_sublink = NULL;//子表節(jié)點(diǎn)
		}
	}

public:
	Type _type;//節(jié)點(diǎn)類型
	GeneralizedNode * _next;
	union
	{
		char _value;//數(shù)據(jù)
		GeneralizedNode * _sublink;//子表的頭指針
	};
};

//廣義表類
class Generalized
{
public:
	Generalized()//無參構(gòu)造函數(shù)
		:_head(new GeneralizedNode(HEAD))
	{}
	Generalized(const char* str)//構(gòu)造函數(shù)
		:_head(NULL)
	{
		_head = _CreateList(str);
	}

	Generalized(const Generalized & g)//拷貝構(gòu)造
	{
		_head = _CopyList(g._head);
	}

	Generalized& operator=(Generalized g)//賦值運(yùn)算符的重載
	{
		swap(_head, g._head);//現(xiàn)代寫法
		return *this;
	}

	~Generalized()//析構(gòu)函數(shù)
	{
		_Delete(_head);//遞歸析構(gòu)
	}

public:
	void print()//打印
	{
		_Print(_head);
	}

	size_t size()//元素個數(shù)
	{
		size_t ret=_Size(_head);
		return ret;
	}

	size_t depth()//廣義表的深度
	{
		size_t ret=_Depth(_head);
		return ret;
	}

public:
	GeneralizedNode * _CreateList(const char* &str)//創(chuàng)建廣義表
	{
		assert(str&&*str == '(');
		//判斷傳入的廣義表是否正確
		str++;//跳過'('

		GeneralizedNode* head = new GeneralizedNode();//創(chuàng)建頭節(jié)點(diǎn)
		GeneralizedNode* cur = head;
		while (*str)
		{
			if (_IsVaild(*str))
			{
				cur->_next = new GeneralizedNode(VALUE, *str);//創(chuàng)建數(shù)據(jù)節(jié)點(diǎn)
				cur = cur->_next;//節(jié)點(diǎn)后移
				str++;//指針后移
			}
			else if (*str == '(')//子表
			{
				GeneralizedNode* SubNode = new GeneralizedNode(SUB);//創(chuàng)建字表的頭節(jié)點(diǎn)
				SubNode->_sublink = _CreateList(str);//遞歸調(diào)用_CreateList函數(shù)
				cur->_next = SubNode;
				cur = cur->_next;
			}
			else if (*str == ')')//表的結(jié)束
			{
				str++;//跳過')'
				return head;//返回頭節(jié)點(diǎn)
			}
			else//其他字符（' '或者','）
			{
				str++;
			}
		}
		assert(false);//強(qiáng)制判斷程序是否出錯
		return head;
	}

	bool _IsVaild(const char ch)//判斷輸入是否合理
	{
		if ((ch >= '0'&&ch <= '9')
			|| (ch >= 'a'&&ch <= 'z')
			|| (ch >= 'A'&&ch <= 'Z'))
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	GeneralizedNode* _CopyList(GeneralizedNode* head)//復(fù)制
	{
		GeneralizedNode* cur = head;
		//創(chuàng)建新的頭節(jié)點(diǎn)
		GeneralizedNode* newHead = new GeneralizedNode();
		GeneralizedNode* tmp = newHead;
		while (cur)
		{
			if (cur->_type == VALUE)//數(shù)據(jù)節(jié)點(diǎn)
			{
				tmp->_next = new GeneralizedNode(VALUE, cur->_value);
				tmp = tmp->_next;
			}
			else if (cur->_type == SUB)//子表節(jié)點(diǎn)
			{
				GeneralizedNode* SubNode = new GeneralizedNode(SUB);
				tmp->_next = SubNode;
				SubNode->_sublink = _CopyList(cur->_sublink);//遞歸調(diào)用
				
				tmp = tmp->_next;
			}
			cur = cur->_next;
		}
		return newHead;
	}

	void _Delete(GeneralizedNode * head)
	{
		GeneralizedNode* cur = head;
		while (cur)
		{
			GeneralizedNode* del = cur;
			if (cur->_type == SUB)//子表節(jié)點(diǎn)時遞歸析構(gòu)
			{
				_Delete(cur->_sublink);
			}
			cur = cur->_next;
			delete del;
		}
	}

	void _Print(GeneralizedNode* head)//打印
	{
		GeneralizedNode* cur = head;
		if (cur == NULL)
		{
			return;
		}
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << "(";
			}
			else if (cur->_type == VALUE&&cur->_next)
			{
				cout << cur->_value<<",";
			}
			else if (cur->_type == VALUE&&cur->_next == NULL)
			{
				cout << cur->_value;
			}
			else if (cur->_type == SUB)
			{
				_Print(cur->_sublink);
				if (cur->_next)
				{
					cout << ",";
				}
			}
			cur = cur->_next;
		}
		if (cur == NULL)
		{
			cout << ")";
			return;
		}
	}

	size_t _Size(GeneralizedNode* head)//元素的個數(shù)
	{
		GeneralizedNode* cur = head;
		size_t count = 0;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				count++;
			}
			else if (cur->_type == SUB)
			{
				count += _Size(cur->_sublink);
			}
			cur = cur->_next;
		}
		return count;
	}

	size_t _Depth(GeneralizedNode* head)//廣義表的深度
	{
		GeneralizedNode* cur = head;
		size_t depth = 1;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				depth++;
			}
			else if (cur->_type == SUB)
			{
				size_t newdepth = _Depth(cur->_sublink);
				if (newdepth++ > depth)//當(dāng)后面子表的深度比現(xiàn)在的深時，更新深度
				{
					depth = newdepth++;
				}
			}
			cur = cur->_next;
		}
		return depth;
	}

private:
	GeneralizedNode * _head;
};

測試代碼和結(jié)果如下：

void Test()
{
	Generalized g1("(a,b(c,d),(e,(f),h))");
	Generalized g2;
	g1.print();
	cout << endl;
	cout << "g1.size()="<< g1.size() << endl << endl;
	cout << "g1.depth()=" << g1.depth() << endl << endl;

	g2 = g1;
	g2.print();
	cout << endl;
	cout << "g2.size()=" << g1.size() << endl << endl;
	cout << "g2.depth()=" << g1.depth() << endl << endl;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享題目：c++實(shí)現(xiàn)廣義表-創(chuàng)新互聯(lián)
文章分享：http://aaarwkj.com/article32/ppdsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、定制網(wǎng)站、商城網(wǎng)站、ChatGPT、靜態(tài)網(wǎng)站、域名注冊

廣告

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