二维数组与广义表的顺序存储详解

需积分: 9 3 下载量 130 浏览量 更新于2024-08-19 收藏 263KB PPT 举报
在数据结构课程的第五章中,主要讨论了数组和广义表的存储方式,其中重点讲解了扩展线性链表的存储结构。首先,让我们理解什么是扩展线性链表。扩展线性链表与传统的线性链表类似,但这里的节点分为两种类型:原子结点(Atom)和表结点(hp)。原子结点是链表中的基本元素,它们通常没有额外的链接指向其他表结点;而表结点则包含了指向原子结点以及指向同一层下一个元素的信息。 数组作为数据结构的重要组成部分,其定义是根据一组下标来访问具有相同类型的元素集合。一维数组是一条有序的线性序列,每个元素通过下标关联,例如一维数组A=(a1, a2, ..., an)。二维数组可以看作是定长线性表的集合,可以按行或列进行展开,每个元素又是一个定长线性表,拥有两个约束关系。数组的定义中提到,除了结构的初始化和销毁外,主要操作包括元素的存取和修改,且一旦定义,数组的维数和维界是固定的。 在数组的顺序表示和实现部分,我们以二维数组为例探讨了顺序存储结构。常见的有两种存储方式: 1. **列序存储**(FORTRAN风格):数组元素按照列的顺序排列,比如: ``` a11 a21 ... am1 a12 a22 ... am2 ... a1n a2n ... amn ``` 这种方式中,每个元素的地址可以通过计算得到,例如LOC(A1)=LOC(a11),表示数组A的第一行第一个元素的位置。 2. **行序存储**(如BASIC, PL/1, COBOL, Pascal, C语言风格):数组元素按照行的顺序排列,即: ``` a11 a12 ... a1n a21 a22 ... a2n ... am1 am2 ... amn ``` 在这种存储方式中,同样可以计算出每个元素的地址,比如LOC(A2) = LOC(a21)。 扩展线性链表的引入,是为了在存储效率和灵活性之间找到平衡。在需要动态调整大小或者频繁插入删除元素的场景中,链表相比于数组有更高的适应性。理解数组和链表的不同特性和存储方式对于深入学习数据结构至关重要,特别是当涉及到高维数据结构和复杂算法设计时。后续章节会进一步探讨广义表的定义、存储结构以及递归算法,这些都是数据结构课程中的核心内容,能够帮助我们更好地理解和应用这些数据结构。