您的位置:首页 > 科技 > IT业 > C++广义表的介绍及创建方法-附C语言实现代码

C++广义表的介绍及创建方法-附C语言实现代码

2024/12/23 4:31:12 来源:https://blog.csdn.net/qq_45398836/article/details/142257220  浏览:    关键词:C++广义表的介绍及创建方法-附C语言实现代码

1. 简介

数组可以存储不允许再分割的数据元素,如字符’X’,数字11,当然它也可以存储数组,二维数组就是一个例子,你可以理解二维数组的每一行的元素是一列中的对应元素的组合。

广义表是一种线性表,或者说,广义表是一种线性表的推广,它属于多层次的线性表,广义表中可以存储不可以再分割的元素,同时也可以存储一张广义表(子表),因此适用情况相对灵活。

设ai为广义表的第i个元素,广义表是n(n≥0)个元素的一个序列,若n=0时则称为空表。广义表GL的一般表示与线性表相同,即:

GL=(a1,a2,…,ai,…,an)

其中n表示广义表的长度,即广义表中所含元素的个数,n≥0。如果ai是单个数据元素,则ai是广义表GL的原子;如果ai是一个广义表,则ai是广义表GL的子表。

一般来说,广义表具有如下重要的特性:

(1)广义表中的数据元素有相对次序

(2)广义表的长度定义为最外层包含元素个数

(3)广义表的深度定义为所含括弧的重数。其中原子的深度为0,空表的深度为1

(4)广义表可以共享;一个广义表可以为其他广义表共享;这种共享广义表称为再入表

(5)广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值

(6)任何一个非空广义表GL均可分解为表头head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。

2. 广义表的结点设计

我们以常规方法来看,广义表是一种不定规模的数据结构,很难为之分配具体的空间,因此创建的方法采用动态的链式方法,动态的创建空间。

如图:

23e23eb5b43541cb8d9b72ef96902c48.png

对于每一个结点而言由如上三大部分组成,其中Tag域为标志字段,其只有两个参数,0或者1(Tag域使用int类型,在某些情况下因为只需要简单判断也可以使用更短的类型,如bool);Atom/Node域的内容由tag标志决定,当Tag为0时表示该节点是原子结点(即存放原子数据),当Tag为1时表示该节点为指向下一个广义表的指针(即表结点),Link域存放与本元素同一层的下一个元素所在的结点地址,当本元素时所在层的最后一个元素时,Link域为NULL;

链式法设计:

#define AtomType int
typedef enum{ATOM,LIST}ElemTag; //ATOM = 0:原子;LIST = 1:子表 
/*结点设计*/
typedef struct GLNode{ElemTag tag; //枚举类型的标志域,只能取定义了的枚举值union{   //union联合体,下面两部分只能取其一;要么取AtomType;要么取结构体ptr,ptr包括两个指针hp,tp AtomType atom;struct{struct GLNode *hp,*tp;}ptr;}; 
}*GList; //定义广义表类型,GList为指针

下面是子表法设计:

/*线性表存储之扩展线性表 = 子表法*/ 
typedef struct GLNode{ElemTag tag;union{AtomType atom;struct GLNode *hp;    //对于列表,hp指向本列表内部第一个元素,而tp是指向本层次上的下一个元素 };                        struct GLNode *tp;
} *GList;

首先定义AtomType的数据类型,可以为基本的int型,也可以为一些其他的数据类型,包括简单的char或者是复杂一些的结构体,不过这里不建议创建过于复杂的结构体。

其次,关于tag域的建立,我们可以使用一个枚举建立,分别表示Atom/Node到底取何种值,而关于Atom/Node域,则可以建立一个union(共用体)来表示,共用体公用内存空间,只能取其一赋值,这也符合广义表的基本需求;而关于表达的Link域,我们使用链式的存储方法可以化简,而使用子表的方式则必须表达。

3. 广义表的创建

如图所示,广义表的每一个结点相互串联,有些结点存储原子数据,有些结点则存储另一份广义表数据,我们创建数据string ss = "(2,3,4, (1, (3, ( 7,8 ) ),2) )";其基本可以分成4层,每一个层中一个括号表示下一层,在数学表示中,我们也常用括号的级数表示广义表。

 e772e415fae64554ad91d6fca82f66cf.png

 因此,广义表的创建就需要进行连接,连接的方法是更具tag进行判断本结点中是Atom(原子)还是Node(结点),再根据其中的选择进行相对应的连接,可以由如下图可知。

732f2d0b373b452f9894061b3ffc073c.png

 对于代码的书写,我们首先需要对传入的字符串进行切割,将每一组括号”()”进行分割,每一组括号其中就表示的一份新的广义表,我们需要找到括号并且与这个括号相互匹配的括号数进行对应,找到并切割掉,以此分离出表头串,方便我们进行后续的操作。

void sever(string &str,string &hstr){//将非空串str分割成两部分,hstr是表头int n = str.size();int i = -1;int k = 0; //k记录尚未配对的“(” 数char ch;    do{ //搜索最外层第一个( ++i;ch = str[i];if(ch == '(') ++k;else if(ch == ')') --k;}while(i<n&&(ch != ','||k!=0));if(i<n){hstr =str.substr(0,i);str = str.substr(i+1,n-i-1);}else{hstr = str.substr(0,str.size());str.clear();}
}

我们通过分割以后可以通过上文介绍的方法进行指针的相互指引,核心就是要注意tag的判断,以及Atom/Node域是使用共用体创建的,要注意两者的空间不可以重叠,严格使用if(){}else{}的语法结构不要乱套。

void CreateGList(GList &L,string s){//采用头尾链表存储结构,创建Lif(s.compare(emp) == 0) L = NULL;else{L = (GList)malloc(sizeof(GLNode));if(!L) exit(0);if(s.size() == 1){ //单个元素,建立原子节点 L->tag = ATOM;L->atom = s[0];}else{ //表节点 ,表尾 L->tag = LIST;GList p,q;p = L; //p是指向当前子表(表尾节点)的指针 string sub;sub = s.substr(1,s.size()-2); //去掉外层括号 string hsub;do{ //重复建立n个子表 sever(sub,hsub); //sub中分理出表头串hsub ,同时,sub去除了hsubCreateGList(p->ptr.hp,hsub);q = p; //记录p,下面sub不为空,要再建立一个表尾节点,q记录上一层的p,用以连接q->ptr.tp = q if(!sub.empty()) {p = (GList)malloc(sizeof(GLNode));if(!p)exit(0);p -> tag = LIST;q -> ptr.tp = p;}}while(!sub.empty());q -> ptr.tp = NULL;}}
}

4. 广义表的深度

我们只需要根据表的情况进行一个递归调用即可判断,当然需要特判一下空表的情况。

int GListDepth(GList L) {if(!L) return 1; //空表1if(L->tag ==ATOM ) return 0;GList pp;//遍历同一层,递归下一层,取表尾,取表头,第一步先去一个表头 int max;for(max = 0, pp =L;pp!=NULL;pp = pp->ptr.tp){int dep = GListDepth(pp->ptr.hp) ;if(dep > max) max = dep; //这一步比较,是比较同一层的depth }return max+1;
}

 

 

 

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com