当前位置:   article > 正文

广义表的存储结构算法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.    广义表的结点设计

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

如图:

262a8f35cb485922ac394ee110e49cba.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域,我们使用链式的存储方法可以化简,而使用子表的方式则必须表达。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/675131
推荐阅读
相关标签
  

闽ICP备14008679号