1
实验 1(线性表的物理实现)日志
一、线性表
线性表是由 n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有
限序列。
其中:
⚫ 数据元素的个数 n 定义为表的长度 n="list".length()("list".length()=0(表
里没有一个元素)时称为空表)。
⚫ 将非空的线性表(n>=1)记作:(a[0],a[1],a[2],…,a[n-1])。
⚫ 数据元素 a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以
不同。
一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的
线性表又称为文件。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数
据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有
一个直接前驱和一个直接后继数据元素。
线性表的存储结构分为顺序表和链表。
二、顺序表
顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。
从定义中我们可以知道这种存储方式存储的数据是连续的,而且数据类型相同,所
以每一个数据元素占据的存储空间是一致的。
顺序表的优缺点:
优点:
1. 逻辑与物理顺序一致,顺序表能够按照下标直接快速的存取元素。
2. 无须为了表示表中元素之间的逻辑关系而增加额外的存储空间。
缺点:
1. 线性表长度需要初始定义,常常难以确定存储空间的容量,所以只能以降低
效率的代价使用扩容机制。
2. 插入和删除操作需要移动大量的元素,效率较低。
三、链表
评论0