《数据结构》课程教学资源（PPT课件讲稿）第五章 多维数组与广义表

第五章多维数组与广义表 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 …