第4章数组和广义表ppt课件.ppt

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

1、第四章数组和广义表★数组的逻辑结构一个二维数组的类型定义如下：其中c,d设为1，数组可表示为：A:array[c..m][d..n]ofElemTypeA=a11a12…a1na21a22…a2n…………am1am2…amn它可以看成是由m个行向量或n个列向量组成的线性表。即，二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。类似地，一个三维数组可以看成是数据元素为二维数组的线性表一个n维数组可视为其数据元素为n-1维数组的线性表。★数组的顺序存储分配a1a2a3…an-1anLoc(ai)=Loc(a1)+(i-1)kA[1:n]=(a1,a2,a3,…

2、,an)若已知每个元素占k个存储单元，并且知道第一个元素的存储地址Loc(a1),则一.一维数组A[1:n]a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn行序为主序分配方式列序为主序分配方式二.二维数组A[1:m][1:n]a11...a1na21...a2na31...aij...amn第1行第2行……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn1.行序为主序分配方式a11a12a13……a1na21a22a23……a2na31a32a33……a3

3、nA[1:m][1:n]=…………aij……am1am2am3……amni-1行若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11),则Loc(aij)=Loc(a11)+(i1)nk+(j1)k=Loc(a11)+[(i1)n+(j1)]ka11...am1a12...am2a13...aij...amn第1列第2列……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn2.列序为主序分配方式a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:m

4、][1:n]=…………aij……am1am2am3……amnj-1列若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11),则Loc(aij)=Loc(a11)+(j1)mk+(i1)k=Loc(a11)+[(j1)m+(i1)]k9数组A[0…5][0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则A[5][5]的地址是（）。Ａ.1175Ｂ.1180Ｃ.1205Ｄ.1210课堂练习A已知二维数组A[m][n]采用行序为主的方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0]),则A[i

5、][j]的地址是。LOC(A[0][0])+(i*n+j)*ka11a12a13……a1na21a22a23……a2nm=…………am1am2am3……amnA[1:m][1:n]所谓压缩存储是指为多个值相同的元素,或者位置分布有规律的那些元素分配尽可能少的存储空间，而对0元素一般情况下不分配存储空间。传统做法★矩阵的压缩存储a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:n][1:n]=…………an1an2an3……ann传统做法：定义一个二维数组A[1:n,1:n]一.对称矩阵的压缩存储一个n阶矩阵A的元素满足性质aij=aji1≤i,j≤n

6、则称矩阵A为n阶对称矩阵。a11a21a22......aij......ann123......n*(n+1)/2a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:n][1:n]=…………an1an2an3……annV只存储下三角元素时寻址公式为：loc(A[i][j])=loc(A[1][1])+[i(i-1)/2+j-1]*k传统做法：定义一个二维数组B[1:n][1:n]0元素0元素二.对角矩阵的压缩存储若一个矩阵中，值非0的元素对称地集中在主对角线两旁的一个带状区域中(该区域之外的元素都为0元素)，称这样的矩阵为对角矩阵。例.三对角矩阵的

7、压缩存储b11b12b21b22b23b32b33b34bn-1nbnn-1bnn0元素0元素非零元素的个数为3（n-2）+4B[1:n][1:n]=b11b12b21bij......b22......1234......3n-2bnnb11b12b21b22b23b32b33b34bn-1nbnn-1bnn0元素0元素B[1:n][1:n]=对角线数组中某元素寻址公式为：loc(A[i][j])=loc(A[1][1