数据结构：第4章-数组.ppt

*数据结构4.1数组的定义和运算第4章数组4.2数组的顺序存储和实现4.3特殊矩阵的压缩存储4.4矩阵的转置数据结构4.1数组的定义和运算定义第4章数组mnmmnnnmAa....aa................a....aaa....aa212222111211=×nm×也可以看成是m个行向量可以看成是个列向量n可看成是一种特殊的线性表，其特殊在于表中的数据元素本身也是一个线性表。数组是一组有固定个数的元素的集合。数据结构4.1数组的定义和运算抽象数据类型定义第4章数组ADTArray{}ADTArray数据对象：D={aj1j2…jn|n0,称为数组的维数，ji是数组的第i维下标，1≤ji≤bi,bi为数组第i维的长度，aj1j2…jn∈ElementSet}数据关系：R={R1,R2,…,Rn}Ri={aj1…ji…jn,aj1…ji+1…jn|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.GetValue(A,e,index1,…,indexn)4.SetValue(A,e,index1,…,indexn)数据结构类型特点:第4章数组1）不考虑插入和删除操作；2）数组是多维的结构，而存储空间是一个一维的结构。数据结构4.1数组的定义和运算运算第4章数组获得特定位置的元素值；修改特定位置的元素值。主要操作是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。其本质是地址计算问题。有两种顺序映象的方式:以行序为主序；以列序为主序。数据结构4.2数组的顺序存储和实现以行序为主序第4章数组例如：a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3L二维数组Am×n中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(n×(i-1)＋(j-1))×称为基地址或基址。L数据结构4.2数组的顺序存储和实现以列序为主序第4章数组例如：L二维数组Am×n中任一元素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,3数据结构4.2数组的顺序存储和实现第4章数组三维数组Ar×m×n中任一元素ai,j,k的存储位置LOC(i,j,k)=LOC(1,1,1)+((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数据结构4.2数组的顺序存储和实现第4章数组推广到一般情况，可得到n维数组数据元素存储位置的映象关系：Loc(A[j1][j2]…[jn]=Loc(A[c1][c2]…[cn])+αi×(ji-ci),1≤i≤n∑ni=1其中：αi=size×(dk-ck+1),1≤i≤n)∏nk=i+1数据结构4.2数组的顺序存储和实现第4