4

header

1

2

3

4

data next

Рис.1Пример структуры данных.

Ячейки в цепочке 1 имеют тип

type

recordtype = record

cursor: integer;

prt recordtype

end

На цепочку можно ссылаться с помощью переменной header (заголовок), имеющей тип recordtype, header указывает на анонимную запись типа recordtype 1 .Эта запись имеет 4 значения в поле cursor. Рассматривается 4 как индекс массива reclist. Эта запись имеет истинный указатель в поле prt на другую анонимную запись, которая, в свою очередь, указывает на индекс 4 массива reclist и имеет нуль-указатель в поле prt.

Абстрактный тип данных «Список».

Списки являются чрезвычайно гибкой структурой, так как их легко сделать большими или меньшими, и их элементы доступны для вставки или удаления в любой позиции списка. Списки также можно объединять, или разбивать на меньшие списки. Списки регулярно используются в приложениях, например в программах информационного поиска, трансляторах программных языков или при моделировании различных процессов. Методы управления памятью широко используют технику обработки списков. Далее будут описаны основные операции, выполняемые над списками, и представлены структуры данных для списков, которые эффективно поддерживают различные подмножества таких операций.

В математике список представляет собой последовательность элементов определённого типа, который в общем случае будет обозначаться как elementtype (тип элемента). Список будет часто представляться в виде последовательности элементов, разделённых запятыми: a1, a2, …, an, где n > 0 и все ai имеют тип elementtype. Количество элементов n будет называться длиной списка. Если n > 1 ,то а1 называется первым элементом списка. В случае n = 0 список будет называться пустым, т.е. не содержащий элементов.

Важное свойство списка заключается в том, что его элементы можно линейно упорядочить в соответствии с их позицией в списке. Говорится, что элемент аi предшествует аi+1 для i = 1, 2, …, n-1 и аi следует за ai-1 для i = 2, 3, …, n. Говорится также, что элемент аi имеет позицию i. Кроме того, постулируется существование позиции, следующей за последним элементом списка. Функция END(L) будет возвращать позицию, следующую за позицией n в n-элементном списке L. Следует отметить, что позиция END(L), рассматриваемая как расстояние от начала списка, может изменяться при уменьшении или увеличении списка, в то время как другие позиции имеют фиксированное (неизменное) расстояние от начала списка.

Для формирования абстрактного типа данных на основе математического определения списка нужно задать множество операторов, выполняемых над объектами типа LIST2 (список). Однако не существует одного множества операторов, выполняемых над списками, удовлетворяющего сразу все приложения.

Чтобы показать некоторые общие операторы, выполняемые над списками, предположим, что имеем приложение, содержащее список почтовой рассылки, который мы хотим очистить от повторяющихся адресов. Концептуально эта задача решается очень просто: для каждого элемента списка удаляются все последующие элементы, совпадающие с данным. Однако для записи такого алгоритма необходимо определить операторы, которые должны найти первый элемент списка, перейти к следующему элементу, осуществить поиск и удаление элементов.

Теперь перейдём к непосредственному определению множества операторов списка. Примем обозначения: L – список объектов типа elementtype, x – объект этого типа, p – позиция элемента в списке. Следует отметить, что «позиция» имеет другой тип данных, чья реализация может быть различной для разных реализаций списков. Обычно позиция понимается как множество целых положительных чисел, но на практике могут встретиться другие представления.