数据结构 03 列表.pdfVIP

3.列表 3.列表 (a) 接口与实现 (a) 接口与实现 邓俊辉 Dont lose the link. 邓俊辉 ‐Robin Milner (1934~2010) deng@tsinghua.edu.cn deng@tsinghua.edu.cn 从静态到动态 从静态到动态 根据是否修改数据结构，所有操作大致分为两类方式 根据是否修改数据结构，所有操作大致分为两类方式 1 ）静态：仅读取，数据结构的内容及组成将不变：get、search 1 ）静态：仅读取，数据结构的内容及组成将不变：get、search 2 ）动态：需写入，数据结构的局部或整体将改变：insert、remove 2 ）动态：需写入，数据结构的局部或整体将改变：insert、remove 与操作方式相对应地，数据元素的存储于组织方式也分为两种 与操作方式相对应地，数据元素的存储于组织方式也分为两种 1 ）静态： 数据空间整体创建或销毁 1 ）静态： 数据空间整体创建或销毁 数据元素的物理存储次序与其逻辑次序严格一致 数据元素的物理存储次序与其逻辑次序严格一致 可支持高效的静态操作 可支持高效的静态操作 比如向量，元素的物理地址与其逻辑次序线性对应 比如向量，元素的物理地址与其逻辑次序线性对应 2 ）动态： 为各数据元素动态地分配和回收的物理空间 2 ）动态： 为各数据元素动态地分配和回收的物理空间 逻辑上相邻的元素记录彼此的物理地址，形成一个整体 逻辑上相邻的元素记录彼此的物理地址，形成一个整体 可支持高效的动态操作 可支持高效的动态操作 Data Structures  Algorithms (Fall 2012), Tsinghua University 1 从向量到列表 从向量到列表 列表（list ）是采用动态储存策略的典型结构 列表（list ）是采用动态储存策略的典型结构 其中的元素称作节点（node ） 其中的元素称作节点（node ） 各节点通过指针或引用彼此联接，构成一个逻辑上的线性序列 各节点通过指针或引用彼此联接，构成一个逻辑上的线性序列 L = { a , a , ..., a } L = { a , a , ..., a } 0 1 n‐1 0 1 n‐1 相邻节点彼此互称前驱（predecessor ）或后继（successor ） 相邻节点彼此互称前驱（predecessor ）或后继（successor ） 前驱或后继若存在，则必然唯一 前驱或后继若存在，则必然唯一 没有前驱/后继的节点称作首 （first/front ）/末 （last/rear ）节点 没有前驱/后继的节点称作首 （first/front ）/末 （last/rear ）节点