第五章数组 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-{a1a2anla1a2.an∈EI emset,. j0,1,b:-1bi是数组第i维的长度，n是位数} 数据关系：R={R,R2R} Rifaj1...ajan aj1...ajitan aj1.aji.ajn,ajl.ait1.an∈D,i=2,3…n 0<=jk=bk-1,1<=k<=n,k!=l 0<=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 }
S 基本操作 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维数组的线形表 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+j)*L - 三维数组B[p][ml[n] LOC(i,j,k)=LOC(0,0,0)+(i*m*n+j*n+k)*L -多维： L0CGj1j2jn)=L0C(0,00)t(b2*..*bn*j1+b3*..*bn*j2 +...+bn*jn-1+jn)*L=LOC(0,0...0)+ciji Cn=L,Ci-1=b*ci,1<i<=n ypb@ustc.edu.cn 4 中国科学技术大学
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数组的顺序表示和实现
数组应用 例寻找两个串最长的公共子串 -通常的匹配算法复杂度0(m*n) 一利用二维数组构造串之间的关系来求解 S1=sgabacbadfgbacst" S2-“gabadfgab' 最大公共子串"badfg”。 算法时间复杂度Om*n) ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 • 例寻找两个串最长的公共子串 – 通常的匹配算法复杂度O(m*n2 ) – 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用