Машинная программа. 9 Классификация вычислительных устройств. 11 Основные устройства компьютера, его архитектура. 13
| Вид материала | Программа |
- Тест «Основные устройства икт» 1 вариант Вкакой строке перечислен минимальный набор, 31.4kb.
- Лекция Внешние устройства компьютера, 309.96kb.
- Назипов Рамиль Хайретдинович Назначение и устройство компьютера урок, 165.22kb.
- Архитектура персонального компьютера, 124.05kb.
- «Архитектура ЭВМ учитель информатики Юдина Наталия Сергеевна Тема: «Устройства персонального, 111.25kb.
- Оболочка Norton Commander. Windows и программа, 26.31kb.
- Лекция 12. Архитектура компьютера, 124.05kb.
- 1. Функциональная схема компьютера. Основные устройства компьютера, их назначение, 132.15kb.
- «Цифровые устройства и микропроцессоры», 23.44kb.
- Классификация и основные параметры, 145.52kb.
4.13. Динамические структуры данных
До сих пор мы встречались с переменными, которые описывались в разделе объявления переменных программы или процедур и функций и которым в программе приписано определенное имя. Таким переменным приписан простой или составной тип, который однозначно определяет объем памяти, необходимой для хранения переменной. Память для поименованных переменных выделяется при компиляции программы. Такая память называется статической. В некоторых ситуациях статическая память имеет серьезные недостатки. Рассмотрим подробнее некоторые аспекты компиляции программы и структуру программного кода.
Код программы состоит из трех автономных частей. Первая часть представляет собой исполняемую часть программы и называется программной секцией. Она включает реализацию операторов программы и всех процедур и функций программы в виде машинных команд. Каждая процедура или функция задается смещением относительно начала программной секции.
Вторая часть называется секцией данных и содержит место для всех статических переменных как программы, так и всех процедур и функций. Переменная задается смещением положения переменной от начала секции данных. Это смещение используется в программном коде, чтобы извлечь значение переменной. Из сказанного понятно, почему необходимо заранее определить объем переменной. Это одна из причин использования в Паскале механизма типов переменных.
Наконец, третья секция программы называется стеком (вид очереди: последний вошел - первый вышел). Стек содержит информацию о вызовах процедур и функций. Пусть при выполнении программы мы обратились к некоторой процедуре. Так как процедуру можно вызвать из нескольких мест, необходимо указать, куда надо возвратиться после окончания работы процедуры. Эти данные вместе с некоторой технической информацией храниться в одной ячейке стека. Поскольку процедура может вызывать другую процедуру или функцию, стек может содержать информацию о нескольких вложенных вызовах. Если вспомнить рекурсию, вложенные вызовы могут содержать повторяющиеся вызовы. После окончании процедуры управление передается туда, куда указывает последний элемент стека, после чего он очищается. Так как память для стека выделяется при компиляции, длина цепочки вложенных вызовов ограничена, и при ее превышении происходит переполнение стека и аварийное завершение программы.
Если число элементов данных заранее не известно, то при использовании статических переменных необходимо выделять память по максимуму. В экономических и информационных задачах число элементов данных может колебаться от нескольких десятков до нескольких тысяч и более, причем в разных случаях соотношение между численностью различных данных различно. В результате оперативной памяти для размещения программы может не хватить. Если же сэкономить на некоторых данных, то при превышении размера программа закончится аварийно, что недопустимо.
Выходом из положения служит использование динамических переменных. Динамической переменной называется переменная, память для которой выделяется в процессе работы программы по специальному запросу. Занимается распределением динамической памяти операционная система. При запросе на размещение динамической переменной операционная система выделяет ей память из числа свободных ячеек и помечает их как занятые. После того, как данная переменная больше не нужна программе, ее можно освободить и снова сделать выделенные ей блоки свободными. Та же память может быть выделена другой переменной той же или даже другой программы (описанная функция операционной системы называется управлением памятью и является одной из важнейших).
В Паскале выделение динамической памяти осуществляется функцией new, а освобождение - функцией dispose. Однако сдесь возникают некоторые концептуальные трудности. Уже говорилось, что транслятор заменяет каждое имя объекта адресом данного объекта (на самом деле смещением от начала соответствующей секции). Но ведь адрес динамической переменной появляется только в момент ее размещения и при компиляции неизвестен. Следовательно, программный код должен быть устроен таким образом, чтобы можно было совершать операции над непоименованными переменными, адрес которых в момент компиляции программы не известен.
Указанное противоречие разрешается использованием в языках программирования специальных переменных - указателей или ссылок. Значением указателя является адрес того участка памяти, где в настоящий момент храниться значение динамической переменной. Следовательно, для указателя существенны две области памяти: одна, где указатель хранится, и другая, на которую указатель указывает. Отметим, что сам указатель является статической переменной и память для него выделяется заранее (это два или четыре байта). Очевидно, что использовать динамическую память имеет смысл тогда, когда сама динамическая переменная требует гораздо большего объема памяти (обычно это массив или запись).
4.13.1. Указатели.
Перейдем теперь к механизму использования указателей в языке Турбо Паскаль. Различают нетипизированные и типизированные указатели. Нетипизированный указатель объявляется при помощи предопределенного типа pointer. Значение нетипизированного указателя представляет собой адрес в оперативной памяти. Значение типизированного указателя также представляет собой адрес, но по этому адресу обязано быть размещено данное только определенного типа. Для оперирования с типизированным указателем используется символ “” (крышка). В разделе объявлений переменных типизированный указатель описывается следующим образом:
<имя переменной-указателя> : <имя типа значения указателя>
Например, указатель типа integer ссылается на переменную целого типа, а указатель типа rec ссылается на запись типа rec, определенную программистом в разделе типов.
Для того, чтобы значение по адресу, хранящемуся в указателе, использовать в выражении, нужно записать крышку после имени указателя: если переменная n имеет значение 1, а переменная p указывает на n, то выражение p равно 1. Используя указатель, можно также присвоить значение по адресу, указанному в указателе: в вышеприведенном примере оператор p:=5 законен и после него переменная n примет значение 5. Общее правило можно сформулировать следующим образом: если в текущий момент указатель ссылается на некоторую переменную, то использование имени указателя с крышкой после него тождественно использованию имени переменной. Преимущество в использовании указателей заключается в том, что меняя содержимое указателя, одно и то же действие можно сделать с различными переменными и даже с непоименованными значениями.
В Турбо Паскале имеется унарная операция @, которая присваивает указателю адрес переменной, являющейся операндом операции: p := @n. После выполнения этой операции указатель p будет указывать на переменную n. Следует отметить, что эта операция не требует, чтобы типы переменной и указателя были согласованы (этим Турбо Паскаль отличается от стандартного Паскаля). Однако лучше без необходимости не смешивать переменные различных типов.
Указателю в Паскале можно присвоить значение специальной предопределенной константы с именем Nil (типа pointer), что означает, что указатель не имеет определенного значения и на него нельзя ссылаться.
Использование указателей в Паскале обусловлено двумя различными обстоятельствами. Во-первых, в некоторых задачах использование указателей позволяет унифицировать действия, которые без использования указателей кажутся сложными и запутанными. Сюда можно отнести обработку списков, очередей, деревьев, поддержку индексов массивов. Во-вторых, указатели необходимы при использовании динамической памяти. Зачастую обе указанные причины переплетаются.
Образование динамической переменной в Паскале осуществляется функцией new, параметром которой должен служить типизированный указатель. Функция new выделяет столько байтов, сколько требуется для динамической переменной заданного типа, а адрес начала выделенной памяти присваивает указателю. После этого динамической переменной можно присвоить какое-либо значение. Следует отметить, что единственный доступ к динамической памяти - это содержимое указателя. Достаточно изменить значение указателя - и динамическая переменная потеряна для программы навсегда. После того, как динамическая переменная перестанет быть нужна, ее можно уничтожить (а занятую ею память освободить для дальнейшего использования) функцией dispose. В качестве параметра функции dispose нужно передать указатель, ссылающийся на уничтожаемую динамическую переменную. После уничтожения динамической переменной указатель на нее теряет смысл, хотя значение адреса сохраняется. Хороший стиль программирования заключается том, что после освобождения памяти функцией dispose(p) указателю p должно быть присвоено значение Nil.
Для пояснения оперирования с указателями приведем несколько примеров. Пусть переменные определены следующим образом:
type
tp1 = array [1..10] of integer;
var
n1,n2: integer;
p1,p2: integer
p3: real;
p4: tp1;
p5: pointer;
После операторов
n1 := 3; n2 := 5; p1 := @n1; p2 := @n2;
указатель p1 будет содержать адрес переменной n1, а указатель p2 будет содержать адрес переменной n2. При этом будет выполняться p1=3, p2=5. После присваивания p2:=p1 переменная p2 будет ссылаться на n1 и окажется p2=3. После присваивания p2:=1 значение 1 занесется в переменную n1 и теперь окажется p1=p2=n1=1, n2=5.
Пусть теперь мы хотим выделить память новым динамическим переменным:
new (p1);
new (p3);
new (p4);
В свободной оперативной памяти выделится 2,6 и 20 байтов для соответственно целой и вещественной переменной и массива из 10 целых чисел, на которые будут ссылаться указатели p1, p3 и p4. Этим переменным пока не присвоено никакого значения. Для занесения значений в динамические переменные мы можем написать примерно следующее
p1 := 7;
p3 := 2.75;
p4[1] := 2;
p4[8] :=6;
и т.д. Если в дальнейшем присвоить p2:=p1, то указатели p1 и p2 будут ссылаться на одно и то же значение. Если изменить указатель p1 оператором p1:=@n1, то на динамическую переменную будет ссылаться только указатель p2. Если изменить также и его, например, p2:=@n2, то адрес динамической переменной, образованной функцией new, будет потерян навсегда и эту динамическую переменную нельзя будет ни использовать, ни закрыть, в то время как память ею будет занята. Для того, чтобы этого не происходило, надо было предварительно освободить память процедурой dispose(p2).
Указатели можно только присваивать и сравнивать на равенство и неравенство. При этом необходимо следить за согласованностью типов указателей: оператор p1:=p2 и сравнение p1=p2 правильные, а оператор p1:=p3 и сравнение p1=p3 будут считаться синтаксической ошибкой. Однако можно выполнить присваивание в два приема с использованием нетипизированного указателя p5, а именно: p5:=p3; p1:=p5. Аналогично можно сравнивать любой типизированный с нетипизированным указателем.
4.13.2. Использование указателей при вызове процедур.
Предположим, что формальный параметр z процедуры p является указателем на значение определенного типа (например, целого). Тогда при обращении к процедуре во внутреннюю переменную скопируется адрес, а само значение по данному адресу не будет затронуто. Если в процедуре встретится присваивание вида z := 7, то по адресу указателя заносится число 7. При выходе из процедуры это значение останется, то есть переменная по этому адресу получит новое значение. Например, после вызова p(@n) переменная n примет значение 7. Эффект будет таким же, как если бы задать параметр обычным целым числом, но описать его выходным (с ключевым словом var) и обратиться к процедуре оператором p(n).
Однако использование указателя имеет свои преимущества. Оно позволяет обойти стандартное ограничение Паскаля на строгое соответствие типов формального и фактического параметров вызова процедуры. Особенно это касается соответствия длин массивов. Дело в том, что определение указателя некоторого типа требует выделения памяти для хранения адреса, но не требует выделения памяти для хранения значения этого типа. Оператор вида p:=@x всего лишь совмещает значение, обозначаемое как p, с уже существующей переменной x. Пусть имеется указатель p на массив некоторой длины n и массив a меньшей длины k, а типы элементов массивов одинаковые. Если теперь присвоить p:=@a, то при обращении к элементам вида p[m], где m>k, фактически произойдет обращение к памяти, не принадлежащей массиву a, что неправильно. Но если программно следить за тем, чтобы индекс в выражении p[m] не превосходил фактической длины массива k, то программа будет действовать корректно. Поэтому можно составить процедуру, обрабатывающую массив максимально возможной длины, а при вызове процедуры передавать ей указатель на начало фактического массива и длину фактического массива. В качестве примера приведем функцию поиска целого значения в массиве произвольной длины.
function find_integer (
x: integer; {Значение для поска}
p: pointer; {Массив для поиска}
n: integer) {Длина массива}
: integer; {Возвращает номер совпавшего элемента или 0 в случае неудачи}
type ar: array [1..30000] of integer;
var
k: integer;
p1: ar;
begin
find_integer := 0;
p1 := p;
for ki:=1 to n do
if p1[k]=x then
begin
find_integer := k;
break
end
end;
Обратиться к данной функции можно следующим образом:
var a: array [1..20] of integer;
...
i := find_integer (23,@a,20);
4.13.3. Использование указателей для обработки списков.
Указатели оказываются незаменимыми в задачах, связанных с добавлением и корректировкой данных в структурно организованных системах данных. Дело в том, что хранение данных в массивах наталкивается на серьезные технические трудности. Добавление данных возможно только вконец массива. Если играет роль порядок данных, то при вставке элемента в середину массива необходимо сдвинуть все остальные элементы. Это очень неудобно или даже невозможно, если номера данных по одному массиву используются в других массивах.
Существует другая возможность описывать упорядоченную последовательность данных - списком. В наборе технологических средств программирования списком называется совокупность однотипных упорядоченнных данных, снабженных средствами, позволяющими переходить от предыдущего значения к последующему. Наиболее естественно обеспечивается переход с помощью указателей. Именно, элемент списка будет состоять из двух частей: первая часть состоит из содержательных данных списка, а вторая часть представляет собой указатель, ссылающийся на следующий элемент списка. Указатель на первый элемент списка хранится в фиксированной переменной. Если он неопределенный (равен Nil), то список пуст. Указатель следующего элемента в последнем элементе списка равен Nil. Общая схема списка такова:
начальный элемент1 элемент2 ... элементN NIL
указатель указатель указатель указательОписание элемента списка в Паскале имеет одну особенность, которую мы поясним на примере. Пусть сами данные описываются как запись типа rec. Тогда элемент списка будет записью из двух полей: одно типа rec и другое типа указатель на элемент списка.
type
rec = record <поля данных> end; {запись данных}
plist = list; {тип указателя на элемент списка }
list = record {тип элемента списка}
d: rec; {данные списка}
p: plist {ссылка на следующий элемент}
end;
var p0: plist; {ссылка на первый элемент списка}
Особенность вышеприведенного описания в том, что при определении типа указателя с именем plist испоьзуется тип list, определяемый ниже в тексте программы, а не выше, как того требует фундаментальное правило Паскаля. Разобранный случай - это единственное исключение из этого правила.
Список, устроенный так, как это было описано выше, называется линейным однонаправленным (или односвязным) списком. При работе с таким списком можно выделить три основные функции:
- поиск элемента списка по критерию;
- добавление элемента внутрь списка;
- удаление элемента из списка.
Пусть функция: {function order (r1,r2: rec): integer;} возвращает -1, 0 или +1 в зависимости от того, предшествует, совпадает или следует запись r1 за записью r2 (порядок следования зависит от полей записи). Тогда поиск в линейном списке записи r заключается в последовательном переборе элементов списка и сравнении записи r с полем d элемента списка. Перебор начинается с элемента p0 и заканчивается тогда, когда order(r,d)=0 (запись найдена), либо order(r,d)=1 (нужной записи не существует), либо указатель на следующую запись равен Nil (список кончился).
function find_in_list (r: rec): plist; {возвращает указатель на элемент, Nil - неудача}
var next: plist;
begin
find_in_list := Nil;
next := po; {Первый элемент списка}
while (next<>Nil) and (order (r, next.d) >= 0) do
{Cписок не кончился и исходная запись больше текущей}
if order (r, next.d) = 0
then begin find_in_list := next; break end {Записи совпадают}
else next := next.p; {исходная больше текущей; продолжить поиск}
end;
Для того, чтобы добавить элемент в список, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после). В модифицированном списке элемент до должен указывать на вставленный элемент, а вставленный - на элемент после. Алгоритм обязан правильно обрабатывать случаи, когда элемент вставляется в начало или конец списка. Обратите внимание, что в процедуре вставки используется указатель на указатель, что совершенно законно.
procedure include_in_list (r: rec);
var next,curr: plist; prev: plist;
begin
next := po; {Первый элемент списка}
prev := @p0; {Сcылка на указатель первого элемента}
while (next<>Nil) and (order (r, next.d) >= 0) do begin
prev := @(next.p); {Сcылка на указатель в предыдущем элементе}
next := next.p {Переход к следующему элементу}
end; {Cписок кончился или последняя запись предшествует текущей}
new (curr); {Создание копии элемента списка}
curr.d := r; {Заполнение элемента}
curr.p := prev; {Ссылка последующий элемент списка}
prev := curr; {Ссылка в прдыдущем элементе на новый}
end;
Для того, чтобы удалить элемент из списка, необходимо вначале определить его местоположение в списке (найти элемент до и элемент после). В модифицированном списке элемент до должен указывать на элемент после. Здесь тавже надо следить за правильностью удаления первого и последнего элемента.
function exclude_from_list (r: rec): boolean;
var next: plist; prev: plist;
begin
exclude_from_list := false;
next := po; {Первый элемент списка}
prev := @p0; {Сcылка на указатель первого элемента}
while (next<>Nil) and (order (r, next.d) <= 0) do
if order (r, next.d) = 0 {Уничтожить элемент списка}
then begin prev := next.p; {Ссылка в прдыдущем элементе на последующий}
dispose (next); {Освободить ненужную память}
exclude_from_list := true; {Элемент удален}
break
end
else begin prev := @(next.p); {Сcылка на указатель в предыдущем элементе}
next := next.p {Переход к следующему элементу}
end
end;
Кольцевой список отличается от линейного тем, что в нем указатель в последнем элементе не равен Nil, а указывает на первый элемент, то есть ссылки замыкают список в кольцо. Кольцевой список позволяет производить поиск не только с первого, но и с любого элемента. Процедуры поиска, добавления и уничтожения в кольцевом списке несколько отличаются за счет проверки условия окончания поиска (next <> p0 вместо next <> Nil).
Если в задаче необходимо двигаться по списку в обоих направлениях, используются двунаправленные (двусвязные) списки. Элемент линейного двунаправленного списка кроме ссылки на последующий элемент содержит ссылку на предыдущий элемент. Двунаправленный список также можно замкнуть в двунаправленное кольцо. Процедуры поиска, добавления и уничтожения для двунаправленного списка в основных чертах повторяют процедуры для обычного списка.
4.13.4. Использование указателей для обработки деревьев.
Графом называется совокупность объектов, называемых вершинами графа, и связей между ними, которые принято называть дугами графа. Граф, в котором каждая связь имеет направление, называется направленным графом. Принято изображать вершины графа точками на плоскости, а связи между ними - отрезками (направленные связи - стрелками). Путем на графе называется последовательность вершин, соединенных дугами. Для направленного графа направление пути должно совпадать с направлением каждой дуги пути.
Пара вершин направленного графа, соединенная стрелкой, называется главной и подчиненной вершиной (или хозяином и слугой, или отцом и сыном). Вершина может быть одновременно отцом и сыном. Циклом в направленном графе называется замкнутый путь, то есть путь, начало и конец которого совпадают. Если граф не имеет циклов, то обязательно имеется хотя бы одна вершина, в которую не входит ни одна стрелка. Такая вершина называется корневой. Граф, у которого ровно одна корневая вершина, является связным. В таком графе для каждой вершины существует путь из корневой вершины в данную. Наконец, деревом называется связный направленный граф без циклов, у каждой вершины которого не более одного хозяина. На самом деле в дереве все вершины, кроме корня, имеют хозяина. В каждую вершину дерева из корня ведет ровно один путь, то есть существует взаимно-однозначное соответствие между вершинами и путями. Если вершина не имеет подчиненных вершин, то она называется концевой вершиной или тупиком или листом.
Назовем корневую вершину вершиной первого уровня, ее сыновей - вершинами второго уровня, сыновей ее сыновей - вершинами третьего уровня и т.д. Максимальный уровень называется глубиной дерева. Далее, для каждой вершины перенумеруем дуги, выходящие из этой вершины. Можно ввести так называемый лексикографический порядок на множестве вершин дерева. Именно, для каждой пары вершин возьмем два пути, ведущие из корня в эти вершины. Тогда эти пути либо один продолжает другой, либо они расходятся с некоторой точки. В первом случае будем предполагать, что более длинный путь следует за более коротким. Во втором случае порядок определяется номерами первых несовпадающих дуг путей.
Приведем пример дерева. В каждой вершине изобразим три цифры: уровень вершины дерева, номер в списке слуг хозяина данной вершины и общий номер в множестве вершин дерева.
1.1.1
2.1.2 2.2.8 2.3.10 2.4.11
3.1.3 3.2.6 3.1.9 3.1.12 3.2.13 3.3.18
4.1.4 4.2.5 4.1.7 4.1.14 4.2.15 4.3.16 4.4.17Тупиками являются вершины с номерами 4,5,7,9,10, 12,14,15,16,17,18.
Важным свойством дерева является свойство подобия, которое заключается в том, что множество всех потомков данного хозяина (сыновей, сыновей сыновей и т.д.) образуют дерево. Оно является поддеревом дерева с корнем в данной вершине. Такое поддерево иногда называют ветвью дерева. В частности, каждое дерево состоит из корня дерева и нескольких ветвей, корнями которых служат все вершины первого уровня дерева.
Деревом изображаются любые иерархические структуры, которые очень часто встречаются на практике. Например структура подразделений компании или структура административного деления регионов. Деревом является классификация видов животных или перечень номенклатуры изделий (и вообще, любая классификация). Иерархия объектов в реальной действительности приводит к иерархии описаний объектов в памяти компьютера.
Как и в случае списков, описание вершины дерева состоит из двух частей: содержательной информации (описания объекта) и структурной информации (положения объекта в дереве). В данный момент нас интересует структурная информация. Ее состав зависит от функций, которые она должна обеспечивать. По крайней мере, необходимо уметь перечислить вершины дерева в порядк взрастания. Для этого можно предложить следующую схему. Для каждой вершины будем задавать структурную информацию в виде двух указателей. Первый указатель ссылается на первого по порядку слугу данной вершины. Если вершина тупиковая и слуг не имеет, то указатель пусть равен значению Nil. Второй указатель ссылается на следующего по порядку слугу среди слуг хозяина данной вершины. Если данная вершина последняя в списке слуг своего хозяина, то указатель пусть также равен значению Nil. Система вторых указателей превращает дерево в совокупность линейных однонаправленных списков слуг некоторого хозяина. Первый указатель при вершине содержит ссылку на начало списка
type
rec = record <поля данных> end; {запись данных}
ptree = tree; {тип указателя на элемент списка }
tree = record {тип элемента списка}
data: rec; {данные вершины дерева}
down: ptree {ссылка на 1-го слугу данной вершины}
right: ptree {ссылка на следующего слугу хозяина вершины}
end;
var root: ptree; {ссылка на корневую вершину дерева}
Пусть теперь дерево описывается в форме совокупности динамических переменных, каждая из которых задает вершины дерева. Приведем пример процедуры, выводящей в файл данные всех вершин дерева в лексикографическом порядке.
procedure write_tree (f: tpf); {f - файловая переменная типа tpf = file of rec}
var k: integer;
path: array [1..20] of tree;
begin
k := 1;
path [k] := root; {Начальная вершина дерева - корневая}
while (k>0) and (path[k]<>Nil) do
begin
write (f, (path[k]).data);
if (path[k]).down<>Nil then
begin path [k+1] :=(path[k]).down;
k:=k+1
end
else
begin while (k>0) and ( (path[k]).right=Nil) do k:=k-1;
if k>0 then path [k] := (path[k]).right
end
end
end;
Другой интересный случай - когда дерево составляют не объекты, а ситуации. Предположим, действительность описывается иерархической структурой ситуаций и нам нужно отыскать ситуацию, к которой относится рассматриваемый нами случай. Пусть мы умеем определять, описывает ли текущая ситуация данный случай или нет. Кроме того, если ситуация не соответствует нашему случаю, пусть мы умеем определять, может ли соответствовать случаю ситуация, подчиненная данной. Другими словами, если x - ситуация, а y - случай, то задана функция agree(x,y), которая возвращает:
- -1, если случай противоречит ситуации;
- +1, если случай может быть согласован с ситуацией;
- 0, если случай полностью соответствует ситуации.
Предположим также, что мы умеем переходить от текущей ситуации как к ситуации сына (вниз по дереву ситуаций), так и к ситуации, следующей за данной среди сыновей ситуации отца для данной (вправо по дереву ситуаций). Тогда обход множества ситуаций в поисках нужной напоминает вышеприведенную процедуру обхода вершин дерева, причем стратегия обхода зависит от значения функции agree(x,y):
- если agree(x,y)=0, то текущая ситуация является искомой;
- если agree(x,y)=-1, то бессмысленно анализировать подчиненные ситуации, то есть с точки зрения поиска текущая ситуация тупиковая и необходимо сделать “шаг вправо”;
- если agree(x,y)=+1, то следует перейти к подчиненной ситуации, то есть сделать “шаг вниз”.
Обозначенный выше метод перебора ситуаций называется методом ветвей и границ. В качестве примера можно привести задачу расстановки на шахматной доске восьми ферзей таким образом, чтобы они не били друг друга. Под ситуацией понимается расстановка ферзей на первых n горизонталях, а подчиненные ситуации - это расстановки ферзей на (n+1) горизонталях. Входные данные в этой задаче отсутствуют, то есть отсутствует переменная x, обозначающая анализируемый случай. Назовем клетку битой, если она бьется хотя бы одним ферзем из уже имеющейся расстановки. Ситуация тупиковая, если n<8 и все поля (n+1)-й горизонтали бьются ферзями из первых n горизонталей. “Шаг вниз” заключается в выборе первой слева небитой клетки (n+1) й горизонтали. “Шаг вправо” заключается в выборе следующей с правой стороны небитой клетки в n й горизонтали. С формальной точки зрения:
- y - расстановка ферзей на первых n горизонталях;
- agree(y)=-1, если ферзь на n-й горизонтали бьется другим ферзем;
- agree(y)=+1, если ферзи не бьют друг друга и n<8;
- agree(y)=0, если ферзи не бьют друг друга и n=8.
Тогда решение задачи полностью укладывается в схему метода ветвей и границ.
4.13.5. Использование деревьев для индексирования.
Дерево называется бинарным, если каждая вершина имеет не более двух подчиненных (не более двух слуг). Бинарные деревья принято задавать иначе, чем произвольные деревья. Вместо ссылок от вершины “вниз” и “вправо” структура дерева задается ссылками к первому (“левому”) и второму (“правому”) слуге данного хозяина. Если один или оба слуги отсутствуют, соответствующие ссылки равны Nil. Путь на бинарном дереве от корня до любой вершины кодируется последовательностью нулей и единиц: нуль соответствует переходу к левому слуге, а единица - к правому. Классификация с помощью бинарного дерева называется бинарной классификацией.
Бинарные деревья играют особую роль в организации баз данных, так как на их основе происходит логическое упорядочение данных. Пусть имеется база данных, состоящая из большого количества записей, причем данные в ней неупорядочены. Для баз данных можно определить минимальный список функций, которые в любой базе данных обязаны выполняться:
- задание порядка в множестве записей (в простейшем случае согласно значению заданного поля); при этом предпочтительнее, чтобы задание порядка не сопровождалось физическим изменением расположения элементов в базе данных;
- переход от текущей записи к последующей и к предыдущей (при условии, что порядок задан);
- вывод всех записей в порядке возрастания (при условии, что порядок задан);
- поиск записи по заданному значению какого-то поля или по сложному критерию;
- поддержание порядка при добавлении, изменении и удалении данных.
Для задания различного порядка в базах данных используются специальные дополнительные структуры. Это связано с двумя обстоятельствами. Во первых, может потребоваться одновременная сортировка одних и тех же данных в различном порядке. Например, каталог изделий можно отсортировать по наименованию, цене, дате изготовления и т.д. Нерационально каждый раз физически сортировать данные в массиве в нужном порядке. Во вторых, должно быть удобно поддерживать правильный порядок при модификации данных. Для этого используют так называемый индекс базы данных. Несколько индексов могут определять разные порядки в одном и том же массиве данных. Существует несколько способов задания индексных структур в форме бинарных деревьев. Укажем один из них.
Пусть данные - это запись, а порядок задается одним из полей этой записи (например, наименованием name). Будем формально различать в бинарном дереве стрелки “вниз влево” и “вниз вправо” (соответственно, говорить о левом подчинении и правом подчинении). Бинарное дерево задает упорядочение массива данных при выполнении следующих условий:
- существует взаимнооднозначное соответствие между записями массива и вершинами дерева;
- возьмем ту ветвь бинарного дерева, в которой корнем служит левый слуга данной вершины; тогда все записи этой левой подветви предшествуют записи, соответствующей данной вершине: аналогично, все записи правой подветви следуют за записью при данной вершине.
В примере с полем name значение этого поля во всех вершинах левой подветви текущей вершины будет в алфавитном порядке стоять выше, чем наименование в текущей вершине.
Перейдем к вопросу о том, как устроено формальное описание дерева индекса массива данных. В описание вершины индексного дерева будут входить четыре компоненты:
type
pterm = term;
term = record
num: longint; {Номер записи, соответствующей вершине}
val: type_val; {Поле упорядочения (type_val - тип поля упорядочения ) }
pleft: pterm; {Cсылка на левую подчиненую вершину ( Nil в случае ее отсутствия) }
pright: pterm {Cсылка на правую подчиненую вершину (Nil в случае ее отсутствия) }
end;
С помощью этого описания можно выполнять все основные функции, которые требуются при работе с базами данных. Например, алгоритм поиска записи с нужным значением поля упорядочения можно описать так:
Назначить текущей вершиной корневую вершину дерева индекса
Значение поля в текущей вершине совпадает с искомым да Запись найденанет
Значение поля в текущей вершине больше (меньше) искомого значения
больше меньшеУ текущей вершины У текущей вершины
есть левый слуга есть правый слуга
да нет да нет
Сделать левого Запись не найдена Сделать правого Запись не найдена
слугу текущим слугу текущим
Очень похожа на описанный алгоритм блок-схема алгоритма добавления записи в дерево индекса.
Назначить текущей вершиной корневую вершину дерева индекса
Значение поля в текущей вершине больше (меньше) искомого значениябольше меньше или равноУ текущей вершины У текущей вершины
есть левый слуга есть правый слуга
да нет да нет
Сделать левого Занести запись в Сделать правого Занести запись вслугу текущим качестве правого слуги слугу текущим качестве правого слугиБолее сложно устроены другие процедуры: переход к следующей и предыдущей записи, составление списка записей в возрастающем порядке, удаление вершины из индексного дерева и т.д. Мы не будем приводить их здесь. Фактически базы данных, как и индексы баз данных, размещаются в файлах. Запись файла индекса базы данных имеет те же четыре компоненты, что были указаны выше. Роль ссылки на запись базы данных играет порядковый номер записи в файле базы данных. Роль ссылки на вершину дерева индекса играет номер записи описания вершины индексного дерева в файле индекса базы данных.