数据结构数组广义表.ppt

数据结构数组广义表 第一页，共三十一页，2022年，8月28日 数组描述 二维数组可用形式化语言描述，即： A(2)=(D,R) 其中：D={aij|aij∈datatype,0≤i≤m-1, 0≤j≤n-1}; R={Row,Col} 行关系：Row={<aij,aij+1>|aij,aij+1∈D,0≤i≤m-1,0≤j≤n-2} 列关系：Col={<aij,ai+1j>|aij,ai+1j∈D,0≤i≤m-2,0≤j≤n-1} 关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1 (周边元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。 二维数组还可以用如下形式描述: A[0] … A[i] … A[m-1] = (A[0]……A[i]……A[m-1] )-----线性表形式 a00 a01 ……a0j …… a0n-1 …………………………………. ai0 ai1 …… aij ….… ain-1 …………………………. am-10 am-11 …am-1j … am-1n-1 A(2) = A[m][n] = 第二页，共三十一页，2022年，8月28日 2.数组的基本运算 多维数组是线性表的推广，而线性表是多维数组的特例。 在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。对数组运算有： (1) 构造一个n维数组：Setarray(A,n,d1d2,......dn)，即生成： A[d1][d2].....[dn]（C语言中，1≤n≤8）。 (2) 撤消一个数组：Dearray(A)，释放数组A的存储空间。 (3) 取值：Aget(A,i1,...,in,x)，将A[i1][i2],...,[in]的值传给变量 x。 (4) 赋值：Assign(A,i1,...,in,x)，将变量 x的值传给A[i1][i2].....[in]。 5.2 数组的存储映像 由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。 在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。 但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元素。 第三页，共三十一页，2022年，8月28日 数组的存储映像 a00 … a0,n-1 … ai0 … ai,n-1 … … am-1,n-1 映像 （ 存储器） a00 a01 ……a0j …… a0n-1 …………………………………. ai0 ai1 …… aij ….… ain-1 …………………………. am-10 am-11 …am-1j … am-1n-1 A[m][n] = 图5.1 思考：1.三维以上数组如何映像? 2.“按列优先”如何映像? 第四页，共三十一页，2022年，8月28日 5.2.1数组元素的地址计算 以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。 1.一维数组： 即: Loc(a0)=b; Loc(a1)=b+L; Loc(ai)=b+i×L; 规律：任一元素ai的地址: a0 a1 … ai-1 ai … an-1 A[n]=( a0, a1,…… ai ,…… an-1) 起始地址b + ( ai前的元素个数i )×L 起址 b: b+L: … … b+i?L: L 图5.3 第五页，共三十一页，2022年，8月28日 数组元素的地址计算 2. 二维数组： a00 … a0,n-1 … ai0 … aij … … am-1,n-1 映像 （ 存储器） 起址 b: b+L: … … b+[i×n]×L: … b+[i?n+j]?L: 由图5.4