Сортировка динамических массивов

Операции с динамическими массивами

Линейный список как абстрактный тип данных

Теперь сформируем список из n элементов:

p : = NIL;
WHILE n>0 DO
BEGIN
New(q);
q^.next:=p;
p:=q;
q^.number:=n;
DEC(n)
END;

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

Основная операция для любого массива – цикл по всем его элементам. Организуется он следующим образом (в примере содержимое поля data всех элементов массива p выводится на печать в файл, связанный с переменной f):

VAR q:Ptr;
BEGIN

{ вспомогательная переменная – портить p нельзя!!!}
q:=p;

WHILE q<>NIL DO
BEGIN
Writeln(f, q^.data);
q:=q^.next
END;

Важно: для такого цикла обязательно нужна вспомогательная переменная-указатель. Если по ошибке воспользоваться той же переменной p, то ее значение окажется затертым, доступ к массиву невозмиожным, да еще и возникнет утечка памяти. Отсюда правило: крайне осторожно обращайтесь с переменной-указателем на голову массива!

Описываемый массив, как и память, в которой он находится, часто называют динамическим. Например, в середину такого массива легко вставить новый элемент (Рис. 10.3).

Рис. 14.3. Вставка элемента в динамический массив.

В программе достаточно написать три строчки:

New(q); { выделили память под новый элемент }
q^.next := p^.next;
p^.next :=q;

А как быть, если нужно вставить элемент не после, а перед заданным? Назад хода нет – ссылки в массиве однонаправленные, идут от головы к хвосту и о предыдущем элементе массива ничего не известно. В таких случаях можно пойти на хитрость:

New(q);
q^ := p^;
p^.number := номер нового элемента;
p^.next:=q

Хитрость заключается в том, что новый элемент все равно вставляется после заданного, а затем два элемента обмениваются хранимыми в них данными.

Удаление элементов из динамического массива выполняется столь же легко (Рис. 10.4).

Рис. 14.4. Удаление элемента из динамического массива.

Программируется это так:

r := p^.next;
p^.next := r^.next;
Dispose(r);

И здесь не обошлось без вспомогательной переменной r.

У динамических массивов есть одно интересное свойство: новые элементы можно "засовывать" в любое место между уже включенными. Это позволяет при необходимости всегда держать динамический массив отсортированным: достаточно при поступлении нового элемента включать его не в голову или в хвост, а сразу на нужное место (Рис. 10.5).

Пусть нам необходимо держать список текстовых строк упорядоченным по алфавиту. Делается это так:

{ выделение памяти под новый элемент }

New(q);

{ ввод текстовой строки }
Readln(q^.data);

{ переменная r указывает на голову массива }
r := p;
{ цикл, пока массив не кончился и пока коды букв в просматриваемых элементах массива меньше введенных }

WHILE (r<>NIL) AND (r^.data<=q^.data) DO
r := r^.next;

{ вставка элемента }
q^.next := r^.next;
r^.next := q

Рис. 14.5. Сортировка динамических массивов.

Упорядоченность массива имеет еще одно важное преимущество: для поиска информации в упорядоченном массиве можно применить исключительно эффективный алгоритм двоичного поиска.