从向量到列表：列表结构与动态操作

从向量到列表：列表结构与动态操作

引用

CSDN

1.

https://wenku.csdn.net/doc/2pxhf43mbg

在计算机科学中，列表是一种基本的数据结构，它与向量（数组）类似，都是线性结构，但它们在存储和访问方式上有显著区别。本文将探讨从向量到列表的转变，以及列表结构的设计和实现，特别是其动态操作的优势。

在计算机科学中，列表是一种基本的数据结构，它与向量（数组）类似，都是线性结构，但它们在存储和访问方式上有显著区别。本章主要探讨了从向量到列表的转变，以及列表结构的设计和实现，特别是其动态操作的优势。

向量，或一维数组，是一种数据结构，其中每个元素的物理位置与其逻辑顺序完全对应。这意味着可以通过元素的秩（即索引）直接访问到它，这种方式被称为“循秩访问”。然而，向量的这种特性也限制了其动态扩展能力，当需要插入或删除元素时，可能需要移动大量元素，导致操作的时间复杂度较高。

相比之下，列表允许元素的物理地址任意分布，它依赖于逻辑上的前后继关系来保持元素的顺序。这种关系可以通过位置（position）或者链接（link）来抽象表示，因此列表元素的访问方式被称为“循位置访问”或“循链接访问”。这种方法虽然牺牲了直接通过秩访问的效率，但它允许在常数时间内插入或删除元素，因为只需要更新相邻元素的链接，而不需要移动大量数据。

列表的实现通常采用链表的形式，每个元素（节点）包含数据部分和指向下一个元素的指针。这样的设计使得列表在动态操作如插入和删除上具有优势，尤其适用于那些元素数量频繁变化的情况。不过，访问列表中的特定元素可能需要遍历链表，时间复杂度为O(n)，这在查找操作上不如向量的O(1)。

本章还将深入讨论有序列表，特别是排序算法的应用，如插入排序、选择排序、快速排序等，并分析这些算法的性能。对于有序列表，排序操作是常见的需求，不同的排序算法有不同的时间复杂度和空间效率，因此在实际应用中需要根据具体情况选择合适的算法。

向量和列表各有优缺点，向量适合静态访问和已知大小的场景，而列表则在动态操作和元素数量不固定的应用中表现出色。在设计和选用数据结构时，应根据实际需求权衡功能、性能和实现的复杂性，以达到最佳的设计效果。

3.2 接口

3.2.1 ListNode模板类

按照表3.1所定义的ADT接口，可定义列表节点模板类如代码3.1所示。出于简洁与效率的考虑，这里并未对ListNode对象做封装处理。列表节点数据项的类型，通过模板参数T指定。

1 typedef int Rank; // 秩
2 #define ListNodePosi(T) ListNode<T>* // 列表节点位置
3 
4 template<typename T> struct ListNode { // 列表节点模板类（以双向链表形式实现）
5 // 成员
6 T data; ListNodePosi(T) pred; ListNodePosi(T) succ; // 数值、前驱、后继
7 // 构造函数
8 ListNode() {} // 针对header和trailer的构造
9 ListNode(T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s = NULL)
10 : data(e), pred(p), succ(s) {} // 默认构造器
11 // 操作接口
12 ListNodePosi(T) insertAsPred(T const& e); // 紧靠当前节点之前插入新节点
13 ListNodePosi(T) insertAsSucc(T const& e); // 紧随当前节点之后插入新节点
14 };

代码3.1 列表节点模板类

每个节点都存有数据对象data。为保证叙述简洁，在不致歧义的前提下，本书将不再区分节点及其对应的data对象。此外，每个节点还设有指针pred和succ，分别指向其前驱和后继。为了创建一个列表节点对象，只需根据所提供的参数，分别设置节点内部的各个变量。其中前驱、后继节点的位置指针若未予指定，则默认取作NULL。

3.2.2 列表

作为一种抽象数据类型，列表对象应支持以下操作接口。

表3.2 列表ADT支持的操作接口

请注意，这里所“定”的ListNodePosi(T)并非真正意义上“列表节点位置”类型。巧合的是，就在本书第1版即将付印之际，C++.0x标准终于被ISO接纳。新标准所拓展的特性之一，就是对模板别名（template alias）等语法形式的支持。因此可以期望在不远的将来，C++编译器将能够支持如下更为直接和简明的描述和实现：

template<typename T> typedef ListNode<T>* ListNodePosi;