第五章数组5.1数组的定义5.2数组的表示和实现5.3数组的压缩中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩
5.1数组的定义ADT Array数据对象: D={ajiaji...ajnl ajiaj2...ain EElemset,j:=0，1，…b:-1bi是数组第i维的长度，n是位数数据关系：R={R,R,"-R,}R={< aji... aj...ajn , aj... ji+...ajn >aji...aj...ajin , aji...aji+...ajn ED, i=2, 3..n0<=jk<=bk-1, 1<=k<=n, k!=I0<=j;<=b;-1 }中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 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维数组的线形表3中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 基本操作 : 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维数组的线形表
5.2数组的顺序表示和实现数组元素的两种存储方式一行主序存储一列主序存储数组中元素在内存映象中的关系- 二维数组A[m][n]LOC(i,j)-LOC(0,0)+(i*n+i)*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)+(b2*...*b.*ji+ b3*..*b*j2+... +bn*jn-1+jn )*L=LOC(0,0... 0)+Zcjicn=-L,Ci-1=b,*c,1<i<=n4中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 • 数组元素的两种存储方式 – 行主序存储 – 列主序存储 • 数组中元素在内存映象中的关系: – 二维数组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)5中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 5 中国科学技术大学 • 例寻找两个串最长的公共子串 – 通常的匹配算法复杂度O(m*n2 ) – 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用