AOP_Tom1 (1021736), страница 74

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 74)

298. Всякий раз при проектировании списка важно предусмотреть все возможные ситуации, особенно случай, когда список пуст. Одной из наиболее распространенных ошибок, возникающих при работе са связанным выделением памяти, является неадекватная обработка пустых списков. Другая распространенная ошибка может быть вызвана темУ что после выполнения манипуляций структурой программист забывает изменить некоторые связи. Для того чтобы избежать ошибок первого типа, следует всегда внимательно проверять "граничные условия". А чтобы не совершать ошибок второго типа, полезно создавать диаграммы состояния до и после выпапнения некоторой операции, а затем, сравнивая их, обнаруживать те связи, которые потребуется изменить. Проиллюстрируем замечания из предыдущего абзаца, применив их к очередям. Сначала рассмотрим операцию вставки; если диаграмма (12) соответствует состоянию до вставки, то диаграмма состояния после вставки элемента данных с конца очереди будет выглядеть,так: (13) (Согласно использованным здесь обозначениям новый узел получен из списка АЧА11.) Сравнивая (12) и (13), можно предложить следующие действия, которые необходимо выполнить для вставки элемента данных Т с конца очереди: Р Чи АЧА11, 1МРО(Р) +- Т, 1.1МК(Р) +- Л, 1.1МК(К) +- Р, В <- Р.

(14) А теперь рассмотрим ьграиичное' состояние, когда очередь пуста. В этом случае состояние до вставки еще потребуется определить, а состояние "после" выглядит так: к — «~~уф )4-а Ахать Было бы желательно снова использовать операции (14), даже если для вставки в пустую очередь придется изменить оба указателя, Р и В, а не только В. Нетрудно обнаружить, что операции (14) можно будет использовать для этого, если В = 1.0С(Р), когда очередь пуста, при условии, чшо Р эз 1.1МК(1.0С(Р) ).

Иначе говоря, для реализации этой идеи значение переменной Р должно храиигпься в поле 1.1МК ее же ячейки. Для максимально эффективной проверки граничных условий при работе с пустой очередью предположим, что Р = Л. Следовательно, пустая очередь задается указателями Р = Л и В = 10С(Г).

Выполнив операции (14) при этих условиях, получим (15). Операция удаления элемента данных из очереди может быть получена аналогичным образом. Если (12) описывает состояние очереди до удаления элемента, то ее состояние после удаления будет таким: (16) ЫАП. При работе с граничными условиями следует убедиться в том, что операция удаления корректно выполняется как до, так и после опустошения очереди, Исходя из этих рассуждений, можно предложить следующий способ удаления элемента данных из очереди в общем случае: Если Р = Л, то 0МОЕВР1.0э'; в противном случае Р+- Р, Р+- 1.1МК(Р), У+-1МР0(Р), АЧА11.~:= Р, (17) а если Р = Л, то В +- 1.0С(Р).

Обратите внимание, что В необходимо будет изменить, если очередь станет пустой. Это именно тот тип "граничного условия", который всегда слелует отслеживать. Изложенный выше метод — вовсе не единственный способ представления очередей в виде линейно связанного списка. Например, в упр. 30 описывается в некоторой степени даже более естественный альтернативный способ, а в конце этой главы приводятся другие методы. Действительно, ни одна из перечисленных выше операций не может рассматриватьсц как единственный возможный способ реализации того или иного действия.

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

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

Однако в остальной части данной главы мы покинем область абстрактных рассуждений и приступим к изучению важных практических примеров использования этих методов. Первый пример такой практической задачи называется топологической соршироокой (горо1оу1со1 гог11пд), которую часто приходится выполнять при проектировании сетей, в так называемых РЕЕТ-диаграммах, и даже в лингвистике. Действительно, она может быть очень полезной всегда, когда приходится выполнять частичное упорядочение (росло( огдегту).

Частичным упорндочением некоторого множества 5 называется такое отношение между элементами множества Я, которое может быть обозначено символом "ч" и обладает следующими свойствами для любых х, у и г (причем необязательно разных) элементов множества Я. 1) Если х С у и у -( г, то х ~ г. (Транзитивность.) 11) Если х -( у и у С х, то х = у. (Антисимметричность.) ш) х -< х.

(Рефлексивность.) х Ч у можно трактовать так: "х предшествует или равно у". Если х ч у и х ~ у, будем обозначать это отношение через х .ч у и трактовать его как "х предшествует у". Легко видеть, что из (1) — (ш) можно получить следующее. Г) Если х ч у и у ч г, то х ~ г.(Транзитивность.) и') Если х ч у, то у г~ х. (Антисимметричность.) ш') х;4 х. (Нерефлексивиость.) Отношение, обозначенное через у ~ х, трактуется так: "у не предшествует х".

Если сначала определить отношение ч со свойствами (Р)-(ш'), то описанный выше процесс можно выполнить в обратной последовательности, т. е. определить отношение х < у, как такое, для которого х -ч у или х = у. Тогда для него должны выполняться условия (1)-(ш). Следовательно, свойства (1) — (ш) и (1') — (ш') можно рассматривать как определения частичного упорядочения. Обратите внимание на то, что свойство (и') на самом деле является следствием свойств (1') и (ш'), однако свойство (й) не следует из свойств (1) и (ш). Частичное упорядочение довольно часто встречается не только в математике, но и в повседневной жизни. Примерами его использовизия в математике являются отношение х < у между действительными числами х и у, отношение х С у между множествами, отношение х~у (х делит у) между положительными целыми числами.

В РЕНТ-диаграммах 5 — это набор заданий, которые следует выполнить, а отношение х С у означает "х должно быть выполнено раньше у". Рис. 6. Частичное упорядочение. Вполне естественно было бы предположить, что 5 является конечным множеством, поскольку оно используется в компьютере. Частичное упорядочение конечного множества всегда можно представить в виде диаграммы, изображенной на рис. 6, на которой объекты изображены маленькими квадратиками, а отношение мев~ду ними — стрелками между этими квадратиками.

В таком случае х ч у означает, что от квадратика с ярлыком х к квадратику с ярлыком у проходит некоторый путь, указанный стрелками. Свойство (й) частичного упорядочения означает, что в такой схеме не сущесгпвует замкнутых пешель (т. е. не существует путей, замкнутых на себя). Например, если в схеме на рис. 6 провести стрелку от квадратика 4 к квадратику 1, то для них нельзя будет установить отношение частичного упорядочения. Задача топологической сортировки заключается в усгпановлении частичного порядка среди обьектов, упорядоченных в линейном порядке, т.

е. в таком расположении объектов линейной последовательности а1аг...а„, чтобы для любых ау ~ аь выполнялось условие у < к. Графически это означает, что квадратики следует расположить на одной линии так, чтобы все стрелки были направлены вправо (рис. 7). Такое переупорядочение не всегда возможно, хотя совершенно ясно, что его нельзя выполнить при наличии замкнутых петель.

Следовательно, искомый алгоритм интересен не только тем, что он позволяет выполнить очень полезную операцию, но и тем, что ои доказывает, что данная операция возможна для любого частичного упорядочения. Рис. 7. Отношение упорядочения, показанного на рис. 6, после выполнения топологиче- ской сортировки. В качестве примера топологической сортировки представим себе большой словарь с определениями технических терминов. Запишем, что гог ~ юы если определи. ние термина гог пррмо или косвенно зависит от определения термина юг. Это отношение является частичным упорядочением лри условии, что не существует никаких "циклических определений". Тогда задача топологической сортировки заключается в поиске таково способа упорядочения терминов в этом словаре, чтобы никакой термин не использовался до тпоио, как он будет определен.

Аналогичные проблемы возникают при создании программ для обработки объявлений в некоторых ассемблерных и компилируемых языках, а также при создании руководства пользователя с описанием языка программирования или при написании учебников об информационных структурах, Существует очень простой способ выполнения топологической сортировки. Сортировку следует начать с объекта, которому не предшествует никакой другой объект данного множества. Этот объект удаляется из исходного множества Я и располэ гевтся первым в итоговой последовательности. Таким образом итоговая последовательность частично упорядочивается и процесс снова повторяется до тех пор, пока все множество не будет рассортировано. Например, на рис.

6 сортировку можно было бы начать, удалив элемент 1 или 9, затем (после удаления элемента 1)— удалив элемент 3 и т. д. Этот алгоритм может оказаться бесполезным только тогда, когда найдется такое непустое частично упорядоченное множество, каждому элементу которого предшествует другой элемент. Но если каждый элемент имеет предшественника, то можно построить последовательность произвольной длины Ьы Ьг, Ьз,..., в которой Ьгег -< Ьз.

Характеристики

Список файлов книги