北京师范大学《数据结构——C语言描述》教学课件：第五章 数组与广义表

第5章数组与广义表

第５章 数组与广义表

第5章数 数组 数组的定义 组与广义 数组是以同型元素为数据元素的线性表。 数组以下标作为元素的标识,通过下标访问各个 表 素 多维数组 多维数组是以同型线性表为数据元素的线性表。 这里的同型指得是具有相同元素类型和相同的表 长

第 ５ 章 数 组 与 广 义 表 一、数组 ◼ 数组的定义 – 数组是以同型元素为数据元素的线性表。 – 数组以下标作为元素的标识，通过下标访问各个 元素。 ◼ 多维数组 – 多维数组是以同型线性表为数据元素的线性表。 – 这里的同型指得是具有相同元素类型和相同的表 长

5以一个3维数组M[4]5][3为例,如下图所示: 章 数 组 与 义 表 M[0][0][0] M|3 M2 M[0][3][2] MII

第 ５ 章 数 组 与 广 义 表 M[0][0][0] M[0][3][2] M[0] M[1] M[2] M[3] M[0][3] 以一个3维数组M[4][5][3]为例，如下图所示：

第5章数 数组 多维数组的实现 组与广义 用一维顺序结构线性表实现多维数组 表 struct Array E1 etype* buffer;//数据区 int dims /维数 in七*; /各维长度

第 ５ 章 数 组 与 广 义 表 一、数组 ◼ 多维数组的实现 – 用一维顺序结构线性表实现多维数组 struct Array { ElemType *buffer; // 数据区 int dims; // 维数 int *L; // 各维长度 };

第设二3维数组A[4][2][3], 5存贮在一个顺序线性表s中 A000 001 002 章结构如下所示 P010 011 A 012 数 A 100 101 A 102 组 A 11 111 A 112 与 A A,A 21 A 2n2 A200A201 P202 义 A A101 A 1∩2 表 A 210 A 211 A 212 A 000 001A002 A010A011A012 A 300A 3012302 A 310 A 311 A 312 2223 A0020012002A01020112012A100A101 311 312

第 ５ 章 数 组 与 广 义 表 设一3维数组A[4][2][3]， 存贮在一个顺序线性表S中， 结构如下所示： 0 1 2 3 4 5 6 7 ... 22 23 A000 A001 A002 A010 A011 A012 A100 A101 ... A311 A312 A310 A311 A312 A300 A301 A302 A210 A211 A212 A200 A201 A202 A110 A111 A112 A100 A101 A102 A010 A011 A012 A000 A001 A002 A310 A311 A312 A300 A301 A302 A210 A211 A212 A200 A201 A202 A110 A111 A112 A100 A101 A102 A010 A011 A012 A000 A001 A002

第5章数 数组 维下标与多维下标之间的换算 组与广义 设多维数组A(10,111n-1),存贮在一个顺序线性表s中。 从一维下标换算到多维下标 表 S(i)→A(i0,i1,…,in-1) 从多维下标换算到—维下标 A(i,i1,.,in-1)→S(i) ndex (015 2n-1 o·41·l2…l21+1·l2·l3…b21+…+in-2·l21+in-1 ∑(·∏)+n1 =k+1

第 ５ 章 数 组 与 广 义 表 一、数组 ◼ 一维下标与多维下标之间的换算 – 设多维数组A(l0,l1,..,ln-1)，存贮在一个顺序线性表S中。 ◼ 从一维下标换算到多维下标 – S(i) → A(i0,i1,..,in-1) ◼ 从多维下标换算到一维下标 – A(i0,i1,..,in-1) → S(i)

第5章数 数组 多维数组的基本操作 组与广义 初始化和撤销 表 按下标访问元素A(i,1,i2

第 ５ 章 数 组 与 广 义 表 一、数组 ◼ 多维数组的基本操作 – 初始化和撤销 – 按下标访问元素A( i0, i1, i2, .. in-1 )

二、稀跪矩阵 5章数 定义 组与广义 含有较多零元的矩阵称为稀疏矩阵。 稀疏矩阵的压缩存贮 只存贮非零元,以减少存贮空间。 表 00501 020000 000040 000307 000100

第 ５ 章 数 组 与 广 义 表 二、稀疏矩阵 ◼ 定义 – 含有较多零元的矩阵称为稀疏矩阵。 ◼ 稀疏矩阵的压缩存贮 – 只存贮非零元，以减少存贮空间。                 0 0 0 1 0 0 0 0 0 3 0 7 0 0 0 0 4 0 0 2 0 0 0 0 0 0 5 0 1 1

二、稀跪矩阵 5章数 特殊矩阵 组与广义 非零元的分布非常有规律。 表 将非零元存贮于一维空间中,根据非零元 的分布规律建立矩阵行列与一维下标之间 的映射关系

第 ５ 章 数 组 与 广 义 表 二、稀疏矩阵 ◼ 特殊矩阵 – 非零元的分布非常有规律。 – 将非零元存贮于一维空间中，根据非零元 的分布规律建立矩阵行列与一维下标之间 的映射关系

第 5 章以三角阵为例 数 组 与 0 0 0 0 义 0 表 Mme(2)(i+1) ji≥j 0 1 3 5 n(n+1)/2-1 22 an-1,n-1

第 ５ 章 数 组 与 广 义 表                 −1,0 −1.1 −1,2 −1, −1 20 21 22 10 11 00 0 0 0 0 0 0 n n n n n a a a a a a a a a a          0 1 2 3 4 5 ... n(n+1)/2-1 a00 a10 a11 a20 a21 a22 ... an-1,n-1 以三角阵为例： i j j i j i i Index i j +   + = 2 ( 1) ( , )