Одно- и двусвязные элементы

Одно- и двусвязные элементы

В следующем примере мы обратимся к базовым структурам данных. Рассмотрим библиотечный класс LINKABLE, описывающий односвязные элементы, используемые в LINKED_LIST - одной из реализаций списков. Вот частичное описание класса:

indexing

description: "Односвязные элементы списка"

class LINKABLE [G] feature

item: G

right: LINKABLE [G]

put_right (other: LINKABLE [G]) is

-- Поместить other справа от текущего элемента.

do right := other end

... Прочие компоненты ...

end

Рис. 16.7.  Односвязный элемент списка

Ряд приложений требуют двунаправленных списков. Класс TWO_WAY_LIST - наследник LINKED_LIST должен быть также наследником класса BI_LINKABLE, являющегося наследником класса LINKABLE.

Рис. 16.8.  Параллельные иерархии

Двусвязный элемент списка имеет еще одно поле:

Рис. 16.9.  Двусвязный элемент списка

В состав двунаправленных списков должны входить лишь двусвязные элементы (хотя последние, в силу полиморфизма, вполне можно внедрять и в однонаправленные структуры). Переопределив right и put_right, мы гарантируем однородность двусвязных списков.

indexing

description: "Элементы двусвязного списка"

class BI_LINKABLE [G] inherit

LINKABLE [G]

redefine right, put_right end

feature

left, right: BI_LINKABLE [G]

put_right (other: BI_LINKABLE [G]) is

-- Поместить other справа от текущего элемента.

do

right := other

if other /= Void then other.put_left (Current) end

end

put_left (other: BI_LINKABLE [G]) is

-- Поместить other слева от текущего элемента.

... Упражнение для читателя ...

... Прочие компоненты ...

invariant

right = Void or else right.left = Current

left = Void or else left.right = Current

end

(Попробуйте написать put_left. Здесь скрыта ловушка! См. приложение A.)

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Как «продать» одно и то же содержание десять раз?

Из книги автора

Как «продать» одно и то же содержание десять раз? Метки: темы блога, вирусное распространение, видео, конкурсКогда вы пишете пост в блог, публикуете картинку или видео, размещаете подкаст, подумайте, нельзя ли использовать тот же контент еще раз или даже несколько раз. В


HTML-элементы управления и серверные элементы управления

Из книги автора

HTML-элементы управления и серверные элементы управления Еще одной новинкой технологии ASP.NET является использование серверных элементов управления. Серверный элемент управления кодируется в Web-странице, а все его события и свойства обрабатываются Web-сервером. Серверные


Элементы

Из книги автора

Элементы В табл. П2.1 приведены описания основных элементов XSLT.Таблица П2.1. Описание основных элементов XSLT Элемент Описание <xsl:apply-imports/> Инструкция. Применяет шаблонные правила, которые содержатся в импортированных преобразованиях <xsl:apply-templates select="выражение"


Игра в очко, или двадцать одно

Из книги автора

Игра в очко, или двадцать одно Исходный файл: Blackjack.fla Двадцать одно – еще одна популярная карточная игра в казино, которую легко можно перенести на компьютер. Раздающий карты следуют определенному набору правил, следовательно, можно написать программу, которая будет


14.5.6. Одно замечание по поводу программы-оболочки

Из книги автора

14.5.6. Одно замечание по поводу программы-оболочки В некоторых местах нашей программы-оболочки обнаруживается недостаток той "декларативной ясности", которая так характерна для программ, написанных на Прологе. Причина состоит в том, что нам пришлось предусмотреть в этой


ТЕХНОЛОГИИ: В одно касание

Из книги автора

ТЕХНОЛОГИИ: В одно касание Автор: Родион НасакинКогда речь заходит об ИТ-решениях в сфере безопасности платежей, на ум сразу же приходят защищенные каналы передачи данных, генераторы одноразовых паролей, разнообразные токены и т. п. Наряду с этим биометрические


Одно правило и несколько определений

Из книги автора

Одно правило и несколько определений Правило типов для решения Кэтколл имеет простую формулировку:Правило типов для КэтколлПолиморфные кэтколлы некорректны.В его основе - столь же простые определения. Прежде всего, полиморфная сущность:Определение: полиморфная


Moto X Skip: разблокировка смартфона в одно касание Николай Маслухин

Из книги автора

Moto X Skip: разблокировка смартфона в одно касание Николай Маслухин Опубликовано 19 августа 2013 Средний пользователь смартфона производит процедуру разблокировки от 40 до 100 раз в день. Это может быть довольно обременительным, даже если телефон не


§ 2.3 Элементы описания книги. Базовые структурные элементы

Из книги автора

§ 2.3 Элементы описания книги. Базовые структурные элементы В самом начале любого файла книги идет признак формата XML<?xml version="1.0" encoding="windows-1251"?>Здесь указана сигнатура принадлежности к формату XML, его версия и кодировка файла. Для русскоязычных FictionBook это обычно windows-1251


§ 2.4 Элементы описания книги (description). Элементы первого уровня

Из книги автора

§ 2.4 Элементы описания книги (description). Элементы первого уровня Элемент title-infoСодержит базовую информацию о книге (заголовок, информация об авторе и переводчике, аннотация, вхождение в серию и т.д.)Cинтаксис: <title-info>content</title-info>.Используется в элементах: descriptionВложенные


§ 2.5 Элементы описания книги (description). Элементы второго уровня

Из книги автора

§ 2.5 Элементы описания книги (description). Элементы второго уровня Элемент genreЖанр произведения.Содержимое элемента строго фиксировано и определяется файлом FictionBookGenres.xsd, входящим в состав спецификации FictionBook.Список жанров с переводом приведен в Приложении В.Cинтаксис:


§ 2.6 Элементы описания книги (description). Элементы третьего уровня (информация об авторе)

Из книги автора

§ 2.6 Элементы описания книги (description). Элементы третьего уровня (информация об авторе) Элемент first-nameИмя автора книги или документа, а также переводчика.Cинтаксис: <first-name>текст</first-name>Используется в элементах: author, translatorВложенные элементы: нетКоличество вхождений:


§ 2.8 Элементы раздела книги (section). Элементы первого уровня.

Из книги автора

§ 2.8 Элементы раздела книги (section). Элементы первого уровня. Элемент citeЦитата. Отрывок текста из другого произведения.В FictionBook с помощью тэга cite также выделяются письма, записки, надписи, списки и еще много чего.Cинтаксис: <cite>content</cite>Используется в элементах: section,


§ 2.9 Элементы раздела книги (section). Элементы второго уровня.

Из книги автора

§ 2.9 Элементы раздела книги (section). Элементы второго уровня. Элемент stanzaСтрофа стихотворения.Cинтаксис: stanza>content</stanza>Используется в элементах: poemВложенные элементы: title, subtitle, vКоличество вхождений: одно и болееАтрибуты: нетВерсия формата: 2.0Пример: см. пример


§ 2.11 Элементы абзаца (стилевые, они же inline элементы)

Из книги автора

§ 2.11 Элементы абзаца (стилевые, они же inline элементы) Элемент aСсылка или сноска.Cинтаксис: <a>content</a>Используется в элементах: code, emphasis, p, strikethrough, strong, style, subtitle, sub, sup, th, td, vВложенные элементы:     code, emphasis, strikethrough, strong, style, sub, sup, imageКоличество вхождений: