Н. Вирт - Программирование на языке Модула-2 (1160777), страница 15
Текст из файла (страница 15)
Из сказанного очевидно, что обозначение р^ не должновычисляться, если р = NIL.Выделим следующие существенные моменты.1. Каждый указательный тип подчинен некоторому другому типу; значения указательноготипа - ссылки на объекты того типа, которому он подчинен.2. Переменная, доступная по ссылке, не имеет имени, и доступ к ней возможен толькочерез посредство указателей.3. Переменные, доступные по ссылке, динамически создаются процедурой выделенияпамяти, которая заносит указатель на эту переменную в р.4. Указательная константа NIL принадлежит всем указательным типам и не указывает нина какой объект.5.
Переменная, адресуемая указателем р, имеет обозначение р^. Чтобы обозначение p^имело смысл, р не должна иметь значение NIL.Списки, называемые также линейными списками, характеризуются тем, что они состоят изузлов, каждый из которых имеет (в точности одну) компоненту - указатель на узел того же типа,что подразумевает рекурсии. Типы узлов - это, как правило, записи: для списков описание типапринимает следующий характерный вид:УкСписка = POINTER TO УзелСпискаУзелСписка =RECORDключ: CARDINAL;Данные:...74следующий: УкСпискаEND"Данные" в действительности могут быть представлены любым числом компонент,представляющих данные, принадлежащие данному узлу. Ключ - часть этих данных: онупоминается здесь отдельно, поскольку принято связывать уникальный идентифицирующий ключс каждым элементом, а также потому, что ключ будет использоваться в последующих примерахдействий над списками. Существенной частью записи является, однако, компонента "следующий",которая, очевидно, помечена так потому, что это указатель на следующий элемент списка.
Прямаярекурсия в описании типа (минуя POINTER ТО) запрещена по той простой причине, что она немогла бы быть завершена. Приведенное выше описание нельзя сократить доСписок =RECORDключ: CARDINAL:...следующий: СписокENDПредположим теперь, что список доступен в программе через его первый элемент, накоторый ссылается указательная переменная.первый: УкСпискаПустой список представляется пустой ссылкой: первый = NIL. Удлинение списка прощевсего осуществляется вставками новых элементов в его начало.
Приведенная нижепоследовательность операторов вставляет новый элемент в список (р - произвольная переменнаятипа УкСписка).А1locate(p,SIZE(УзeлCпиcкa));WITH р^ DO(* присвоить значения ключу и данным *)следующий := первыйEND;первый : = рПостроив список последовательной вставкой узлов, мы можем пожелать найти а списке узел,ключ которого равен заданной величине х. Очевидно, нужно использовать повторение: для этогоподходит цикл с условием продолжения, поскольку мы не знаем заранее количества узлов, аследовательно, повторений.
Мудрая предосторожность - предусмотреть в алгоритме возможностьпустого списка.р := первый;WHILE (Р # NIL) & (Р^.ключ # х) DOр := p^.следующийEND;IF р # NIL THEN найден END75Обратите внимание на использование в алгоритме правила вычисления логическогопроизведения а&Ь. Если оказывается, что а ложно, то Ь не вычисляется. Если бы это было не так,то могло бы случиться, что логический сомножитель (р^.key # х) вычислялся при р = NIL, а этозапрещено.Удаление элемента особенно просто для первого узла:р := первый;первый := p^.следующий;Deallocate(p,SIZE(УзелСписка))Мы здесь считаем, что процедура Deallocate импортируется из того же модуля, что иAllocate. Deallocate вновь освобождает память, выделенную ранее под переменную р.
Припользовании этой процедурой важна крайняя осторожность: если указатель на уничтожаемуюпеременную был присвоен другим переменным, то теперь они будут указывать нанесуществующий объект. Программисту не следует надеяться, что эта ошибка будетавтоматически обнаружена системой.Другая часто встречающаяся динамическая структура - это дерево - Ее особенностьзаключается в том, что каждый узел имеет п компонент-указателей. Число п называют степеньюдерева. Наиболее частым и в некотором смысле оптимальным вариантом является двоичноедерево с n = 2. Приведем соответствующие описания.УкДерева =POINTER TO УзелДерева;УзелДерева =RECORDключ: CARDINAL;Данные:...левый,правый: УкДереваENDРоль переменной "первый", как было в случае списков, будет выполнять переменная,называемаякорень: УкДереваПри корень = NIL считается, что дерево пустое.
Деревья часто используются дляпредставления совокупностей данных с возрастающим порядком ключей, причем таким образом,чтобы поиск элементов по ключу был очень эффективным. Приведем последовательностьоператоров, осуществляющих поиск в упорядоченном двоичном дереве. Заслуживает вниманияего сходство с двоичным поиском в упорядоченном массиве. Как и раньше, р -переменная типаУкДерево.p := корень;WHILE (p # NIL) & (р^.ключ = х) DOIF p^.ключ < х THEN р := p^.
правыйELSE p^.левый76END ENDIF P # NIL THEN найден ENDЭтот пример является циклической версией поиска по дереву. Теперь приведемрекурсивную версию. Она, кроме того, дополнена так, что когда узла с данным значением ключане существует в дереве, то он создается и вставляется на соответствующее место.PROCEDURE Поиск(VAR р: УкДерева; х: CARDINAL): УкДерева;BEGINIF P # NIL THENIF р^.ключ < x THENRETURN Поиск(р^.правый,х)ELSIF p^.ключ > X THENRETURN Поиск(р^.левый,x)ELSERETURN PENDELSE (* узел не найден, вставка узла *)Allocate(р,SIZЕ(УзелДерева));WITH р^ DOключ := х; левый := NIL; правый := NILEND;RETURN рENDEND ПоискТеперь вызов процедуры-функции поиск(корень,х) осуществляет поиск по дереву,представленному переменной "корень".На этом закончим примеры действий над списками и деревьями, иллюстрирующие работус указателями.
У списков и деревьев все узлы имеют один и тот же тип. Однако указателипозволяют создавать структуры и более общего вида, состоящие из узлов различного типа.Типично для всех этих структур то, что все их узлы описываются как записи, так что записьстановится особенно полезной структурой при использовании, ее совместно с указателями.Создание и уничтожение узлов осуществляются стандартными процедурами выделения иосвобождения памяти, которые являются частью системного механизма управления памятью.Иногда может оказаться более эффективной самостоятельная работа программы с памятью безобращения к системным средствам. Это легко реализовать, заведя в программе для каждого типаузла список и занося освобождаемые узлы в соответствующие списки. Этот списокпросматривается всякий раз, когда требуется новый узел.PROCEDURE НовУзел(VAR р: УкУзел);77BEGINIF свободные = NIL THEN Allocated,SIZE(Узел))ELSE p := свободные; свободные := р^.следующийENDEND НовУзелНедостаток Такого "персонального управления памятью" в том, что при наличиинескольких списков свободных узлов не происходит перераспределения памяти между ними.22.
ПРОЦЕДУРНЫЕ ТИПЫДо сих пор мы рассматривали процедуры исключительно как Фрагменты программ, т.е.тексты, определяющие действия, которые должны быть выполнены над переменными счисловыми, логическими, символьными и другими значениями. Однако процедуры можнорассматривать и как объекты, которые можно присваивать переменным. При таком подходеописание процедуры представляет собой особую разновидность описания константы, значениемкоторой и является процедура. Если мы в дополнение к константам введем переменные, то станетвозможным описывать типы, значениями которых будут процедуры.
Такие типы называютсяпроцедурными типами.Описание процедурного типа задает число и типы параметров, а также, если это Функция,тип результата. Например, процедурный тип с одним аргументом типа REAL и с таким жерезультатом описывается какFunc = PROCEDURE(REAL): REALа тип с двумя аргументами типа CARDINAL Ргос2 = PROCEDURE(CARDINAL,CARDINAL)Общий синтаксис описания процедурного типа:$ТипПроцедура - "PROCEDURE" [СписокФормТипов].$СписокФормТипов - "(" [["VAR"] ФормТип${"," ФормТип}] ")"$[":" КвалИдент].Если мы теперь опишем, например, переменныеf: Funcр: Ргос2то возможны такие присваивания:f := sin; p := WriteCardПосле этого вызов р(х,6) станет эквивалентен WriteCard(x,6), a f(х) станет эквивалентенsin(x).Теперь можно описать процедуры, параметрами которых в свою очередь являютсяпроцедуры.
Рассмотрим, например, следующую задачу: нужно над каждым элементом двоичногодерева проделать некоторое действие, т.е. выполнить процедуру. Удобно записать решение в видерекурсивной процедуры, описывающей обход дерева и вызывающей для каждого обходимого узла78требуемую процедуру. Последняя получается как параметр и называется поэтому Формальнойпроцедурой.PROCEDURE ОбходДерева(р: УкДерево; Q: Рrос2);BEGINIF p # NIL THENОбходДерева(р^. левый,Q);Q(р^.ключ,6);ОбходДерева(р^.правый,Q)ENDEND ОбходДереваЕсли мы теперь запишемОбходДерева(корень,WriteCard)то значения ключей всех узлов будут выведены в порядке, задаваемом деревом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
