"ExtensibleVector" （数据结构）

"ExtensibleVector"

表示一个动态可扩展向量，其中元素是通用表达式.

更多信息

  • 可扩展向量可用于连续添加和前置元素以及有效的元素提取和更新.
  • CreateDataStructure[ "ExtensibleVector"]创建一个新的空 "ExtensibleVector"
    CreateDataStructure[ "ExtensibleVector",elems]创建包含 elems 的新 "ExtensibleVector"
    Typed[x,"ExtensibleVector"]将类型 "ExtensibleVector" 赋予 x
  • 对于类型为 "ExtensibleVector" 的数据结构，可使用下列运算：
  • ds["Append",x]将 x 追加到 ds 末端时间：O(1)
    ds["Copy"]返回 ds 的副本时间：O(n)
    ds["Drop",i]删除 ds 的第 i 个部分时间：O(n)
    ds["DropAll"]删除 ds 的所有元素时间：O(n)
    ds["DropLast"]删除 ds 的最后一个元素时间：O(1)
    ds["Elements"]返回 ds 的元素列表时间：O(n)
    ds["EmptyQ"] 若 ds 没有元素，则为 True时间：O(1)
    ds["Fold",fun,init]将 fun 应用于 ds 的以 init 开始的元素，并累计结果时间：O(n)
    ds["Insert",x,i ]在位置 i 处将 x 插入 ds时间：O(1)
    ds["JoinBack",elems ]将 elems 添加到 ds 的后端时间：O(nelems)
    ds["JoinFront",elems ]将 elems 添加到 ds 的前端时间：O(nelems)
    ds["Length",x]储存在 ds 中的元素数量时间：O(1)
    ds["Part",i]给出 ds 的第 i 个部分时间：O(1)
    ds["Prepend",x]将 x 追加到 ds 的首端时间：O(1)
    ds["SetPart",i,elem]更新 ds 的第 i 个部分时间：O(1)
    ds["SwapPart",i,j]将 ds 的第 i 个部分和第 j 个元素进行互换时间：O(1)
    ds["Visualization"]返回 ds 的可视化时间：O(n)
  • 还支持以下函数：
  • dsi===dsj若 dsi 等于 dsj，则为 True
    ds["Part",i]=val将 ds 的第 i 个元素设为 val
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换为正规表达式

范例

打开所有单元关闭所有单元

基本范例  (2)

可用 CreateDataStructure 创建新的 "ExtensibleVector"：

可在末端追加元素：

可在首端追加元素：

返回长度：

提取第一个元素：

更改元素：

元素已更新：

返回 ds 的表达式版本：

追加速度很快：

可生成数据结构的可视化形式：

加总所有元素：

范围  (1)

信息  (1)

可使用 CreateDataStructure 创建新的 "ExtensibleVector"：

关于数据结构 ds 的信息：

应用  (11)

求逆  (1)

对"ExtensibleVector" 就地求逆的简单函数：

要使用的示例数据结构：

对元素求逆：

冒泡排序  (1)

冒泡排序是一种简单的排序算法，易于编码，但通常性能较差：

要使用的示例数据结构：

对元素进行排序：

数据结构就地排序：

插入排序  (1)

插入排序是一种简单的排序算法，易于编码，通常对大型数组性能较差，但对小型数组很有用：

要使用的示例数据结构：

对元素进行排序：

数据结构就地排序：

快速排序  (1)

快速排序是一种高效的排序算法. 是一个用嵌套函数的基本操作：

要使用的示例数据结构：

对元素进行排序：

数据结构就地排序：

合并排序  (1)

合并排序是一种高效的排序算法. 是一个使用工作区的简单操作：

要使用的示例数据结构：

对元素进行排序：

数据结构就地排序：

堆排序  (1)

堆排序 (Heapsort) 是一种有效的排序算法，它通过构建堆进行工作：

要使用的示例数据结构：

对元素进行排序：

Timsort  (1)

Timsort 是一种混合且高效的排序算法：

要使用的示例数据结构：

对元素进行排序：

费舍尔耶茨洗牌  (1)

费舍尔耶茨 (Fisher–Yates) 洗牌生成有限序列的随机排列：

用于洗牌的样本数组：

应用该洗牌：

回文  (1)

如果数组围绕中间对称，则该数组是回文：

这不是回文：

这是回文：

快速选择  (1)

快速选择 (Quickselect) 是一种与快速排序 (Quicksort) 算法相关的选择算法. 它返回列表中第 k 个最小的元素：

要使用的示例数据结构：

第三小的元素为 7：

堆  (1)

堆是一种基于树图的数据结构，其中（对于最小堆）存储在子级中的值小于存储在父级中的值. 其通常用于实现优先级队列，且通常用数组而非树图来实现.

将数组转换为堆：

要使用的示例数据结构：

将数组转换为堆；很难看到堆属性：

该方程生成树图：

可视化可轻松查看最小堆属性：

属性和关系  (2)

"FixedArray"  (1)

许多适用于 "ExtensibleVector" 的算法也适用于 "FixedArray".

"DynamicArray"  (1)

许多适用于 "ExtensibleVector" 的算法也适用于 "DynamicArray".