【数据结构】广义表

一、问题概述

广义表是非线性的数据结构，是由若干个元素组合而成的，广义表中可以有子表，类似这样的：

我们以C=(a,b,(c,d))为例，将它定义为这样的数据结构：

我们会给定字符串的形式，如：char * str = "(a,d))"; 然后将它转化为如上的数据结构。

二、解决办法

（1）将符号'('看作是头节点，然后将是数值的部分链入当前位置的下一个位置；

（2）当遇到SUB时，就链入它的_sublink（连接子表的指针），此时可用递归（子表相当于是表的子问题）；

（3）直到str为空时，广义表的数据结构创建完成。

三、实现代码

//GeneralizedList.h

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

enum Type
{
	HEAD,VALUE,SUB,};

struct GeneralizeListNode
{
	Type _type;
	GeneralizeListNode* _next;

	union
	{
		char _value;
		GeneralizeListNode* _sublink;
	};

	GeneralizeListNode(Type type,char value = 0)
		:_next(NULL),_type(type),_value(value)
	{
		if(type == VALUE)
		{
			_value = value;
		}
		if(type == SUB)
		{
			_sublink = NULL;
		}
	}
};

class GeneralizeList
{
	typedef GeneralizeListNode Node;
public:
	GeneralizeList()
		:_head(NULL)
	{}
	//构造函数
	GeneralizeList(const char* str)
	{
		_head = Create(str);
	}
	//拷贝构造函数
	GeneralizeList(const GeneralizeList& g)
	{
		_head = _Copy(g._head);
	}
	//赋值运算符重载（1）
	//GeneralizeList& operator=(const GeneralizeList& g)
	//{
	//	if(this != &g)
	//	{
	//		Node* tmp = _Copy(g._head);
	//		delete _head;
	//		_head = tmp;
	//	}
	//	return *this;
	//}
	//赋值运算符重载（2）
	GeneralizeList& operator=(const GeneralizeList& g)
	{
		if(_head != g._head)
		{
			GeneralizeList tmp(g);
			swap(_head,tmp._head);
		}
		return *this;
	}

	~GeneralizeList()
	{
		if(_head)
		{
			_Destroy(_head);
			_head = NULL;
		}
	}

	void Print()
	{
		_Print(_head);
		cout<<endl;
	}

public:
	Node* Create(const char*& str)            //创建表
	{
		assert(*str == '(');
		Node* head = new Node(HEAD);
		++str;
		Node* tail = head;
		while(*str)
		{
			if((*str >= '0' && *str <= '9')
				||(*str >= 'a' && *str <= 'z')
				||(*str >= 'A' && *str <= 'Z'))
			{
				tail->_next = new Node(VALUE,*str);
				tail = tail->_next;
				++str;
			}
			else if(*str == '(')
			{
				tail->_next = new Node(SUB);
				tail = tail->_next;
				tail->_sublink = Create(str);
				++str;
			}
			else if(*str == ')')
			{
				++str;
				return head;
			}
			else
			{
				++str;
			}
		}
		return head;
	}

	void _Print(Node* head)
	{
		assert(head);
		Node* cur = head;
		while(cur)
		{
			if(cur->_type == HEAD)
			{
				cout<<"(";
			}
			else if(cur->_type == VALUE)
			{
				cout<<cur->_value;
				if(cur->_next != NULL)
				{
					cout<<",";
				}
			}
			else if(cur->_type == SUB)
			{
				_Print(cur->_sublink);
				if(cur->_next != NULL)
				{
					cout<<",";
				}
			}
			else
			{
				assert(false);
			}
			cur = cur->_next;
		}
		cout<<")";
	}

	Node* _Copy(Node* head)
	{
		Node* cur = head;
		Node* newHead = new Node(HEAD);
		Node* newTail = newHead;
		while(cur)
		{
			if(cur->_type == HEAD)
			{
				cur = cur->_next;
			}
			else if(cur->_type == VALUE)
			{
				newTail->_next = new Node(VALUE,cur->_value);
				newTail = newTail->_next;
				cur = cur->_next;
			}
			else if(cur->_type == SUB)
			{
				newTail->_next = new Node(SUB);
				newTail = newTail->_next;
				newTail->_sublink = _Copy(cur->_sublink);
				cur = cur->_next;
			}
			else
			{
				assert(false);
			}
		}
		return newHead;
	}

	void _Destroy(Node* head)       //销毁表
	{
		Node* cur = head;
		while(cur)
		{
			if(cur->_type == HEAD || cur->_type == VALUE)
			{
				Node* del = cur;
				cur = cur->_next;
				delete del;
			}
			else if(cur->_type == SUB)
			{
				Node* del = cur;
				cur = cur->_next;
				_Destroy(del->_sublink);
				delete del;
			}
			else
			{
				assert(false);
			}
		}
	}

	size_t Size()
	{
		return _Size(_head);
	}

	size_t _Size(Node* head)              //元素个数
	{
		assert(head);
		size_t count = 0;
		Node* cur = head;
		while(cur)
		{
			if(cur->_type == VALUE)
			{
				++count;
			}
			else if(cur->_type == SUB)
			{
				count += _Size(cur->_sublink);
			}
			cur = cur->_next;
		}
		return count;
	}

	size_t Depth()
	{
		return _Depth(_head);
	}

	size_t _Depth(Node* head)        //表的深度
	{
		Node* cur = head;
		size_t MaxDepth = 1;
		while(cur)
		{
			if(cur->_type == SUB)
			{
				size_t Depth = _Depth(cur->_sublink);
				if(Depth+1 > MaxDepth)
				{
					MaxDepth = Depth+1;
				}
			}
			cur = cur->_next;
		}
		return MaxDepth;
	}
protected:
	Node* _head;
};


void FunTest()
{
	char* str = "(a,d),(e,(f),g))";
	GeneralizeList g1(str);
	g1.Print();
	GeneralizeList g2(g1);
	g2.Print();
	GeneralizeList g3;
	g3 = g1;
	g3.Print();
	cout<<g3.Size()<<endl;
	cout<<g3.Depth()<<endl;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"GeneralizedList.h"
int main()
{
	FunTest();
    return 0;
}

四、运行结果

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!