Ch04 数组、串及广义表01.ppt

第四章 数组、 串与广义表 数据结构电子教案 第四章 数组、串与广义表 一维数组与多维数组 特殊矩阵 稀疏矩阵 字符串 广义表 一维数组 定义 数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。 一维数组的示例 在高级语言中的一维数组只能按元素的下标直接存取数组元素的值。 一维数组的定义和初始化 #include iostream.h void main ( ) { int a[3] = { 3, 5, 7 }, *elem, *p, i; // 静态数组 for (i = 0; i 3; i++) cout a[i] endl; p = elem = new int[3]; // 动态数组 for (i = 0; i 3; i++) cin elem[i]; while (elem) { cout *elem endl; elem++; } delete p; } 多维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k 数组的连续存储方式 一维数组 二维数组 一维数组常常被称为向量（Vector）。 二维数组 A[m][n] 可看成是由 m 个行向量组成的向量，也可看成是由 n 个列向量组成的向量。 一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。 同理，一个三维数组类型可以定义为其数据元素为二维数组类型的一维数组类型。 依次类推。 静态定义的数组，其维数和各维的维界不再改变，在编译时静态分配存储空间。一旦数组空间用完则不能扩充。在生存期结束时系统会自动释放其所占的空间。 动态定义的数组，其维界不在说明语句中显式定义，而是在程序运行中通过 new 动态分配和初始化，在对象销毁时通过 delete 动态释放。 用一维内存来表示多维数组，就必须按某种次序将数组元素排列到一个序列中。 二维数组的动态定义和初始化 #include iostream.h ………… int **A; int row = 3, col = 3; int i, j; A = new int *[row]; for (i = 0; i row; i++) // 行指针初始化 A[i] = new int [col]; for (i = 0; i row; i++) // 访问A[i][j] for (j = 0; j col; j++) cin A[i][j]; 二维数组的动态定义和初始化 ………… for (i = 0; i row; i++) // 释放二维动态数组 delete A[i]; delete A;   三维数组 各维元素个数（维界）为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储地址： （按页／行／列存放） LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l n 维数组 各维的维界为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储地址： LOC ( i1, i2, …, in ) = a + ( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * l 特殊矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。 对称矩阵 三对角矩阵 对称矩阵的压缩存储 设有一个 n ? n 的对称矩阵 A。 为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。 数组 B 共有 n + ( n - 1 ) + ??? + 1 = n*(n+1)/2 个元素。（全部存储要 n2 个元素） 三对角矩阵的压缩存储 三对角矩阵中除主对角