С помощью динамических массивов вы можете построить простой список пе-
ременного размера. Новый элемент в список добавляется следующим образом. Со-
здайте новый массив, который на один элемент больше старого. Скопируйте эле-
менты старого массива в новый и добавьте новый элемент. Затем освободите старый
массив и установите указатель массива на новую страничку памяти.
Следующий фрагмент кода содержит операцию, которая добавляет элемент
в динамический массив. Для удаления элемента можно написать аналогичный код,
только массив необходимо сделать меньше.
var
List : PintArray; • // Массив.
Numltems : Integer; // Количество используемых элементов.
procedure Addltemfnew_item : Integer);
var
new_array : PintArray;
i : Integer;
begin
// Создание нового массива.
GetMem(new_array,(Numltems+l)*SizeOf(Integer)) ;
- // Копирование элементов в новый массив.
for i := 1 to Numltems do
new_array~ [ i ] := LisfMi];
// Сохранение нового элемента.
new_array [Numltems+l] := new_item,-
// Освобождение ранее выделенной памяти.
if (Numltems>0) then FreeMem(List);
// Установка указателя на новый массив.
List := new_array;
// Обновление размера.
NumItems := NumIt ems+1;
end;
Для динамических массивов Delphi 4 алгоритм добавления элемента в конец
списка будет еще проще - при изменении размера массива программа автомати-
чески создает новый и копирует в него содержимое старого.
var
List : Array Of Integer; // Массив.
procedure Addltem(new_item : Integer);
begin
// Увеличиваем размер массива на 1 элемент.
SetLength(List,Length(List)+1);
// Сохранение нового элемента.
List[High(List)] := new_item;
end;
Эта простая схема хорошо работает для небольших списков, но у нее есть два
существенных недостатка. Вр-первых, приходится часто менять размер массива.
Чтобы создать список из 1000 элементов, необходимо 1000 раз изменить размеры
массива. Ситуация осложняется еще тем, что чем больше становится список, тем
больше времени потребуется на изменение его размера, поскольку необходимо
каждый раз копировать растущий список в заново выделенную память.
Чтобы размер массива изменялся не так часто, при его увеличении можно
вставлять дополнительные элементы, например, по 10 элементов вместо 1. Когда
вы будете впоследствии прибавлять новые элементы к списку, они разместятся
в уже существующих в массиве неиспользованных ячейках, не увеличивая размер
массива. Новое приращение размера потребуется, только если пустые ячейки за-
кончатся.
Точно так же можно избежать изменения размера каждый раз при удалении
элемента из списка. Подождите, пока в массиве не накопится 20 неиспользован-
ных ячеек, и только потом уменьшайте его размер. При этом нужно оставить 10 пус-
тых ячеек для того, чтобы можно было добавлять новые элементы, не изменяя раз-
мер массива.
Обратите внимание, что максимальное число неиспользованных ячеек (20)
должно быть больше, чем минимальное (10). Это сокращает количество измене-
ний размера массива при добавлении или удалении элементов.
При такой схеме список будет содержать несколько свободных ячеек, однако
их число мало, и лишние затраты памяти невелики. Свободные ячейки позволяют
вам перестраховаться от изменения размеров массива всякий раз, когда необходи-
мо добавить или удалить элемент из списка. Фактически, если вы постоянно до-
бавляете или удаляете только один или два элемента, вам может никогда не пона-
добиться изменять размер массива.
Следующий код показывает применение этого способа для расширения списка:
var
List : PIntArray; // Массив.
Numltems : Integer; // Количество используемых элементов.
NumAllocated : Integer; // Количество заявленных элементов.
procedure Addltem(new_item : Integer);
var
new_array : PIntArray;
i : Integer;
begin
// Определение наличия свободных ячеек.
if (NumItems>=NumAllocated) then
begin
// Создание нового массива.
NumAllocated := NumAllocated+10;
GetMem(new_array,NumAllocated*SizeOf(Integer));
// Копирование существующих элементов в новый массив.
for i := 1 to NumIterns do
new.array*[i] := ListA[i];
// Освобождение ранее выделенной памяти.
if (Numltems>0) then FreeMem(List);
// Установка указателя на новый массив.
List := new_array;
end;
// Обновление количества элементов.
NumIterns := NumItems+1;
// Сохранение нового элемента.
new_аггаy^[Numltems] := new_item;
end;
Для Delphi, начиная с 4 версии, этот код будет выглядеть следующим образом:
var
List : Array Of Integer; // Массив.
Numltems : Integer; // Количество используемых элементов.
procedure Addltem(new_item : Integer);
begin
// Определение наличия свободных ячеек.
if (NumItems>=Length(List)) then
begin
// Создание нового массива.
SetLength(List,Length(List)+10)
end;
// Обновление количества элементов.
Numltems := NumIterns+1;
// Сохранение нового элемента.
List[Numltems] := new_item;
end;
Но для очень больших массивов это не самое удачное решение. Если вам ну-
жен список из 1000 элементов, к которому обычно добавляется по 100 элементов,
на изменение размеров массива будет тратиться слишком много времени. В этом
случае лучше всего увеличивать размер массива не на 10, а на 100 или более ячеек.
Тогда вы сможете прибавлять по 100 элементов одновременно без лишнего расхо-
да ресурсов.
Более гибкое решение состоит в том, чтобы сделать количество дополнитель-
ных ячеек зависящим от текущего размера списка. В таком случае для небольших
списков приращение окажется тоже небольшим. Размер массива будет изменять-
ся чаще, но на это не потребуется большого количества времени. Для больших
списков приращение размера будет больше, поэтому их размер станет изменять-
ся реже.
Следующая программа пытается поддерживать приблизительно 10% списка
свободными. Когда массив полностью заполнен, его размер увеличивается на 10%.
Если количество пустых ячеек возрастет до 20% от размера массива, программа
уменьшает его.
При увеличении размера массива добавляется как минимум 10 элементов,
даже если 10% от размера массива меньше 10. Это сокращает количество необхо-
димых изменений размера массива при малых размерах списка. |
Главная
Каталог файлов
