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

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

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

В листинге 5.5 представлена реализация словаря в виде определения класса TreeDictionary и реализация операции добавления нового слова в словарь. На приложенном компакт-диске в папке "Chapter5\5.2\constBiocks" вы можете найти и реализацию некоторых других операций, а также пример работы с таким словарем.
гг'...............*:.....¦:.т-.7:.........*..-..г7.......*....................?
[ Листинг 5,5. Добавлениеслов в словарь с распределением памяти под узлы j
! с помощью собственной системы управления памятью j
//--------- treedictionary.h -------------------------------------------------
//===========:=====================================================:=======:
// Класс TreeDictionary реализует простое бинарное дерево слов // с хранением узлов дерева в системе распределения памяти,
// представленной объектом класса BlockBuffer //=======^=========^=====^====^====^==================:
class TreeDictionary {
// Вложенная структура Treeitem представляет узел дерева struct Treeitem {
string word; // Хранящееся в словаре слово
Treeitem * left, // Ссылка на левое поддерево (меньшие слова)
* right; // Ссылка на правое поддерево (большие слова)
300
Гпава 5
// Конструктор задает содержимое узла Treeitem (string word,
Treeitem * left = NULL, Treeitem * right = NULL)
: word(word), left(left), right(right) {}
};
// Корень дерева:
Treeitem * root;
// Система управления памятью для узлов дерева BlockBuffer <sizeof(Treeitem)> * memoryManagement;
public :
// Конструктор дерева создает пустое дерево и систему // управления памятью. Аргумент capacity задает максимальное // количество слов, которые могут одновременно храниться в словаре. TreeDictionary(int capacity)
: root(NULL),
memoryManagement(new BlockBuffer<sizeof(Treeitem)>(capacity))
{}
// Деструктор словаря просто уничтожает систему управления памятью ^TreeDictionary() { delete memoryManagement; }
// Функция добавления нового слова в словарь: void addWord(string w);
private:
// Вспомогательная рекурсивная функция, реализующая простой // алгоритм добавления нового узла в дерево словаря void addWord(const string & w, Treeitem ** root);
};
//-------- treedictionary.cpp --------------------------------------------
// Функция добавления нового слова в словарь просто обращается // к рекурсивному варианту функции с тем же именем void TreeDictionary::addWord(string w) { addWord(w, & root);
}
// Рекурсивная функция добавления нового слова в словарь void TreeDictionary::addWord(const string & w, Treeitem ** root) { if (*root == NULL) {
Алгоритмы распределения памяти
301
// Достигнут лист дерева. Новый узел создается в памяти,
// выделяемой системой управления памяти memoryManagement Treeitem *item = new (memoryManagement->get () ) Treeitem (w) ;
*root = item;
} else if (w < (*root)->word) {
// Слово добавляется в левое поддерево addWord(w, &(*root)->left);
} else {
// Слово добавляется в правое поддерево addWord(w, &(*root)->right);
}
}
Распределение памяти блоками постоянной длины хорошо подходит для случая, когда в системе управления памятью хранятся объекты одного и того же типа. Если же система создается для случая, когда она должна выделять память разного размера для хранения различных объектов, то простой алгоритм, предложенный в этом разделе, не годится. В следующем разделе мы рассмотрим другие алгоритмы распределения памяти и приведем способы их реализации.
5.3. Распределение памяти блоками переменной длины
Для распределения памяти блоками переменной длины можно использовать практически тот же способ, что и для управления блоками одной и той же длины. Разница состоит в том, что теперь в каждом свободном блоке необходимо хранить длину этого блока, и, кроме того, свободный блок при повторном его выделении системой может быть использован не полностью. Если имеется свободный блок некоторого размера, а в систему поступил запрос на блок памяти меньшего размера, то этот свободный блок можно разделить на две части и, выдав одну из этих частей по запросу, оставить другую часть блока в системе.
К сожалению, именно из-за возможного дробления блоков простая система распределения памяти, приведенная в предыдущем разделе, оказывается неэффективной. Если не предпринимать никаких дополнительных усилий, то в процессе эксплуатации системы распределения памяти свободные блоки становятся все меньше по размеру, и это в конце концов может привести к тому, что система не сможет удовлетворить очередной запрос к памяти, даже несмотря на то, что фактически свободная память в системе имеется. Такое явление называют фрагментацией памяти, и борьба с фрагментацией является
302
Гпава 5
одним из главных вопросов, которые ставят перед собой разработчики систем распределения памяти.
Прежде всего, укажем на две возможные причины потерь памяти при ее выделении системой. Во-первых, как уже было сказано, в системе может содержаться большое количество отдельных свободных блоков маленького размера, так что система не сможет найти непрерывный участок памяти достаточной длины. Такой вид фрагментации обычно называют внешней фрагментацией памяти. Возможный способ борьбы с внешней фрагментацией — это всевозможные алгоритмы, позволяющие находить расположенные рядом свободные блоки памяти и соединять их в блоки большего размера.
Предыдущая << 1 .. 98 99 100 101 102 103 < 104 > 105 106 107 108 109 110 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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