线性表
线性表
线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序,可写成\([a,b,c,…]\)的形式,方括号中的内容既表示线性表中的全部元素,也表示这些元素的排序。对于线性表中任意前后相邻的\(x_i\)与\(x_{i+1}\)元素,通常称\(x_i\)的后继为\(x_{i+1}\),\(x_{i+1}\)的前驱为\(x_i\),首个元素的前驱为空,最后一个元素的后继为空。需注意到线性表本身是个逻辑概念,其不限制也不依赖于具体实现,就类似于集合这样的概念,在讨论算法时经常会遇到这种类型的概念。
在算法领域人们更关心线性表的实现,因为线性表本身十分简答。
实际的计算机硬件基本都采用相同的“内存模型”,其包括由确定的\(K\)个连续整数构成的\(K\)个内存地址,每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存,一段时间后内存返回该地址中的数据,写入内存的流程大致是同时提供地址和数据给内存,一段时间后内存完成写入。在这种“内存模型”下,线性表的实现方案通常是数组或链表,这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”,也有一定的可能会用其他方案来实现线性表。… 阅读全文