Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 101

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 95 96 97 98 99 100 < 101 > 102 103 104 105 106 107 .. 161 >> Следующая

Поясним сказанное на примере. Возьмем реализацию метода цифровой сортировки, приведенную нами в разд. 2.2, и изменим в ней систему построения списков отдельных элементов массива. В листинге 2.11 список ключей был представлен шаблоном KeyList, параметризованным типом ключей кеу, при этом в классе были определены следующие основные три метода:
// добавляет ключ key в список в качестве последнего элемента: void addKey(const Key & key);
// переносит все ключи из списка в массив array, начиная с индекса from: int toArray(Key * array, int from);
// очищает список: void clear();
Алгоритмы распределения памяти
291
Реализация этих трех методов непосредственно использовала работу с буфером памяти класса ListBuffer<Key>, указатель на который мы должны были передавать конструктору списка при его создании. Буфер памяти состоял из элементов списков класса Е1ет<кеу>, и для того, чтобы поместить очередной элемент списка в этот буфер, мы вызывали метод get:
int nextElem =* buffer->get();
Теперь поступим по-другому. Будем строить список из ключей традиционным образом, используя для связи элементов указатели. В листинге 5.1 приведен новый шаблон KeyList, в котором определение списка ключей сделано вполне традиционно. Конструктор списка здесь очень близок к традиционному. Подобный конструктор мы использовали уже многократно в примерах разд. 1.2, 2.5, 2.4 и др. При добавлении нового ключа в список будем применять оператор new так, как мы это обычно и делали, и, таким образом, функция добавления нового элемента теперь тоже примет уже ставший привычным вид.
j Листинг 5,1. Определение списка элементов для цифровой сортировки
//=_=======_========_=====_=======_=ет======_====ет====:==
// Класс KeyList представляет список ключей, связанных указателями.
/,=sssss=SSSB=sssss=s=a^^
template Cclass Кеу>
class KeyList {
Elem<Key> * first; 11 Указатель на первый элемент списка
Elem<Key> * last; // Указатель на последний элемент списка
public :
// Конструктор
KeyList() : first(NULL), last(NULL) {}
// Операция добавления нового элемента в конец списка void addKey(const Key & key) {
// Запрашиваем свободный элемент у системы распределения памяти Elem<Key> * newElem = new Е1ет<Кеу>(key);
// Присоединяем новый элемент к уже имеющемуся списку if (first == NULL) { first = newElem;
} else {
last->next = newE'lem;
}
last = newElem;
}
292
Гпава 5
// Операция toArray переносит все элементы списка во фрагмент // массива array, начиная с элемента с индексом from.
//В качестве результата функция выдает индекс первого элемента // массива, следующего за перенесенным фрагментом int toArray(Key * array, int from) {
// Организуем просмотр элементов с помощью указателя ptr.
Elem<Key> * ptr = first; while (ptr != NULL) {
array[from++] = ptr->value; ptr = ptr->next;
}
return from;
}
// Функция очистки списка просто обнуляет указатели //на первый и последний элементы списка, void clear() { first = last = NULL; }
};
Немного необычно реализован только метод clear для удаления из списка всех его элементов: в нем не происходит освобождения памяти с помощью оператора delete, как это обычно делалось при реализации списков, вместо этого просто обнуляются указатели на первый и последний элементы списка.
Если реализацию шаблона Е1ет<кеу> оставить без изменения (напомним, что в разд. 2.2 он был описан в виде простой структуры с двумя полями, представляющей элемент списка ключей), то цифровая сортировка будет корректно работать с таким измененным определением шаблона KeyList, но мы потеряем все преимущества, полученные нами ранее от реализации собственной системы отведения памяти под элементы списков в буфере ListBuffer<Key>. Для того чтобы оператор new Eiem<Key> обращался за очередным элементом памяти не в стандартную систему распределения памяти, а к нашему буферу, надо всего лишь переопределить оператор new в классе Е1ет<Кеу>.
Если мы хотим использовать свою систему управления памятью, то мы должны также несколько изменить реализацию шаблона ListBuffer, приспособив его для использования в операторах new и delete. Изменим реализацию метода get таким образом, чтобы вместо индекса свободного элемента выдавать указатель на этот элемент. Если это сделать, то отпадает также надобность в специальной операции доступа к элементам буфера, который был реализован в листинге 2.11 в виде оператора индексации в классе ListBuffer. Итак, реализация нашей системы принимает вид, показанный в листинге 5.2.
Алгоритмы распределения памяти
293
Чтобы упростить доступ к системе, в классе ListBuffer определена также статическая переменная singleton, назначение которой — представлять систему распределения памяти вне класса ListBuffer. Доступ к ней осуществляется с помощью статической общедоступной функции getinstance. В такой ситуации конструктор системы должен быть скрыт от ее пользователей; вместо этого в открытом доступе имеется статическая функция setNewBuffer, с помощью которой можно создать новый буфер памяти и записать указатель на него в переменную singleton.
Предыдущая << 1 .. 95 96 97 98 99 100 < 101 > 102 103 104 105 106 107 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.