2.4.3.Списки

Список представляет собой последовательность элементов определенного типа. Список представляется в виде последовательности элементов, разделенных запятыми: a₁,a₂,...,a_n, где n0, и все a_i имеют некоторый тип elementtype. Количество элементов n называют длиной списка. Если n1, то a₁ называется первым элементом, а a_n - последним элементом списка. В случае n=0 имеем пустой список, который не содержит элементов.

Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке. Говорят, что элемент a_i предшествует a_i+1 для i=1,2,...,n-1 и a_i следует за a_i-1 для i = 2,3,...,n. Также говорят, что элемент a_i имеет позицию i.

Определим множества операторов списка. При этом будем использовать следующие обозначения: L - список объектов типа elementtype, x - объект типа elementtype, р - позиция элемента в списке. Обычно позиции - это целые положительные числа, но на практике могут встретиться другие представления.

1. INSERT(x,p,L). Этот оператор вставляет объект x в позицию p в списке L, перемещая элементы от позиции p и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов a₁,a₂,...,a_n, то после выполнения этого оператора он будет иметь вид a₁,a₂,..., a_p-1,x,a_p,...,a_n. Если p принимает значение ENDLIST, равное n+1, то будем иметь a₁,a₂,...,a_n,x. Если в списке L нет позиции p, и p не равно ENDLIST, то результат выполнения этого оператора не определен.

2. LOCATE(x,L). Эта функция возвращает позицию объекта x в списке L. Если в списке объект x встречается несколько раз, то возвращается позиция первого от начала списка объекта x. Если объекта x нет в списке L, то возвращается ENDLIST.

3. RETRIEVE(p,L). Эта функция возвращает элемент, который стоит в позиции p в списке L. Результат не определен, если в списке L нет позиции p. Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

4. DELETE(p,L). Этот оператор удаляет элемент в позиции p списка L. Так, если список L состоит из элементов a₁,a₂,...,a_n, то после выполнения этого оператора он будет иметь вид a₁,a₂,...,a_p-1,a_p+1,...,a_n. Результат не определен, если в списке L нет позиции p или p=ENDLIST.

5. NEXT(p,L) и PREVIOUS(p,L). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции p в списке L. Если p - последняя позиция в списке L, то NEXT(p,L)= ENDLIST. Функция NEXT не определена, когда p=ENDLIST, или в списке L нет позиции p. Функция PREVIOUS не определена, если р=1, или в списке L нет позиции p.

6. NULLIST(L). Эта функция делает список L пустым и возвращает позицию ENDLIST.

7. FIRST(L), LAST(L). Эти функции возвращают соответственно первую и последнюю позиции в списке L.

8. PRINTLIST(L). Печатает элементы списка L в порядке их расположения.

9. EMPTYLIST(L). Эта функция возвращает значение true (истина), если список L пустой и значение false (ложь) в противном случае.