数据结构05数组和广义表.pptVIP

2020 3 26 1 本章主要介绍数组的概念及多维数组在计算机中的存放 特殊矩阵的压缩存储及相应运算 广义表的概念和存储结构及其相关运算的实现 通过本章学习 要求掌握如下内容 1 多维数组的定义及在计算机中的存储表示 2 对称矩阵 三角矩阵 对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式 3 稀疏矩阵的三元组表示及转置算法实现 4 稀疏矩阵的十字链表表示及相加算法实现 5 广义表存储结构表示及基本运算 本章学习导读 2020 3 26 2 数组和广义表可看成是一种特殊的线性表 其特殊在于 表中的数据元素本身也是一种线性表 5 1 1数组的定义数组是大家都已经很熟悉的一种数据类型 几乎所有高级语言程序设计中都设定了数组类型 数组 Array 是由n n 1 个相同类型数据元素a0 al ai an 1构成的有限序列 n是数组的长度 其中数组中的数据元素ai是一个数据结构 即ai可以是线性表中的一个元素 本身也可以是一个线性表 而线性子表中的每一个数据元素还可以再分解 根据数组元素ai的组织形式不同 数组可以分为一维数组 二维数组以及多维 n维 数组 5 1数组 2020 3 26 3 有时也把一维数组称为向量 二维数组称为矩阵 在二维或多维数组中 每个数组元素都受到2个或n个关系的约束 当数组为n维时 其对应线性表中的每个元素又是一个线性表 在每个关系中 每个元素都有一个直接后继 因此 就其单个关系而言 这n个关系中的每一个仍然是一种线性关系 数组中每个元素都是由一个值和一组下标来确定的 同线性表一样 数组中的所有数据元素都必须属于同一数据类型 元素下标的个数被称为数组的维数 显然 当维数为1时 数组就退化为定长的线性表 2020 3 26 4 1 一维数组一维数组可以看成是一个线性表或一个向量 它在计算机内是存放在一块连续的存储单元中 适合于随机查找 一维数组记为A n 或A a0 al ai an 1 一维数组中 一旦a0的存储地址 一个数据元素所占存储单元数L确定 则ai的存储地址LOC ai 就可求出 LOC ai LOC a0 i L 0 i n 2 二维数组二维数组 又称矩阵 matrix 二维数组中的每一个元素又是一个定长的线性表 一维数组 都要受到两个关系即行关系和列关系的约束 也就是每个元素都同属于两个线性表 例如 设A是一个有m行n列的二维数组 则A可以表示为 2020 3 26 5 可以看成由m个行向量组成的向量 也可以看由n个列向量组成的向量 数组中的每个元素由元素值aij及一组下标 i j 来确定 aij既属于第i行的行向量 又属于第j列的列向量 其中 ai ai 0ai 1 ai n 1 0 i n 可以认为Am n A A是这样的一维数组 A a0 al ai am 1 2020 3 26 6 显然 二维数组同样满足数组的定义 一个二维数组可以看作是每个数据元素都是相同类型的一维数组 以此类推 任何多维数组都可以看作一个线性表 这时线性表中的每个数据元素也是一个线性表 多维数组是特殊的线性表 是线性表的推广 数组的性质 1 数组中的数据元素数目固定 一旦定义了一个数组 其数据元素数目不再有增减变化 它属于静态分配存储空间的数据结构 2 数组中的数据元素必须具有相同的数据类型 3 数组中的每个数据元素都有一组唯一的下标值 4 数组是一种随机存储结构 可随机存取数组中的任意数据元素 2020 3 26 7 对于多维数组 有两种存储方式 Am n以行序为主序的顺序存储 数组元素按行向量排列 即第i 1个行向量紧接在第i个行向量之后 把所有数组元素顺序存放在一块连续的存储单元中 任一数据元素的存储地址可由公式算出 Loc ai j loc a0 0 i n j L以列序为主序的顺序存储在以列序为主序的存储方式中 数组元素按列向量排列 即第j 1个列向量紧接在第j个列向量之后 把所有数组元素顺序存放在一块连续的存储单元中 任一数据元素的存储地址可由公式算出Loc ai j loc a0 0 j m i L 2020 3 26 8 推广到一般设二维数组行下界为c1 行上界为d1 列下界为c2 列上界为d2 即数组A c1 d1 c2 d2 则以行序为主序的求元素地址公式可以为 Loc ai j loc ac1 c2 i c1 d2 c2 1 j c2 L则以列序为主序的求元素地址公式可以为 Loc ai j loc ac1 c2 j c1 d1 c1 1 i c1 L 2020 3 26 9 5 1 2数组的基本操作数组一旦被定义 它的维数和维界就不再改变 因此 除了结构的初始化和销毁之外 数组的基本操作一般不会含有元素的插入或删除等操作 数组只有访问数组元素和修改元素值的操作 1 取值操作 给定一组下标 读其对应的数据元素 2 赋值操作 给定一组下标 存储或修改与其相对应的数据元素 我们着重研究二维和三维数组 因为它们的应用是广泛的 尤其是二维数组 2020 3 26 10 5 1 3数组的存储结构 通常 数组在内存中被映象为向量 即用向量作为数组的一种存储结构 这是因为内存的地址空间是一维的 数组的行列固定后 通过一个映象函数 则可根据数组元素的下标得到它的存储地址 对于一维数组按下标顺序分配即可 对多维数组分配时 要把它的元素映象存储在一维存储器中 一般有两种存储方式 一是以行为主序 或先行后列 的顺序存放 如BASIC PASCAL COBOL C等程序设计语言中用的是以行为主的顺序分配 即一行分配完了接着分配下一行 另一种是以列为主序 先列后行 的顺序存放 如FORTRAN语言中 用的是以列为主序的分配顺序 即一列一列地分配 2020 3 26 11 以行为主序的分配规律是 最右边的下标先变化 即最右下标从小到大 循环一遍后 右边第二个下标再变 从右向左 最后是左下标 以列为主序的分配规律恰好相反 最左边的下标先变化 即最左下标从小到大 循环一遍后 左边第二个下标再变 从左向右 最后是右下标 2020 3 26 12 例如一个2 3的二维数组 逻辑结构可以用左图表示 以行为主序的内存映象如右图 a 所示 分配顺序为 a11 a12 a13 a21 a22 a23 以列为主序的分配顺序为 a11 a21 a12 a22 a13 a23 它的内存映象如右图 b 所示 2020 3 26 13 设有m n二维数组Amn 下面我们看按元素的下标求其地址的计算 以 行为主序 的分配为例 设数组的基址为LOC a11 每个数组元素占据l个地址单元 那么aij的物理地址可用一线性寻址函数计算 LOC aij LOC a11 i 1 n j 1 l在C语言中 数组中每一维的下界定义为0 则 LOC aij LOC a00 i n j l推广到一般的二维数组 A c1 d1 c2 d2 则aij的物理地址计算函数为 LOC aij LOC ac1c2 i c1 d2 c2 1 j c2 l 2020 3 26 14 同理对于三维数组Amnp 即m n p数组 对于数组元素aijk其物理地址为 LOC aijk LOC a111 i 1 n p j 1 p k 1 l推广到一般的三维数组 A c1 d1 c2 d2 c3 d3 则aijk的物理地址为 LOC i j LOC ac1c2c3 i c1 d2 c2 1 d3 c3 1 j c2 d3 c3 1 k c3 l 2020 3 26 15 三维数组的逻辑结构和以行为主序的分配示意图如图所示 2020 3 26 16 2 由于C语言采用行序为主序的存储方式 有 LOC a2 3 LOC a0 0 i n j k 1000 2 4 3 4 1044 例1 在C语言中 对于给定的二维数组floata 3 4 计算 1 数组a中的数组元素数目 2 若数组a的起始地址为1000 且每个数组元素长度为32位 即4个字节 数组元素a 2 3 的内存地址 解 1 由于C语言中数组的行 列下标值的下界均为0 该数组行上界为3 1 2 列上界为4 1 3 所以该数组的元素数目共有3 4 12个 2020 3 26 17 例2 有m名学生 每人考n门功课 试写出求任一学生总分数和任一课程总分数的数据结构和算法 解 把学生的考试成绩存放在m行n列的二维数组中 则第i 0 i为10人 defineN3 假设为3intscore M N 学生成绩二维数组求第i名学生总分数的算法为 intstudent sum intscore M N inti intj sum 0 for j 0 j N j sum sum score i j return sum 2020 3 26 18 求第j门课程总分数的算法为 intcourse sum intscore M N intj inti sum 0 for i 0 i M i sum sum score i j return sum 2020 3 26 19 矩阵是数值计算程序设计中经常用到的数学模型 它是由m行和n列的数值构成 当m n时称为方阵 在高级程序设计语言中 通常用二维数组表示矩阵 然而在数值分析过程中经常遇到一些比较特殊的矩阵 它们的阶数很高 矩阵中元素数量很大 而且有很多元素的值相同或是零值元素 如对称矩阵 三角矩阵 带状矩阵和稀疏矩阵等 为了节省存储空间并且加快处理速度 需要对这类矩阵进行压缩存储 压缩存储的原则是 不重复存储相同元素 不存储零值元素 5 2矩阵的压缩存储 2020 3 26 20 5 2 1特殊矩阵的压缩存储方法特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵 主要形式有对称矩阵 三角矩阵 对角矩阵等 1 对称矩阵的压缩存储对称矩阵是一个n阶方阵 若一个n阶矩阵A中的元素满足 ai j aj i 0 i j n 1 则称A为n阶对称矩阵 15137a0050800a10a1118926a20a21a2330251 70613an 10an 11an 12 an 1n 1 对称矩阵 2020 3 26 21 在这个下三角矩阵中 第i行恰有i 1个元素 元素总数为 n n 现把这些元素存储在n n 1 2个元的空间中 由于对称矩阵中的元素关于主对角线对称 因此可以为每一对对称的矩阵元素分配1个存储空间 n阶矩阵中的n n个元素就可以被压缩到n n 1 2个元素的存储空间中去 Sak与aji的对应关系 称一维数组Sa 0 n n 1 2 为n阶对称矩阵A的压缩存储 其存储对应关系如上图 对称矩阵的压缩存储 2020 3 26 22 2 三角矩阵的压缩存储三角矩阵也是一个n阶方阵 有上三角和下三角矩阵 下 上 三角矩阵是主对角线以上 下 元素均为零的n阶矩阵 设以一维数组Sb 0 n n 1 2 作为n阶三角矩阵B的存储结构 仍采用按行存储方案 则B中任一元素bi j和Sb k 之间存在着如下对应关系 其中 Sb n n 1 2 中存放常数c或0 2020 3 26 23 3 对角矩阵的压缩存储对角方阵 或称带状矩阵 是指所有的非零元素 简称非零元 都集中在以主对角线为中心的带状区域中 即除了主对角线上和紧靠着主对角线上下方若干条对角线上的元素外 所有其它元素皆为零的矩阵 常见的有三对角矩阵 五对角矩阵 七对角矩阵等 下图是一个具有3 1 m n 条非零元素带的n阶对角矩阵 具有3条非零对角线的对角矩阵 2020 3 26 24 对于n阶有m m必为奇数 因为副对角线关于主对角线对称 条非零元素带的对角矩阵 只需存放对角区域内的所有非零元素即可 在n阶对角矩阵A中 主对角线元素数最多 n个 然后向两边依次减少 每隔一条元素带元素数就减少1个 最外端的对角线有n m 1 2个元素 所以非零元素总数u为 u m n 2 m 1 2 m 1 2 1 l m n m2 1 4设以一维数组Sa u l 为对角矩阵A的存储结构 若按行存储非零元 则A中任一元素ai j和Sa k 之间存在着如下对应关系 结论 对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中 不同的排列方案也就对应不同的存储方案 2020 3 26 25 5 2 2稀疏矩阵的压缩存储方法如果一个矩阵中非零元较零元少 且分布没有一定规律 称该矩阵为稀疏矩阵 根据存储时所附加信息的不同 稀疏矩阵的顺序存储方法包括 三元组表示法 带辅助行向量的二元组表示法和伪地址表示法 其中以三元组表示法最常用 三元组表示法就是在存储非零元的同时 存储该元素所对应的行下标和列下标 稀疏矩阵中的每一个非零元素由一个三元组 i j aij 唯一确定 矩阵中所有非零元素存放在由三元组组成的数组中 由线性表的两种不同存储结构可以得到稀疏矩阵压缩的不同的存储方法 2020 3 26 26 假设有一个6 7阶稀疏矩阵A 其元素情况以及非零元对应的三元组表 以行序为主序 如图所示 a 稀疏矩阵 b 三元组表示 三元组表中的第一行分别表示稀疏矩阵A的行数 列数和非零元的个数 显然 非零元素的三元组是按行号递增的顺序 相同行号的三元组按列号递增的顺序排列的 图5 4 2020 3 26 27 1 三元组顺序表假设以行序为主序 且以一维数组作为三元组表的存储结构 可以得到稀疏矩阵的一种压缩存储方法 称为三元组顺序表 三元组顺序表的数据结构定义如下 defineNUM100 矩阵中非零元素最大个数typedefstruct 三元组结构 intr c 行 列 号ElemTyped 元素值 tupletype 三元组定义typedefstruct introws 矩阵行数值intcols 矩阵列数值intnums 非零元素个数tupletypedata NUM 三元组表 table 三元组顺序表定义 2020 3 26 28 1 稀疏矩阵的转置运算转置是矩阵中最简单的一种运算 对于一个m n的矩阵其转置矩阵是一个n m的矩阵 设为Bn m且满足ai j bj i即 a i j b j i 其中 0 i m 1 0 j n 1即A的行是B的列 A的列是B的行 稀疏矩阵的三元组表 2020 3 26 29 三元组表示的稀疏矩阵的转置常用的算法有以下两种 1 矩阵的列序转置 传统的转置算法 矩阵A是按行序为主序存储的 若按列序为主序进行转置就可以得到A阵的转置矩阵B 假设矩阵A的三元组存入一维数组中 只要在数组中按三元组的列域cols的值开始扫描 从第0列至第n 1列 依序将三元组列域与行域值对换 并顺次存入数组mb中 算法如下 inttranspose tablema tablemb inti j k 0 n t if ma nums 0 return 0 矩阵中无非零元素m ma rows m为矩阵A的列数n ma cols n为矩阵A的行数t ma nums 为矩阵中非零元素个数mb rows n 转置矩阵B的列数 2020 3 26 30 mb cols 转置矩阵B的行数mb nums t 转置矩阵中的非零元素个数for i 0 i n i 按矩阵A的列序扫描for j 0 j t j if ma data j c i 判断第j个三元组是不是第i列的 mb data k r ma data j c mb data k c ma data j r mb data k d ma data j d return 1 成功完成矩阵转置 以上算法的时间复杂度分析 若n为转置矩阵的列数 t为矩阵中非零元素个数 则算法的时间花费主要在两个循环上 所以若时间复杂度为O n t 也就是说 时间的花费和矩阵A的列数和非零元素个数的乘积成正比 若用m n的二维数组表示矩阵 则相应的矩阵转置算法的循环为 for i 0 i n i for j 0 j m j b i j a j i 此时 时间复杂度为O m n 2020 3 26 31 2 快速转置算法 三元组顺序表虽然节省了存储空间 但时间复杂度比一般矩阵转置的算法还要复杂 其效率低的原因是算法要从A的三元组表中寻找第一列 第二列 要反复搜索A表 若能直接确定A中每一三元组在B中的位置 则对A的三元组表扫描一次即可 这是可以做到的 因为A中第一列的第一个非零元素一定存储在B data 1 如果还知道第一列的非零元素的个数 那么第二列的第一个非零元素在B data中的位置便等于第一列的第一个非零元素在B data中的位置加上第一列的非零元素的个数 如此类推 因为A中三元组的存放顺序是先行后列 对同一行来说 必定先遇到列号小的元素 这样只需扫描一遍A data即可 2020 3 26 32 为此 需要设置两个一维数组num 0 n 和rpos 0 n num 0 n 统计M中每列非零元素的个数 rpos 0 n M中的每列第一个非零元素在T中的位置 算法通过rpos数组建立位置对应关系 rpos 0 0 rpos col rpos col 1 num col 1 0 col M rows 例如图5 4 a 所示的稀疏矩阵的三元组表对应的num 0 n 1 和rpos 0 n 1 如图5 5所示 算法5 2见教科书P100 图5 5矩阵的num和rpos数组值 2020 3 26 33 快速转置算法如下 voidfasttranstri tritupletableb tritupletablea intp q col k intnum 0 a n copt 0 a n b m a n b n a m b t a t if b t 0 printf a 0 n for col 1 col a u col num col 0 for k 1 k a t k num a data k j cpot 0 1 for col 2 col a t col cpot col cpot col 1 num col 1 for p 1 p a t p col a data p j q cpot col b data q i a data p j b data q j a data p i b data q v a data p v cpot col 2020 3 26 34 2 行逻辑链接的顺序表 带行表的三元组 有时为了方便某些矩阵运算 在按行优先存储的三元组中 加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置 当将行表作为三元组表的一个新增属性加以描述时 就得到了稀疏矩阵的另一种顺序存储结构 带行表的三元组表 称这种 带行链接信息 的三元组表为行逻辑链接的顺序表 其类型描述如下 definemaxrow100typedefstruct tripledata maxsize intrpos maxrow intn m t rtripletable 2020 3 26 35 下面讨论两个稀疏矩阵相乘的例子 容易看出这种表示方法的优越性 若设Q M N其中 M是m1 n1矩阵 N是m2 n2矩阵 当n1 m2时有 for i 1 i m1 i for j 1 j n2 j q i j 0for k 1 k n1 k q i j m i k n k j 此算法的复杂度为O m1 n1 n2 2020 3 26 36 5 3 2稀疏矩阵的十字链表存储 三元组表可以看作稀疏矩阵顺序存储 但是在做一些操作 如加法 乘法 时 非零元个数及位置在操作过程中变化较大时 这种表示就十分不便 在这节中 我们介绍稀疏矩阵的一种链式存储结构 十字链表 它具备链式存储的特点 因此 在某些情况下 采用十字链表表示三元组的线性表更为恰当 2020 3 26 37 下图是一个稀疏矩阵的十字链表 2020 3 26 38 用十字链表表示稀疏矩阵的基本思想是 对每个非零元素存储为一个结点 结点由5个域组成 其结构如图表示 其中 i域存储非零元素的行号 j域存储非零元素的列号 value域存储本元素的值 right向右域 用以链接同一行中下一个非零元素 down向下域 用以链接同一列中下一个非零元素 next域 用以各行 列 表头结点与其下一结点之间的链接 算法思想 同一行的非零元素通过right域链接成一个链表 同一列的非零元素通过down域链接成一个链表 每一个非零元既是某个行链表中的结点 同时又是某个列链表中的结点 整个矩阵构成了一个十字交叉的链表 故称为十字链表 a 结点结构 b 头结点结构图5 6十字链表结点结构 2020 3 26 39 结点的结构定义如下 typedefstructolnode inti j Elemtypee structolnode right down olnode olink typedefstruct olink rhead chead intmu nu tu CrossList 2020 3 26 40 5 3广义表的定义 5 3 1广义表的定义1 广义表的定义广义表也是线性表的推广 是一种多层次的线性结构 线性表中的元素仅限于原子项 即不可以再分 而广义表中的元素既可以是原子项 也可以是子表 另一个线性表 主要用于人工智能领域的表处理语言LISP语言 广义表是n 0个元素a1 a2 an的有限序列 其中每一个ai或者是原子 或者是一个子表 广义表通常记为LS a1 a2 an 其中LS为广义表的名字 n为广义表的长度 每一个ai为广义表的元素 但在习惯中 一般用大写字母表示广义表 小写字母表示原子 若n 0时为空表 记作 L 2020 3 26 41 当广义表L非空 n 0 时 第一个数据元素a0被称为广义表的表头 head 其余数据元素组成的表 a1 an 1 被称为广义表L的表尾 tail 分别记为head A a0 tail a1 an 1 因此 一个广义表是由表头和表尾构成的 2 广义表举例1 A A为空表 长度为0 2 B e B是一个只含有原子e的表 其长度为l 3 C a b c d C是长度为2的广义表 第一项为原子 第二项为子表 4 D A B C e a b c d 5 E a a b a b c E中只含有一个元素 该元素是一个表 E的长度为l 6 F a F a a a F是长度为2的广义表 第一项为原子 第二项为它本身 2020 3 26 42 3 广义表的表示方法 用次序关系和层次关系表示 1 用L a1 a2 an 形式 其中每一个ai为原子或广义表 例如 A b c B a A E a E 都是广义表 2 将广义表中所有子表写成原子形式 并利用圆括号嵌套 例如 广义表A B C可以描述为 A b c B a A b c E a E a E 3 将广义表用树和图来描述 层次关系 上面提到的广义表A B C的描述见图5 8 次序关系 2020 3 26 43 广义表中数据元素的最大层次为表的深度 数据元素的层次就是包括该元素的括号对的数目 例如广义表G a b c d 中 数据元素a b在第一层 数据元素c在第二层 数据元素d在第三层 广义表G的深度为3 图5 8广义表的图形表示 从图5 8可以看出 广义表的图形表示像倒着画的一棵树 树根结点代表整个广义表 各层树枝结点代表相应的子表 树叶结点代表单元素或空表 如A表 2020 3 26 44 4 广义表的深度一个广义表的深度是指该广义表展开后所含括号的层数 例如 A b c 的深度为1 B A d 的深度为2 C f B h 的深度为3 广义表兼有线性结构和层次结构的特性 归纳如下 1 广义表中的数据元素有固定的相对次序 2 广义表的长度定义为最外层括弧中包含的数据元素个数 3 广义表的深度定义为广义表书写形式中括弧的最大重数 因此空表的深度为1 因为一个单元素不是广义表 所以从定义上讲没有深度可言 但可以认为它的深度为0 4 广义表可被其它广义表所共享 例如上述例子中广义表B同时也是广义表D中的一个子表 5 广义表可以是一个自递归的表 例如上述例子中的广义表F 自递归的广义表的长度是个有限值 而深度为无限值 2020 3 26 45 5 广义表的分类 1 线性表 元素全部是原子的广义表 2 纯表 与树对应的广义表 见图5 8的 c d e 3 再入表 与图对应的广义表 允许结点共享 4 递归表 允许有递归关系的广义表 例如E a E 这四种表的关系满足 递归表 再入表 纯表 线性表 再入表 2020 3 26 46 广义表基本运算广义表有两个重要的基本操作 即取头操作 Head 和取尾操作 Tail 根据广义表的表头 表尾的定义可知 对于任意一个非空的列表 其表头可能是单元素也可能是列表 而表尾必为列表 例如 Head B eTail B Head C aTail C b c d Head D ATail D B C Head E aTail E E Head F Tail F 此外 在广义表上可以定义与线性表类似的一些操作 如建立 插入 删除 拆开 连接 复制 遍历等 2020 3 26 47 CreateLists ls 根据广义表的书写形式创建一个广义表ls IsEmpty ls 若广义表ls空 则返回True 否则返回False Length ls 求广义表ls的长度 Depth ls 求广义表ls的深度 Locate ls x 在广义表ls中查找数据元素x Merge ls1 ls2 以ls1为头 ls2为尾建立广义表 CopyGList ls1 ls2 复制广义表 即按ls1建立广义表ls2 Head ls 返回广义表ls的头部 Tail ls 返回广义表的尾部 2020 3 26 48 5 3 2广义表的存储结构由于广义表的元素类型不一定相同 表中的数据元素可以是单元素 原子项 也可以是广义表 因此 难以用顺序结构存储表中元素 通常采用链接存储方法来存储广义表中元素 并称之为广义链表 需要两种结构的结点 1 表结点 用以表示广义表 由三个域组成 标志域tag 指向表头的指针域sublist和指向下一个结点的指针域link 如图5 9 a 所示 2 原子结点 用以表示原子项 由三个域组成 标志域tag 值域data和指向下一个元素结点的指针域link 如图5 9 b 所示 2020 3 26 49 每个数据元素都可用表结点或原子结点表示 它们的主要区别在于从不同的角度反映广义表的构成 例如 广义表C的链表存储结构如图5 10所示 图5 10广义表 a b c d 的链表存储结构图 二叉树 2020 3 26 50 广义表的链式结构描述如下 typedefcharElemType typedefstructglnode inttag union ElemTypedata structglnode sublist val structglnode link GListNode 可将一个广义表看成一棵树 为了方便存储 通常将其转换成一棵二叉树 广义表C转换成二叉树过程如图5 11所示 2020 3 26 51 广义表C 图5 11广义表的转换过程 2020 3 26 52 5 3 3广义表的基本操作广义表的基本操作主要有 求广义表的长度和深度 向广义表插入元素和从广义表中查找或删除元素 建立广义表的存储结构 输出广义表和复制广义表等 由于广义表是一种递归的数据结构 所以对广义表的运算一般采用递归的算法 1 求广义表的深度广义表深度的递归定义是 它等于所有子表中表的最大深度加1 若一个表为空或仅由单元素所组成 则深度为l 求广义表深度的递归函数GListDepth 如下 2020 3 26 53 1LS为空表时GListDepth LS 0LS为原子时max GListDepth ai sh为h的子表 1其它情况 intGListDepth GListL 采用头尾链表存储结构 求广义表L的深度 if L return1 空表深度为1if L tag ATOM return0 原子深度为0for max 0 pp L pp pp pp ptr tp dep GListDepth pp ptr hp 求以pp ptr hp为头指针的子表深度if dep max max dep returnmax 1 非空表的深度是各元素的深度的最大值加1 GListDepth 2020 3 26 54 2 广义表的复制复制一个广义表的过程如下 对于广义表的头结点 p 若为空 则返回空指针 若为表结点 则递归复制子表 否则 复制单元素结点