Удаление двунаправленного списка

Операция удаления двунаправленного списка реализуется аналогично удалению однонаправленного списка.

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

Основная особенность такой организации состоит в том, что в этом списке нет элементов, содержащих пустые указатели, и, следовательно, нельзя выделить крайние элементы.

Циклические списки, так же как и линейные, бывают однонаправленными и двунаправленными.

Циклический однонаправленный список похож на линейный однонаправленный список, но его последний элемент содержит указатель, связывающий его с первым элементом (рис. 32.1).

Для полного обхода такого списка достаточно иметь указатель на произвольный элемент, а не на первый, как в линейном однонаправленном списке. Понятие "первого" элемента здесь достаточно условно и не всегда требуется. Хотя иногда бывает полезно выделить некоторый элемент как "первый" путем установки на него специального указателя. Это требуется, например, для предотвращения "зацикливания" при просмотре списка.

Рис. 32.1. Циклический однонаправленный список

Основные операции, осуществляемые с циклическим однонаправленным списком:

создание списка;

печать (просмотр) списка;

вставка элемента в список;

удаление элемента из списка;

поиск элемента в списке;

проверка пустоты списка;

удаление списка.

Для описания алгоритмов этих основных операций будем использовать те же объявления, что и для линейного однонаправленного списка.

Циклический двунаправленный список похож на линейный двунаправленный список, но его любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке, а второй указывает на предыдущий элемент (рис. 32.2).

Рис. 32.2. Циклический двунаправленный список

Основные операции, осуществляемые с циклическим двунаправленным списком:

создание списка;

печать (просмотр) списка;

вставка элемента в список;

удаление элемента из списка;

поиск элемента в списке

проверка пустоты списка;

удаление списка.

Для описания алгоритмов этих основных операций будем использовать те же объявления, что и для линейного двунаправленного списка.

Вопрос №23 Шаблоны проектирования. Обзор.

В разработке программного обеспечения, шаблон проектирования или паттерн (англ. design pattern) — повторимая архитектурная конструкция, представляющая собой решение проблемы проектирования в рамках некоторого часто возникающего контекста.

Обычно шаблон не является законченным образцом, который может быть прямо преобразован в код; это лишь пример решения задачи, который можно использовать в различных ситуациях. Объектно-ориентированные шаблоны показывают отношения и взаимодействия между классами или объектами, без определения того, какие конечные классы или объекты приложения будут использоваться.

«Низкоуровневые» шаблоны, учитывающие специфику конкретного языка программирования, называются идиомами. Это хорошие решения проектирования, характерные для конкретного языка или программной платформы, и потому не универсальные.

На наивысшем уровне существуют архитектурные шаблоны, они охватывают собой архитектуру всей программной системы.

Правильно сформулированный шаблон проектирования позволяет, отыскав удачное решение, пользоваться им снова и снова.

Шаблоны определяют лишь общий подход. Любой шаблон проектирования определяет лишь общий подход к решению задачи. Потребуется или нет добавлять новые функции, зависит от конкретной ситуации. Шаблоны проектирования в сущности только наброски или эскизы, показывающие, как правильно приступить к работе. Не следует представлять их себе некими догматами, высеченными на камне.

Первоначальное происхождение – из архитектуры. Архитектор Кристофер Александер установил, что, сфокусировав внимание на структурах, предназначенных для решения подобных задач, можно обнаружить сходство между различными проектами, которым присуще высокое качество. Он назвал эти сходства шаблонами.

Он определил понятие шаблона как "решение проблемы в контексте". Каждый шаблон описывает проблему, которая возникает в данной среде снова и снова, а затем предлагает принцип ее решения таким способом, который можно будет применять многократно, получая каждый раз результаты, не повторяющие друг друга.

В качестве заключения укажем четыре компонента, которые, по мнению Александера, должны присутствовать в описании каждого шаблона.

• Имя шаблона.

• Назначение шаблона и описание задачи, которую он призван решать.

• Способ решения поставленной задачи.

• Ограничения и требования, которые необходимо принимать во внимание при решении задачи.

Александер принял как постулат, что с помощью шаблонов может быть решена любая архитектурная задача, с которой столкнется проектировщик. Затем он пошел дальше и высказал утверждение о том, что совместное использование нескольких шаблонов позволит решать комплексные архитектурные проблемы.

Хотя в начале 1990_х над шаблонами проектирования работали многие исследователи, наибольшее влияние на это сообщество оказала книга Гаммы, Хелма, Джонсона и Влиссайдеса Шаблоны проектирования: элементы многократного использования кода в объектно_ориентированном программировании. Эта работа приобрела очень широкую известность. Свидетельством ее популярности служит тот факт, что четыре автора книги получили шутливое прозвище "банда четырех".

В книге рассматривается несколько важных аспектов проблемы.

• Применение идеи шаблонов проектирования в области разработки программного обеспечения.

• Описание структур, предназначенных для каталогизации и описания шаблонов

проектирования.

• Обсуждение 23 конкретных шаблонов проектирования.

• Формулирование концепций объектно-ориентированных стратегий и подходов, построенных на применении шаблонов проектирования.

Теперь, когда мы знаем, что такое шаблоны проектирования, можно попытаться ответить на вопрос, зачем нужно их изучать.

• Возможность многократного использования. Повторное использование решений из уже завершенных успешных проектов позволяет быстро приступить к решению новых проблем и избежать типичных ошибок. Разработчик получает прямую выгоду от использования опыта других разработчиков, избежав необходимости вновь и вновь изобретать велосипед.

• Применение единой терминологии. Профессиональное общение и работа в группе (команде разработчиков) требует наличия единого базового словаря и единой точки зрения на проблему. Шаблоны проектирования предоставляют подобную общую точку зрения как на этапе анализа, так и при реализации проекта.

Однако существует и третья причина, по которой следует изучать шаблоны проектирования.

Шаблоны проектирования предоставляют нам абстрактный высокоуровневый взгляд как на проблему, так и на весь процесс объектно-ориентированной разработки. Это помогает избежать излишней детализации на ранних стадиях проектирования.

Порождающие шаблоны (Creational) — шаблоны проектирования, которые абстрагируют процесс инстанцирования. Они позволяют сделать систему независимой от способа создания, композиции и представления объектов. Шаблон, порождающий классы, использует наследование, чтобы изменять инстанцируемый класс, а шаблон, порождающий объекты, делегирует инстанцирование другому объекту.

Структурные шаблоны (Structural) определяют различные сложные структуры, которые изменяют интерфейс уже существующих объектов или его реализацию, позволяя облегчить разработку и оптимизировать программу.

Поведенческие шаблоны (Behavioral) определяют взаимодействие между объектами, увеличивая таким образом его гибкость.

Date: 2016-07-25; view: 393; Нарушение авторских прав