第四章数组和广义表
数组和广义表是线性表的推广。在前面介绍的线性结构中,数据元素都只属非结构的原子类型,而数组和广义表中的数据元素本身也是一个线性表。
一、数组的逻辑结构
数组是一种特殊的线性表,它的每一个数据元素本身也是一个线性表。数组可以是一维、 二维、三维或多维的。数组的逻辑结构可以看成是一种推广的线性表,每一个数据元素本身也是一个线性表。
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
四、数组的应用
数组是一种非常重要的数据结构,它有很多实际应用,例如矩阵运算、图像处理、数据库管理等。
五、广义表
广义表是一种特殊的数组,它的每一个数据元素本身也是一个线性表。广义表可以是一维、 二维、三维或多维的。
六、数组和广义表的比较
数组和广义表都是线性表的推广,但它们有所不同。数组的每一个数据元素本身也是一个线性表,而广义表的每一个数据元素本身也是一个线性表,但广义表的数据元素可以是不同类型的。
七、结论
数组和广义表是线性表的推广,它们都是非常重要的数据结构。了解数组和广义表的逻辑结构和顺序存储分配是非常重要的。