串零个或多个字符组成的有限序列将元素类型限制为字符线性表具有相同类型的数据元素的有限序列将元素类型扩充为线性表 ( 多维 ) 数组线性表中的数据元素可以是线性表 2

Size: px

Start display at page:

Download "串零个或多个字符组成的有限序列将元素类型限制为字符线性表具有相同类型的数据元素的有限序列将元素类型扩充为线性表 ( 多维 ) 数组线性表中的数据元素可以是线性表 2"

豫蒋
7 years ago
Views:

1 Array Zibin Zheng( 郑子彬 ) School of Data and Computer Science, SYSU 课程主页 :

2 串零个或多个字符组成的有限序列将元素类型限制为字符线性表具有相同类型的数据元素的有限序列将元素类型扩充为线性表 ( 多维 ) 数组线性表中的数据元素可以是线性表 2

3 数组与广义表数组是一种人们非常熟悉的数据结构, 几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型数组这种数据结构可以看成是线性表的推广科学计算中涉及到大量的矩阵问题, 在程序设计语言中一般都采用数组来存储, 被描述成一个二维数组但当矩阵规模很大且具有特殊结构 ( 对角矩阵三角矩阵对称矩阵稀疏矩阵等 ), 为减少程序的时间和空间需求, 采用自定义的描述方式广义表是另一种推广形式的线性表, 是一种灵活的数据结构, 在许多方面有广泛的应用 3

4 数组的定义数组是由一组类型相同的数据元素构成的有序集合, 每个数据元素称为一个数组元素 ( 简称为元素 ), 每个元素受 n(n 1) 个线性关系的约束, 每个元素在 n 个线性关系中的序号 i 1 i 2 i n 称为该元素的下标, 并称该数组为 n 维数组数组的特点元素本身可以具有某种结构, 属于同一数据类型 ; 数组是一个具有固定格式和数量的数据集合 4

5 数组的定义 a 11 a 12 a 1n A= a 21 a 22 a 2n a m1 a m2 a mn 例如, 元素 a 22 受两个线性关系的约束, 在行上有一个行前驱 a 21 和一个行后继 a 23, 在列上有一个列前驱 a 12 和和一个列后继 a 32 5

6 数组线性表的推广 A= a 11 a 12 a 1n a 21 a 22 a 2n a m1 a m2 a mn A=(A 1,A 2,,A n ) 其中 : A i =(a 1i,a 2i,,a mi ) (1 i n) 二维数组是数据元素为线性表的线性表 6

7 数组的基本操作在数组中插入 ( 或删除 ) 一个元素有意义吗? 将元素 x 插入到数组中第 1 行第 2 列 x 删除数组中第 1 行第 2 列元素 a 11 a 12 a 1n a 11 a 12 a 1n A= a 21 a 22 a 2n A= a 21 a 22 a 2n a m1 a m2 a mn a m1 a m2 a mn 7

8 数组的基本操作 ⑴ 存取 : 给定一组下标, 读出对应的数组元素 ; ⑵ 修改 : 给定一组下标, 存储或修改与其相对应的数组元素存取和修改操作本质上只对应一种操作寻址数组应该采用何种方式存储? 数组没有插入和删除操作, 所以, 不用预留空间, 适合采用顺序存储 8

9 数组的定义抽象数据类型 ADT Array{ 数据对象 :j i = 0,1,,b i -1, 1,2,,n ; D = { aj 1 j 2 j n>0 称为数组的维数,b n i 是数组第 i 维的长度,j i 是数组元素第 i 维的下标,aj 1 j 2 j ElemSet } n 数据关系 :R = {R 1, R 2,, R n } R i ={<aj 1 j 2 j i j, a n j 1 j 2 j i+1 j > 0 j n k b k -1,1 k n 且 k i,0 j i b i -2, aj 1 j 2 j i+1 j D } n 基本操作 : } ADT Array 由上述定义知,n 维数组中有 b 1 b 2 b n 个数据元素, 每个数据元素都受到 n 维关系的约束 9

10 数组的定义 (a) 矩阵表示形式 (b) 列向量的一维数组形式 (c) 行向量的一维数组形式二维数组图例形式 10

11 数组的定义 A m n a a... am 11 21,1 a a a m, a a a 1, n 2, n... m, n 数组的特点 : 元素数目固定 ; 下标有界 ; 数组的操作 : 照下标进行读写 11

12 数组的顺序表示和实现数组一般不做插入和删除操作, 也就是说, 数组一旦建立, 结构中的元素个数和元素间的关系就不再发生变化因此, 一般都是采用顺序存储的方法来表示数组问题 : 计算机的内存结构是一维 ( 线性 ) 地址结构, 对于多维数组, 将其存放 ( 映射 ) 到内存一维结构时, 有个次序约定问题即必须按某种次序将数组元素排成一列序列, 然后将这个线性序列存放到内存中二维数组是最简单的多维数组, 以此为例说明多维数组存放 ( 映射 ) 到内存一维结构时的次序约定问题 12

13 数组的顺序表示和实现通常有两种顺序存储方式 : ⑴ 行优先顺序 (Row Major Order) 将数组元素按行排列, 第 i+1 个行向量紧接在第个行向量后面以二维数组为例 i, 按行优先顺序存储的线性序列为 : a 11, a 12,, a 1n, a 21, a 22,, a 2n,..., a m1, a m2,, a mn 在 PASCAL C 语言中, 数组就是按行优先顺序存储的 ⑵ 列优先顺序 (Column Major Order) 将数组元素按列向量排列, 第 j+1 个列向量紧接在第个列向量之后 j,a 的 m n 个元素按列优先顺序存储的线性序列为 : a 11, a 21,, a m1, a 12, a 22,, a m2,..., a n1, a n2,, a nm 在 FORTRAN 语言中, 数组就是按列优先顺序存储的 13

14 数组的顺序表示和实现 A m n a11 a21... am,1 m,2 m, n a 11 a a 1,n a 21 a a 2n a m1 a m2... a m-n a a a a1, n a 2, n... a 第 1 行第 2 行第 m 行行优先存储 14

15 数组的顺序表示和实现以上规则可以推广到多维数组的情况 : 优先顺序可规定为先排最右的下标, 从右到左, 最后排最左下标 : 列优先顺序与此相反, 先排最左下标, 从左向右, 最后排最右下标按上述两种方式顺序存储的序组, 只要知道开始结点的存放地址 ( 即基地址 ), 维数和每维的上下界, 以及每个数组元素所占用的单元数, 就可以将数组元素的存放地址表示为其下标的线性函数 15

16 数组的顺序表示和实现设有二维数组 A=(a ij ) m n, 若每个元素占用的存储单元数为 l( 个 ), LOC[a 11 ] 表示元素 a 11 的首地址, 即数组的首地址以行优先顺序存储第 1 行中的每个元素对应的 ( 首 ) 地址是 : LOC[a 1j ] = LOC[a 11 ] + (j-1) l j = 1, 2,, n 第 2 行中的每个元素对应的 ( 首 ) 地址是 : LOC[a 2j ] = LOC[a 11 ] + n l + (j - 1) l j = 1,2,, n 第 m 行中的每个元素对应的 ( 首 ) 地址是 : LOC[a mj ] = LOC[a 11 ] + (m - 1) n l + (j - 1) l j = 1, 2,, n 16

17 数组的顺序表示和实现由此可知, 二维数组中任一元素 a ij 的 ( 首 ) 地址是 : LOC[a ij ] = LOC[a 11 ] + [(i - 1) n + (j - 1)] l (1) i=1,2,,m j=1,2,,n 根据 (1) 式, 对于三维数组 A=(a ijk ) m n p, 若每个元素占用的存储单元数为 l ( 个 ),LOC[a 111 ] 表示元素 a 111 的首地址, 即数组的首地址以行优先顺序存储在内存中三维数组中任一元素 a ijk 的 ( 首 ) 地址是 : LOC(a ijk ) = LOC[a 111 ] + [(i-1) n p + (j-1) p + (k-1)] l (2) 17

18 数组的顺序表示和实现推而广之, 对 n 维数组 A=(aj 1 j 2 j ), 若每个元素占用的存 n 储单元数为 l ( 个 ),LOC[a 11 1 ] 表示元素 a 11 1 的首地址则以行优先顺序存储在内存中 n 维数组中任一元素 aj 1 j 2 j 的 ( 首 ) 地址是 : n LOC[aj 1 j 2 j ] = LOC[a n 11 1] + [(b 2 b n ) (j 1-1) + (b 3 b n ) (j 2-1) + + b n (j n-1-1) + (j n - 1)] l 18

19 数组的顺序表示和实现以列优先顺序存储第 1 列中的每个元素对应的 ( 首 ) 地址是 : LOC[a j1 ] = LOC[a 11 ] + (j - 1) l j = 1, 2,, m 第 2 列中的每个元素对应的 ( 首 ) 地址是 : LOC[a j2 ] = LOC[a 11 ] + m l + (j-1) l j = 1, 2,, m 第 n 列中的每个元素对应的 ( 首 ) 地址是 : LOC[a jn ] = LOC[a 11 ] + (n - 1) m l + (j - 1) l j = 1, 2,, m 由此可知, 二维数组中任一元素 a ij 的 ( 首 ) 地址是 : LOC[a ij ] = LOC[a 11 ] + [(i - 1) m + (j - 1)] l i = 1, 2,, n j = 1, 2,, m 19

20 数组的顺序表示和实现假设二维数组 A 的规模为 6X8, 每个元素用相邻的 6 个字节存储, 存储器按字节编址已知 A 的起始存储位置 ( 基地址 ) 为 1000, 计算 : (1) 数组 A 的体积 ( 即存储量 ) 6 x 8 x 6 = 288 (2) 数组 A 的最后一个元素 a 68 的第一个字节的地址 = 1282 (3) 按行存储时, 元素 a 25 的第一个字节的地址 (1 x 8 + 4) x 6 = 1072 (4) 按列存储时, 元素 a 58 的第一个字节的地址 (7 x 6 + 4) x 6 =

21 矩阵的压缩存储在科学与工程计算问题中, 矩阵是一种常用的数学对象, 在高级语言编制程序时, 简单而又自然的方法, 就是将一个矩阵描述为一个二维数组矩阵在这种存储表示之下, 可以对其元素进行随机存取, 各种矩阵运算也非常简单, 并且存储的密度为 1 a a... am a a a m a1n a2n... a mn 一个 m n 的矩阵 21

22 矩阵的压缩存储对于高阶矩阵, 若其中非零元素呈某种规律分布或者矩阵中有大量的零元素, 若仍然用常规方法存储, 可能存储重复的非零元素或零元素, 将造成存储空间的大量浪费对这类矩阵进行压缩存储 : 多个相同的非零元素只分配一个存储空间 ; 零元素不分配空间 22

23 矩阵的压缩存储特殊矩阵所谓特殊矩阵就是指非零元素或零元素的分布具有一定规律的矩阵常见的这类矩阵有 : 对称矩阵下 ( 上 ) 三角矩阵对角线矩阵等等 23

24 矩阵的压缩存储 -- 对称矩阵对称矩阵若一个 n 阶方阵 A=(a ij ) n n 中的元素满足性质 : a ij = a ji 1 i, j n 且 i j 则称 A 为对称矩阵, 如下图所示 A= A= a 11 a 21 a 22 a 31 a 32 a 33 a n1 a n2 a nn 对称矩阵示例 24

25 矩阵的压缩存储 -- 对称矩阵对称矩阵中的元素关于主对角线对称, 因此, 让每一对对称元素 a ij 和 a ji (i j) 分配一个存储空间, 则 n 2 个元素压缩存储到 n(n+1)/2 个存储空间, 能节约近一半的存储空间不失一般性, 假设按行优先顺序存储下三角形 ( 包括对角线 ) 中的元素设用一维数组 ( 向量 )sa[0 n(n+1)/2] 存储 n 阶对称矩阵, 如下图所示为了便于访问, 必须找出矩阵 A 中的元素的下标值 (i,j) 和向量 sa[k] 的下标值 k 之间的对应关系 K n(n-1)/2 n(n+1)/2 sa a 11 a 21 a 22 a 31 a 32 a 33 a n1 a n2 a nn 对称矩阵的压缩存储示例 25

26 矩阵的压缩存储 -- 对称矩阵若 i j:a i j 在下三角形中, 直接保存在 sa 中 a i j 之前的 i-1 行共有元素个数 : (i-1) = i (i-1) / 2 而在第 i 行上,a i j 之前恰有 j-1 个元素, 因此, 元素 a i j 保存在向量 sa 中时的下标值 k 之间的对应关系是 : k = i (i - 1) / 2 + j - 1 i j 若 i<j: 则 a ij 是在上三角矩阵中因为 a ij =a ji, 在向量 sa 中保存的是 a ji 依上述分析可得 : k = j (j - 1) / 2 + i - 1 i<j 对称矩阵元素 a i j 保存在向量 sa 中时的下标值 k 与 (i,j) 之间的对应关系是 : i (i-1)/2+j-1 当 i j 时 K= 1 i, j n j (j-1)/2+i-1 当 i<j 时 26

27 矩阵的压缩存储 -- 对称矩阵根据上述的下标对应关系, 对于矩阵中的任意元素 a ij, 均可在一维数组 sa 中唯一确定其位置 k; 反之, 对所有 : k=1, 2,, n(n+1)/2, 都能确定 sa[k] 中的元素在矩阵中的位置 (i,j) 称 sa[0 n(n+1)/2] 为 n 阶对称矩阵 A 的压缩存储 27

28 矩阵的压缩存储 -- 三角矩阵以主对角线划分, 三角矩阵有上三角和下三角两种上三角矩阵的下三角 ( 不包括主对角线 ) 中的元素均为常数 c( 一般为 0) 下三角矩阵正好相反, 它的主对角线上方均为常数, 如下图所示 a 11 a 12 a 1n c a 22 a 2n c c a nn a 11 a 21 c c a 22 c a n2 a nn a n1 (a) 上三角矩阵示例 (b) 下三角矩阵示例三角矩阵示例 28

29 矩阵的压缩存储 -- 三角矩阵三角矩阵中的重复元素 c 可共享一个存储空间, 其余的元素正好有 n(n+1)/2 个, 因此, 三角矩阵可压缩存储到向量 sa[0 n(n+1)/2] 中下三角矩阵元素 a i j 保存在向量 sa 中时的下标值 k 与 (i,j) 之间的对应关系是 : i (i-1)/2+j-1 当 i j 时 K= 1 i,j n n (n+1)/2 当 i<j 时上三角矩阵元素 a i j 保存在向量 sa 中时的下标值 k 与 (i,j) 之间的对应关系是 : K= i (i-1)/2+j-1 当 i j 时 1 i,j n n (n+1)/2 当 i>j 时 29

30 矩阵的压缩存储 -- 对角矩阵矩阵中, 除了主对角线和主对角线上或下方若干条对角线上的元素之外, 其余元素皆为零即所有的非零元素集中在以主对角线为了中心的带状区域中, 如图所示 A= a 11 a a 21 a 22 a a 32 a 33 a a n-1 n-2 a n-1 n-1 a n-1 n a n n-1 a n n 三对角矩阵示例 30

31 矩阵的压缩存储 -- 对角矩阵如上图三对角矩阵, 非零元素仅出现在主对角 (a i i,1 i n) 上主对角线上的那条对角线 (a i i+1,1 i n-1) 主对角线下的那条对角线上 (a i+1 i,1 i n-1) 显然, 当 i-j >1 时, 元素 a ij =0 由此可知, 一个 k 对角矩阵 (k 为奇数 )A 是满足下述条件 : 当 i-j >(k- 1)/2 时, a i j = 0 31

32 矩阵的压缩存储 -- 对角矩阵对角矩阵可按行优先顺序或对角线顺序, 将其压缩存储到一个向量中, 并且也能找到每个非零元素和向量下标的对应关系仍然以三对角矩阵为例讨论当 i=1,j=1 2, 或 i=n, j=n-1 n 或 1<i<n-1, j=i-1 i i+1 的元素 a ij 外, 其余元素都是 0 对这种矩阵, 当以按行优先顺序存储时, 第 1 行和第 n 行是 2 个非零元素, 其余每行的非零元素都要是 3 个, 则需存储的元素个数为 3n-2 K n-3 3n-2 sa a 11 a 12 a 21 a 22 a 23 a 32 a 33 a 34 a n n-1 a nn 三对角矩阵的压缩存储示例 32

33 矩阵的压缩存储 -- 对角矩阵如前图所示三对角矩阵的压缩存储形式数组 sa 中的元素 sa[k] 与三对角矩阵中的元素 a ij 存在一一对应关系, 在 a ij 之前有 i-1 行, 共有 3 (i-1)-1 个非零元素, 在第 i 行, 有 j-i+1 个非零元素, 这样, 非零元素 a ij 的地址为 : LOC[a i j ] = LOC[a 11 ] + [3 (i 1) 1 + (j i + 1)] l =LOC[a 11 ] + (2 i + j 3) l 上例中,a 34 对应着 sa[7], k = 2 i + j 3 = = 7, 称 sa[0 3 n-2] 是 n 阶三对角矩阵 A 的压缩存储上述各种特殊矩阵, 其非零元素的分布都是有规律的, 因此总能找到一种方法将它们压缩存储到一个向量中, 并且一般都能找到矩阵中的元素与该向量的对应关系, 通过这个关系, 仍能对矩阵的元素进行随机存取 33

34 稀疏矩阵稀疏矩阵 (Sparse Matrix): 对于稀疏矩阵, 目前还没有一个确切的定义设矩阵 A 是一个 n m 的矩阵中有 s 个非零元素, 设 δ=s/(n m), 称 δ 为稀疏因子, 如果某一矩阵的稀疏因子 δ 满足 δ 0.05 时称为稀疏矩阵 34

35 稀疏矩阵三元组表示法矩阵中的每个元素都是由行序号和列序号唯一确定的因此, 我们需要用三项内容表示稀疏矩阵中的每个非零元素, 即形式为 : (i,j,value) 其中,i 表示行序号,j 表示列序号,value 表示非零元素的值, 通常将它称为三元组 (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (4,6,2), (5,2,18), (6,7,-7), (7,4,-6) 35

36 稀疏矩阵三元组顺序表若以行序为主序, 稀疏矩阵中所有非 0 元素的三元组, 就可以得构成该稀疏矩阵的一个三元组顺序表相应的数据结构定义如下 : 三元组结点定义 #define MAX_SIZE 101 typedef int elemtype ; typedef struct { int row ; /* 行下标 */ int col ; /* 列下标 */ elemtype value; /* 元素值 */ } Triple ; 三元组顺序表定义 typedef struct { int rn ; /* 行数 */ int cn ; /* 列数 */ int tn ; /* 非 0 元素个数 */ Triple data[max_size] ; } TMatrix ; 36

37 稀疏矩阵 37

38 稀疏矩阵矩阵的运算包括矩阵的转置矩阵求逆矩阵的加减矩阵的乘除等在此, 先讨论在这种压缩存储结构下的求矩阵的转置的运算一个 m n 的矩阵 A, 它的转置 B 是一个 n m 的矩阵, 且 b[i][j]=a[j][i], 0 i n,0 j m, 即 B 的行是 A 的列,B 的列是 A 的行设稀疏矩阵 A 是按行优先顺序压缩存储在三元组表 a.data 中, 若仅仅是简单地交换 a.data 中 i 和 j 的内容, 得到三元组表 b.data,b.data 将是一个按列优先顺序存储的稀疏矩阵 B, 要得到按行优先顺序存储的 b.data, 就必须重新排列三元组表 b.data 中元素的顺序 38

39 稀疏矩阵的转置求转置矩阵的基本算法思想是 : 1 将矩阵的行列下标值交换即将三元组表中的行列位置值 i j 相互交换 ; 2 重排三元组表中元素的顺序即交换后仍然是按行优先顺序排序的算法思想 : 按稀疏矩阵 A 的三元组表 a.data 中的列次序依次找到相应的三元组存入 b.data 中每找转置后矩阵的一个三元组, 需从头至尾扫描整个三元组表 a.data 找到之后自然就成为按行优先的转置矩阵的压缩存储表示 39

40 稀疏矩阵的转置 40

41 稀疏矩阵的转置转置矩阵的算法如下 : void TransMatrix(TMatrix a, TMatrix b) { int p, q, col ; } b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ; /* 置三元组表 b.data 的行列数和非 0 元素个数 */ if (b.tn==0) printf( The Matrix A=0\n ); else{ } q=0; for (col=1; col<=a.cn ; col++) /* 每循环一次找到转置后的一个三元组 */ for (p=0 ;p<a.tn ; p++) /* 循环次数是非 0 元素个数 */ if (a.data[p].col==col) { b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value; q++ ; } 算法分析 : 本算法主要的工作是在 p 和 col 的两个循环中完成的, 故算法的时间复杂度为 O(cn x tn), 即矩阵的列数和非 0 元素的个数的乘积成正比 41

42 稀疏矩阵的转置一般传统矩阵的转置算法为 : for(col=1; col<=n ;++col) for(row=0 ; row<=m ;++row) b[col][row]=a[row][col] ; 其时间复杂度为 O(n m) 当非零元素的个数 tn 和 m n 同数量级时, 算法 TransMatrix 的时间复杂度为 O(m n 2 ) 由此可见, 虽然节省了存储空间, 但时间复杂度却大大增加所以上述算法只适合于稀疏矩阵中非 0 元素的个数 tn 远远小于 m n 的情况 42

43 稀疏矩阵的快速转置快速转置的算法算法思想 : 直接按照稀疏矩阵 A 的三元组表 a.data 的次序依次顺序转换, 并将转换后的三元组放置于三元组表 b.data 的恰当位置前提 : 若能预先确定原矩阵 A 中每一列的 ( 即 B 中每一行 ) 第一个非 0 元素在 b.data 中应有的位置, 则在作转置时就可直接放在 b.data 中恰当的位置因此, 应先求得 A 中每一列的非 0 元素个数附设两个辅助向量 num[ ] 和 cpot[ ] num[col]: 统计 A 中第 col 列中非 0 元素的个数 cpot[col] : 指示 A 中相应列第一个非 0 元素在 b.data 中的位置 43

44 稀疏矩阵的快速转置显然有位置对应关系 : cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2 col a.cn 44

45 十字链表对于稀疏矩阵, 当非 0 元素的个数和位置在操作过程中变化较大时, 采用链式存储结构表示比三元组的线性表更方便矩阵中非 0 元素的结点所含的域有 : 行列值行指针 ( 指向同一行的下一个非 0 元 ) 列指针( 指向同一列的下一个非 0 元 ) 其次, 十字交叉链表还有一个头结点, 结点的结构如图 5-10 所示 row col value down right 十字链表结点结构 rn cn tn down right (a) 结点结构 (b) 头结点结构 45

46 十字链表由定义知, 稀疏矩阵中同一行的非 0 元素的由 right 指针域链接成一个行链表, 由 down 指针域链接成一个列链表则每个非 0 元素既是某个行链表中的一个结点, 同时又是某个列链表中的一个结点, 所有的非 0 元素构成一个十字交叉的链表, 称为十字链表此外, 还可用两个一维数组分别存储行链表的头指针和列链表的头指针 46

47 十字链表十字链表结点的描述如下 : typedef struct Clnode { int row, col ; /* 行号和列号 */ elemtype value ; /* 元素值 */ struct Clnode *down, *right ; } OLNode ; /* 非 0 元素结点 */ typedef struct { int rn; /* 矩阵的行数 */ int cn; /* 矩阵的列数 */ int tn; /* 非 0 元素总数 */ OLNode *rchead ; OLNode *chead ; } CrossList ; 47

48 广义表广义表是线性表的推广和扩充, 在人工智能领域中应用十分广泛在前面的内容中, 我们把线性表定义为 n(n 0 ) 个元素 a 1, a 2,, a n 的有穷序列, 该序列中的所有元素具有相同的数据类型且只能是原子项 (Atom) 所谓原子项可以是一个数或一个结构, 是指结构上不可再分的若放松对元素的这种限制, 容许它们具有其自身结构, 就产生了广义表的概念广义表 (Lists, 又称为列表 ): 是由 n(n 0) 个元素组成的有穷序列 : LS=(a 1,a 2,,a n ) 其中 a i 或者是原子项, 或者是一个广义表 LS 是广义表的名字,n 为它的长度若 a i 是广义表, 则称为 LS 的子表 48

49 广义表的定义线性表的推广, 表中的元素可以是表 LS = ( a1, a2,, an ) A = () 习惯上 : 原子用小写字母, 子表用大写字母 B = ( e ) C = ( a, ( b, c, d ) ) D = ( A, B, C ) E = ( a, E ) 49

50 广义表的定义广义表的长度 : 元素的数目广义表的表头 : 非空广义表中第一个元素广义表的表尾 : 除表头元素之外, 其余元素构成的表广义表的深度 : 广义表中括号的重数长度表头表尾深度 A=() 0 1 B=(e) 1 e () 1 C=(a,(b,c,d)) 2 a ((b,c,d)) 2 D=(A,B,C) 3 A (B,C) 3 E=(a,E) 2 a (E) 无穷大 50

51 广义表的定义广义表及其示例广义表表长 n 表深 h A=() 0 0 B=(e) 1 1 C=(a,(b,c,d)) 2 2 D=(A,B,C) 3 3 D A B C e a b c d 广义表的图形表示 51

52 广义表的定义广义表的重要结论 : 广义表的元素可以是原子, 也可以是子表, 子表的元素又可以是子表, 即广义表是一个多层次的结构广义表可以被其它广义表所共享, 也可以共享其它广义表广义表共享其它广义表时通过表名引用广义表本身可以是一个递归表根据对表头表尾的定义, 任何一个非空广义表的表头可以是原子, 也可以是子表, 而表尾必定是广义表 52

53 广义表的存储结构由于广义表中的数据元素具有不同的结构, 通常用链式存储结构表示, 每个数据元素用一个结点表示因此, 广义表中就有两类结点 : 一类是表结点, 用来表示广义表项, 由标志域, 表头指针域, 表尾指针域组成 ; 另一类是原子结点, 用来表示原子项, 由标志域, 原子的值域组成只要广义表非空, 都是由表头和表尾组成, 即一个确定的表头和表尾就唯一确定一个广义表标志 tag=0 原子的值标志 tag=1 表头指针 hp 表尾指针 tp (a) 原子结点 (b) 表结点广义表的链表结点结构示意图 53

54 广义表的存储结构相应的数据结构定义如下 : typedef struct GLNode { int tag ; /* 标志域, 为 1: 表结点 ; 为 0 : 原子结点 */ union { elemtype value; /* 原子结点的值域 */ struct {struct GLNode *hp, *tp ; } ptr ; } Gdata ; } GLNode ; /* 广义表结点类型 */ 54

55 广义表的存储结构例 : 对 A=(),B=(e),C=(a, (b, c, d) ),D=(A, B, C),E=(a, E) 的广义表的存储结构如图所示 55

56 广义表的存储结构对于上述存储结构, 有如下几个特点 : (1) 若广义表为空, 表头指针为空 ;hp 指向广义表的表头结点 ( 或为原子结点, 或为表结点 ),tp 指向广义表的表尾 ( 表尾为空时, 指针为空, 否则必为表结点 ) (2) 这种结构求广义表的长度深度表头表尾的操作十分方便 (3) 表结点太多, 造成空间浪费 56

57 谢谢! 57

Microsoft PowerPoint - ds-1.ppt [兼容模式]

Microsoft PowerPoint - ds-1.ppt [兼容模式] http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说明总学时 : 72( 学时 )= 56( 课时 )+ 16( 实验 ) 行课时间 : 第 1 ~14 周周学时 : 平均每周 4 学时上机安排待定考试时间 : 课程束第 8 11 12 章的内容为自学内容 ; 目录中标有

串 零个或多个字符组成的有限序列 将元素类型限制为字符线性表 具有相同类型的数据元素的有限序列 将元素类型扩充为线性表 ( 多维 ) 数组 线性表中的数据元素可以是线性表 2

串零个或多个字符组成的有限序列将元素类型限制为字符线性表具有相同类型的数据元素的有限序列将元素类型扩充为线性表 ( 多维 ) 数组线性表中的数据元素可以是线性表 2