数据结构教案（苏2）.ppt

《数据结构教案（苏2）.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表数组是一种人们非常熟悉的数据结构，几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型。数组这种数据结构可以看成是线性表的推广。科学计算中涉及到大量的矩阵问题，在程序设计语言中一般都采用数组来存储，被描述成一个二维数组。但当矩阵规模很大且具有特殊结构(对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等)，为减少程序的时间和空间需求，采用自定义的描述方式。广义表是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。5.1数组的定义数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标

2、，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值，如此类推。数组是由n(n>1)个具有相同数据类型的数据元素a1，a2，…，an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。◆数组中的数据元素具有相同数据类型。◆数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。◆数组中的数据元素个数是固定的。5.1.1数组的抽象数据类型定义1.抽象数据类型定义ADTArray{数据对象：ji=0,1,…,bi-1,1,2,…,n;D={aj1j2…jn

3、n>0称为数组的维数，bi是数组第i维的长度，ji是数

4、组元素第i维的下标，aj1j2…jn∈ElemSet}数据关系：R={R1,R2,…,Rn}Ri={

5、0≦jk≦bk-1，1≦k≦n且k≠i，0≦ji≦bi-2，aj1j2…ji+1…jn∈D}基本操作：……}ADTArray由上述定义知，n维数组中有b1b2…bn个数据元素，每个数据元素都受到n维关系的约束。2.直观的n维数组以二维数组为例讨论。将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表。设二维数组A=(aij)mn，则A=(α1，α2，…，αp)(p=m或n)其中

6、每个数据元素αj是一个列向量(线性表)：αj=(a1j，a2j，…，amj)1≦j≦n或是一个行向量：αi=(ai1，ai2，…，ain)1≦i≦m如图5-1所示。a11a12…a1na21a22…a2n……………am1am2…amnA=……………A=a11a12…a1na21a22…a2nam1am2…amna11a21┆am1a12a22┆am2a1na2n┆amn┆┆┆A=图5-1二维数组图例形式(a)矩阵表示形式(b)行向量的一维数组形式(c)列向量的一维数组形式5.2数组的顺序表示和实现数组一般不做插入和删除操作，也就是说，数组一旦建立，结

7、构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。问题：计算机的内存结构是一维(线性)地址结构，对于多维数组，将其存放(映射)到内存一维结构时，有个次序约定问题。即必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放到内存中。二维数组是最简单的多维数组，以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。通常有两种顺序存储方式⑴行优先顺序(RowMajorOrder)：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。对二维数组，按行优先顺序存储的线性序列为：a11,a12,…,a1

8、n,a21,a22,…a2n,……,am1,am2,…,amnPASCAL、C是按行优先顺序存储的，如图5-2(b)示。⑵列优先顺序(ColumnMajorOrder)：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anmFORTRAN是按列优先顺序存储的，如图5-2(c)。图5-2二维数组及其顺序存储图例形式a11a12…a1na21a22…a2n……………am1am2…amnA=(a)二维数组的表示形式(b)

9、行优先顺序存储(c)列优先顺序存储a11a12…a1n第1行a21a22…a2n第2行am1am2…Amn第m行┆┆……a11a21…am1第1列a12a22…am2第2列a1ma2m…amn第n列┆┆……设有二维数组A=(aij)mn，若每个元素占用的存储单元数为d(个)，LOC[a11]表示元素a11的首地址，即数组的首地址。1.以“行优先顺序”存储⑴第1行中的每个元素对应的(首)地址是：LOC[a1j]=LOC[a11]+(j-1)dj=1,2,…,n(2)第2行中的每个元素对应的(首)地址是：LOC[a2j]=LOC[a11]+nd+(

10、j-1)dj=1,2,…,n………⑶第m行中的每个元素对应的(首)地址是：LOC[amj]=LOC[a11