数据结构与算法|数据结构与算法之广义表算法|数据结构

数据结构与算法之广义表

- 前提条件
- 广义表的基本概念
- 广义表的存储结构
- - 存储结构类型定义
- 广义表的分解方式
- - 方式一：按表头和表尾分解
  - 方式二：按元素分解
- 广义表的基本操作
- - 求广义表深度
  - 在表尾添加元素
- 参考文献

【数据结构与算法|数据结构与算法之广义表】
前提条件

熟悉C语言与指针

熟悉数据结构与算法

广义表的基本概念

将线性表的元素定义进行扩展，每个元素也可以是一个表，得到一种“表中有表”的递归数据结构，称为广义表。

例如，在常用的操作系统中，文件系统(File System)的组织结构是一个典型的广义表应用。

在某个文件夹下,既可能存在文件,也可能存在文件夹。如下图是C:\Program Files\Wandoujia文件夹的情况。Wandoujia文件夹是一个广义表,从图左边的树形组织结构可以看出,其包含了3个子文件夹:App、CrashReports和 Update,它们也都是广义表。在图右边展开的Update文件夹包含了4个子文件夹和1个文件:1.1.0.3、Download 、Install、Offiline和 wandoujia_update.exe ,而Download文件夹继续包含了其他文件夹,形成了表中有表的结构。

文章图片

广义表(Generalized List)一般记作 L = ( α 1 , α 2 , . . . , α n ) L=(α_1,α_2,...,α_n) L=(α1?,α2?,...,αn?)

其中, α i α_i αi?既可以是不再细分的元素,也可以是广义表,分别称为广义表L的原子和子表。

表头(Head)和表尾(Tail):对于非空广义表,第一个元素 α 1 α_1 α1?构成了L的表头。表头可能是原子,也有可能是表。陈表头之外的元素序列 ( α 2 , . . . , α n ) (α_2,...,α_n) (α2?,...,αn?)，构成了L的表尾，表尾必定是一个广义表。

长度(Length):广义表的元素个数。空表的长度为0。

深度(Depth):广义表中括弧的最大嵌套层数。空表的深度为1,原子的深度为0.
下图是一组广义表示例。其中,L5共享了L1、L3和 L4,L6是一个无穷深度的列表 a , ( a , ( a , … ) ) ) a,(a, (a,…))) a,(a,(a,…)))。

文章图片

广义表的存储结构

由于广义表的每个元素既可以是原子,又可以是表,导致不能统一规定每个元素所需的存储空间。如果采用顺序存储结构,则无法在初始化时确定所需要的内存空间,因此,广义表通常采用链式存储结构,以便于进行存储空间的管理。
广义表的结点分为两种,分别称为原子结点和表结点。表结点用于表示一个广义表,含有值为LIST的标志域tag、指向表头的指针域hp和指向表尾的指针域tp。原子结点用于表示一个原子,含有值为ATOM的标志域tag和存放原子的值域atom,如图所示。
表结构

tag=LIST	hp	tp

原子结构

tag=ATOM	atom

对于广义表 L 5 = ( ( ) , ( a ) , ( b , ( c , ( d ) , e ) ) ) L5=((),(a),(b,(c,(d),e))) L5=((),(a),(b,(c,(d),e))),结构示意图如下。

文章图片
注：0为原子结点，1为表结点。

存储结构类型定义

typedef char AtomType; typedef enum { ATOM,LIST //ATOM值为0表示原子,LIST值为1表示表结点 }ElemTag; typedef struct GLNode{ ElemTag tag; //区分原子结点和表结点 union{ //原子结点共用存储空间 AtomType atom; //当tag==ATOM时，本项有意义,存放原子结点值 struct{ //当tag==LIST时，本项有意义 struct GLNode *hp; struct GLNode *tp; }ptr; //表结点的指针域，其中，ptr.hp指向表头; ptr.tp指向表尾 }un; }GLNode.*GList; //广义表

广义表的分解方式方式一：按表头和表尾分解
方式二：按元素分解

以 L = ( f , ( g ) , h ) 为例 L=(f,(g),h)为例 L=(f,(g),h)为例

文章图片
注：方式二比方式一的分解层数少。方式一每次只将问题规模分为1和n-1，而方式二则将问题规模划分成n个子问题，每个子问题的规模为1。

广义表的基本操作求广义表深度

基本思路:依据分解方式一，将广义表划分成表头和表尾。分别求出表头深度h1和表尾深度h2，然后作比较。
- (1)如果是空表或者原子，则直接求得深度1或0。
- (2)如果是非空表，则分别对表头和表尾递归求解。
- (3)广义表的深度是表头深度加1和表尾深度较大值。

int GListDepth(GList L) { //求广义表L的深度 if(NULL==L) return 1; if(ATOM==L->tag) return 0; h1=GListDepth(L->un.ptr.hp)+1; //表头深度加1 h2=GListDepth(L->un.ptr.tp); //表尾的深度与原表相同 return h1>=h2?h1:h2; }

在表尾添加元素

该操作可基于分解方式二确定广义表的最后一个元素位置，在此位置后添加新的表结点，并将参数p赋予其表头指针hp。

文章图片

Status Append(GList &L,GLNode *p){ //在广义表L的末尾添加p元素 GList tail = (GList)malloc(sizeof(GLNode)); if(NULL==tail) return OVERFLOW; tail->tag = LIST; tail->un.ptr.hp = p; tail->un.ptr.tp = NULL; if(NULL==L) L = tail; else{ //定位至最后一个结点 for(GLNode *pp=L; pp->un.ptr.tp!=NULL; pp=pp>un.ptr.tp); pp->un.ptr.tp=tail; } return OK; }

参考文献 [1] 严蔚敏，吴伟民. 数据结构（C语言版）. 北京：清华大学出版社，2020
[2] 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版）（第二版）. 北京：人民邮电出版社，2021
[3] 吴伟民，李小妹，刘添添，黄剑锋，苏庆，林志毅，李杨.数据结构. 北京：高等教育出版社，2017
[4] 王道论坛. 2022数据结构考研复习指导. 北京：电子工业出版社，2021