数据结构广义表

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数据结构广义表介绍广义表是一种扩展了线性表的数据结构，可以存储不仅仅是数据元素，还可以存储子表，从而形成多级结构。

在广义表中，元素可以是基本类型（如整数、字符等），也可以是广义表。

广义表由一组元素组成，每个元素可以是一个基本元素或者是一个子表。

广义表可以为空，称为空表。

广义表中的元素的个数称为广义表的长度。

广义表的表示广义表可以通过两种方式进行表示：括号表示和逗号表示。

1.括号表示：使用括号将广义表括起来，每个元素之间使用逗号分隔。

例如，(1,2,3)表示一个包含3个元素的广义表，分别为1、2和3。

2.逗号表示：用逗号将广义表的元素分隔开，如果元素是基本元素，则直接写在逗号之间，如果元素是子表，则将子表表示为广义表的形式。

例如，1,2,3表示一个包含3个元素的广义表，分别为1、2和3。

广义表的操作广义表支持多种操作，包括获取广义表的长度、判断广义表是否为空、获取广义表的头、获取广义表的尾、判断两个广义表是否相等、复制广义表等。

获取广义表的长度获取广义表的长度即求广义表中元素的个数。

可以使用递归的方式来实现这个操作。

如果广义表为空，则长度为0；否则，长度等于广义表头的长度加上广义表尾的长度。

判断广义表是否为空判断广义表是否为空即判断广义表中是否没有元素。

如果广义表长度为0，则为空；否则，不为空。

获取广义表的头获取广义表的头即获取广义表中第一个元素。

如果广义表为空，则没有头；否则，头等于广义表中的第一个元素。

获取广义表的尾获取广义表的尾即获取广义表中除了第一个元素以外的所有元素。

如果广义表为空，则没有尾；否则，尾等于广义表中除了第一个元素以外的所有元素所组成的广义表。

判断两个广义表是否相等判断两个广义表是否相等即判断两个广义表中的元素是否完全相同。

如果两个广义表都为空，则相等；如果两个广义表的长度不相等，则不相等；否则，判断广义表的头是否相等，如果相等则判断广义表的尾是否相等。

复制广义表复制广义表即创建一个与原广义表相同的新广义表。

第6章广义表z6.1 广义表的基本概念z6.2 广义表的存储结构z6.3 广义表的操作算法16.1 广义表的基本概念广义表（列表）的概念-n( ≥0 )个表元素组成的有限序列，记作LS= ( a1, a1, a2, …, a n)LS是表名，a i是表元素，它可以是单个元素(称为原子) ，可以是表(称为子表) 。

n为表的长度。

n= 0 的广义表为空表。

n> 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。

2广义表举例：（1）A=（）（2）B=（e）（3）C=（a, (b, c, d) )（4）D=（A，B，C）（5）E= (a , E）9任意一个非空广义表，均可分解为表头和表尾。

9对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。

3广义表的基本操作：•结构的创建和销毁InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);•状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);•插入和删除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);•遍历Traverse_GL(L, Visit());66. 2 广义表的存储结构z由于广义表中的元素不是同一类型，因此难以用顺序结构表示，通常采用链接存储方法存储广义表，并称之为广义链表。

z由于广义表中有两种数据元素，原子或子表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。

z下面介绍一种广义表的链式存储结构。

78扩展的线性链表表示法：-子表结点由三个域组成：标志域、表头指针域和指向下一个元素的指针域；-原子结点的三个域为：标志域、值域和指向下一个元素的指针域。

数据结构5.3_⼴义表的定义和存储结构⼴义表定义：⼴义表(Lists，⼜称列表)是⼀种⾮线性的数据结构，是线性表的⼀种推⼴。

即⼴义表中放松对表元素的原⼦限制，容许它们具有其⾃⾝结构。

⼀个⼴义表是n（n≥0）个元素的⼀个序列，若n=0时则称为空表。

GL=(a1,a2,…,ai,…,an)其中n表⽰⼴义表的长度，即⼴义表中所含元素的个数，n≥0。

如果ai是单个数据元素，则ai是⼴义表GL的原⼦；如果ai是⼀个⼴义表，则ai是⼴义表GL的⼦表。

习惯上⽤⼤写表⽰⼴义表的名称；⽤⼩写字母表⽰原⼦。

当⼴义表⾮空时，称第⼀个元素a1为GL的表头（Head），称其余元素组成的表（a2,a3,...an）是GL的表尾（Tail）。

可以发现上述⼴义表的定义描述时，⼜⽤到了⼴义表的概念；⼴义表的存储结构：⼴义表中的数据元素可以具有不同的结构（或是原⼦，或是列表）。

因此难以⽤顺序存储结构表⽰，通常采⽤链式存储结构。

每个数据元素可⽤⼀个结点表⽰。

如何设定结点的结构？由于列表中的数据元素可能为原⼦或列表。

因此需要两种结构的结点：⼀种是表结点⽤于表⽰列表，⼀种是原⼦结点⽤于表⽰原⼦；若列表不空，则可以分解成表头和表尾；⼀个表结点可以由3个域组成：标志域（标识是表还是原⼦）、指⽰表头的指针域、指⽰表尾的指针域；对于原⼦结点只需要2个域：标志域、值域；--------⼴义表的头尾链表存储表⽰--------typedef enum {ATOM, LIST} ElemTag; //ATOM==0 原⼦； LIST==1 ⼦表typedef struct GLNode{ ElemTag tag; //公共部分，⽤于区分原⼦结点和表结点 union{ //原⼦结点和表结点的联合部分 AtomType atom; //atom是原⼦结点的值域， struct{ struct GLNode *hp *tp}ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 };} *GList; //⼴义表类型--------⼴义表的扩展线性链表存储表⽰--------typedef enum {ATOM, LIST}ElemTag;typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct GLNode *hp; } struct GLNode *tp;} *GList;相关链接：。

数据结构_广义表的运算数据结构——广义表的运算在计算机科学的数据结构领域中，广义表是一种较为复杂但又十分有趣和实用的数据结构。

它就像是一个“大容器”，可以容纳各种各样的数据元素，包括其他的广义表。

广义表的定义相对灵活，它可以是空表，也可以是由单个元素或者多个元素组成的表。

这些元素可以是原子，比如整数、字符等不可再分的数据；也可以是子表，也就是另一个广义表。

那么，广义表有哪些常见的运算呢？首先就是表头和表尾的获取。

表头指的是广义表中的第一个元素，如果这个元素本身是一个子表，那么这个子表整体就是表头。

而表尾则是除了表头之外的其余部分。

比如说，对于广义表｀（a, （b, c)， d)｀，其表头是｀a` ，表尾是｀（（b, c)， d)｀。

接下来是广义表的长度和深度的计算。

长度指的是广义表中元素的个数，需要注意的是，子表算一个元素。

比如｀（a, （b, c)， d)｀的长度是3 。

而深度则是指广义表中括号嵌套的层数，空表的深度为1 。

对于｀（a, （b, （c)））｀，其深度为 3 。

广义表的创建也是一项重要的运算。

我们可以通过逐个输入元素的方式来创建广义表。

在创建过程中，需要明确每个元素是原子还是子表，以正确构建广义表的结构。

广义表的复制运算也必不可少。

这就像是给一个广义表做了一个“克隆”，得到一个完全相同的副本。

在复制过程中，需要注意对原子和子表的分别处理，确保复制的准确性。

插入和删除操作在广义表中同样有着重要的应用。

比如，我们可以在广义表的指定位置插入一个新的元素或者子表，也可以删除指定位置的元素或者子表。

合并广义表则是将两个或多个广义表组合成一个新的广义表。

在合并过程中，需要考虑元素的顺序和结构，以保证合并后的广义表符合预期。

遍历广义表是对广义表中所有元素进行访问的操作。

常见的遍历方式有深度优先遍历和广度优先遍历。

深度优先遍历就像是在探索一个迷宫，沿着一条路径一直走到底，然后再回溯；而广度优先遍历则是先访问同一层的元素，再依次访问下一层。

数据结构29：⼴义表的长度和深度⼴义表的长度通过前⼀节对⼴义表的介绍，例⼦中给出了⼏个⼴义表的长度。

例如：空表的长度为 0，只含有⼀个原⼦的⼴义表长度为 1，等等。

⼴义表的长度指的是⼴义表中数据元素的数量。

这⾥需要指明的是，⼀个⼴义表中，⼀个原⼦算做是⼀个元素，⼀个⼦表也只算做⼀个元素。

在 LS = (a1,a2,…,a n) 中，a i表⽰原⼦或者⼦表， LS 的长度为 n。

⼴义表的深度⼴义表的深度，指的是⼴义表中括号的重数。

例如：C=(a,(b,c,d))：图1 ⼴义表C的深度图1中，从前往后数左括号的数量就是⼴义表C的深度，为2；也可以从右往左数右括号的数量（红⾊）。

求解⼴义表的深度求⼴义表的深度之前，⾸先要将⼴义表⽤某个数据结构表⽰出来，在前边学习⼴义表时，介绍了两种表⽰⼴义表的⽅法。

这⾥采⽤的⽅法是第⼀种。

表⽰结构为：（拿⼴义表C为例）⼴义表第⼀节中有具体实现的代码，实现函数为：creatGlist(Glist C)。

这⾥不再过多介绍。

求⼴义表深度的算法⽤到的是递归的思想，解题思路是：1. 从⼴义表 C 的开头位置，⼀次遍历表中每个数据元素：当遍历对象为原⼦时，返回原⼦的深度为 0 ；遍历对象为表 C 的⼦表时，继续遍历⼦表中的数据元素。

2. 递归的出⼝有两个：当遍历对象为原⼦时，返回 0 ；遍历对象为空表时，返回 1 （空表的深度为 1 ）；3. 设置⼀个初始值为 0 的整形变量 max ，⽤ max 和遍历过程中返回的整形数值进⾏⽐较，取⼤的那⼀个，知道程序结束，max + 1就是⼴义表的深度。

实现代码为：int GlistDepth(Glist C){ //如果表C为空表时，直接返回长度1； if (!C) { return1; } //如果表C为原⼦时，直接返回0； if (C->tag == 0) { return0; } int max = 0; //设置表C的初始长度为0； for (Glist pp=C; pp; pp=pp->ptr.tp) { int dep = GlistDepth(pp->ptr.hp); if (dep>max) { max = dep; //每次找到表中遍历到深度最⼤的表，并⽤max记录 } } //程序运⾏⾄此处，表明⼴义表不是空表，由于原⼦返回的是0，⽽实际长度是1，所以，此处要+1； return max+1;}完整代码演⽰#include <stdio.h>#include <stdlib.h>typedef struct GLNode{ int tag; //标志域 union { char atom; //原⼦结点的值域 struct { struct GLNode *hp, *tp; }ptr; //⼦表结点的指针域，hp指向表头；tp指向表尾 };}*Glist, GNode;Glist creatGlist(Glist C){ //⼴义表C C=(Glist)malloc(sizeof(GNode)); C->tag = 1; //表头原⼦‘a’ C->ptr.hp = (Glist)malloc(sizeof(GNode)); C->ptr.hp->tag = 0; C->ptr.hp->atom = 'a'; //表尾⼦表（b,c,d）,是⼀个整体 C->ptr.tp = (Glist)malloc(sizeof(GNode)); C->ptr.tp->tag = 1; C->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode)); C->ptr.tp->ptr.tp = NULL; //开始存放下⼀个数据元素（b,c,d）,表头为‘b’，表尾为（c,d） C->ptr.tp->ptr.hp->tag = 1; C->ptr.tp->ptr.hp->ptr.hp = (Glist)malloc(sizeof(GNode)); C->ptr.tp->ptr.hp->ptr.hp->tag = 0; C->ptr.tp->ptr.hp->ptr.hp->atom = 'b'; C->ptr.tp->ptr.hp->ptr.tp = (Glist)malloc(sizeof(GNode)); //存放⼦表(c,d)，表头为c，表尾为d C->ptr.tp->ptr.hp->ptr.tp->tag = 1; C->ptr.tp->ptr.hp->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode)); C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag = 0; C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom = 'c'; C->ptr.tp->ptr.hp->ptr.tp->ptr.tp = (Glist)malloc(sizeof(GNode)); //存放表尾d C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag = 1; C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode)); C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag = 0; C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom = 'd'; C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp = NULL; return C;}//求⼴义表的深度，递归调⽤int GlistDepth(Glist C){ if (!C) { return1; } if (C->tag == 0) { return0; } int max = 0; for (Glist pp=C; pp; pp=pp->ptr.tp) { int dep = GlistDepth(pp->ptr.hp); if (dep>max) { max = dep; } } return max+1;}int main(int argc, const char *argv[]){ Glist C = creatGlist(C); printf("%d", GlistDepth(C)); return0;}运⾏结果：2。

数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。

5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。

其数据元素通常也称为数组元素。

数组地每个数据元素都有一个序号,称为下标。

可以通过数组下标访问数据元素。

数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。

如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。

如aij表示第i行j列地数据元素。

数组也是一种线性数据结构,它可以看成是线性表地一种扩充。

一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。

如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。

数据结构广义表一、引言数据结构是计算机科学的基础，广义表是一种重要的数据结构。

广义表是在线性表的基础上扩展而来，可以包含任意类型的元素，包括另一个广义表。

本文将详细介绍广义表的概念、表示方法、基本操作以及应用。

二、概念1. 广义表定义广义表是一种线性结构，可以包含原子和子表两种类型的元素。

其中，原子可以是任何数据类型，而子表则是一个嵌套的广义表。

2. 广义表表示广义表可以用括号表示法来表示。

例如：(a, b, (c, d), e)就是一个包含4个元素的广义表，其中第3个元素为一个嵌套的广义表。

3. 广义表分类根据广义表中元素所属类型不同，可以将其分为两类：原子和子表。

- 原子：指不再能被分解成更小单位的元素。

- 子表：指由若干个元素组成的序列，每个元素既可以是原子也可以是另一个子列表。

三、表示方法1. 递归表示法递归表示法是一种常用且简单易懂的方法。

它将一个非空广义列表示为左括号、若干元素和右括号的形式，其中每个元素可以是原子或另一个广义表。

例如：(a, b, (c, d), e)就是一个递归表示法。

2. 链式存储表示法链式存储表示法是一种更加灵活的方法。

它将广义表表示为一个链表，每个节点有两个指针域，分别指向下一个元素和下一个子表。

例如：(a, b, (c, d), e)可以用链式存储表示法表示为：四、基本操作1. 头尾操作头尾操作是指对广义表中第一个元素或最后一个元素进行操作。

- 头部操作：获取广义表中的第一个元素。

- 尾部操作：获取广义表中的最后一个元素。

2. 插入操作插入操作是指在广义表中插入新的元素或子表。

- 插入原子：在广义列表示中插入新的原子。

- 插入子表：在广义列表示中插入新的子列表。

3. 删除操作删除操作是指从广义列表示中删除某个元素或子列表。

- 删除原子：从广义列表示中删除某个原子。

- 删除子表：从广义列表示中删除某个子列表。

五、应用场景1. 树结构树结构可以用广义表来表示。