Бинарные деревья.

Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.

При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.

На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное дерево, а на 6.12(c) показаны все четыре возможных расположения сыновей некоторой вершины бинарного дерева.

Рис. 6.13. Изображения бинарных деревьев

Бинарные деревья, изображенные на рис.6.13(a) и 6.13(d), представляют собой разные позиционные деревья, хотя они не являются разными упорядоченными деревьями.

В позиционном бинарном дереве каждая вершина представлена единственным образом посредством строки символов над алфавитом {0,1}, при этом корень характеризуется пустой строкой. Любой сын вершины "u" характеризуется строкой, префикс (начальная часть) которой является строкой, характеризующей "u".

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

Представить m-арное дерево в памяти ЭВМ сложно, т.к. каждый элемент дерева должен содержать столько указателей, сколько ребер выходит из узла (при m-3,4.5.6... соответствует 3,4,5,6... указателей). Это приведет к повышенному расходу памяти ЭВМ, разнообразию исходных элементов и усложнит алгоритмы обработки дерева. Поэтому m-арные деревья, лес необходимо привести к бинарным для экономии памяти и упрощению алгоритмов. Все узлы бинарного дерева представляются в памяти ЭВМ однотипными элементами с двумя указателями (см.разд. 6,2,5), кроме того, операции над двоичными деревьями выполняются просто и эффективно.

Бинарный поиск

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

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

Для того, чтобы найти нужную запись в таблице, в худшем случае требуется log2(N) сравнений. Это значительно лучше, чем при последовательном поиске.

Программная иллюстрация бинарного поиска в упорядоченном массиве приведена в следующем примере, где a - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элементт отсутствует в массиве.

{===== Программный пример 3.5 =====} Function BinSearch(a : SEQ; key : integer) : integer; Var b, e, i : integer; begin b:=1; e:=N; { начальные значения границ } while b

Трассировка бинарного поиска ключа 275 в исходной последовательности:

75, 151, 203, 275, 318, 489, 524, 519, 647, 777

представлена в таблице 3.4.

Таблица 3.4

Представление битовых типов.

В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Чаще всего такие задачи возникают в системном программировании, когда, например, отдельный разряд связан с состоянием отдельного аппаратного переключателя или отдельной шины передачи данных и т.п. Данные такого типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту данного. В языке PASCAL роль битовых типов выполняют беззнаковые целые типы byte и word. Над этими типами помимо операций, характерных для числовых типов, допускаются и побитовые операции. Аналогичным образом роль битовых типов играют беззнаковые целые и в языке C.

В языке PL/1 существует специальный тип данных - строка битов, объявляемый в программе, как: BIT(n).

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

Операции над битовыми типами.

Над битовыми типами возможны три группы специфических операций: операции булевой алгебры, операции сдвигов, операции сравнения.

Операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor). Эти операции и по названию, и по смыслу похожи на операции над логическими операндами, но отличие в их применении к битовым операндам состоит в том, что операции выполняются над отдельными разрядами операндов.

Так операция НЕ состоит в том, что каждый разряд операнда изменяет значение на противоположный. Выполнение операции, например, ИЛИ над двумя битовыми операндами состоит в том, что выполняется ИЛИ между первым разрядом первого операнда и первым разрядом второго операнда, это дает первый разряд результата; затем выполняется ИЛИ между вторым разрядом первого операнда и вторым разрядом второго, получается второй разряд результата и т.д.

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

Представление в памяти.

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

Например, +10 и -15 в двоичном виде можно представить так:

Отметим, что по соглашению 0 используется для представления знака плюс и 1 - для минуса. Такое представление удобно для программистов т.к. легко воспринимается, но не является экономичным.

Если требуется сложить или вычесть два числа, то для решения вопроса о том, какие действия следует при этом предпринять, надо сначала определить знак каждого числа. Например, сложение чисел +6 и -7 на самом деле подразумевает операцию вычитания, а вычитание -6 из +7 операцию сложения. Для анализа знакового бита требуется особая схема и, кроме того, при представлении числа в виде знака и величины необходимы отдельные устройства для сложения и вычитания, т.е., если положительное и отрицательные числа представлены в прямом коде, операции над кодами знаков выполняются раздельно. Поэтому представление чисел в виде знака и значения не нашло широкого применения.

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

Дополнительный код отрицательного числа формируется по следующим правилам:

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

Числовые множества

Стандартный числовой тип, который может быть базовым для формирования множества - тип byte.

Множество хранится в памяти как показано в таблице 3.3.

Таблица 3.3

где @S - адрес данного типа множество.

Бит поля установлен в 1, если элемент входит в множество, и в 0 - если не входит.

Например, S : set of byte; S:=[15,19]; Содержимое памяти при этом будет следующим: @S+0 - 00000000 @S+2 - 00001000 @S+1 - 10000000 . . . . . . @S+31 - 00000000

Деки в вычислительных системах

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

Однако, в качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь. Однако, в REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит. В распоряжении программиста имеются операции QUEUE - запись строки в конец буфера и PULL - выборка строки из начала буфера. Дополнительная операция PUSH - запись строки в начало буфера - превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.

Деревья Хаффмена (деревья минимального кодирования)

Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения.

1) назначим коды:

А В А С С D А

7*3=21 всего 21 бит - неэффективно

2) Сделаем иначе: предположим, что каждому символу назначен 2-битовый код

А В А С С D А

Тогда кодировка требует лишь 14 бит.

3) Выберем коды, которые минимизируют длину сообщения по частоте вхождений символа в строку: много вхождений - код короткий, мало вхождений - код длинный.

А -3 раза, С -2 раза, В -1 раз, D -1 раз то-есть можно:

1. использовать коды переменной длины. 2. код одного символа не должен совпадать с кодом другого (раскодирование идет слева направо).

Если А имеет код 0 т.к часто встречается, то В, С, D - начинаются с 1, если дальше 0,то это С, следующий может быть 0 или 1: 1 - D , 0 - В; то-есть В и D различаются по последнему биту, А -по первому, С - по второму, B и D - по третьему.

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

Частота появления группы символов равна сумме частот появления каждого символа.

Сообщение АВАССDА кодируется как 0110010101110 и требует лишь 13 бит.

В очень длинных сообщениях, которые содержат символы, встречающиеся очень редко - экономия существенна.

Рис.6.30 Дерево Хаффмена

Обычно коды создаются на основе частоты во всем множестве сообщений, а не только в одном.

Деревья при работе с арифметическими выражениями

Операция объединения двух символов в один использует структуру бинарного дерева. Каждый узел содержит символ и частоту вхождения. Код любого символа может быть определен просмотром дерева снизу вверх, начиная с листа. Каждый раз при прохождении узла приписываем слева к коду 0, если поднимаемся по левой ветви и 1, если поднимаемся по правой ветви. Как только дерево построено код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с места, представляющего этот символ. Начальное значение кода пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается ноль, если справа - 1. Часть info узла дерева содержит частоту появления символа представляемого этим узлом. Дерево Хаффмена строго бинарное. Если в алфавите п символов, то дерево Хаффмена может быть представлено массивом узлов размером 2п-1. Поскольку размер памяти, требуемой под дерево известен, она может быть выделена заранее.

МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.

Дано выражение а*(-b)+с/d

Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,

Рис.6.31 Представление выражения в виде дерева

Рис. 6.32 Представление выражения в виде бинарного дерева.

перемножать, вычитать, дифференцировать, интегрировать, сравнивать на эквивалентность и т.д. Т.е. получаются символьные выражения, которые можно закодировать в виде таблиц:

(-) - операция унарного минуса; () - операция возведения в степень; (+) - операция сложения; (*) - операция умножения; (/) - операция деления. (Е) - указательная переменная, адресующая корень дерева, каждая вершина которого состоит из левого указателя (LPТR), правого указателя (RPTR) и информационного поля TYPE.

Для неконцевой вершины поле TYPE задает арифметическую операцию, связанную с этой вершиной. Значения поля TYPE вершин +,-,*, /, (-) и равны 1, 2, 3, 4, 5, 6 соответственно.

Для концевых вершин поле символа в TYPE имеет значение 0, что означает константу или переменную.
В этом случае правый указатель вершины задает адрес таблицы символов, который соответствует данной константе или переменной. В дереве указывается тип оператора, а не он сам, что позволяет упростить обработку таких деревьев.

Физическая структура

Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура представлена на рис. 3.3.

Рис. 3.3. Физическая структура двумерного массива из (k1-n1+1) строк и (k2-n2+1) столбцов

Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования. Так в FORTRAN элементы распределяются по столбцам - так, что быстрее меняется левые индексы, в PASCAL - по строкам - изменение индексов выполняется в направлении справа налево.

Количество байтов памяти, занятых двумерным массивом, определяется по формуле :

ByteSize = (k1-n1+1)*(k2-n2+1)*SizeOf(Тип)

Адресом массива является адрес первого байта начального компонента массива. Смещение к элементу массива Mas[i1,i2] определяется по формуле:

ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)]*SizeOf(Тип) его адрес : @ByteNumber = @mas + ByteNumber. Например: var Mas : Array [3..5] [7..8] of Word;

Базовый тип элемента Word требует два байта памяти, тогда таблица 3.2 смещений элементов массива относительно @Mas будет следующей:

Таблица 3.2

Этот массив будет занимать в памяти: (5-3+1)*(8-7+1)*2=12 байт; а адрес элемента Mas[4,8]:

@Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6

Физическая структура указателя

Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. Рассмотрим в качестве примера структуру адреса в микропроцессоре i8086.

Машинное слово этого процессора имеет размер 16 двоичных разрядов. Если использовать представление адреса в одном слове, то можно адресовать 64 Кбайт памяти, что явно недостаточно для сколько-нибудь серьезного программного изделия. Поэтому адрес представляется в виде двух 16-разрядных слов - сегмента и смещения. Сегментная часть адреса загружается в один из специальных сегментных регистров (в i8086 таких регистров 4). При обращении по адресу задается идентификатор сегментного регистра и 16-битное смещение. Полный физический (эффективный) адрес получается следующим образом. Сегментная часть адреса сдвигается на 4 разряда влево, освободившиеся слева разряды заполняются нулями, к полученному таким образом коду прибавляется смещение, как показано на рис. 2.8.

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

Рис 2.8. Вычисление полного адреса в микропроцессоре i8086.

Еще раз повторим, что физическая структура адреса принципиально различна для разных аппаратных архитектур. Так, например, в микропроцессоре i386 обе компоненты адреса 32-разрядные; в процессорах семейства S/390 адрес представляется в виде 31-разрядного смещения в одном из 19 адресных пространств, в процессоре Power PC 620 одним 64-разрядным словом может адресоваться вся как оперативная, так и внешняя память.

Операционная система MS DOS была разработана именно для процессора i8086 и использует описанную структуру адреса даже, когда выполняется на более совершенных процессорах. Однако, это сегодня единственная операционная система, в среде которой программист может работать с адресами в реальной памяти и с физической структурой адреса. Все без исключения современные модели процессоров аппаратно выполняют так называемую динамическую трансляцию адресов и совместно с современными операционными системами обеспечивают работу программ в виртуальной (кажущейся) памяти. Программа разрабатывается и выполняется в некоторой виртуальной памяти, адреса в которой линейно изменяются от 0 до некоторого максимального значения. Виртуальный адрес представляет собой число - номер ячейки в виртуальном адресном пространстве. Преобразование виртуального адреса в реальный производится аппаратно при каждом обращении по виртуальному адресу. Это преобразование выполняется совершенно незаметно (прозрачно) для программиста, поэтому в современных системах программист может считать физической структурой адреса структуру виртуального адреса. Виртуальный же адрес представляет собой целое число без знака. В разных вычислительных системах может различаться разрядность этого числа. Большинство современных систем обеспечивают 32-разрядный адрес, позволяющий адресовать до 4 Гбайт памяти, но уже существуют системы с 48 и даже 64-разрядными адресами.

Формирование таблиц символов.

В качестве примера приложения бинарных деревьев сформулируем алгоритм ведения древовидно-структурированной таблицы символов.

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

Древовидное представление таблицы выбирают по двум причинам:

1. Записи символов по мере их возникновения равномерно распределяются в соответствии с лексикографическим порядком, то при хранении записей в дереве в таком же порядке табличный просмотр становится почти эквивалентен двоичному просмотру.

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

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

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

В некотором смысле таблица символов представляет собой множество деревьев - по одному для каждого уровня блочной структуры программы.

Вершины бинарного дерева таблицы символов имеют формат:

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

Характерные особенности полустатических структур

Полустатические структуры данных характеризуются следующими признаками:

они имеют переменную длину и простые процедуры ее изменения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

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

Хранение информации

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

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

Оперативная память предназначена для запоминания более постоянной по своей природе информации. Важнейшим свойством оперативной памяти является адресуемость. Это означает, что каждая ячейка памяти имеет свой идентификатор, однозначно идентифицирующий ее в общем массиве ячеек памяти. Этот идентификатор называется адресом. Адреса ячеек являются операндами тех машинных команд, которые обращаются к оперативной памяти. В подавляющем большинстве современных вычислительных систем единицей адресации является байт - ячейка, состоящая из 8 двоичных разрядов. Определенная ячейка оперативной памяти или множество ячеек могут быть связаны с конкретной переменной в программе. Однако для выполнения арифметических вычислений, в которых участвует переменная, необходимо, чтобы до начала вычислений значение переменной было перенесено из ячейки памяти в регистр. Если результат вычисления должен быть присвоен переменной, то результирующая величина снова должна быть перенесена из соответствующего регистра в связанную с этой переменной ячейку оперативной памяти.

Информация и ее представление в памяти

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

Интервальный тип

Логическая структура.

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

Машинное представление.

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

var A: 220..250; (* Занимает 1 байт *) В: 2221..2226; (* Занимает 2 байта *) C: 'A'..'K'; (* Занимает 1 байт *) begin A:=240; C:='C'; B:=2222; end.

После выполнения данной программы содержимое памяти будет следующим:

A - 11110000; C - 01000011; B - 10101110 00001000.

Операции.

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

Таблица 2.4

Примечание: запись chr(ord(0)) в таблице следует понимать как: символ с кодом 0.

А) Интервальный тип от символьного: определение кода символа и, наоборот, символа по его коду.

Пусть задана переменная типа tz:'d'..'h'. Данной переменной присвоено значение 'e'. Байт памяти отведенный под эту переменную будет хранить ASCII-код буквы 'e' т.е. 01100101 (в 10-ом представлении 101).

Б) Интервальный тип от перечислимого: определение порядкового номера идентификатора по его значению и, наоборот, по номеру идентификатора - его значение.

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

Изображение чисел в позиционной системе счисления

Изображение чисел в любой позиционной системе счисления с натуральным основанием R (R >1) базируется на представлении их в виде произведения целочисленной степени m основания R на полином от этого основания :

n Ar = R^m * СУММА (a[i]*R^(-i)) , (1.1) i=1

где:

a[i] { 0,1,..., R-1 } - цифры R-ичной системы счисления ; n - количество разрядов (разрядность), используемых для представления числа; R - основание системы счисления; m {..., -2, -1, 0,+1,+2,...} - порядок числа; R^(-i) - позиционный вес i - того разряда числа.

Так, в десятичной (R=10) системе для представления чисел используются цифры a = {0,1,...9}; в двоичной (R=2) - a = {0,1}, в шестнадцатеричной (R=16), a = {0,1....9,A,B,C,D,E,F} где прописные латинские буквы A..F эквивалентны соответственно числам 10..15 в десятичной системе. Например,

1) 815=10^3*(8*10^(-1)+1*10^(-2)+5*10(-3))=8*10^2+1*10^1+5*10^0; 2) 8.15=10^1*(8*10^(-1)+1*10^(-2)+5*10^(-3))=8*10^0+1*10^(-1)+5*10^(-2); 3) 0.0815= 10^(-1)*(8*10^(-1)+1*10^(-2)+5*10^(-3))= =8*10^(-2)+1*10^(-3)+5*10^(-4);

Язык программирования LISP

LISP является наиболее развитым и распространенным языком обработки списков. "Идеология" и терминология этого языка в значительной степени повлияла на общепринятые подходы к обработке списков и использовалась и нами в предыдущем изложении. Все данные в LISP представляются в виде списков, структура элементсписка соответствует рис.5.15. LISP обеспечивает базовые функции обработки списков - car, cdr, cons, atom. Также многие вторичные функции реализованы в языке как базовые - для повышения их эффективности. Помимо чисто списковых операций в языке обеспечиваются операции для выполнения арифметических, логических операций, отношения, присваивания, ввода-вывода и т.д. Операция cond обеспечивает ветвление.

Сама LISP-программа представляется как список, записанный в скобочной форме. Элементами простого программного списка является имя операции/функции и ее параметры. Параметрами могут быть в свою очередь обращения к функциям, которые образуют подсписки. Как правило, вся программа на LISP представляет собой единственное обращение к функции с множеством вложенных обращений - рекурсивных или к другим функциям. Поэтому программирование на языке LISP часто называют "функциональным программированием". Функции, приведенные нами в примере 5.11 являются переложением на язык PASCAL их LISP-реализаций.

Системы программирования LISP строятся и как компиляторы, и как интерпретаторы. Однако, независимо от подхода к построению системы программирования, она обязательно включает в себя "сборку мусора" (см.раздел 5.7). Обратите внимание на то, что в примере 5.11, представляя PASCAL-реализацию операций языка LISP, мы в некоторых функциях выделяли память, но нигде ее не освобождали. Система программирования LISP автоматически следит за использованием памяти и обеспечивает ее освобождение.

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

Классификация структур данных

Теперь можно дать более конкретное определение данного на машинном уровне представления информации.

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры данного".

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам.

Понятие "ФИЗИЧЕСКАЯ структура данных" отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.

Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных.

Л И Т Е Р А Т У Р А

Ленгсам Й., Огенстайн М., Тененбаум А.

Структуры данных для персональных ЭВМ. М.: Мир, 1989.

Трамбле Ж., Соренсон П.

Введение в структуры данных. М.: Машиностроение, 1982. Дж. Уоркли.

Архитектура и программное обеспечение микро ЭВМ. Том 1. Структуры данных. М.: Мир, 1984. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. Вирт Н.

Алгоритмы + структуры данных = программы. М.:Мир, 1985. Нагао М., Катаяма Т., Уэмура. Структуры и базы данных. М.: Мир, 1984. Костин Е.Е., Шаньгин В.Ф. Организация и обработка стру- ктур данных в вычислительных системах. М.: Высш. школа, 1987. Трофимова И.П.

Системы обработки и хранения информации. М.: Высш. школа, 1989. Замулин А.В. Система программирования баз данных и знаний. Новосибирск : Наука, 1990. Замулин А.В. Типы данных в языках программирования и базах данных. Новосибирск : Наука, 1987. Разумов О.С. Организация данных в вычислительных системах. М.: Статистика, 1978. 184 с. Джонс Ж., Харроу К. Решение задач в системе Турбо-Паскаль. М.: Финансы и статистика, 1991. 718 с. Морс С.П., Альберт Д.Д.

Архитектура микропроцессора 80286. М.: Радио и связь, 1990. Р. Джордейн.

Справочник программиста персональных компьютеров типа IВМ РС, ХТ и АП. М.: Финансы и статистика, 1992. Макаровский Б.Н.

Информационные системы и структуры данных. Учебное пособие вузов. М.: Статистика, 1980. Флорес И.

Структуры и управление данными. М.: Радио и связь, 1982.

17. Холл П. Вычислительные структуры (введение в нечисленное программирование). М.: Мир, 1978. 214 с.

18. Дрибас В.П. Реляционные модели баз данных. Минск : Изд. БГУ, 1982. 192 с. Агафонов В.Н. Типы и абстракция данных в языках программирования. / Данные в языках программирования. М.: Мир, 1982 Брукс Ф.П. Как проектируются и создаются программные комплексы. М.: Наука, 1979 Виноградов М.М.

Модели данных и отображения моделей данных : алгебраический подход. / Теория и приложения систем баз данных. М.: ЦЭМИ АП СССР, 1984. Леман Д., Смит М. Типы данных / Данные в языках программирования.
М.: Мир, 1982. Хоор К. О структурной организации данных / Структурное программирование. М.: Мир, 1975. Зайцев В.Ф. Кодирование информации в ЕС ЭВМ. М.: Радио и связь, 1986. Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. М.:Мир, 1976. Кнут Д. Искусство программирования для ЭВМ. т.3. Сортировка и поиск. М.:Мир, 1976. Пратт Т. Языки программирования. Разработка и реализация. М.:Мир, 1979.

Данные в языках программирования. / Под ред. В.Н.Агафонова.М.:Мир, 1982. Вирт Н. Систематическое программирование. ВведениеМ.:Мир, 1982. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.:Мир, 1981. Баррон Д. Введение в языки программирования. М.:Мир, 1980. Ахо А., Холкрофт Дж., Ульман Дж.

Построение и анализ вычислительных алгортимов. М.:Мир, 1979. Керниган Б., Ритчи Д. Язык программирования Си. М.:Финансы и статистика, 1992. Фостер Дж. Обработка списков. М.:Мир, 1974.

Логическая структура

Массив - такая структура данных, которая характеризуется:

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

Другое определение: массив - это вектор, каждый элемент которого - вектор.

Синтаксис описания массива представляется в виде:

< Имя > : Array [n1..k1] [n2..k2] .. [nn..kn] of < Тип >.

Для случая двумерного массива:

Mas2D : Array [n1..k1] [n2..k2] of < Тип >, или Mas2D : Array [n1..k1 , n2..k2] of < Тип >

Наглядно двумерный массив можно представить в виде таблицы из (k1-n1+1) строк и (k2-n2+1) столбцов.

Логическая структура дека

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Операции над деком:

включение элемента справа; включение элемента слева; исключение элемента справа; исключение элемента слева; определение размера; очистка.

Рис. 4.2. Состояния дека в процессе изменения.

На рис. 4.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Разработать программный пример, иллюстрирующий организацию дека и операции над ним не сложно по образцу примеров 4.1, 4.3. В этом модуле должны быть реализованы процедуры и функции:

Function DeqWrRight(a: data): boolean; - включение элемента справа;

Function DeqWrLeft(a: data): boolean; - включение элемента слева;

Function DeqRdRight(var a: data): boolean; - исключение элемента справа;

Function DeqRdLeft(var a: data) : boolean; - исключение элемента слева; Procedure DeqClr; - очистка;

Function DeqSize : integer; - определение размера.

Логическая структура очереди

Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.

Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение.

Логическая структура, определения

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.

Многосвязная структура обладает следующими свойствами:

1) на каждый элемент (узел, вершину) может быть произвольное количество ссылок; 2) каждый элемент может иметь связь с любым количеством других элементов; 3) каждая связка (ребро, дуга) может иметь направление и вес.

В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.

Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным графом. Обозначение связей: неориентированных - (A,B), ориентированных - . Примеры изображений графов даны на рис.6.1. Скобочное представление графов рис.6.1:

а).((A,B),(B,A)) и б).(< A,B >,< B,A >).

Рис.6.1. Граф неориентированный (а) и ориентированный (б).

Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узела -полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.

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

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

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

Логически структура- граф может быть представлена матрицей смежности или матрицей инцидентности.

Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае (рис.6.2).

Логическая структура стека

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается"). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.

Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).

Полезными могут быть также вспомогательные операции:

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

x:=pop(stack); push(stack,x).

Некоторые авторы рассматривают также операции включения/исключения элементов для середины стека, однако структура, для которой возможны такие операции, не соответствует стеку по определению.

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

а). пустого; б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C'; д, е). после последовательного удаления из стека элементов 'C' и 'B'; ж). после включения в стек элемента 'D'.

Рис 4.1. Включение и исключение элементов из стека.

Как видно из рис. 4.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название, например A,B,C,D... Тогда в момент времени, когда на столе книг нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни одного элемента. Если же мы начнем последовательно класть книги одну на другую, то получим стопку книг (допустим, из n книг), или получим стек, в котором содержится n элементов, причем вершиной его будет являться элемент n+1. Удаление элементов из стека осуществляется аналогичным образом т. е. удаляется последовательно по одному элементу, начиная с вершины, или по одной книге из стопки.

Логическая структура строки

Строка - это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом.

Строки обладают следующими важными свойствами:

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

Говоря о строках, обычно имеют в виду текстовые строки - строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Действительно, текстовая строка является наиболее универсальной формой представления любой информации: на сегодняшний день вся сумма информации, накопленной человечеством - от Ветхого Завета до нашего учебного пособия - представлена именно в виде текстовых строк. В наших дальнейших примерах этого раздела будем работать именно с текстовыми строками. Однако, следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Так, в языке PL/1, наряду с типом данных "символьная строка" - CHAR(n) - существует тип данных "битовая строка" - BIT(n). Битовые строки, составляются из 1-битовых символов, принадлежащих алфавиту: { 0, 1 }. Все строковые операции с равным успехом применимы как к символьным, так и к битовым строкам.

Кодирование символов было рассмотрено в главе 2. Отметим, что в зависимости от особенности задачи, свойств применяемого алфавита и представляемого им языка и свойств носителей информации могут применяться и другие способы кодирования символов. В современных вычислительных системах, однако, повсеместно принята кодировка всего множества символов на разрядной сетке фиксированного размера (1 байт).

Значениями логического типа BOOLEAN может быть одна из предварительно объявленных констант false (ложь) или true (истина).

Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true соответствует любое ненулевое значение байта. Например: false всегда в машинном представлении: 00000000; true может выглядеть таким образом: 00000001 или 00010001 или 10000000.

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

Над логическими типами возможны операции булевой алгебры - НЕ (not), ИЛИ (or), И (and), исключающее ИЛИ (xor) - последняя реализована для логического типа не во всех языках. В этих операциях операнды логического типа рассматриваются как единое целое - вне зависимости от битового состава их внутреннего представления.

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

Интересно, что в языке C данные логического типа отсутствуют, их функции выполняют данные числовых типов, чаще всего - типа int. В логических выражениях операнд любого числового типа, имеющий нулевое значение, рассматривается как "ложь", а ненулевое - как "истина". Результатами логического типа являются целые числа 0 (ложь) или 1 (истина).

Логическое и машинное представление записей

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

Пример записи - совокупность сведений о некотором студенте.

Объект "студент" обладает свойствами:

"личный номер" - характеризуется целым положительным числом, "фамилия-имя-отчество" - характеризуется строкой символов и т.д.

Пример: var rec:record num :byte; { личный номер студента } name :string[20]; { Ф.И.О. } fac, group:string[7]; { факультет, группа } math,comp,lang :byte; {оценки по математике, выч. } end; {технике, ин. языку }

В памяти эта структура может быть представлена в одном из двух видов :

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

Рис. 3.10. Представление в памяти переменной типа record в виде последовательности полей

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

Рис. 3.11. Представление в памяти переменной типа record в виде связного списка.

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

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

Логическое представление и изображение деревьев.

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

МЕТОД ВЛОЖЕННЫХ СКОБОК

(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))

Рис.6.11. Представление дерева : а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна

Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину "дерево".

Машинное представление деревьев в памяти ЭВМ.

Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).

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

где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.

Рассмотрим машинное представление бинарного дерева, изображенного на рис. 6.20.

Рис. 6.20. Логическое представление дерева

Рис. 6.21. Машинное связное представление дерева представленного на рис.6.20

Рассмотрим последовательное представление деревьев. Оно удобно и эффективно в случае, если древовидная структура в течение времени своего существования не подвергается значительным изменениям, за счет включения вершин, удаления вершин и т.д.

Выбор метода последовательного представления деревьев определяется также набором тех операций, которые должны быть выполнены над древовидными структурами. (Пример статистической древовидной структуры - пирамидальный метод сортировки). Простейший метод представления дерева в виде последовательной структуры заключается во введении вектора FATHER, задающего отбор для всех его вершин. Этот метод можно использовать также для представления леса. Недостаток метода - он не отображает упорядочения вершин дерева. Если в предыдущем примере поменять местами вершины 9 и 10, последовательное представление останется тем же.

Рис. 6.22. Диаграммы дерева: а) исходное б) перестройка в бинарное

Последовательное представление дерева, логическая диаграмма которого дана на рис. 6.22 , задается следующим образом:

i 1 2 3 4 5 6 7 8 9 10 FATHER [i] 0 1 1 1 2 3 3 7 4 4 ,

где ветви определяются как {(FATHER[i],i)}, i = 2,3,...,10.

Вершины 2,3,4 являются сыновьями вершины 1, вершина 5 - сыном вершины 2, вершины 6,7 - сыновьями вершины 3, вершина 8 имеет отца вершина 7 и вершины 9 и 10 - сыновья вершины 4.

Машинное представление очереди FIFO и реализация операций

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

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

Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.

МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.

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

Например, для простого ориентированного графа, изображенного на рис.6.2 массив определяется как:

mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0))

Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.

СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.

Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представления орграфов связными нелинейными списковыми структурами.

В первом варианте два типа элементов - атомарный и узел связи (см. раздел 5.5). На рис.6.5 показана схема такого представления для графа рис.6.2. Скобочная запись связей этого графа:

( < A,B >, < B,C >, < C,D >, < B,D >, < D,C > )

Рис.6.5. Машинное представление графа элементами двух типов

Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель-data/down-указатель (см.раздел 5.5). На рис.6.6 тот же граф представлен элементами одного формата.

Рис.6.6. Машинное представление графа однотипными элементами

Многосвязная структура - граф - находит широкое применение при организации банков данных, управлении базами данных, в системах программного иммитационного моделирования сложных комплексов, в системах исскуственного интеллекта, в задачах планирования и в других сферах.
Алгоритмы обработки нелинейных разветвленных списков, к которым могут быть отнесены и графы, даны в разделе 5.5.

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

Пусть дана часть каpты доpожной сети и нужно найти наилучший маpшpут от города 1 до города 5. Такая задача выглядит достаточно пpостой, но "наилучший" маpшpут могут опpеделять многие фактоpы. Например: (1) pасстояние в километpах; (2) вpемя пpохождения маpшpута с учетом огpаничений скоpости; (3) ожидаемая пpодолжительность поездки с учетом доpожных условий и плотности движения; (4) задеpжки, вызванные пpоездом чеpез гоpода или объездом гоpодов; (5) число гоpодов, котоpое необходимо посетить, напpимеp, в целях доставки гpузов. Задачи о кpатчайших путях относятся к фундаментальным задачам комбинатоpной оптимизации.

Сpеди десятков алгоpитмов для отыскания кpатчайшего пути один из лучших пpинадлежит Дейкстpе. Алгоpитм Дейкстpы, опpеделяющий кpатчайшее pасстояние от данной веpшины до конечной, легче пояснить на пpимеpе. Рассмотpим гpаф, изобpаженный на pис.6.7, задающий связь между гоpодами на каpте доpог. Пpедставим гpаф матpицей смежности A, в котоpой: A(i,j)-длина pебpа между узлами i и j. Используя полученную матрицу и матрицы, отражающие другие факторы, можно определить кратчайший путь.

Машинное представление стека и реализация операций

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

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

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

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

Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.

Программный модуль, представленный в примере 4.1, иллюстрирует операции над стеком, расширяющимся в сторону уменьшения адресов. Указатель стека всегда указывает на первый свободный элемент.

В примерах 4.1 и 4.3 предполагается, что в модуле будут уточнены определения предельного размера структуры и типа данных для элемента структуры:

const SIZE = ...; type data = ...; {==== Программный пример 4.1 ====} { Стек } unit Stack; Interface const SIZE=...; { предельный размер стека } type data = ...; { эл-ты могут иметь любой тип } Procedure StackInit; Procedure StackClr; Function StackPush(a : data) : boolean; Function StackPop(Var a : data) : boolean; Function StackSize : integer; Implementation Var StA : array[1..SIZE] of data; { Стек - данные } { Указатель на вершину стека, работает на префиксное вычитание } top : integer; Procedure StackInit; {** инициализация - на начало } begin top:=SIZE; end; {** очистка = инициализация } Procedure StackClr; begin top:=SIZE; end; { ** занесение элемента в стек } Function StackPush(a: data) : boolean; begin if top=0 then StackPush:=false else begin { занесение, затем - увеличение указателя } StA[top]:=a; top:=top-1; StackPush:=true; end; end; { StackPush } { ** выборка элемента из стека } Function StackPop(var a: data) : boolean; begin if top=SIZE then StackPop:=false else begin { указатель увеличивается, затем - выборка } top:=top+1; a:=StA[top]; StackPop:=true; end; end; { StackPop } Function StackSize : integer; {** определение размера } begin StackSize:=SIZE-top; end; END.

Машинное представление связных линейных списков

На рис. 5.1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

Рис.5.1. Структура односвязного списка

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рис. 5.2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рис. 5.2.

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

Рис.5.2. Структура двухсвязного списка

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

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

Рис.5.3. Структура кольцевого двухсвязного списка

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

Множества

Логическая структура.

Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы.

Физическая структура.

Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.

Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества.

Номер байта для конкретного элемента Е вычисляется по формуле:

ByteNumber = (E div 8)-(min div 8),

номер бита внутри этого байта по формуле:

BitNumber = E mod 8

{===== Программный пример 3.3 =====} const max=255; min=0; E=13; var S : set of byte; ByteSize, ByteNumb, BitNumb : byte; begin S:=[]; { обнуление множества } S:=S+[E]; { запись числа в множество } ByteSize:=(max div 8)-(min div 8)+1; Bytenumb:=(E div 8)-(min div 8); BitNumb:=E mod 8; writeln(bytesize); { на экране 32 } writeln(bytenumb); { на экране 1 } writeln(bitnumb); { на экране 5 } end.

Множество из элементов перечислимого типа

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

Пример: Type Video=(MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA); Var S : set of Video;

В памяти будет занимать :

ByteSize = (9 div 8)-(0 div 8)+1=2 байта

При этом память для переменной S будет распределена как показано на рис. 3.8.

Рис. 3.8. Распределение памяти для переменной типа set of Video

Если выполнить оператор S:=[CGA,SVGA], содержимое памяти при этом будет:

@S+0 - 10000010 @S+1 - 00000000

Множество от интервального типа

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

Например, type S=10..17; var I:set of S;

Это не значит, что первый элемент будет начинаться с 10-того или 0-ого бита, как может показаться на первый взгляд. Как видно из формулы вычисления смещения внутри байта 10 mod 8 = 2, смещение первого элемента множества I начнЯтся со второго бита. И, хотя множество этого интервала свободно могло поместиться в один байт, оно займЯт (17 div 8)-(10 div 8)+1 = 2 байта.

В памяти это множество имеет представление как на рис. 3.9.

Рис. 3.9. Представление переменной типа set of S

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

Например, Type S = 510..520; Var I : S; begin I:=[512]; end. Представление в памяти переменной I будет: @i+0 - 00000000 @i+1 - 00000001

Мультисписки

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

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

Рис.5.11. Пример мультисписка

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

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

Каждая подзадача работает со своим подмножеством как с линейным списком, используя для этого определенное поле связок. Специфика мультисписка проявляется только в операции исключения элемента из списка. Исключение элемента из какого-либо одного списка еще не означает необходимости удаления элемента из памяти, так как элемент может оставаться в составе других списков. Память должна освобождаться только в том случае, когда элемент уже не входит ни в один из частных списков мультисписка. Обычно задача удаления упрощается тем, что один из частных списков является главным - в него обязательно входят все имеющиеся элементы. Тогда исключение элемента из любого неглавного списка состоит только в переопределении указателей, но не в освобождении памяти. Исключение же из главного списка требует не только освобождения памяти, но и переопределения указателей как в главном списке, так и во всех неглавных списках, в которые удаляемый элемент входил.

Непозиционные системы счисления

Числа используются для символического представления количества объектов. Очень простым методом представления количества является использование одинаковых значков. В такой системе между значками и пересчитываемыми объектами устанавливается взаимно однозначное соответствие. Например, шесть объектов могут быть представлены как ****** или 111111. Такая система становится очень неудобной, если попытаться с ее помощью представить большие количества.

Системы счисления, подобные римской, обеспечивают частичное решение проблемы представления большого количества объектов. В римской системе дополнительные символы служат для представления групп значков. Например, можно принять что I=*, Y=IIIII, X=YY, L=XXXXX и т.д. Заданная величина представляется с помощью комбинирования символов в соответствии с рядом правил, которые в некоторой степени зависят от положения символа в числе. Недостатком системы, которая с самого начала основывается на группировании некоторого множества символов с целью формирования нового символа, является то обстоятельство, что для представления очень больших количеств требуется очень много уникальных символов.

Очереди с приоритетами

В реальных задачах иногда возникает необходимость в формировании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. Так, и FIFO, и LIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.

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

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

Очереди в вычислительных системах

Идеальным примером кольцевой очереди в вычислительной системы является буфер клавиатуры в Базовой Системе Ввода-Вывода ПЭВМ IBM PC. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 40:1E до 40:2D включительно. По адресам 40:1A и 40:1C располагаются указатели на начало и конец очереди соответственно. При нажатии на любую клавишу генерируется прерывание 9. Обработчик этого прерывания читает код нажатой клавиши и помещает его в буфер клавиатуры - в конец очереди. Коды нажатых клавиш могут накапливаться в буфере клавиатуры, прежде чем они будут прочитаны программой. Программа при вводе данные с клавиатуры обращается к прерыванию 16H. Обработчик этого прерывания выбирает код клавиши из буфера - из начала очереди - и передает в программу.

Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT, Unix, OS/2, ЕС и др.). Ресурсы вычислительной системы (процессор, оперативная память, внешние устройства и т.п.( используются всеми задачами, одновременно выполняемыми в среде такой операционной системы. Поскольку многие виды ресурсов не допускают реально одновременного использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Эти очереди обычно приоритетные, однако, довольно часто применяются и FIFO-очереди, так как это единственная логическая организация очереди, которая гарантированно не допускает постоянного вытеснения задачи более приоритетными. LIFO-очереди обычно используются операционными системами для учета свободных ресурсов.

Также в современных операционных системах одним из средств взаимодействия между параллельно выполняемыми задачами являются очереди сообщений, называемые также почтовыми ящиками. Каждая задача имеет свою очередь - почтовый ящик, и все сообщения, отправляемые ей от других задач, попадают в эту очередь. Задача-владелец очереди выбирает из нее сообщения, причем может управлять порядком выборки - FIFO, LIFO или по приоритету.

Операции

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

В соответствии с формулами (3.3), (3.4) и по аналогии с вектором (3.1), (3.2) для двумерного массива c границами изменения индексов:

[B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как:

Addr[I(1),I(2)] = Addr[B(1),B(2)] + { [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип) (3.5) Обобщая (3.5) для массива произвольной размерности: Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)] получим: Addr[I(1),I(2),...,I(n)] = Addr[B(1),B(2),...B(n)] - n n (3.6) - Sizeof(Тип)*СУММА[B(m)*D(m)] + Sizeof(Тип)*СУММА[I(m)*D(m)] m=1 m=1

где Dm зависит от способа размещения массива. При размещении по строкам:

D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

при размещении по столбцам:

D(m)=[E(m-1)-B(m-1)+1]*D(m-1), где m = 2,...,n и D(1)=1

При вычислении адреса элемента наиболее сложным является вычисление третьей составляющей формулы (3.6), т.к. первые две не зависят от индексов и могут быть вычислены заранее. Для ускорения вычислений множители D(m) также могут быть вычислены заранее и сохраняться в дескрипторе массива. Дескриптор массива, таким образом, содержит:

начальный адрес массива - Addr[I(1),I(2),...,I(n)]; число измерений в массиве - n; постоянную составляющую формулы линеаризации (первые две составляющие формулы (3.6); для каждого из n измерений массива:

значения граничных индексов - B(i), E(i); множитель формулы линеаризации - D(i).

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

Например, если в PL/1-программе объявлен двумерный массив:

DECLARE A(10,10) BINARY FIXED;

то выражение: A[*,I] - будет обращаться к одномерному массиву, состоящему из элементов: A(1,I), A(2,I),...,A(10,I).

Символ-джокер "*" означает, что выбираются все элементы массива по тому измерению, которому соответствует заданный джокером индекс. Использование джокера позволяет также задавать групповые операции над всеми элементами массива или над выбранным его измерением,

например: A(*,I) = A(*,I) + 1

К операциям логического уровня над массивами необходимо отнести такие как сортировка массива, поиск элемента по ключу. Наиболее распространенные алгоритмы поиска и сортировок будут рассмотрены в данной главе ниже.

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

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

Объективным критерием, позволяющим оценить эффективность того или иного алгоритма, является, так называемый, порядок алгоритма. Порядком алгоритма называется функция O(N), позволяющая оценить зависимость времени выполнения алгоритма от объема перерабатываемых данных (N - количество элементов в массиве или таблице). Эффективность алгоритма тем выше, чем меньше время его выполнения зависит от объема данных. Большинство алгоритмов с точки зрения порядка сводятся к трем основным типам:

- степенные - O(N^a); - линейные - O(N); - логарифмические - O(logA(N)). (Здесь и далее запись вида "logА" обозначает "логарифм по основанию А").

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

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

В последующем изложении все описания алгоритмов даны для работы с таблицей, состоящей из записей R[1], R[2], ..., R[N] с ключами K[1], K[2], ..., K[N]. Во всех случаях N - количество элементов таблицы. Программные примеры для сокращения их объема работают с массивами целых чисел. Такой массив можно рассматривать как вырожденный случай таблицы, каждая запись которой состо- ит из единственного поля, которое является также и ключом. Во всех программных примерах следует считать уже определенными: константу N- целое положительное число, число элементов в массиве; константу EMPTY - целое число, признак "пусто" (EMPTY=-1); тип - type SEQ = array[1..N] of integer; сортируемые последовательности.

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

Из всех задач программирования сортировка, возможно, имеет самый богатый выбор алгоритмов решения. Назовем некоторые факторы, которые влияют на выбор алгоритма (помимо порядка алгоритма).

1). Имеющийся ресурс памяти: должны ли входное и выходное множества располагаться в разных областях памяти или выходное множество может быть сформировано на месте входного. В последнем случае имеющаяся область памяти должна в ходе сортировки динамически перераспределяться между входным и выходным множествами; для одних алгоритмов это связано с большими затратами, для других - с меньшими.

2). Исходная упорядоченность входного множества: во входном множестве (даже если оно сгенерировано датчиком случайных величин) могут попадаться упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого (в том числе и уже упорядоченного) множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе.

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

4). Сложность алгоритма является не последним соображением при его выборе. Простой алгоритм требует меньшего времени для его реализации и вероятность ошибки в реализации его меньше. При промышленном изготовлении программного продукта требования соблюдения сроков разработки и надежности продукта могут даже превалировать над требованиями эффективности функционирования.