81
правка
Изменения
м
→Интерфейс: miniscule TeX-segment fixes
* <tex> [ X ]</tex> статический конструктор, который принимает элемент X и возвращает массив, который содержит X в качестве его единственного элемента.
* <tex> LENGTH [A] </tex> возвращает длину массива A.
* ε <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> .
==Реализация персистентных массивом в виде сбалансированных деревьев==
