数据结构-合肥工业大学 4(合肥工大).ppt

《数据结构-合肥工业大学 4(合肥工大).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章数组和广义表华电计算机系第四章数组和广义表★数组的逻辑结构★数组的顺序存储分配★矩阵的压缩存储★稀疏矩阵★广义表华电计算机系★数组的逻辑结构NorthChinaElectricPowerUniversity一个二维数组的类型定义如下：其中c,d设为1，数组可表示为：ElemTypeA[c..m][d..n]A=a11a12…a1na21a22…a2n…………am1am2…amn它可以看成是由m个行向量或n个列向量组成的线性表。也即，二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是

2、一个线性表。类似地，一个三维数组可以看成是数据元素为二维数组的线性表一个n维数组可视为其数据元素为n-1维数组的线性表。华电计算机系NorthChinaElectricPowerUniversity★数组的顺序存储分配一.一维数组A[1:n]a1a2a3…an-1anLoc(ai)=Loc(a1)+(i-1)kA[1:n]=(a1,a2,a3,…,an)若已知每个元素占k个存储单元，并且知道第一个元素的存储地址Loc(a1),则华电计算机系NorthChinaElectricPowerUniversity

3、二.二维数组A[1:m][1:n]a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn行序为主序分配方式列序为主序分配方式华电计算机系NorthChinaElectricPowerUniversitya11...a1na21...a2na31...aij...amn第1行第2行……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn1.行序为主序分配方式华电计算机系NorthChi

4、naElectricPowerUniversitya11a12a13……a1na21a22a23……a2na31a32a33……a3nA[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)]k华电计算机系NorthChinaElectricPowerUniversitya11...am1a

5、12...am2a13...aij...amn第1列第2列……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn2.列序为主序分配方式华电计算机系NorthChinaElectricPowerUniversitya11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:m][1:n]=…………aij……am1am2am3……amnj-1列若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11

6、),则Loc(aij)=Loc(a11)+(j1)mk+(i1)k=Loc(a11)+[(j1)m+(i1)]k华电计算机系a11a12a13……a1na21a22a23……a2nm=…………am1am2am3……amnA[1:m][1:n]所谓压缩存储是指为多个值相同的元素,或者位置分布有规律的那些元素分配尽可能少的存储空间，而对0元素一般情况下不分配存储空间。传统做法★矩阵的压缩存储华电计算机系a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:

7、n][1:n]=…………an1an2an3……ann传统做法：定义一个二维数组A[1:n,1:n]一.对称矩阵的压缩存储一个n阶矩阵A的元素满足性质aij=aji1≤i,j≤n则称矩阵A为n阶对称矩阵。华电计算机系a11a21a22......aij......annk=123......n*(n+1)/2a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:n][1:n]=…………an1an2an3……annA中任意一元素aij与V[k]之间存在对应关系:k={i(

8、i-1)/2+j当i≥j时j(j-1)/2+i当i