西南科技大学：《数据结构》课程教学资源（PPT课件讲稿）第五章 数组和串

5.1数组 DS 一维数组的示例 计算机学院信息教研室 学a35274918605477834102 乙*

5.1 数组 ◼一维数组的示例 计 算 机 学 院 信 息 教 研 室 DS

一维数组的特点 DS ◆连续存储的线性聚集(别名向量) 算◆除第一个元素外,其他每一个元素 机有一个且仅有一个直接前驱。 院◆除最后一个元素外,其他每一个元 信素有一个且仅有一个直接后继。 自 教◆只要知道一个数组元素在数组中是 研第几个就可直接存取这个数组元素 室

计 算 机 学 院 信 息 教 研 室 DS 一维数组的特点 连续存储的线性聚集（别名 向量） 除第一个元素外，其他每一个元素 有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元 素有一个且仅有一个直接后继。 只要知道一个数组元素在数组中是 第几个,就可直接存取这个数组元素

4◆一维数组 i=0时 Loci LOC(i-1)+l,i>0时 01 3456789 a35274918605477834102 LOC (a ) =LoC (a; -1)+/=a+i*/

一维数组    − +  = = ( ) , 0 时 α , 0 时 ( ) LOC i l i i LOC i 1 LOC ( ai ) = LOC ( ai -1 ) + l =α+ i*l

DS 维数组的数组元素可以是基本数据类 型可以是复杂数据类型当基本类型也 计是数组时一维数组扩充为二维数组(矩 算阵) 机 Ik]直接前驱直接后驱 行的方向a[j[k-1 a[lkk+1 点列的方向ki_ai+ki 教 沿矩阵边缘无直接前驱和直接后驱的情 研况 室

计 算 机 学 院 信 息 教 研 室 DS 一维数组的数组元素可以是基本数据类 型,可以是复杂数据类型. 当基本类型也 是数组时,一维数组扩充为二维数组(矩 阵). A[j][k] 直接前驱 直接后驱 行的方向 a[j][k-1] a[j][k+1] 列的方向 a[j-1][k] a[j+1][k] 沿矩阵边缘:无直接前驱和直接后驱的情 况

二维数组(矩阵)三维数组 m1=5m2=4 n3 a[2][2] m2 3×4×6 2×6 M2 n1 m3 a[3][212] 行向量71页向量下标 列)向量下标行向量下标 列向量下k

二维数组(矩阵) 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

二维数组(矩阵)三维数组 m1=5m2=4 n3 a[2][2] m2 3×4×6 2×6 M2 n1 m3 a[3][212] 行向量71页向量下标 列)向量下标行向量下标 列向量下k

二维数组(矩阵) 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

二维数组 00a0[1]a[012 a01[m-1 al0a[1[1a(12 al1lm-1 a+a2101a(21]21a12lm-1 (a[n-1][0] a[n-1]1] an-1][2].a[n-1]m-13 行优先LOC(ij)= =a+(i*m+j*

• 二维数组                 − − − − − − − − = [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] 1 0 1 1 1 2 1 1 2 0 2 1 2 2 2 1 1 0 1 1 1 2 1 1 0 0 0 1 0 2 0 1 a n a n a n a n m a a a a m a a a a m a a a a m a          行优先 LOC ( i, j ) = = a + ( i * m + j) * l

安全类数组的提出 DS 算 机考虑了数足下标越界问题, 院且可以重新定义数组元素个数 自 教 研 室

安全类数组的提出 考虑了数足下标越界问题， 且可以重新定义数组元素个数 计 算 机 学 院 信 息 教 研 室 DS

5.3特殊矩阵的压缩存储 DS 科学和工程计算问题中经常用到矩阵运算 矩阵数据元素一般用二维数组来存储 算 机3591 当遇到特殊矩阵时, 为了降低空间复杂度 院5847可考虑对矩阵进行压 自 缩存储--只存储其中 教9430数值不同的部分 研 室1701

5.3 特殊矩阵的压缩存储 科学和工程计算问题中经常用到矩阵运算， 矩阵数据元素一般用二维数组来存储 当遇到特殊矩阵时， 为了降低空间复杂度， 可考虑对矩阵进行压 缩存储----只存储其中 数值不同的部分 计 算 机 学 院 信 息 教 研 室 DS 3 5 9 1 5 8 4 7 9 4 3 0 1 7 0 1

§5.3特殊矩阵的压缩存储 Amnm保存mn个数据 上三角 对称 矩阵359矩阵 0101720 5847 00 9 9430 0003 70

§5.3 特殊矩阵的压缩存储 A[m][n] 保存m*n个数据 1 5 11 18 0 10 17 20 0 0 1 9 0 0 0 3 3 5 9 1 5 8 4 7 9 4 3 0 1 7 0 1 上三角 矩阵 对称 矩阵