VC++2012编程演练数据结构广义表

广义表是一种非线性的数据结构，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。
线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，…，dn的有限序列，但不同的是，广义表中的di 则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。
　　l D=（）空表；其长度为零。www.zzzyk.com
　　l A=（a，（b，c））表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。
　　l B=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。
　　l C=（a，C）长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（…））））。
　　其中，A，B，C，D是广义表的名字。下面以广义表A为例，说明求表头、表尾的操作如下：
　　head（A）=a；表A的表头是：a
　　tail（A）=（（b，c））；表A的表尾是（（b，c））。广义表的表尾一定是一个表。
　（1）广义表的元素可以是子表，而子表还可以是子表…，由此，广义表是一个多层的结构。
　　（2）广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。周游广义表（3）广义表具有递归性，如广义表C。
　　由于广义表GL=（d1，d2，d3，…，dn）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点，一类是单个元素结点，一类是子表结点。从上节得知，任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点置需要两个域：标志域和值域。

我们创建一个工程

类的声明如下
[cpp]
#if !defined(AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_)
#define AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

//广义表的类定义
#include<string.h>
#include<stdio.h>
#include<math.h>
typedef enum{INTGR,CH,LST}ElemTag;
class GList
{public:
ElemTag utype;
GList *first;
union
{ int intinfo;
char charinfo;
GList *hlink;
};
//构造函数
GList(){}
//返回由elem指示的表元素的值
GList &Info(GList *&elem);
//返回表元素elem的元素值的数据类型
int nodetype(GList *elem) {return elem->utype;}
//将由elem指示的表元素的值修改为x
GList &setInfo(GList *&elem,GList &x);
//判断广义表是否相等的重载函数
int operator ==(GList &m);
//判断广义表是否相等
int equal(GList *s,GList *t);
//返回由ls指示的广义表的第一个元素的值
GList &Head(GList *&ls);
//返回广义表除第一个元素以外其它元素组成的表
GList *Tail();
//返回广义表的第一个元素
GList *First();
//返回由elem指示的表元素的直接后继元素
GList *Next(GList *elem);
//返回一个以x为头,由ls指示的广义表为尾的新表
GList *Addon(GList *ls,GList &x);
//由ls指示的广义表的复制
GList *Copy(GList *ls);
//求由ls指示的非递归表的深度
int depth(GList *&ls);
//判断广义表是否为空
bool GlistEmpty() {return first==NULL;}
//将广义表的头元素重置为x
void setHead(GList *&ls,GList &x);
//将elem2插到表中元素elem1后
void setNext(GList *elem1,GList *elem2);
//将x定义为由ls指示的广义表的尾
void setTail(GList *&ls,GList &x);
//插入元素x作为由ls指示的广义表的第一元素
GList *InsertGL(GList *&ls,GList &x);
//删除广义表中含数x或结点x的操作
GList *delvalue(GList *&ls,int x);
//删除广义表中含数x或结点x的操作
GList *delvalue(GList *&ls,char x);
//S是广义表的书写形式串,由S创建广义表GL
GList *CreateGList(char *&s);
//建立广义表时调用的过程
int sever(char *&str1,char *&hstr1);
//广义表的输出
void prtGlist(GList *h);
};

#endif // !defined(AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_)

类的实现如下
[cpp]
#include "stdafx.h"
#include "guangyi.h"

//广义表的类实现
//返回由elem指示的表元素的值
GList &GList::Info(GList *&elem)
{static GList *pitem=new GList;
pitem->utype=elem->utype;
if(elem->utype==LST)
pitem->hlink=elem->hlink;
if(elem->utype==INTGR)
pitem->intinfo=elem->intinfo;
if(elem->utype==CH&&elem->charinfo!=')')
pitem->charinfo=elem->charinfo;
pitem->first=elem->first;
return *pitem;
}
//将由elem指示的表元素的值修改为x
GList &GList::setInfo(GList *&elem,GList &x)
{elem->utype=x.utype;
if(x.utype==INTGR)
elem->intinfo=elem->intinfo;
if(x.utype==CH&&x.charinfo!=')')
elem->charinfo=x.charinfo;
return *elem;
}
//返回由ls指示的广义表的第一个元素的值
GList &GList::Head(GList *&ls)
{static GList *temp;
if(ls==NULL)
{cout<<"Illegal head operation.\n";exit(1);}
else {
temp=new GList;
ls=ls->first;
temp=ls;
if(ls->utype==INTGR)
    temp->intinfo=ls->intinfo;
if(ls->utype==CH)
    temp->charinfo=ls->charinfo;}
temp->first=ls;
return *temp;
}
//返回广义表除第一个元素以外其它元素组成的表
GList *GList::Tail()
{if(first==NULL)
{cout<<"Illegal head operation.\n";exit(1);}
return first->first;
}
//返回广义表的第一个元素
GList *GList::First()
{if(hlink==NULL) return NULL;
else return hlink;
}
//返回由elem指示的表元素的直接后继元素
GList *GList::Next(GList *elem)
{if(elem->first==NULL) return NULL;
else return elem->first;
}
//插入元素x作为由ls指示的广义表的第一元素
GList *GList::InsertGL(GList *&ls,GList &x)
{if(ls->hlink==NULL) ls->hlink=&x;
else {
   static GList *temp=new GList;
   temp->utype=x.utype;
   temp->first=ls->first;
   temp->intinfo=x.intinfo;

补充：软件开发 , Vc ,