Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 59477
Реклама
Сейчас на сайте
Гостей: 3
На сайте нет зарегистрированных пользователей

Пользователей: 13,110
новичок: kostya001001
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Программа тестирования (тест) - вступительные экзамены (математика, физи...
Метод конечных разностей для интерполяции/экстраполяции на Delphi
Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Список переменного размера
С помощью динамических массивов вы можете построить простой список пе-
ременного размера. Новый элемент в список добавляется следующим образом. Со-
здайте новый массив, который на один элемент больше старого. Скопируйте эле-
менты старого массива в новый и добавьте новый элемент. Затем освободите старый
массив и установите указатель массива на новую страничку памяти.
Следующий фрагмент кода содержит операцию, которая добавляет элемент
в динамический массив. Для удаления элемента можно написать аналогичный код,
только массив необходимо сделать меньше.
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. Это сокращает количество необхо-
димых изменений размера массива при малых размерах списка.
Опубликовал Kest September 13 2009 01:58:07 · 0 Комментариев · 8458 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
База данных: Книж...
База для Allsubmi...
Bitmap [для кнопок]
CarGame [Исходник...
Изучаем Ассемблер
De Knop
Профессиональное ...
Delphi 2005 для .NET
Indy in Depth Глу...
Rss Parser
Progressbar
DiskInfo
Еext Editor
Шкрыль А. - Разра...
BSButton
DelphiXIsoDemo1
3d Tank [Исходник...
Приложение Клиент...
Х. М. Дейтел, П. ...
Delphi World 6.0

Топ загрузок
Приложение Клие... 100512
Delphi 7 Enterp... 90288
Converter AMR<-... 20092
GPSS World Stud... 15006
Borland C++Buil... 12720
Borland Delphi ... 8946
Turbo Pascal fo... 7093
Калькулятор [Ис... 5137
Visual Studio 2... 5018
FreeSMS v1.3.1 3554
Случайные статьи
безопасностиТабл
Класс MediaStore
Раздел 2.6
Алгоритмы WRR
Содержание
Эксперименты с при...
File: are not allo...
Нахождение геометр...
Производительность
Линии проекции
Модули в XHTML
Деструкторы в язы...
Классические игров...
Проблема ввода-выв...
Мебельные петли
домена в запросе
Потолки Екатеринбург
Класс TCanvas
Работа со списками...
Административное о...
Выбор наилучших ал...
Стандарт XPath
Операции отношения...
Игровые автоматы. ...
Контактная информация
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?