1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Интерфейс==
* <tex> [ X ]</tex> статический конструктор, который принимает элемент <tex> X </tex> и возвращает массив, который содержит <tex> X </tex> в качестве его единственного элемента.* <tex> LENGTH [A] </tex> возвращает длину массива <tex> A </tex>.* ε <tex> \varepsilon </tex> является пустым массивом, иногда также обозначается <tex> [ ]</tex>
* <tex> A [i] </tex> принимает массив <tex> A = [a_0, ..., a_{n-1} ] </tex> и индекс <tex> i = 0..n - 1 </tex> , затем возвращает <tex> a_i </tex>.
* <tex> CONCATENATE(A,B) </tex> конкатентирует два массива: если <tex> if A = [a_0,..., a_{n-1} ] </tex> and и <tex> B = [b_0,..., b_{m-1} ], ; n, m \geq 0</tex> , результат будет <tex> [a_0 ,..., a_{n−1}, b_0,..., b_{m-1}] </tex> . Часто записывается как <tex> A • B</tex> вместо <tex> CONCATENATE</tex> (A,B)</tex> .* <tex> HEAD</tex> (A, i) </tex> принимает на вход массив <tex> A = [a_0,...,a_{n−1}] </tex> и производный <tex> int</tex> , возвращает массив <tex> [a_0,...,a_{min(i−1,n−1)} ] </tex> . Если <tex> i < 0</tex> результатом будет <tex> [ ]</tex> .
* <tex> TAIL (A,i) </tex> принимает на вход массив <tex> A = [a_0,...,a_n−1] </tex> и производный <tex> int</tex> , возвращает массив <tex> [a_{max(i,0)} ,...,a_{n−1}]</tex> . Если <tex> i \geq n</tex> , результатом будет <tex> [ ]</tex> .
* Если <tex> B</tex> - структура, то <tex> seq (B) </tex> обозначает строку, которая представлена <tex> B</tex> .
Основываясь на вышеприведенных операциях, ADT может быть расширен следующими операциями:
* <tex> A[i] \leftarrow x </tex> является сокращенным обозначением <tex> A \leftarrow REPLACE(A,i, x)</tex> .
* <tex> INSERT[A,i, x]</tex> получает массив <tex> A = [a_0,...,a_{n-1}]</tex> , индекс <tex> i = 0..n - 1 </tex> , и новый элемент <tex> x </tex> и возвращает массив <tex> [a_0,...,a_{i-1}, x,a_i ,...,a_{n−1}] = HEAD(A,i) [x] • TAIL(A,i) </tex> , длина которого <tex> n-1</tex> .
* <tex> LEFTPART (A) </tex> : возвращает массив, представляющий последовательность префикса <tex> A</tex> .* <tex> RIGHTPART(A) </tex> : возвращает массив, представляющий последовательность суффикса <tex> A</tex> .
==Реализация персистентных массивом массивов в виде сбалансированных деревьев==
Будем использовать сбалансированные деревья в качестве нашей стандартной реализации постоянных массивов. (Реализации сбалансированных деревьев, таких как AVL-деревья и B-деревья, можно найти в соответствующих разделах сайта)
Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.
