第五章多维数组与广义表 2007.9
2007.9 第五章 多维数组与广义表
●51多维数组 5.1.1多维数组的定义 5.1.2多维数组的存储 ●52矩阵的压缩存储 5.2.1特殊矩阵 5.2.2稀疏矩阵 ●53广义表
5.1 多维数组 5.1.1多维数组的定义 5.1.2多维数组的存储 5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵 5.3 广义表
51多维数组
5.1 多维数组
511多维数组的定义 维数组 维数组可以看成是一个线性表或一个向量,它在计算机 内是存放在一块连续的存储单元中,适合于随机查找。 有一个直接前驱和一个直接后继 二维数组 二维数组可以看成是向量的推广。 有两个直接前驱和两个直接后继 a0a01 ac a10 all a1 A am-10am-11
5.1.1多维数组的定义 一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机 内是存放在一块连续的存储单元中，适合于随机查找。 有一个直接前驱和一个直接后继 二维数组 二维数组可以看成是向量的推广。 有两个直接前驱和两个直接后继 a00 a01 …… a0n-1 a10 a11 …… a1n-1 …………………………. A= am-1 0 am-1 1 …… am-1 n-1
维数组 最多可有三个直接前驱和三个直接后继 ●多维数组 把三维以上的数组称为多维数组, 可有多个直接前驱和多个直接后继 是一种非线性结构
三维数组 最多可有三个直接前驱和三个直接后继 多维数组 把三维以上的数组称为多维数组， 可有多个直接前驱和多个直接后继 是一种非线性结构
在C语言中的描述 pedef int datatype datatype array l(NI datatype array2 [M[N] datatype array 3[XYz 数组一旦被定义,它的维数和维界就不再改 变。因此,数组只有存取元素和修改元素值的 操作
在C语言中的描述 typedef int datatype; datatype array1[N]; datatype array2[M][N]; datatype array3[X][Y][Z]; 数组一旦被定义，它的维数和维界就不再改 变。因此，数组只有存取元素和修改元素值的 操作
5.2多维数组的存储 考虑问题的基本出发点: 计算机的内存结构是一维的。因此用一维内存来存多 维数组,就必须按某种次序将数组元素排成线性序列。 数组一旦建立,结构中的元素个数和元素间的关系就 不再发生变化。因此,一般都是采用顺序存储的方法 来表示数组
考虑问题的基本出发点： 计算机的内存结构是一维的。因此用一维内存来存多 维数组，就必须按某种次序将数组元素排成线性序列。 数组一旦建立，结构中的元素个数和元素间的关系就 不再发生变化。因此，一般都是采用顺序存储的方法 来表示数组。 5.2 多维数组的存储
两种顺序存储方式 行优先顺序—将数组元素按行排列 在 PASCAL、C语言中,数组就是按行优先顺序存储的。 列优先顺序—一将数组元素按列向量排列 在FO○ RTRAN语言中,数组就是按列优先顺序存储的。 推广到多维数组的情况 行优先顺序:先排最右下标,从右到左,最后排最左下标 列优先顺序:先排最左下标,从左向右,最后排最右下标
两种顺序存储方式 行优先顺序——将数组元素按行排列 在PASCAL、C语言中，数组就是按行优先顺序存储的。 列优先顺序——将数组元素按列向量排列 在FORTRAN语言中，数组就是按列优先顺序存储的。 推广到多维数组的情况： 行优先顺序：先排最右下标，从右到左，最后排最左下标 列优先顺序：先排最左下标，从左向右，最后排最右下标
计算机如何实现数组元素的随机存取? 如何计算数组元素的地址? 按上述两种方式顺序存储的序组,只要知道 开始结点的存放地址(即基地址) 维数 每维的上、下界 每个数组元素所占用的单元数, 就可以将数组元素的存放地址表示为其下标的线性函 数。因此,数组中的任一元素可以在相同的时间内存 取,即顺序存储的数组是一个随机存取结构
计算机如何实现数组元素的随机存取？ 按上述两种方式顺序存储的序组，只要知道： 开始结点的存放地址（即基地址）， 维数 每维的上、下界 每个数组元素所占用的单元数， 就可以将数组元素的存放地址表示为其下标的线性函 数。因此，数组中的任一元素可以在相同的时间内存 取，即顺序存储的数组是一个随机存取结构。 如何计算数组元素的地址？
如何计算数组元素的地址? 内存内存 0 维数组m0a1n2|-mn ao a00 维数组 ao1 On-1 a1 三维数组a0a ap aon n a10 aIn a dol aio al Listsize -1 a-10 am-11 m-I n1
一维数组 二维数组 三维数组 如何计算数组元素的地址？ 内存 0 ListSize -1 a0 a1 a2 … an a00 a01 …… a0n-1 a10 a11 …… a1n-1 …………………………. am-1 0 am-1 1 …… a m-1 n-1 a00 a01 …… a0n-1 a10 a11 …… a1n-1 …………………………. am-1 0 am-1 1 …… a m-1 n-1 a0 a1 … an 内存 a00 … a0n a10 … a1n …