【文件属性】：
文件名称：从向量到列表-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2021-07-10 17:12:23
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
§3.1 从向量到列表
不同数据结构内部的存储与组织方式各异，其操作接口的使用方式及时空性能也不尽相同。
在设计或选用数据结构时，应从实际应用的需求出发，先确定功能规范及性能指标。比如，引入
列表结构的目的，就在于弥补向量结构在解决某些应用问题时，在功能及性能方面的不足。二者
之间的差异，表面上体现于对外的操作方式，但根源则在于其内部存储方式的不同。
3.1.1 从静态到动态
数据结构支持的操作，通常无非静态和动态两类：前者仅从中获取信息，后者则会修改数据
结构的局部甚至整体。以第2章基于数组实现的向量结构为例，其size()和get()等静态操作均
可在常数时间内完成，而insert()和remove()等动态操作却都可能需要线性时间。究其原因，
在于“各元素物理地址连续”的约定此即所谓的“静态存储”策略。
得益于这种策略，可在O(1)时间内由秩确定向量元素的物理地址；但反过来，在添加（删
除）元素之前（之后），又不得不移动O(n)个后继元素。可见，尽管如此可使静态操作的效率
达到极致，但就动态操作而言，局部的修改可能引起大范围甚至整个数据结构的调整。
列表（list）结构尽管也要求各元素在逻辑上具有线性次序，但对其物理地址却未作任何
限制此即所谓“动态存储”策略。具体地，在其生命期内，此类数据结构将随着内部数据的
需要，相应地分配或回收局部的数据空间。如此，元素之间的逻辑关系得以延续，却不必与其物
理次序相关。作为补偿，此类结构将通过指针或引用等机制，来确定各元素的实际物理地址。
例如，链表（linked list）就是一种典型的动态存储结构。其中的数据，分散为一系列称
作节点（node）的单位，节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点，
只需在局部，调整少量相关节点之间的指针。这就意味着，采用动态存储策略，至少可以大大降
低动态操作的成本。