对多的关系,如图4.3所示
4.1 数据结构
(2)数据的物理结构。
数据的物理结构是指数据在计算机中是如何存储的,即数据的逻辑结构在计算机存储
上的实现。它有多种不同的方式,其中顺序存储结构和链式存储结构是最常用的两种存
储方式。
① 顺序存储结构
顺序存储结构是将逻辑上相邻的数据元素存储在物理上也相邻的一系列存储单元里,
因此效率比较低。
4.1 数据结构
4.1.1 线性结构
② 链式存储结构的线性表,也叫链表。链表中的每一个结点在内存中的存储单元不一
定连续。为了表示数据元素之间的逻辑关系,每个存储单元除了存放数据元素本身
之外,还需要存储逻辑上相关的下一个元素的存储地址,所以每一个数据元素对应
一个物理存储单元,包含数据域和指针域两部分,如图4.6所示。
4.1.1 线性结构
2.栈
(1)栈的定义。
栈是一种操作受限的特殊线性表,它只能在表的一端(栈顶)进行插入和删除运算。与线性
表相同,数据元素之间仍为一对一关系。设栈S=(a1,a2,...,an),按照a1,a2,...,an顺序依次先后进栈,
则称a1是栈底元素,an是栈顶元素。进栈和出栈只能在栈顶操作,且遵循后进先出(Last In First
元素逻辑上相关的数据元素的地址。其主要特点是:由于结点除存储数据元素本身之外(数
据域),还要存储逻辑上相关的相邻元素的地址(指针域),因此与顺序存储结构相比,存
储密度小、空间利用率低,会占用更大的存储空间。但与顺序存储结构相比,这样的做的优
点是:在进行插入和删除操作时仅需要修改相应指针域的值即可,不会造成其他元素的大量
i个数据元素。删除成功后,线性表L的数据元素个数减1,即长度减1。