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

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

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 40 41 42 43 44 45 < 46 > 47 48 49 50 51 52 .. 161 >> Следующая

// Проверка переполнения: старшая единица в слове // служит маркером дна стека
if (stack & 0x80000000) throw StackOverflow();
stack «= 1; // содержимое сдвигается влево на один бит
stack |= (е & 1); // новый элемент записывается в младший бит
}
// Операция выталкивания элемента из стека void pop() {
// стек пуст, если в нем содержится только маркер дна стека if (stack == 1) throw StackUnderflow();
stack »= 1; // Содержимое слова сдвигается вправо
}
Базовые алгоритмы
129
II Операция выдачи содержимого вершины стека // (ссылка на временную переменную!) int & top () {
if (stack == 1) throw StackUnderflow();
// На самом деле при такой реализации нельзя выдать полноценную // ссылку для записи значения, поскольку невозможно адресовать // один-единственный бит. Поэтому используется не очень-то красивый // суррогат: выдается ссылка на локальную временную переменную.
//В реальной работе со стеком функцию top можно использовать // только для чтения значения, но не для записи на вершину стека! int temp = stack & 1; return temp;
}
// Операция выдачи содержимого вершины стека (во временной переменной) const int & top() const {
if (stack == 1) throw StackUnderflow(); int temp = stack & 1; return temp;
}
// Операция проверки пустоты стека bool empty() const { return stack == 1;
}
};
В приведенной реализации есть один существенный недостаток. Функция доступа к значению, лежащему на вершине стека, фактически не может быть реализована в таком виде, как она заявлена в интерфейсе stack. Проблема состоит в том, что невозможно сформировать адрес одного бита внутри слова. Поэтому вместо двух вариантов функции top (), выдающей в качестве результата ссылку на значение, лежащее на вершине стека, следовало бы определить две функции, скажем, int topValue() И void replaceTop (int bit) ДЛЯ выдачи битового значения, лежащего на вершине стека и замены этого значения на новое. Конечно, реализовать такие две функции не составило бы труда, но, к сожалению, если мы хотим, чтобы у нас оставалась реализация заданного интерфейса stack, надо выдерживать этот интерфейс полностью в том виде, в котором он был заявлен. Таким образом, имеем две довольно безрадостные альтернативы: либо отказаться от того, что наша реализация является реализацией интерфейса stack, признав ее самостоятельным классом, либо смириться с тем, что функция top о в этой реализации не применима для замены значения, лежащего на вершине стека.
130
Гпава 2
Можно написать реализацию стека, основанную на той же идее, но с элементами данных, занимающими не один бит, а два или даже три. Разумеется, чем более крупные элементы записываются в стек, тем меньше их число удастся записать. Так, для элементов шириной в три бита (например, целые числа из диапазона от 0 до 7) в 32-разрядном слове хватит места для 10 элементов, так что максимальная глубина стека составит 10 позиций.
2.4. Итераторы
В этом разделе мы рассмотрим вопрос о том, как лучше всего организовать просмотр элементов сложной структуры данных. Пусть, например, некоторая программа использует определение списка целых чисел, приведенное нами в разд. 1.2. Программа может построить список, используя операции, определенные В классе IntList, такие как IntList: : addFirst И IntList: : addLast, ИЛИ удалять ИЗ него элементы С ПОМОЩЬЮ операции IntList: : remove, однако, для того, чтобы просматривать содержимое элементов списка, этих операций не достаточно. Попробуем восполнить этот недостаток.
Если в программе требуется проверять, имеется ли в списке некоторое конкретное число, то удобнее всего было бы иметь среди операций класса intList метод boolean hasEiement (int). Конечно, такую операцию определить несложно, тем более что, по-видимому, она была бы полезна во многих случаях. Однако таких ситуаций может оказаться довольно много, и не всегда получится, что соответствующая операция будет достаточно общей для того, чтобы стоило включать ее в интерфейс класса. Например, если в программе требуется подсчитывать количество отрицательных элементов списка, то, конечно, тоже можно было бы определить операцию int intList:: negatives о, но на самом деле такая операция слишком специфична для того, чтобы включать ее непосредственно в описание класса.
Имеется и еще одно соображение. Основу обеих приведенных в качестве примеров операций составляет одно и то же действие — просмотр элементов списка. Повторять это действие в реализации каждой из операций не очень разумно. Если бы удалось выделить просмотр элементов в отдельную операцию, то это не только позволило бы легко определять все действия, подобные приведенным выше, но и обеспечило бы независимость реализации просмотра элементов от конкретных действий с элементами списка.
Одно из возможных решений этой задачи — это описать абстрактное действие над элементами списка в виде класса (конечно, это опять будет абстрактный класс) и параметризовать просмотр элементов списка объектом такого класса.
Остановимся на этом решении чуть более подробно. Абстрактный класс, представляющий операцию, выполняемую над элементами списка, будет со-
Предыдущая << 1 .. 40 41 42 43 44 45 < 46 > 47 48 49 50 51 52 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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