廣義表(Lists，又稱列表)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，是線性表的一種推廣。即廣義表中放松對(duì)表元素的原子限制，容許它們具有其自身結(jié)構(gòu)。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、虛擬主機(jī)、營銷軟件、網(wǎng)站建設(shè)、閩侯網(wǎng)站維護(hù)、網(wǎng)站推廣。

思想：廣義表就類似下圖的結(jié)構(gòu)，他的大體（下圖第一行）相當(dāng)于一個(gè)帶頭結(jié)點(diǎn)的鏈表，

             代碼思想，首先要有一個(gè)頭結(jié)點(diǎn)為HEAD類型，每一個(gè)廣義表有且只有一個(gè)HEAD，而后每個(gè)節(jié)點(diǎn)如果有分支則把它定義為SUB類型，SUB便是它分支的一個(gè)新頭他有一個(gè)sublink指針指向他的第一個(gè)元素，如果沒有則是VALUE類型。

 

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

enum Type
{
	HEAD,
	VALUE,
	SUB
};
struct generalizelistNode
{
	generalizelistNode * _next;
	Type _type;
	union
	{
		char _value;
		generalizelistNode *sublink;
	};
	generalizelistNode(Type type=HEAD,char value=0)
		:_type(type),
		_value(value),
		_next(NULL)
	{
	}
};

class Generalizelist
{
protected:
	bool isvalue(char c)
	{
		if (c >= 'a'&&c<='z' || c>='A'&&c <= 'Z' || c>='0'&&c <= '9')
		{
			return true;
		}
		else
		{
			return false;
		}
	}
public:
	Generalizelist(char *&str)
	{
		_head = generallist(str);
	}
	~Generalizelist()
	{
		Empty(_head);
	}
	void Print()
	{
		_Print(_head);
	}
	Generalizelist& operator=(Generalizelist g)
	{
		swap(_head, g._head);
	}
	Generalizelist(Generalizelist &g)
	{
		_head = copy(g._head);
	}
	int Size()
	{
		return _Size(_head);
	}
	int Depth()
	{
		return _Depth(_head);
	}
protected:
	generalizelistNode* generallist(char *&str)
	{
		assert(*str == '(');
		generalizelistNode *head = new generalizelistNode(HEAD);
		generalizelistNode *cur = head;
		str++;
		while (*str)
		{
			if (isvalue(*str))
			{
				generalizelistNode *Node = new generalizelistNode(VALUE,*str);
				cur->_next = Node;
				cur = Node;
				str++;
			}
			else if (*str == '(')
			{
				generalizelistNode *sub = new generalizelistNode(SUB);
				cur->_next = sub;
				cur = sub;
				sub->sublink = generallist(str);
			}
			else if (*str==')')
			{
				++str;
				return head;
			}
			else
			{
				str++;
			}
		}
	}

	void _Print(generalizelistNode *head)
	{
		generalizelistNode *cur = head;
		while (cur)
		{
			if (cur->_type == HEAD)
			{
				cout << '(';
			}
			else if (cur->_type == VALUE)
			{
				cout << cur->_value;
				if (cur->_next)
				{
					cout << ",";
				}
			}
			else
			{
				_Print(cur->sublink);
			}
			cur = cur->_next;
		}
		cout << ")";
	}
	generalizelistNode * copy(generalizelistNode *&_cur)
	{	
		generalizelistNode *cur = _cur;
		generalizelistNode *newhead = new generalizelistNode(HEAD);
		generalizelistNode *tmp = newhead;
		cur = cur->_next;
		while (cur)
		{
			if (cur->_type == VALUE)
			{
				generalizelistNode *node = new generalizelistNode(VALUE, cur->_value);
				tmp->_next = node;
				tmp = node;
				cur = cur->_next;
			}
			else
			{
				generalizelistNode *node = new generalizelistNode(SUB);
				tmp->_next = node;
				tmp = node;
				tmp->sublink = copy(cur->sublink);
				cur = cur->_next;
			}
		}
		return newhead;
	}
	void Empty(generalizelistNode *&head)
	{
		generalizelistNode *tmp = head;
		head = head->_next;
		delete tmp;
		while (head)
		{
			if (head->_type == VALUE)
			{
				generalizelistNode *tmp = head;
				head = head->_next;
				delete tmp;
			}
			else if (head->_type == SUB)
			{
				generalizelistNode *tmp = head;
				Empty(tmp->sublink);
				head = head->_next;
			}
		}
	}
	int _Size(generalizelistNode *&cur)
	{
		int count = 0;
		generalizelistNode *tmp = cur;
		while (tmp)
		{
			if (tmp->_type == VALUE)
			{
				count++;
				tmp = tmp->_next;
			}
			else if (tmp->_type == SUB)
			{
				count += _Size(tmp->sublink);
				tmp = tmp->_next;
			}
			else
			{
				tmp = tmp->_next;
			}
			
		}
		return count;
	}
	int _Depth(generalizelistNode *&cur)
	{
		generalizelistNode *tmp = cur;
		int depth = 1;
		while (tmp)
		{
			int sub_depth=1;
			if (tmp->_type == SUB)
			{
				sub_depth = _Depth(tmp->sublink);
				tmp = tmp->_next;
				if (sub_depth + 1 > depth)
				{
					depth += sub_depth;
				}
			}
			else
			{
				tmp = tmp->_next;
			}
		}
		return depth;
	}
private:
	generalizelistNode *_head;
};



void Test()
{
	char *str1 = "(a,b,(c,d),e,f)";
	Generalizelist T1(str1);
	T1.Print();
	Generalizelist T2(T1);
	cout <<endl;
	T2.Print();
	cout << endl;
	Generalizelist T3 = T2;
	T3.Print();
	cout << endl;
	cout << T3.Size() << endl;
	cout << T3.Depth() << endl;
}
#include"GeneralizeList.h"


int main()
{
	Test();
	return 0;
}

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

文章標(biāo)題：數(shù)據(jù)結(jié)構(gòu)--廣義表-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://www.rwnh.cn/article26/csiojg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、手機(jī)網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站收錄、營銷型網(wǎng)站建設(shè)、域名注冊

廣告

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