最近学习了广义表,我们知道广义表也是一种线性表,而顾名思义广义表就是不止一个表,下面来举个栗子:
A=( )
B=(1 , 2,3)
C=(1 ,2 ,3, ( a , b ,c) )
D=(1, 2, 3, (a,( b,c),d),4)
以上A,B,C,D都是广义表,只不过深度不一样,也就是括号的对数不一样,A是个特殊的广义表,即空表。B里面有三个元素,C里面有6个元素,包括一个子表(a,b,c),C也同理,只不过多了一层子表。由此可总结为一句话:表里有表
这样看可能不太直观,下面以广义表C为例来看一下它的结构图:
(图画得有点丑,不要吐槽我)
每当遇到一个前括号,就要创建一个子表,直到遇见收括号。
那么如何创建一个广义表呢,在创建节点结构体的时候,我们要考虑每个节点的类型,有可能是头结
点,也有可能是子表节点,也有可能是普通的值节点,所以在构造节点的时候就要定义一个三元体,由
于是表里有表,我们可以用递归的方法来解决广义表的问题,每个子表都可以递归为一个子问题,就可
以很轻松的解决掉这个问题了。
下面是具体实现的代码:
先构造一个三元结构体:
enum Type
{
HEAD,
VALUE,
SUB,
};
template<class T>
struct GeneralizedNode
{
Type _type;
GeneralizedNode<T>* _next;
union
{
char _value;
GeneralizedNode<T>* _sublink; //子表的头结点
};
public:
GeneralizedNode(Type type = HEAD,char value = '\0')
:_type(type)
,_next(NULL)
{
if (type == VALUE)
{
_value = value;
}
else if (type == SUB)
{
_sublink = NULL;
}
}
};
下面来构造一个广义表类
template<class T>
class GeneralizedList
{
public:
GeneralizedList()
:_head(new GeneralizedNode<T>(HEAD))
{}
GeneralizedList(const char* str)
{
_head=_CreateList(str);
}
GeneralizedList(const GeneralizedList& g) //拷贝构造
{
_head = Copy(g._head;)
}
size_t Size()
{
return size(_head);
}
size_t depth()
{
return Depth(_head);
}
void print()
{
Print(_head);
}
protected:
GeneralizedNode<T>* _CreateList(const char*& str)
{
assert(str && *str == '(');
++str;
GeneralizedNode<T>* Head = new GeneralizedNode<T>(HEAD,NULL);
GeneralizedNode<T>* cur = Head;
while (*str)
{
if (_IsValue(*str))
{
cur->_next = new GeneralizedNode<T>(VALUE,*str);
cur = cur->_next;
str++;
}
else if (*str == '(')
{
GeneralizedNode<T>* newNode= new GeneralizedNode<T>(SUB); //将一个子表结点加入到链表中
cur->_next = newNode;
cur = cur->_next;
cur->_sublink = _CreateList(str);
str++;//递归创建一个子表结点
}
else if (*str == ')') //表示一个表已经结束
{
str++;
return Head;
}
else
{
str++; //不需要处理的情况
}
}
assert(false);
return Head;
}
size_t Depth(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* cur = head;
size_t depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
size_t subdepth = Depth(cur->_sublink);
if (subdepth+1 > depth)
{
depth=subdepth;//保存较大的深度
}
}
cur = cur->_next;
}
return depth;
}
size_t size(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* cur = head;
size_t count = 0;
while (cur)
{
if (cur->_type != SUB)
{
count++;
}
else
{
count += size(cur->_sublink);
}
cur = cur->_next;
}
return count;
}
void Print(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* 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 << ',';
}
}
cur = cur->_next;
}
cout << ')';
}
bool _IsValue(char ch) //检查是否为合法值
{
if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z'))
{
return true;
}
return false;
}
protected:
GeneralizedNode<T>* _head;
};
下面给出测试代码:
#include"Generalized.h"
void Test()
{
char* ch = "(a,b,c,(1,2),c)";
GeneralizedList<char> gl1(ch);
gl1.print();
cout << endl;
cout << "广义表深度为:" << gl1.depth() << endl;
cout << "广义表大小为:" << gl1.Size() << endl;
}
int main()
{
Test();
getchar();
return 0;
}
运行结果:
以上就是C++实现广义表的方法啦,里面也许还存在着一些问题,希望大家能够指正出来,共同促进学习。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。