Организация и функционирование компьютеров

Существует другая возможность описывать упорядоченную последовательность данных – списком. В наборе технологических средств программирования списком называется совокупность однотипных упорядоченнных данных, снабженных средствами, позволяющими переходить от предыдущего значения к последующему. Наиболее естественно обеспечивается переход с помощью указателей. Именно, элемент списка будет состоять из двух частей: первая часть состоит из содержательных данных списка, а вторая часть представляет собой указатель, ссылающийся на следующий элемент списка. Указатель на первый элемент списка хранится в фиксированной переменной. Если он неопределенный (равен Nil), то список пуст. Указатель следующего элемента в последнем элементе списка равен Nil. Общая схема списка такова:

начальный элемент1 элемент2 … элементN NIL

указатель указатель указатель указатель

Описание элемента списка в Паскале имеет одну особенность, которую мы поясним на примере. Пусть сами данные описываются как запись типа rec. Тогда элемент списка будет записью из двух полей: одно типа rec и другое типа указатель на элемент списка.

type

rec = record end; {запись данных}

plist = ^list; {тип указателя на элемент списка }

list = record {тип элемента списка}

d: rec; {данные списка}

p: plist {ссылка на следующий элемент}

end;

var p0: plist; {ссылка на первый элемент списка}

Особенность вышеприведенного описания в том, что при определении типа указателя с именем plist испоьзуется тип list, определяемый ниже в тексте программы, а не выше, как того требует фундаментальное правило Паскаля. Разобранный случай – это единственное исключение из этого правила.

Список, устроенный так, как это было описано выше, называется линейным однонаправленным (или односвязным) списком. При работе с таким списком можно выделить три основные функции:

• поиск элемента списка по критерию;

• добавление элемента внутрь списка;

• удаление элемента из списка.

Пусть функция: {function order (r1,r2: rec): integer;} возвращает -1, 0 или +1 в зависимости от того, предшествует, совпадает или следует запись r1 за записью r2 (порядок следования зависит от полей записи). Тогда поиск в линейном списке записи r заключается в последовательном переборе элементов списка и сравнении записи r с полем d элемента списка. Перебор начинается с элемента p0^ и заканчивается тогда, когда order(r,d)=0 (запись найдена), либо order(r,d)=1 (нужной записи не существует), либо указатель на следующую запись равен Nil (список кончился).

function find_in_list (r: rec): plist; {возвращает указатель на элемент, Nil – неудача}

var next: plist;

begin

find_in_list := Nil;

next := po; {Первый элемент списка}

while (nextNil) and (order (r, next^.d) >= 0) do

{Cписок не кончился и исходная запись больше текущей}

if order (r, next^.d) = 0

then begin find_in_list := next; break end {Записи совпадают}

else next := next.p; {исходная больше текущей; продолжить поиск}

end;

Для того, чтобы добавить элемент в список, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после). В модифицированном списке элемент до должен указывать на вставленный элемент, а вставленный – на элемент после. Алгоритм обязан правильно обрабатывать случаи, когда элемент вставляется в начало или конец списка. Обратите внимание, что в процедуре вставки используется указатель на указатель, что совершенно законно.

procedure include_in_list (r: rec);

var next,curr: plist; prev: ^plist;