5.1数组的定义5.2数组的表示和实现5.3数组的压缩
第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩
ADT Array数据对象：D=(ajiaj2...ajnl ajiaj...ajn EElemset,j:=0，1,"""b;-1bi是数组第i维的长度，n是位数1数据关系：R={R,R2"-R,}R={< aj... aj.. jn , aj... ji+...ajn >aj... aji... ajn , aj... aji+...ajn ED, i=2, 3...n0<=jk<=bk-1, 1<=k<=n, k!=I0<=j;<=b;-1 }
5.1数组的定义 ADT Array{ 数据对象：D={aj1 aj2.ajn| aj1 aj2.ajn∈Elemset, ji=0,1,.bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1 ,R2.Rn} Ri={< aj1.aji.ajn , aj1.aji+1.ajn >| aj1.aji.ajn , aj1.aji+1.ajn ∈D,i=2,3.n 0<=jk<=bk-1,1<=k<=n,k!=I 0<=ji<=bi-1 }
基本操作：initArray(&A,n,bound1,bound2...boundn)DestroyArray(&A)Value(A,&e,indexl,index2..... indexn)Assign(&A,e,indexl,index2......indexn)↑ADT Array二维数组定义一其数据元素是一维数组的线形表·N维数组定义-其数据元素是N-1维数组的线形表
基本操作 : initArray(&A,n,bound1,bound2.boundn) DestroyArray(&A) Value(A,&e,index1,index2.indexn) Assign(&A,e,index1,index2.indexn) }ADT Array • 二维数组定义 − 其数据元素是一维数组的线形表 • N维数组定义 − 其数据元素是N－1维数组的线形表
·数组元素的两种存储方式一行主序存储一列主序存储·数组中元素在内存映象中的关系- 二维数组A[m][n]LOC(i,j)-LOC(O,O)+(i*n+i)*L- 三维数组B[p][m][n]LOC(i,j,k)=LOC(0,0,O)+(i*m*n+j*n+k)*L一多维：LOC(i1.j...jn)-LOC(0,... 0)+(b2*..*bn*j1+ b3*...*bn*j2+... +bn*jn-1+jn )*L=LOC(0,0... O)+ZcijiCn=L,Ci-1=b,*ci,1<i<=n
• 数组元素的两种存储方式 − 行主序存储 − 列主序存储 • 数组中元素在内存映象中的关系: − 二维数组A[m][n] LOC(i,j)=LOC(0,0)+(i*n+j)*L − 三维数组B[p][m][n] LOC(i,j,k)=LOC(0,0,0)+(i*m*n+j*n+k)*L − 多维： LOC(j1 ,j2.jn )=LOC(0,0.0)+(b2 *.*bn*j1+ b3 *.*bn*j2 +.+bn*jn-1+jn )*L=LOC(0,0.0)+∑ci j i cn=L,ci-1=bi*ci ,1<i<=n 5.2数组的顺序表示和实现
。例寻找两个串最长的公共子串一通常的匹配算法复杂度O(m*n2）一利用二维数组构造串之间的关系来求解S1=sgabacbadfgbacst"S2=gabadfgab"最大公共子串“badfg"。算法时间复杂度O(m*n)
• 例寻找两个串最长的公共子串 − 通常的匹配算法复杂度O(m*n2 ) − 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用