数据结构第四章数组和广义表.doc

第四章数组和广义表 数组和广义表是线性表的推广。在前面介绍的线性结构中，数据元素都只属非结构的原子类型，而数组和广义表中的数据元素本身也是一个线性表。 一、数组的逻辑结构 数组是一种特殊的线性表，它的每一个数据元素本身也是一个线性表。数组可以是一维、 二维、三维或多维的。数组的逻辑结构可以看成是一种推广的线性表，每一个数据元素本身也是一个线性表。 1. 一维数组 一维数组是一个线性表，例如 A[1:n]，它可以看成是一个由 n 个数据元素组成的线性表。 2. 二维数组 二维数组是一个特殊的数组，它可以看成是一种推广的线性表，每一个数据元素本身也是一个线性表。例如 A[1:m,1:n]，它可以看成是一个由 m 个行向量或 n 个列向量组成的线性表。 三、数组的顺序存储分配 数组的顺序存储分配是指数组元素在存储器中的顺序安排。数组的顺序存储分配可以是行存储或列存储。下面是数组的顺序存储分配公式： 1. 一维数组的寻址公式： loc(ai)=loc(a1)+(i-1)*l 2. 二维数组的寻址公式： loc(A[i,j])=loc(A[1,1])+[n(i-1)+(j-1)]*l 3. 三维数组的寻址公式： loc(A[j1,j2,j3])=loc(A[1,1,1])+[m*n(j1-1)+(j2-1)*n+(j3-1)]*l 4. n 维数组的寻址公式： loc(A[j1,j2,...,jn])=loc(A[1,1,...,1])+[(j1-1)*d2*d3*...*dn+(j2-1)*d3*...*dn+...+(jn-1)]*l 例子： 已知 A[1:2,1:3,1:4]，设 l=1，求 A[2,3,2] 的地址。 loc[i,j]=loc[1,1]+(i*(i-1)+j-1)*1 解： loc[2,3,2]=loc[1,1]+(2*(2-1)+3-1)*1=loc[1,1]+6*1 四、数组的应用 数组是一种非常重要的数据结构，它有很多实际应用，例如矩阵运算、图像处理、数据库管理等。 五、广义表 广义表是一种特殊的数组，它的每一个数据元素本身也是一个线性表。广义表可以是一维、 二维、三维或多维的。 六、数组和广义表的比较 数组和广义表都是线性表的推广，但它们有所不同。数组的每一个数据元素本身也是一个线性表，而广义表的每一个数据元素本身也是一个线性表，但广义表的数据元素可以是不同类型的。 七、结论 数组和广义表是线性表的推广，它们都是非常重要的数据结构。了解数组和广义表的逻辑结构和顺序存储分配是非常重要的。