《数组和矩阵》由会员分享，可在线阅读，更多相关《数组和矩阵（94页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法20102010年秋季年秋季Chapter4 Chapter4 数组和矩阵数组和矩阵本章教学内容本章教学内容vv数组数组 vv矩阵矩阵 vv特殊矩阵特殊矩阵 vv稀疏矩阵稀疏矩阵4.1 4.1 数组数组从本质上讲，数组是从本质上讲，数组是 一个一个 （）偶）偶对的集合，其中每个数据元素都由一个值和一个下标组成。对的集合，其中每个数据元素都由一个值和一个下标组成。一维数组是一维数组是n n（n n 0 0）个）个相同数据类型的数据元素相同数据类型的数据元素a a0 0，a a1 1，a an-1n-1构成的有限线性序列，且该有限序列存储在一块构成的有限线性序列，且该有
2、限序列存储在一块地址连续地址连续的内存单元的内存单元中。中。其中，其中，n n叫做数组长度或数组大小；叫做数组长度或数组大小；如果如果n=0n=0，则是空数组。，则是空数组。1 1、一维数组一维数组的定义的定义 数组中的每一个元素在数组中的位置由数组中的每一个元素在数组中的位置由下标唯一确定下标唯一确定； 数组中的各数据元素处于一个数组中的各数据元素处于一个线性结构线性结构中；中； 一维数组也叫做一维数组也叫做向量向量。2 2、一维数组的、一维数组的特点特点3 3、 二维数组二维数组当每一个数组元素当每一个数组元素aiai（0 0 inin1 1）本身又是一个一维数本身又是一个一维数组组时，一
3、维数组扩充为二维数组。时，一维数组扩充为二维数组。二维数组也叫做矩阵，如二维数组也叫做矩阵，如anmanm可以看作是由可以看作是由n n个行向量个行向量和和mm个列向量所组成的向量。个列向量所组成的向量。a00a00a0k-1a0k-1a0ka0ka0k+1a0k+1a0m-1a0m-1aj-10aj-10aj-1k-1aj-1k-1aj-1kaj-1kaj-1k+1aj-1k+1aj-1m-1aj-1m-1aj0aj0ajk-1ajk-1ajkajkajk+1ajk+1ajm-1ajm-1aj+10aj+10aj+1k-1aj+1k-1aj+1kaj+1kaj+1k+1aj+1k+1aj+1
4、m-1aj+1m-1an-10an-10an-1k-1an-1k-1an-1kan-1kan-1k+1an-1k+1an-1m-1an-1m-1uu 例如：二维数组例如：二维数组anmanm 总共有总共有nmnm个数组元素；个数组元素； 每一个数组元素每一个数组元素ajkajk同时处于同时处于两个向量两个向量之中；之中； 数组元素数组元素ajkajk有有两个两个直接直接前驱前驱和和两个两个直接直接后继后继； 数组元素在数组中的位置由下标的数组元素在数组中的位置由下标的二元组二元组jkjk唯一确定。唯一确定。4 4、 在一个在一个三维三维数组数组amam1 1mm2 2mm3 3 中：中： 总共
5、有总共有mm1 1mm2 2mm3 3个个数组元素；数组元素； 每一个数组元素每一个数组元素aijkaijk同时处于同时处于三个三个向量之中；向量之中； 数组元素数组元素aijkaijk有有三个三个直接直接前驱前驱和和三个三个直接直接后继后继； 数组元素在数组中的位置由下标的数组元素在数组中的位置由下标的三元组三元组ijkijk唯一确定。唯一确定。5 5、在一个、在一个n n维维数组数组amam1 1mm2 2mmn n 中：中： 总共有总共有mm1 1mm2 2mmn n个个数组元素；数组元素； 每一个数组元素每一个数组元素aiai1 1ii2 2iin n 同时处于同时处于n n个个向量之
6、中；向量之中； 数组元素数组元素aiai1 1ii2 2iin n 有有n n个个直接直接前驱前驱和和n n个个直接直接后继后继； 数组元素在数组中的位置由下标的数组元素在数组中的位置由下标的n n元组元组i i1 1ii2 2iin n 唯一唯一确定。确定。高维数组高维数组1 1、数组、数组ADTADT抽象数据类型抽象数据类型 ArrayArray 实例实例形如形如(index , value)(index , value)的数据对集合，其中任意两对数据的的数据对集合，其中任意两对数据的 indexindex值都各不相同值都各不相同操作操作Create Create( )( )：创建创建一个
7、空的数组一个空的数组Store Store( (index, valueindex, value) )：添加数据添加数据(index, value)(index, value)，同时删除具，同时删除具 有相同有相同indexindex值的数据对（如果存在）值的数据对（如果存在）Retrieve Retrieve( (indexindex) )：返回索引值为返回索引值为indexindex的数据对的数据对 设一维数组设一维数组anan的第一个数组元素的存储地址为的第一个数组元素的存储地址为a a，每一个数，每一个数 组元素的存储大小为组元素的存储大小为l l，则任一数组元素的存储地址，则任一数组
8、元素的存储地址LOC(i)LOC(i)为：为：01in-1a al lLOC(i)LOC(i)iil lLOC(i)LOC(i)a a， i=0i=0时时LOC(i-1)+LOC(i-1)+l l ，i0i0时时LOC(i)LOC(i) LOC(i-1)+LOC(i-1)+l l a+i*a+i*l lLOC(1)LOC(1) LOC(0)+LOC(0)+l l a+a+l lLOC(2)LOC(2) LOC(1)+LOC(1)+l l a+2*a+2*l l，LOC(1)LOC(1)LOC(2)LOC(2)2 2、一维数组的顺序存储结构、一维数组的顺序存储结构用一组连续的存储单元存放二维数组
9、用一组连续的存储单元存放二维数组将它的下标映射将它的下标映射到其相应的一维数组的存储位置。到其相应的一维数组的存储位置。（1 1）行主映射行主映射：以行序为主的存储方式：以行序为主的存储方式如如C C、C+C+和和PASCALPASCAL等语言采用这种存储方式。等语言采用这种存储方式。（2 2）列主映射列主映射：以列序为主的存储方式：以列序为主的存储方式如如FORTRANFORTRAN语言采用这种存储方式。语言采用这种存储方式。3 3、二维数组的顺序存储结构、二维数组的顺序存储结构如何用一维的存储地址来表示多维的关系如何用一维的存储地址来表示多维的关系以行（列）序为主的存储方式：先存储第以行（
10、列）序为主的存储方式：先存储第0 0行（列），再存储第行（列），再存储第1 1行（列）行（列） ，继续下去，最后存储第，继续下去，最后存储第n-1n-1行（行（m-1m-1列）列） ； 第第i+1i+1行（行（j+1j+1列）的第一个元素列）的第一个元素 ai+10ai+10（a0j+1a0j+1）是紧接在第）是紧接在第i i行（第行（第j j列）的最后一个元素之后存放的。列）的最后一个元素之后存放的。a00a00 a01a01a0m-1a0m-1 a10a10a11a11a1m-1a1m-1an-10an-10an-1m-1an-1m-1a00a00 a10a10an-10an-10 a01
11、a01a11a11am-11am-11a0m-1a0m-1an-1m-1an-1m-1第第0 0行行第第1 1行行第第n-1n-1行行第第0 0列列第第1 1列列第第m-1m-1列列（a a）以）以行序行序为主为主（b b）以）以列序列序为主为主假设有二维数组假设有二维数组anmanm，且，且下标均从下标均从0 0开始开始，每个数据元素，每个数据元素 的存储大小为的存储大小为l l，那么，任一数组元素，那么，任一数组元素ajkajk在相应的一维数组在相应的一维数组中存放地址为：中存放地址为：LOC(j,k)LOC(j,k) = = LOC(0,0)+(j*m+k)*lLOC(0,0)+(j*m
12、+k)*l以行优先的顺序讨论地址的映射方法以行优先的顺序讨论地址的映射方法a00a00a0k-1a0k-1a0ka0ka0k+1a0k+1a0m-1a0m-1aj-10aj-10aj-1k-1aj-1k-1aj-1kaj-1kaj-1k+1aj-1k+1aj-1m-1aj-1m-1aj0aj0ajk-1ajk-1ajkajkajk+1ajk+1ajm-1ajm-1aj+10aj+10aj+1k-1aj+1k-1aj+1kaj+1kaj+1k+1aj+1k+1aj+1m-1aj+1m-1an-10an-10an-1k-1an-1k-1an-1kan-1kan-1k+1an-1k+1an-1m-1
13、an-1m-1LOC(i,j,k)=LOC(i,0,0)+(j*mLOC(i,j,k)=LOC(i,0,0)+(j*m3 3+k)*+k)*l l=LOC(i-1,0,0)+(m=LOC(i-1,0,0)+(m2 2*m*m3 3+j*m+j*m3 3+k)*+k)*l l= LOC(0,0,0)+(i*m= LOC(0,0,0)+(i*m2 2*m*m3 3+j*m+j*m3 3+k)*+k)*l l 假设有三维数组假设有三维数组amam1 1mm2 2mm3 3 ，且下标均从，且下标均从0 0开始，每个数开始，每个数 据元素的存储大小为据元素的存储大小为l l，那么，任一数组元素，那么，任一数组元素aijkai
