Упорядоченный список

Глава 9. Списки, стеки, очереди

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

Упорядоченный список

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

type TInfo = integer;

PNode = ^TNode;

TNode = record

Info: TInfo;

Next: PNode

end;

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

q список пуст;

q новый элемент меньше первого элемента существующего списка, и его следует поместить в начало;

q новый элемент требуется поместить в середину существующего списка.

В последнем варианте требуется сначала определить место, куда следует вставить новый элемент. Для этого нужно двигаться по списку до тех пор, пока либо не найдется элемент, больший или равный вставляемому, либо не будет достигнут конец списка. Для удобства вставки используем дополнительный указатель — на предыдущий элемент. Все это учтено в процедуре, приведенной в листинге 9.1.

Листинг 9.1. Процедура Вставка в упорядоченный список

procedure Insert(var p: PNode; e: TInfo);

// p — указатель на список, e — значение нового элемента

var q,r : PNode;

Found: Boolean; // признак того, что место для вставки найдено

begin

if p=nil then begin // список пуст, создание первого элемента

new(p);

with p^ do begin

Info:=e; Next:=Nil;

end;

end else begin // вставка элемента в список

if e<=p^.Info then begin // вставка перед списком

new(q);

with q^ do begin

Info:=e; Next:=p

end;

p:=q

end

else begin // поиск места и вставка

found:=false; q:=p^.Next; r:=p;

while not found and (q<>Nil) do // поиск места для вставки

if e<=q^.Info then found:=true // место найдено

else begin // двигаемся дальше

r:=q; q:=q^.Next;

end;

// вставка должна быть между r и q

new(r^.Next); r:=r^.Next;

with r^ do begin

Info:=e; Next:=q

end;

end

end

end;

Для иллюстрации работы с упорядоченным списком создадим проект. Форма проекта показана на рис. 9.1.

Рис. 9.1. Форма работы с упорядоченным списком.

На форме выставлены четыре компонента:

q компонент Edit ввода следующего значения для вставки в список;

q кнопка , при нажатии на которую производится вставка;

q компонент Panel для вывода списка;

q кнопка Очистить, удаляющая список и подготавливающая ввод нового списка.

q Обработчик события кнопки Очистить очищает поле компонента Edit, панель вывода и инициализирует список:

procedure TFormSortList.ClearClick(Sender: TObject);

begin

EditInsert.Text:='';

PanelOutList.Caption:='';

DelList(q); // удаление старого списка, инициализация нового

EditInsert.SetFocus;

end;

q Обработчик события кнопки , представленный в листинге 9.2, вставляет значение из поля компонента Edit в список:

Листинг 9.2. Вставка в упорядоченный список (событие Click кнопки )

procedure TFormSortList.SpeedButtonInsertClick(Sender: TObject);

begin

s:=EditInsert.Text; x:=StrToInt(s); // формирование очередного числа

Insert(q,x); // вставка в список

s:=''; r:=q;

while r<>nil do begin // собираем список для вывода

s:=s+' '+IntToStr(r^.Info);

r:=r^.Next;

end;

PanelOutList.Caption:=s; // вывод списка

EditInsert.Text:=''; // очистка поля Edit

EditInsert.SetFocus;

end;

Для работы приложения необходим еще модуль работы со списком. Он называется UnitList и содержит, кроме вышеприведенных описания списка и процедуры Insert, еще процедуру DelList — удаление списка:

procedure DelList(var p: PNode);

// удаление списка с освобождением занимаемой им памяти

var q: PNode;

begin

while p<>Nil do begin

q:=p; p:=p^.Next;

dispose(q);

end;

end;