WOLFRAM

Wolfram 语言与系统参考资料中心

"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]将 fun 应用于 ds 的元素，并累计结果时间：O(n)
    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 的输入形式
    Length[ds]数组长度
    Normal[ds]将 ds 转换成正规表达式

范例

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

基本范例  (2)

可用 CreateDataStructure 创建新的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]

可以追加元素：

Wolfram Language code: ds["Append", f[1]]

返回总长度：

Wolfram Language code: ds["Length"]

提取第一个元素：

Wolfram Language code: ds["Part", 1]

改变元素：

Wolfram Language code: ds["Part", 1] = f[2]

该元素已被更新：

Wolfram Language code: ds["Part", 1]

返回表达式形式的 ds：

Wolfram Language code: Normal[ds]

快速追加元素：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]; Do[ds["Append", i], {i, 1000}]

可视化数据结构：

Wolfram Language code: ds["Visualization"]

求所有元素的和：

Wolfram Language code: ds["Fold", Plus, 0]

范围  (18)

信息  (1)

可用 CreateDataStructure 创建新的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

创建  (2)

创建一个空的 "DynamicArray"：

Wolfram Language code: CreateDataStructure["DynamicArray"]

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: CreateDataStructure["DynamicArray", {x, y, z}]

运算  (15)

"Append"  (1)

向 "DynamicArray" 追加元素：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]; ds["Append", f[x, y]]

获取数组的内容：

Wolfram Language code: Normal[ds]

"Copy"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {1, 2, 3}]

复制数组：

Wolfram Language code: ds1 = ds["Copy"]

两个数组的内容相同：

Wolfram Language code: {Normal[ds], Normal[ds1]}

修改副本不会影响原来的数组：

Wolfram Language code: ds1["Append", 42]; {Normal[ds], Normal[ds1]}

"Drop"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

删除数组的第五个元素：

Wolfram Language code: ds["Drop", 5]

可视化数组：

Wolfram Language code: ds["Visualization"]

"DropAll"  (1)

创建一个 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

删除数组中的所有元素：

Wolfram Language code: ds["DropAll"]

数组现在是空的：

Wolfram Language code: Length[ds]

"DropLast"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

丢弃最后一个元素并获取被丢弃的值：

Wolfram Language code: ds["DropLast"]

可视化数组：

Wolfram Language code: ds["Visualization"]

"Elements"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

以列表形式返回内容：

Wolfram Language code: ds["Elements"]

Normal 返回同一列表：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

测试 "DynamicArray" 是否为空：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]; ds["EmptyQ"]

在添加一个元素后，数组不再为空：

Wolfram Language code: ds["Append", x]; ds["EmptyQ"]

"Fold"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]

用 Plus 合并数组中的所有元素，计算它们的总和：

Wolfram Language code: ds["Fold", Plus]

也可以指定一个初始值来开始累加：

Wolfram Language code: ds["Fold", Plus, 42]

"Insert"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[8]]

在指定位置插入元素：

Wolfram Language code: ds["Insert", x, 5]

可视化数组的内容：

Wolfram Language code: ds["Visualization"]

"JoinBack"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[5]]

向数组末尾追加多个元素：

Wolfram Language code: ds["JoinBack", Range[6, 10]]

可视化数组：

Wolfram Language code: ds["Visualization"]

"Length"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[5]]

获取数组中元素的数量：

Wolfram Language code: ds["Length"]

Length 给出同样的值：

Wolfram Language code: Length[ds]

"Part"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]

获取数组的第五个元素：

Wolfram Language code: ds["Part", 5]

"SetPart"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]

将数组的第五个元素设为不同的值：

Wolfram Language code: ds["SetPart", 5, x]

可视化数组：

Wolfram Language code: ds["Visualization"]

以下语句同样有效：

Wolfram Language code: ds["Part", 6] = y; ds["Visualization"]

"SwapPart"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]

将第五个和第六个元素的值互换：

Wolfram Language code: ds["SwapPart", 5, 6]

可视化数组：

Wolfram Language code: ds["Visualization"]

"Visualization"  (1)

创建一个含有初始值的 "DynamicArray"：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]

可视化数组的内容：

Wolfram Language code: ds["Visualization"]

应用  (11)

反向排列  (1)

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

Wolfram Language code: ArrayReverse[ ds : DataStructure["DynamicArray", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, ds["SwapPart", start, end] ]; ds];

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

反向排列其中的元素：

Wolfram Language code: Normal[ArrayReverse[ds]]

冒泡排序  (1)

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

Wolfram Language code: BubbleSort[ ds : DataStructure["DynamicArray", _]] := Module[{repeat = True}, While[repeat, repeat = False; Do[ If[ds["Part", i] > ds["Part", i + 1], ds["SwapPart", i, i + 1]; repeat = True];, {i, ds["Length"] - 1}]]; ds];

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

对元素进行排序：

Wolfram Language code: Normal[BubbleSort[ds]]

数据结构已原地排序：

Wolfram Language code: Normal[ds]

插入排序  (1)

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

Wolfram Language code: InsertionSort[ ds : DataStructure["DynamicArray", _]] := Module[{len, i, j}, len = ds["Length"]; Do[j = i; While[j > 1 && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, 2, len}]; ds]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

对元素进行排序：

Wolfram Language code: Normal[InsertionSort[ds]]

数据结构已原地排序：

Wolfram Language code: Normal[ds]

Quicksort  (1)

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

Wolfram Language code: Quicksort[ ds : DataStructure["DynamicArray", _]] := Module[{partitionFun, sortFun}, partitionFun = Function[{low, high}, Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i]]; sortFun = Function[{low, high}, If[low < high, Module[{p = partitionFun[low, high]}, sortFun[low, p - 1]; sortFun[p + 1, high] ] ]]; sortFun[1, ds["Length"]]; ds]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

对元素进行排序：

Wolfram Language code: Normal[Quicksort[ds]]

数据结构已原地排序：

Wolfram Language code: Normal[ds]

归并排序  (1)

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

Wolfram Language code: MergeSort[ ds : DataStructure["DynamicArray", _]] := MergeSortSplit[ds["Copy"] , 1, ds["Length"] + 1, ds]
Wolfram Language code: MergeSortSplit[ b_, start_, end_, a_] := Module[{mid}, If[end - start > 1, mid = Quotient[end + start, 2]; MergeSortSplit[a, start, mid, b]; MergeSortSplit[a, mid, end, b]; MergeSortJoin[ b, start, mid, end, a] ]; a]
Wolfram Language code: MergeSortJoin[ a_, start_, mid_, end_, b_] := Module[{i = start, j = mid, k}, Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

对元素进行排序：

Wolfram Language code: Normal[MergeSort[ds]]

数据结构已原地排序：

Wolfram Language code: Normal[ds]

堆排序  (1)

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

Wolfram Language code: Heapsort[ds : DataStructure["DynamicArray", _]] := Module[{len = ds["Length"]}, Do[Heapify[ds, ii], {ii, Quotient[len, 2], 1, -1}]; ds ]
Wolfram Language code: Heapify[p : DataStructure["DynamicArray", _], k_Integer] := Module[{i = k, l, n = p["Length"]}, While[(l = 2 i) ≤ n, If[(l < n) && (p["Part", l] > p["Part", l + 1]), l++]; If[p["Part", i] > p["Part", l], p["SwapPart", l, i]; i = l, i = n + 1];];]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

元素已原地排序：

Wolfram Language code: Heapsort[ds]; Normal[ds]

Timsort  (1)

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

Wolfram Language code: Timsort[ds : DataStructure["DynamicArray", _]] := Module[{blockSize = 32, len = ds["Length"], size, mid, right}, Do[InsertionWorker[ds, ii, Min[ii + 32, len]], {ii, 1, len, blockSize}]; size = blockSize; While[size < len, Do[ mid = left + size; right = Min[left + 2 * size, len]; MergeWorker[ds, left, mid, right] , {left, 1, len, 2 * size} ]; size *= 2 ]; ]
Wolfram Language code: InsertionWorker[ ds : DataStructure["DynamicArray", _], left_, right_] := Module[{i, j}, Do[j = i; While[j > left && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, left, right}]; ds]
Wolfram Language code: MergeWorker[ b_, start_, mid_, end_] := Module[{a, i = start, j = mid, k}, a = b["Copy"]; Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

元素已原地排序：

Wolfram Language code: Timsort[ds]; Normal[ds]

Fisher–Yates 洗牌算法  (1)

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

Wolfram Language code: FisherYatesShuffle[ ds : DataStructure["DynamicArray", _]] := ( Do[ ds["SwapPart", i, RandomInteger[{1, i}]], {i, ds["Length"] - 1, 1, -1} ]; ds );

样本数组：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100} ];

应用洗牌算法：

Wolfram Language code: Normal[FisherYatesShuffle[ds]]

回文  (1)

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

Wolfram Language code: IsPalindrome[ ds : DataStructure["DynamicArray", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, If[ds["Part", start] =!= ds["Part", end], Return[False] ] ]; True];

以下数组不是回文：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}]; IsPalindrome[ds]

以下数组是回文：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 2, 9}]; IsPalindrome[ds]

Quickselect  (1)

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

Wolfram Language code: Quickselect[ds : DataStructure["DynamicArray", _], k_] := QuickselectWorker[ds, 1, ds["Length"], k];
Wolfram Language code: QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0}, While[True, If[low === high, Return[ds["Part", low]]]; pivotIdx = SelectPartition[ds, low, high]; Which[ k === pivotIdx, Return[ds["Part", k]], k < pivotIdx, high = pivotIdx - 1, True, low = pivotIdx + 1 ] ] ];
Wolfram Language code: SelectPartition[ds_, low_, high_] := Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i];

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

第三个最小的元素是 7：

Wolfram Language code: Quickselect[ds, 3]

堆  (1)

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

将数组转换为堆：

Wolfram Language code: MinHeapify[ds : DataStructure["DynamicArray", _]] := MinHeapify[ds, 1]
Wolfram Language code: MinHeapify[ds_, i_] := Module[{l, r, p, smallest}, l = If[getLeftChildIdx[i] <= ds["Length"], ds["Part", getLeftChildIdx[i]], -Infinity ]; r = If[getRightChildIdx[i] <= ds["Length"], ds["Part", getRightChildIdx[i]], -Infinity ]; p = ds["Part", i]; smallest = If[getLeftChildIdx[i] <= ds["Length"] && l < p, getLeftChildIdx[i], i]; If[getRightChildIdx[i] <= ds["Length"] && r < ds["Part", smallest], smallest = getRightChildIdx[i]]; If[smallest =!= i, ds["SwapPart", i, smallest]; MinHeapify[ds, smallest] ]; ];
Wolfram Language code: getLeftChildIdx[i_] := 2i
Wolfram Language code: getRightChildIdx[i_] := 2i + 1
Wolfram Language code: getParentIdx[i_] := Quotient[i, 2]

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

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Reverse[{9, 8, 7, 6, 5, 4, 3, 2, 1}]];

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

Wolfram Language code: MinHeapify[ds]; Normal[ds]

下面的函数生成一个树：

Wolfram Language code: MakeHeapTree[array_] := Module[{data = Normal[array]}, TreeGraph[Flatten[MakeHeapTree[data, 1]], VertexLabels -> "Name", GraphLayout -> {"LayeredEmbedding", "RootVertex" -> First[data]}] ] MakeHeapTree[arry_, idx_] := { If[getLeftChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getLeftChildIdx[idx]]]], MakeHeapTree[arry, getLeftChildIdx[idx]] }, Nothing ], If[getRightChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getRightChildIdx[idx]]]], MakeHeapTree[arry, getRightChildIdx[idx]] }, Nothing ] }

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

Wolfram Language code: MakeHeapTree[ds]

属性和关系  (5)

InputForm  (1)

InputForm 返回 "DynamicArray" 的序列化内容：

Wolfram Language code: InputForm[CreateDataStructure["DynamicArray", Range[10]]]

这种序列化形式可用于重建数据结构：

Wolfram Language code: DataStructure["DynamicArray", {"Data" -> {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}]

Length  (1)

Length 可用于获取 "DynamicArray" 中元素的数量：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; Length[ds]

"Length" 运算可完成同样的操作：

Wolfram Language code: ds["Length"]

Normal  (1)

Normal 可用于获取 "DynamicArray" 的元素：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; Normal[ds]

"Elements" 运算可完成同样的操作：

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQ 可用于测试两个数组是否包含相同元素，以及顺序是否相同：

Wolfram Language code: ds1 = CreateDataStructure["DynamicArray", Range[10]]; ds2 = CreateDataStructure["DynamicArray", Range[10]]; ds1 === ds2

如果丢弃一个元素，数组就不再相同：

Wolfram Language code: ds1["DropLast"]; ds1 === ds2

"FixedArray"  (1)

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