ИСАУ: Алгоритм операций над списками в векторной форме и их программная реализация

В векторном списке элементы также располагаются в памяти в произвольном порядке. Но в самом элементе содержится только информационная область. Данные о порядке следования элементов содержатся в дополнительной области. Эта область представляет собою вектор (массив) ссылок на элементы. Порядок элементов определен порядком появления ссылок в векторе. Эта векторная область сама является динамическим объектом, т.к. наперед неизвестно количество элементов в списке и, соответственно, размер вектора не определен априори. Элемент в векторном списке идентифицируется индексом вектора ссылок. Это является основой особенностей векторного списка. Для определенности в последующем рассмотрении будем считать, что начальное значение индекса равно единице. В векторном списке реализуется прямой метод доступа к элементу в отличие от последовательного метода доступа в сцепленном списке. Эта особенность определяет множество новых свойств списка, организованного подобным образом. Принципы программной реализации векторного списка. Элементы в списке могут определяться, как и в сцепленном списке, за исключением отсутствия области связи. type PTEl = ^Person; Person = record // Информационная область Surname : string[30];    // Фамилия Name : string[20];   // Имя Patronymic : string[30];   // Отчество Age : byte; // Возраст Birthday :TDate;         // Дата рождения Salary :integer;       // Зарплата end; Рассмотрим основные отличительные черты векторного списка при выполнении следующих основных операций над списком.

• создание нового списка;
• включение элемента в список;
• удаление элемента из списка;
• поиск элемента в списке;
• сортировка элементов списка;

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

• Вектора ссылок, представляющего собой динамический массив указателей на элементы списка.
• Размера вектора, хранящегося в переменной содержащей размер динамического массива (максимально допустимое количество элементов для текущего размера вектора).
• Счетчика элементов списка, содержащего реально хранимое количество элементов в списке в данный момент.

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

1. Проверить условие того, что значение счетчика количества элементов меньше, чем размер вектора.

1.1. Если условие не выполнено, то увеличить вектор ссылок на некоторую величину и соответственно скорректировать размер вектора.

2. Занести ссылку на новый элемент в N+1 элемент вектора ссылок.
3. Увеличить на единицу значение счетчика элементов списка.

Предположим, что в списке содержится N элементов. Необходимо включить новый элемент в список после k-того элемента, где 0<k<N. Алгоритм включения элемента не в конец списка формулируется следующим образом:

1. Проверить условие k<1. Если условие выполнено, то требование не корректно. Завершить алгоритм.
2. Проверить условие k>N. Если условие выполнено, то требование не корректно. Завершить алгоритм.
3. Проверить условие k=N. Если условие выполнено, то выполнить алгоритм включения в конец списка, приведенный выше. Завершить алгоритм.
4. Проверить условие того, что значение счетчика количества элементов меньше, чем размер вектора.

4.1. Если условие не выполнено, то увеличить вектор ссылок на некоторую величину и соответственно скорректировать размер вектора.

5. Переместить в векторе ссылок на одну позицию вниз все ссылки начиная с последней и кончая k+1.
6. Занести ссылку на новый элемент в k+1 элемент вектора ссылок.

Удаление элемента Задача удаления элемента из векторного списка формулируется следующим образом. Имеем векторный список, содержащий N элементов. Необходимо удалить элемент с индексом k, где 0<k<N. Алгоритм формулируется следующим образом:

1. Проверить условие k<1. Если условие выполнено, то требование не корректно. Завершить алгоритм.
2. Проверить условие k>N. Если условие выполнено, то требование не корректно. Завершить алгоритм.
3. Проверить условие k=N. Если условие выполнено, то:

3.1. Освободить память, занимаемую k–тым элементом. 3.2. Удалить ссылку с индексом k из вектора ссылок. 3.3. Уменьшить значение счетчика количества элементов на единицу. 3.4. Завершить алгоритм.

4. Освободить память, занимаемую k–тым элементом.

4.1. Удалить ссылку с индексом k из вектора ссылок. 4.2. Переместить в векторе ссылок ссылки с индексами от k до N+1 вверх на одну позицию. 4.3. Уменьшить значение счетчика количества элементов на единицу. Поиск элемента в списке Алгоритмы поиска элемента в неупорядоченном векторном списке практически не имеет особенностей по сравнению с аналогичным алгоритмом сцепленного списка. Алгоритм поиска элемента в упорядоченном векторном списке имеет принципиальное отличие. Т.к. список упорядоченный и в векторном списке реализуется прямой доступ к элементам, то при поиске требуемого элемента возможно и целесообразно реализовать поиск методом половинного деления. При таком подходе значительно увеличивается скорость поиска, т.к. если список имеет N элементов, то максимальное количество шагов поиска равняется log2N. Сравните — в сцепленном списке среднее количество шагов поиска в лучшем случае N/4. Сортировка элементов списка Алгоритмы сортировки списка в векторной форме так же принципиально отличаются от рассмотренного выше алгоритма сортировки сцепленного списка. И это отличие также базируется на возможности прямого доступа к элементам списка. Обратим внимание на тот факт, что при сортировке списка в векторной форме достаточно перемещать в памяти только ссылки, хранимые в векторе ссылок. Изменение положения самих элементов не требуется, а это, естественно, сказывается очень положительно на скорости выполнения сортировки. Т.к. ссылки расположены в векторе фактически представляющим собой массив ссылок, то в данном случае допустимо и рационально использование любых алгоритмов сортировки массивов. А группа этих алгоритмов развита достаточно хорошо. Например, если не требуется высокого быстродействия, можно использовать простой в реализации алгоритм сортировки методом пузырька. А если количество элементов в списке значительно и требуется высокая скорость их сортировки, то необходимо использовать более сложные алгоритмы, например, алгоритм сортировки Шелла или QuickSort.