《数组与广义表》PPT课件.ppt

《《数组与广义表》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组与广义表主讲：薛春艳第5章数组和广义表数组的定义和运算1数组的顺序存储和实现2特殊矩阵的压缩存储3广义表的存储结构4【定义】数组是线性表的结构上的扩展。即线性表中的数据元素本身也是一个数据结构。数组可以看成是数据元素本身就是线性表的线性表。5.1数组的定义和运算一维数组是一个线性表，其每个元素是一个不可分割的最小单位。二维数组可以看成是一个线性表，线性表中的每个数据元素也是一个线性表。n维数组是一个线性表，其每个数据元素是一个n-1维的数组。Am×n=a11a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am

2、1am2┅amj┅amnA=(12┅j┅n)我们可以把二维数组看成一个线性表：A=(12…j…n)，其中j（1≤j≤n）本身也是一个线性表，称为列向量。矩阵Am×n看成包含n个列向量的线性表，即j=(a1j,a2j,…,amj)Am×n=a11a12…a1j…a1na21a22…a2j…a2n┇┇ai1ai2…aij…ain┇┇am1am2…amj…amnB‖12┇i┇m我们还可以将数组Am×n看成包含m个行向量的线性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一个线性表，称为行向量，即：i=（a

3、i1，ai2，…，aij，…，ain）。对于数组A，一旦给定其维数n及各维长度bi（1≤i≤n），则该数组中元素的个数和元素之间的关系就不再发生变化了，既不可以对数组做插入和删除操作，也不涉及移动元素操作。数组的特点数组中的数据元素具有相同的数据类型。数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素。数组中的元素个数是固定的。【数组的特点】数组是一组有固定个数的数据元素的集合。由于数组中的数据元素的个数是固定的，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法的位置插入和删除一个元素，对于数组的操作一般只有两类：【数

4、组的操作——两类】（1）给定下标，存取对应位置的元素值；（2）给定下标，修改对应位置的元素值。因此，数组的操作主要是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。其实质就是地址计算问题。数组的运算数组的顺序存储和实现由于在数组中数据元素的个数是固定的，因此对于数组而言，采用顺序存储表示比较适合。在计算机中，内存储器的结构是一维的。对于一维数组可直接采用顺序存储。用一维的内存存储表示多维数组，就必选按某种次序将数组中的元素排成一个线性序列，然后将这个线性序列存放在一维的内存储器中，这就是数组的顺序存储结构。数组的顺序存储结构有两种：

5、一种是按行序存储，另一种是按列序存储。a00...a0,n-1a10...a1,n-1...aij...am-1,n-1第1行第2行……a00a01a02……a0,n-1a10a11a12……a1,n-1Am×n=…………am-1,0am-1,1am-1,2……am-1,n-11.行序为主序分配方式a00a02a03……a0,n-1a10a11a12……a1,n-1a20a21a22……a2,n-1A[m][n]=……ai,0ai,1……aij……am-1,0am-1,1am-1,2……am-1,n-1i行若知道第一个元素的存储地址Loc(a00),

6、如果每个元素占size个存储单元，则任意元素aij的地址计算公式为：Loc[i,j]=Loc[0,0]+(n×i+j)×size数组元素地址=数组首地址+数组首地址与所求元素之间的距离该元素前面的数据元素个数×每个数据元素占的存储单元二维数组Am×n中任一元素ai,j的存储位置:Loc(i,j)=Loc(0,0)+[n×i+j]×sizea0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2size已知：m=2，n=3，Loc(0,0)=100，i=1，j=1，size=4Loc(1,1)=Loc(0,0)+

7、[3×1+1]×4=100+4*4=116a0,1a0,0a0,2a1,0a1,1a1,21001041081121161202.列序为主序分配方式a00...am-1,0a01...an-1,1...aij...am-1,n-1第1列第2列……a00a01a02……a0,n-1a10a11a12……a1,n-1Am×n=…………am-1,0am-1,1am-1,2……am-1,n-1Loc(aij)=Loc(a00)+[mj+i]size若知道第一个元素的存储地址Loc(a11),如果每个元素占size个存储单元则任意元素aij的地址计算公式为

8、：a00a01a02……a0,n-1a10a11a12……a1,n-1a20a21a22……a2,n-1……