"DynamicArray" （数据结构）

"DynamicArray"

表示一个动态可扩展数组，其中的元素是普通表达式.

更多信息

  • 可扩展数组可用于连续追加元素以及有效地提取和更新元素.
  • CreateDataStructure[ "DynamicArray"]创建新的空 "DynamicArray"
    CreateDataStructure[ "DynamicArray",elems]创建包含 elems 的新 "DynamicArray"
    Typed[x,"DynamicArray"]指定 x 的类型为 "DynamicArray"
  • 对于类型为 "DynamicArray" 的数据结构，可进行以下操作：
  • 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["Length",x]存储在 ds 中的元素的数量时间：O(1)
    ds["Part",i]给出 ds 中的第 i 个元素时间：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 创建新的 "DynamicArray"：

可以追加元素：

返回总长度：

提取第一个元素：

改变元素：

该元素已被更新：

返回表达式形式的 ds：

快速追加元素：

可视化数据结构：

求所有元素的和：

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "DynamicArray"：

数据结构 ds 的信息：

应用  (11)

反向排列  (1)

下面是一个简单的函数，可对 "DynamicArray" 进行原地反转：

下面是一个样本数据结构：

反向排列其中的元素：

冒泡排序  (1)

冒泡排序是一种简单的排序算法，很容易编程实现，但性能通常较差：

下面是一个样本数据结构：

对元素进行排序：

数据结构已原地排序：

插入排序  (1)

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

下面是一个样本数据结构：

对元素进行排序：

数据结构已原地排序：

Quicksort  (1)

Quicksort 是一种高效的排序算法. 下面使用嵌套函数来实现：

下面是一个样本数据结构：

对元素进行排序：

数据结构已原地排序：

归并排序  (1)

归并排序是一种高效的排序算法. 下面使用工作区 (workspace) 来实现：

下面是一个样本数据结构：

对元素进行排序：

数据结构已原地排序：

堆排序  (1)

堆排序是一种高效的排序算法，通过构建一个堆来原地排序：

下面是一个样本数据结构：

元素已原地排序：

Timsort  (1)

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

下面是一个样本数据结构：

元素已原地排序：

Fisher–Yates 洗牌算法  (1)

Fisher–Yates 洗牌算法生成有限序列的随机排列：

样本数组：

应用洗牌算法：

回文  (1)

如果数组以中心对称，则为回文：

以下数组不是回文：

以下数组是回文：

Quickselect  (1)

Quickselect 是与 Quicksort 算法相关的选择算法. 返回的是列表中第 k 个最小的元素：

下面是一个样本数据结构：

第三个最小的元素是 7：

堆  (1)

堆是基于树的数据结构，其中，存储在子树上的值小于存储在其父树中的值（对于最小堆）. 通常用于实现优先队列，一般情况下用数组而不是树来实现.

将数组转换为堆：

下面是一个样本数据结构：

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

下面的函数生成一个树：

将其可视化，以便更容易地看出最小堆属性：

属性和关系  (1)

"FixedArray"  (1)

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