数组和广义表实用教案.pptx

(dìngyì)
数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有(jùyǒu)某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。
由于数组中各元素具有统一的类型(lèixíng)，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是一维数组的推广。
第1页/共57页
第一页，共57页。
例如(lìrú)，二维数组A：
(dìngyì)(续)
Am×n=
a11 a12 … a1n
a21 a22 … a2n
… … … …
am1 am2 … amn
二维数组A可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。
数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改(xiūgǎi)元素值的操作。
第2页/共57页
第二页，共57页。
由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序(cìxù)将数组元素排成一列序列，然后将这个线性序列存放在存储器中。
数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般采用顺序存储的方法来表示数组。
数组的顺序(shùnxù)表示
第3页/共57页
第三页，共57页。
行优先顺序(shùnxù)或以行为主序存储方式：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序(shùnxù)存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn
在PASCAL、C等语言中，数组就是按行优先顺序(shùnxù)存储的。
数组的顺序(shùnxù)表示(续)
Am×n=
a11 a12 … a1n
a21 a22 … a2n
… … … …
am1 am2 … amn
LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d
第4页/共57页
第四页，共57页。
列优先顺序(shùnxù)或以列为主序存储方式：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序(shùnxù)存储的线性序列为：
a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm
在FORTRAN语言中，数组按列优先顺序(shùnxù)存储。
数组的顺序(shùnxù)表示(续)
Am×n=
a11 a12 … a1n
a21 a22 … a2n
… … … …
am1 am2 … amn
LOC(aij)=LOC(a11)+[(j-1)*m+i-1]*d
第5页/共57页
第五页，共57页。
行优先顺序——先排最右的下标，从右到左，最后(zuìhòu)排最左下标。
列优先顺序——先排最左下标，从右向左，最后(zuìhòu)排最左下标。
例如：三维数组Am*n*p以行优先方式顺序存储，则
LOC(aijk)=LOC(a111)+[(i-1)*m*n+
(j-1)*n+(k-1)]*d
数组的顺序(shùnxù)表示(续)
第6页/共57页
第六页，共57页。
只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素(yuán sù)所占用的单元数，就可以将数组元素(yuán sù)的存放地址表示为其下标的线性函数。因此，数组中的任一元素(yuán sù)可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
数组存储(cún chǔ)的特点
第7页/共57页
第七页，共57页。
压缩存储：为多个(duō ɡè)值相同的非零元素只分配一个存储空间；对零元素不分配空间。
矩阵的压缩(yā suō)存储
第8页/共57页
第八页，共57页。
特殊矩阵：非零元素按照一定(yīdìng)的规律分布。
(jǔ zhèn)的压缩存储
a1,1 a1,2 … a1,n
a2,1 a2,2 … a2,n
… … ai,j …
an,1 an,2 … an,n
a