- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
3.5. Применение объектов
В последующем изложении во многих примерах будут рассматриваться особенности выполнения различных алгоритмов не над фактическими данными, а над указателями, задающими расположение этих данных. Необходимость этого состоит в отделении особенностей физического и логического представления данных от обрабатываемых их алгоритмов. Разделяя данные и средства манипулирования ими, мы будем больше основное внимание уделять характеристикам алгоритмов, а не заниматься ненужной разработкой или оптимизацией методов для числовых, строковых и любых другим типов данных.
Поскольку фактически будет проводиться работа с указателями, имеет смысл использовать структуры данных, которые хранят элементы в форме указателей. Таким образом, совокупность обрабатываемых данных должна быть определенным образом организована посредством своих указателей.
Класс TList предоставляет возможность организовать работу со списком разнотипных объектов посредством указателей. Класс позволяет добавлять, удалять, перегруппировывать, сортировать и получать доступ к объектам, на которые указывают элементы списка.
Для доступа к элементу списка служит свойство класса:
List: PPointerList;
которое представляет структуру:
PPointerList = ^TPointerList;
TPointerList = array[0..MaxListSize-1] of Pointer;
Перед работой с объектом списка его необходимо создать путем вызова конструктора:
var aList: TList;
...
aList:=TList.Create;
...
try
...
finally
aList.Free;
end;
Свойство Items позволяет выполнить обращение к элементу массива через методы чтения- записи для проверки на выход за диапазон. Свойство List выполняет прямое обращение без проверки и по скорости доступа выше. Например, для сохранения в объекте aList указателя p под первым порядковым номером следует выполнить обращение:
aList.Items[0]:=p;
или поскольку свойство Items является свойством по умолчанию:
aList[0]:=p;
Свойство Count содержит общее число элементов списка. Не все элементы списка содержат фактические указатели, некоторые могут содержать адресный ноль nil. Увеличение значения свойства Count приведет к добавлению в конец списка nil-элементов, а уменьшение – удаление элементов с конца списка. Метод Pack служит для удаления всех nil-элементов из списка и коррекции значения Count.
Свойство Capacity предназначено для управления динамической памятью при добавлении элементов. Чтение свойства позволит определить количество объектов, которые список может хранить без включения механизма перераспределения памяти. Добавление нового элемента приводит к автоматическому увеличению значения емкости. Для повышения быстродействия перед добавлением большого числа «тяжеловесных» объектов желательно предварительно задать свойство Capacity:
aList.Clear;
aList.Capacity:=Count;
for i:=1 to Count do List.Add(...);
Метод Add добавляет новый элемент, заданным своим указателем, в конец списка и возвращает его порядковый номер (индекс).
function Add(Item: Pointer): Integer;
Метод Clear удаляет все элементы из списка и устанавливает счетчик Count в 0.
Для удаления элемента из списка, заданного своим порядковым номером, служит метод Delete. После выполнения метода все элементы, следовавшие за удаленным, будут смещены, а значение счетчика уменьшено на единицу. Метод не освобождает память, ассоциированную с удаленным элементом.
procedureDelete(Index: Integer);
Метод Remove удаляет первый найденный элемент, заданный указателем, и возвращает порядковый номер элемента, предшествовавший удаленному. После выполнения метода все элементы, следовавшие за удаленным, будут смещены, а значение счетчика уменьшено на единицу.
function Remove(Item: Pointer): Integer;
Метод Extract удаляет элемент списка по указателю.
function Extract(Item: Pointer): Pointer;
Метод Exchange меняет местами содержимое двух элементов, заданных порядковыми номерами.
procedure Exchange(Index1, Index2: Integer);
Методы First и Last возвращают первый и последний элементы списка:
function First: Pointer;
function Last: Pointer;
Метод IndexOf возвращает порядковый номер первого вхождения элемента в список. При отсутствии элемента функция возвращает -1.
functionIndexOf(Item:Pointer):Integer;
Метод Insert помещает элемент в заданную позицию списка. Все элементы, начиная с заданного, смещаются вверх на один.
procedure Insert(Index: Integer; Item: Pointer);
Метод Move перемещает указатель с первой позиции на вторую.
procedure Move(CurIndex, NewIndex: Integer);
Метод Sort выполняет сортировку элементов списка в соответствии с функцией сравнения.
procedure Sort(Compare: TListSortCompare);
Прототип функции следующий:
TListSortCompare = function(Item1, Item2: Pointer): Integer;
Функция должна возвращать положительное целое, при Item1 < Item2, 0 при равенстве и отрицательное целое при Item1 > Item2.
При уничтожении объекта списка TList память, выделенная под элементы, не освобождается. В таких случаях говорят, что объект не владеет своими данными. В некотором роде это преимущество, поскольку можно быть уверенным в сохранности данных. Однако существует проблема, связанная с ручным освобождением элементов списка. Следующий код удаления некорректен:
for i:=0 to aList.Count-1 do
begin
TObject(aList[i]).Free;
aList.Delete(i);
end;
Ошибка заключается в том, что при очередном удалении элемента уменьшается общее их количество, а верхняя граница переменной цикла остается прежней. Правильнее было бы организовать обратный цикл и начать удалять с последнего элемента:
for i:=aList.Count-1 downto 0 do
begin
TObject(aList[i]).Free;
aList.Delete(i);
end;