资源描述：
《数据结构与算法 王曙燕 chapter5 多维数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、15.2多维数组5.3矩阵的压缩存储5.4广义表5.5实例分析与实现5.1应用实例2应用实例：魔方阵魔方阵是一个古老的智力问题，它要求在一个N×N的方阵中填入1～N2的数字（N要求为奇数），使得每一行、每一列、每条对角线的累加和都相等。35.2多维数组定义mnmmnnnmAa....aa................a....aaa....aa212222111211=×nm×也可以看成是m个行向量可以看成是个列向量n可看成是一种特殊的线性表，其特殊在于表中的数据元素本身也是一个线性表。数组是一组有固定个数的元素的集合。4抽
2、象数据类型定义ADTArray{}ADTArray数据对象：D={aj1j2…jn
3、n>0,称为数组的维数，ji是数组的第i维下标，1≤ji≤bi,bi为数组第i维的长度，aj1j2…jn∈ElementSet}数据关系：R={R1,R2,…,Rn}Ri={
4、1≤jk≤bk,1≤k≤n,且k≠i,1≤ji≤bi-1,aj1…ji…jn,aj1…ji+1…jn∈D,i=1,…,n}基本操作：1.InitArray(A,n,bond1,…,bondn)2.Destroy(A)3.Get
5、Value(A,e,index1,…,indexn)4.SetValue(A,e,index1,…,indexn)5.2多维数组5类型特点:1）不考虑插入和删除操作；2）数组是多维的结构，而存储空间是一个一维的结构。5.2多维数组6运算获得特定位置的元素值；修改特定位置的元素值。主要操作是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。其本质是地址计算问题。有两种顺序映象的方式:以行序为主序；以列序为主序。5.2多维数组7以行序为主序例如：a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,
6、3a2,1a2,2a2,3L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(n×(i-1)＋(j-1))×称为基地址或基址。L5.2多维数组8以列序为主序例如：L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(m×(j-1)＋(i-1))×称为基地址或基址。La1,2a1,1a1,3a2,1a2,2a2,3a2,1a1,1a1,2a2,2a1,3a2,35.2多维数组9三维数组Ar×m×n中任一元素ai,j,k的存储位置LOC(i,j,k)=LOC(1,1,1
7、)+((i-1)×m×n＋(j-1)×n+(k-1))×Lj1,j2,j3代替数组下标i,j,k，并且j1,j2,j3的下限分别为c1,c2,c3，上限为d1,d2,d3,每个元素占size个存储单元。则aj1,j2,j3的存储位置LOC(j1,j2,j3)=LOC(c1,c2,c3)+((j1-c1)×(d2-c2+1)×(d3-c3+1)＋(j2-c2)×(d3-c3+1)+(j3-c3))×size数据结构与算法5.2多维数组10推广到一般情况，可得到n维数组数据元素存储位置的映象关系：Loc(A[j1][j2]…[jn
8、]=Loc(A[c1][c2]…[cn])+αi×(ji-ci),1≤i≤n∑ni=1其中：αi=size×(dk-ck+1),1≤i≤n)∏nk=i+15.2多维数组11例如：设有二维数组A[10][20]，其每个元素占2个字节，第一个元素A1,1的存储地址为100，则按行优先顺序存储时元素A5,6的存储地址为?若按列优先顺序存储时元素A5,6的存储地址为?A5,6=100+[(5-1)*20+(6-1)]*2=270按行优先按列优先A5,6=100+[((6-1)*10+(5-1)]*2=2085.2多维数组125.3矩阵
9、的压缩存储特殊矩阵①三角矩阵②带状矩阵稀疏矩阵①三元组顺序表②十字链表13第5章数组和广义表特殊矩阵：①三角矩阵下三角矩阵nnnnncccccccccaaaaaaaaaa………………321333231222111LOC(i,j)=LOC(1,1)+前i-1行非零元素个数＋第i行中aij前非零元素的个数=LOC(1,1)+i(i-1)/2+j-1数据结构与算法5.3矩阵的压缩存储14特殊矩阵：①三角矩阵上三角矩阵LOC(i,j)=LOC(1,1)+前i-1行非零元素个数＋第i行中aij前非零元素的个数=LOC(1,1)+(i-1
10、)(2n-i+2)/2+j-innnnccccc0aaaaaaaaaa...........................333223221131211n5.3矩阵的压缩存储15第5章数组和广义表特殊矩阵：②带状矩阵LOC(i,j)=LOC(1,1)+3(i-1)-1+j-
