Чтение онлайн

на главную - закладки

Жанры

Основы объектно-ориентированного программирования

Мейер Бертран

Шрифт:
Надо сказать, что стеки присутствуют в дидактических представлениях абстрактных типов данных в таком большом количестве, что Э. Дейкстра как-то остроумно заметил, что "абстрактные типы данных являются прекрасной теорией, целью которой является описание стеков". Совершенно справедливо. Но в следующих лекциях курса понятие абстрактных типов данных так часто применяется в гораздо более сложных случаях, что я не чувствую стыда, начиная рассмотрение с этого ключевого примера. Он является простейшим из известных мне примеров, содержащих в себе почти все важные идеи абстрактных типов данных.

Представления

стеков

Существует несколько физических представлений стеков:

Рис. 6.1. Три возможных представления стеков

Этот рисунок иллюстрирует три наиболее популярных представления стеков. Для удобства ссылок дадим каждому из них свое имя:

[x]. МАССИВ_ВВЕРХ: представляет стек посредством массива representation и целого числа count, с диапазоном значений от 0 (для пустого стека) до capacity– размера массива representation, элементы стека хранятся в массиве и индексируются от 1 до count.

[x]. МАССИВ_ВНИЗ: похож на МАССИВ_ВВЕРХ, но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free, является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free+1.

[x]. СПИСОЧНОЕ: при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item, содержащем сам элемент, и previous, содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека.

Рядом с каждым представлением на рисунке приведен фрагмент программы (в духе Паскаля), с соответствующей реализацией основной стековой операции: втолкнуть элемент x на вершину стека (push).

Для представлений с помощью массивов МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ команды увеличивают или уменьшают указатель на вершину (count или free) и присваивают x соответствующему элементу массива. Так как эти представления поддерживают стеки с не более чем capacity элементами, то корректные реализации должны содержать защищающие от переполнения тесты соответствующего вида:

if count " capacity then ...

if free " 0 then ...,

(на рисунке они для простоты опущены).

Для представления СПИСОЧНОЕ вталкивание элемента

требует четырех действий:

[x]. создания новой ячейки n (здесь оно выполняется с помощью процедуры Паскаля new, которая выделяет память для нового объекта);

[x]. присваивания x полю item новой ячейки;

[x]. присоединения новой ячейки к вершине стека путем присвоения ее полю previous текущего значения указателя last;

[x]. изменения last так, чтобы он ссылался на только что созданную ячейку.

Хотя эти представления встречаются чаще всего, существует и много других представлений стеков. Например, если вам нужны два стека с однотипными элементами и память для их представления ограничена, то можно использовать один массив с двумя метками вершин count как в представлении МАССИВ_ВВЕРХ и free как в МАССИВ_ВНИЗ. При этом один стек будет расти вверх, а другой - вниз. Условием полного заполнения этого представления является равенство count= free.

Преимущество такого представления состоит в уменьшении риска переполнить память: при двух массивах размера n, представляющих стеки способом МАССИВ_ВВЕРХ или МАССИВ_ВНИЗ, память исчерпается, как только любой из стеков достигнет n элементов. А в случае одного массива размера 2n, содержащего два стека лицом к лицу, работа продолжается до тех пор, пока их общая длина не превысит 2n, что менее вероятно, если стеки растут независимо друг от друга. (Для любых переменных p и q, max (p +q) "= max (p) + max (q)).

Рис. 6.2. Представление двух стеков лицом к лицу

Каждое из этих и другие возможные представления полезны в разных ситуациях. Выбор одного из них в качестве эталона для определения стека был бы типичным примером излишней спецификации. Почему мы должны, например, предпочесть МАССИВ_ВВЕРХ представлению СПИСОЧНОЕ? Большинство видимых свойств представления МАССИВ_ВВЕРХ– массив, число count, верхняя граница - несущественны для понимания представляемой ими структуры.

Опасность излишней спецификации

Почему так плохо использовать конкретное представление в качестве спецификации?

Можно напомнить результаты изучения Линцем (Lientz) и Свенсоном (Swanson) стоимости сопровождения. Было установлено, что более 17% стоимости ПО приходится на изменения в форматах данных. Ясно, что метод, который ставит анализ и проектирование в зависимость от физического представления структур данных, не обеспечит разработку достаточно гибкого ПО.

Поделиться:
Популярные книги

Часовая башня

Щерба Наталья Васильевна
3. Часодеи
Фантастика:
фэнтези
9.43
рейтинг книги
Часовая башня

Камень Книга седьмая

Минин Станислав
7. Камень
Фантастика:
фэнтези
боевая фантастика
6.22
рейтинг книги
Камень Книга седьмая

Путь Шедара

Кораблев Родион
4. Другая сторона
Фантастика:
боевая фантастика
6.83
рейтинг книги
Путь Шедара

Страж Кодекса. Книга VII

Романов Илья Николаевич
7. КО: Страж Кодекса
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Страж Кодекса. Книга VII

Наследник павшего дома. Том I

Вайс Александр
1. Расколотый мир
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Наследник павшего дома. Том I

Идеальный мир для Демонолога 9

Сапфир Олег
9. Демонолог
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Демонолога 9

Отверженный III: Вызов

Опсокополос Алексис
3. Отверженный
Фантастика:
фэнтези
альтернативная история
7.73
рейтинг книги
Отверженный III: Вызов

Бастард

Майерс Александр
1. Династия
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Бастард

Агенты ВКС

Вайс Александр
3. Фронтир
Фантастика:
боевая фантастика
космическая фантастика
5.00
рейтинг книги
Агенты ВКС

Возвышение Меркурия. Книга 17

Кронос Александр
17. Меркурий
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 17

Жандарм 5

Семин Никита
5. Жандарм
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Жандарм 5

Кодекс Крови. Книга ХIV

Борзых М.
14. РОС: Кодекс Крови
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Кодекс Крови. Книга ХIV

Последний реанорец. Том I и Том II

Павлов Вел
1. Высшая Речь
Фантастика:
фэнтези
7.62
рейтинг книги
Последний реанорец. Том I и Том II

Ведунские хлопоты

Билик Дмитрий Александрович
5. Бедовый
Фантастика:
юмористическое фэнтези
городское фэнтези
мистика
5.00
рейтинг книги
Ведунские хлопоты