第5章教组和广义表 5.1数组 511数组的基本概念 从逻辑结构上看,数组是一个二元组( (index,alue)的集合, 对每个 index,都有一个 value值与之对应。 index称为下标,可 以由一个整数、两个整数或多个整数构成,下标含有n(心1) 个整数称为维数是m。数组按维数分为一维、二维和多维数组。 一维数组4是n(n>1)个相同类型数据元素a1,a2,…,, an构成的有限序列,其逻辑表示为:A=(a1a2…,an),其中, A是数组名,a1(1scn)为数组4的第元素。 个二维数组可以看作是每个数据元素都是相同类型的一 维数组的一维数组。以此类推,任何多维数组都可以看作一个 线性表,这时线性表中的每个数据元素也是一个线性表。多维 数组是线性表的推广
第5章 数组和广义表 5.1 数 组 5.1.1 数组的基本概念 从逻辑结构上看，数组是一个二元组(index,value)的集合， 对每个index，都有一个value值与之对应。index称为下标，可 以由一个整数、两个整数或多个整数构成，下标含有n（n≥1） 个整数称为维数是n。数组按维数分为一维、二维和多维数组。 一维数组A是n（n＞1）个相同类型数据元素a1，a2，…， an构成的有限序列，其逻辑表示为：A=（a1 ,a2 ,…,an），其中， A是数组名，ai（1≤i≤n）为数组A的第i个元素。 一个二维数组可以看作是每个数据元素都是相同类型的一 维数组的一维数组。以此类推，任何多维数组都可以看作一个 线性表，这时线性表中的每个数据元素也是一个线性表。多维 数组是线性表的推广
抽象数据类型雄维数组定义如下: ADT· Array 数据对象 D=a|j=1…,h2,i=1,2,…,d)/第i维的长度为h 数据关系 R=r12… rd+ r1={|1≤jk≤b,1≤k≤d且k≠,1≤j≤b1-1,i=2,…d 基本运算 value(a,i1,i2,…;ia):A是已存在的d维数组,其运算结果是返回a[i1,i2;…,id]值。 Assign(A,e,i1,i2…,ia):A是已存在的d维数组,其运算结果是置a[i1,i2…id]=e。 DIsp(A,b1,b2,…,ba):输出d维数组a的所有元素值
抽象数据类型d维数组定义如下：
5.12数组的存储结构 数组通常采用顺序存储方式来实现。 一维数组的所有元素依逻辑次序存放在一片连续的内存存 储单元中,其起始地址为第一个元素a的地址即LOC(a1),假设 每个数据元素占用k个存储单元,则任一数据元素a的存储地址 LOC(a)就可由以下公式求出: LOC(a)=LOC(a1)+(1)×k(2≤i≤n) 该式说明一维数组中任一数据元素的存储地址可直接计 算得到,即一维数组中任一数据元素可直接存取,正因如此 所以一维数组具有随机存储特性。同样,二维及多维数组也 满足随机存储特性
5.1.2 数组的存储结构 数组通常采用顺序存储方式来实现。 一维数组的所有元素依逻辑次序存放在一片连续的内存存 储单元中，其起始地址为第一个元素a1的地址即LOC(a1 )，假设 每个数据元素占用k个存储单元，则任一数据元素ai的存储地址 LOC(ai )就可由以下公式求出： LOC(ai )=LOC(a1 )+(i-1)×k （2≤i≤n） 该式说明一维数组中任一数据元素的存储地址可直接计 算得到，即一维数组中任一数据元素可直接存取，正因如此， 所以一维数组具有随机存储特性。同样，二维及多维数组也 满足随机存储特性
对于d(2)维数组,其数据元素的存储必须约定存放 次序即存储方案,这是因为存储单元是一维的(计算机的存 储结构是线性的),而数组是d的。通常存储方案有两种: 以行序为主序,如CC++、C#、 Pascal、Basi等 语言采用。 ●以列序为主序,如 Fortran语言采用
对于d（d≥2）维数组，其数据元素的存储必须约定存放 次序即存储方案，这是因为存储单元是一维的（计算机的存 储结构是线性的），而数组是d维的。通常存储方案有两种： ⚫ 以行序为主序，如C/C++、C#、Pascal、Basic等 语言采用。 ⚫ 以列序为主序，如Fortran语言采用
下面以二维数组为例子以讨论。对于一个n行n列的二 维数组Amxn,有: 若采用以行序为主序的存储方式,即先存储第1行,紧 接着存储第2行,…,最后存储第m行。此时,二维数组的 线性排列次序为: 1,1,41,2,1,n12,412,2,…,2,n,…,4m14m,2…mn 」L LOC(a)=LOC(a,t)+(i-1)×+(-1)×k
下面以二维数组为例予以讨论。对于一个m行n列的二 维数组Am×n，有： = m m m n n n m n a a a a a a a a a A ,1 ,2 , 2,1 2,2 2, 1,1 1,2 1, ... ... ... ... ... ... ... 若采用以行序为主序的存储方式，即先存储第1行，紧 接着存储第2行，…，最后存储第m行。此时，二维数组的 线性排列次序为： a1,1,a1,2,…,a1,n ,a2,1,a2,2,…,a2,n ,…,am,1,am,2,…am,n LOC(ai,j )=LOC(a1,1)+[(i-1)×n+(j-1)]×k
若采用以列序为主序的存储方式,即先存储第1列,然 后紧接着存储第2列,∴,最后存储第n列。此时,二维数组 的线性排列次序为: 1,192,1 m11,22,2,m291,n:2,n LOC(a)=LoC(an,1)+(0-1)xm+(1)×k
若采用以列序为主序的存储方式，即先存储第1列，然 后紧接着存储第2列，…，最后存储第n列。此时，二维数组 的线性排列次序为： a1,1,a2,1,…,am,1,a1,2,a2,2,…,am,2,…,a1,n ,a2,n ,…am,n LOC(ai,j )=LOC(a1,1)+[(j-1)×m+(i-1)]×k
5.1.3特殊矩阵的压缩存储 二维数组也称为矩阵,一个n行n列的矩阵,当m=n时 称为方阵,方阵的元素可以分为三部分,即上三角部分 主对角部分和下三角部分 a0,1 a0,2 C0.n-1 上三角部分 aij:1 2.0 2.1 C2.n-1 下三角部分 主对角线
5.1.3 特殊矩阵的压缩存储 二维数组也称为矩阵，一个m行n列的矩阵，当m=n时， 称为方阵，方阵的元素可以分为三部分，即上三角部分， 主对角部分和下三角部分： − − − − − − − − 1,0 1,1 1,2 1, 1 2,0 2,1 2,2 2, 1 1,0 1,1 1,2 1, 1 0,0 0,1 0,2 0, 1 ... ... ... ... ... ... ... ... ... n n n n n n n n a a a a a a a a a a a a a a a a 主对角线 ai,j：i=j 上三角部分 ai,j：ij
1.对称矩阵的压缩存储 若一个阶方阵ln,m|中的元素满足=2(0≤,压n1),则 称其为m阶对称矩阵。 可以将其压缩存放到一个一维数组b0.n(m+1)2-1中,只存放 主对角和下三角部分的元素,a和b之间的映射关系: t(t+1) + 当i≥j k- (+1) 当i<
1. 对称矩阵的压缩存储 若一个n阶方阵a[n,n]中的元素满足ai,j=aj,i（0≤i，j≤n-1），则 称其为n阶对称矩阵。 可以将其压缩存放到一个一维数组b[0..n(n+1)/2-1]中，只存放 主对角和下三角部分的元素，ai,j和bk之间的映射关系：
上三角矩阵: (2n-1+1) +J- 2 n(n+1 下三角矩阵 i(+1) n(n+1) 2 其中,数组b的元素bx+y2中存放着常数c
2.对角矩阵的压缩存储 半带宪为对角矩阵: 条 条 对于l1的三对角矩阵,只存储其非零元素,并存储到 一维数组中,即以行序为主序将的非零元素a;存储到b 的元素b中,归纳起来有k=2计
2. 对角矩阵的压缩存储 半带宽为l的对角矩阵 ： ... l条 l条 0 0 ... 对于l=1的三对角矩阵，只存储其非零元素，并存储到 一维数组b中，即以行序为主序将a的非零元素ai,j存储到b 的元素bk中，归纳起来有k=2i+j