Учебное пособие Чебоксары 2008 удк 004. 657 П 36 icon

Учебное пособие Чебоксары 2008 удк 004. 657 П 36



Смотрите также:
1   2   3   4   5   6   7

4. Методы ускорения доступа к данным

^ Хеширование данных

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

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



Рис.4.1. Хеш-таблица

Идеальной хеш-функцией является такая хеш-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса:

.

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

Рассмотрим пример реализации несовершенной хеш-функции на языке Turbo Pascal. Предположим, что ключ состоит из четырех символов. При этом таблица имеет диапазон адресов от 0 до 10000.

function hash (key : string[4]): integer;

var

f: longint;

begin

f:=ord (key[1]) - ord (key[2]) + ord (key[3]) -ord (key[4]);

{вычисление функции по значению ключа}

f:=f+255*2;

{совмещение начала области значений функции с начальным

адресом хеш-таблицы (a=1)}

f:=(f*10000) div (255*4);

{совмещение конца области значений функции с конечным адресом

хеш-таблицы (a=10 000)}

hash:=f

end;

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

^ Методы разрешения коллизий

Для разрешения коллизий используются различные методы, которые в основном сводятся к методам “цепочек“ и “открытой адресации“ (рис 4.2).

Методом цепочек называется метод, в котором для разрешения коллизий во все записи вводятся указатели, используемые для организации списков – “цепочек переполнения”. В случае возникновения коллизии при заполнении таблицы в список для требуемого адреса хеш-таблицы добавляется еще один элемент (рис 4.3.). Поиск в хеш-таблице с цепочками переполнения осуществляется следующим образом. Сначала вычисляется адрес по значению ключа. Затем осуществляется последовательный поиск в списке, связанном с вычисленным адресом.

Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения.



Рис.4.2. Разновидности методов разрешение коллизий



Рис.4.3. Разрешение коллизий при добавлении элементов

методом цепочек

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

^ Линейное опробование (а) сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом:

а = h(key) + c*i ,

где i – номер попытки разрешить коллизию.

При шаге равном единице происходит последовательный перебор всех элементов после текущего.

^ Квадратичное опробование (б) отличается от линейного тем, что шаг перебора элементов нелинейно зависит от номера попытки найти свободный элемент:

a = h(key2) + ci + di 2.

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

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

а)



б)



в)



Рис.4.4. Разрешение коллизий при добавлении элементов

методами открытой адресации: а – линейное опробование; б - квадратичное опробование; в – двойное опробование

Еще одна разновидность метода открытой адресации, которая называется двойным хешированием, основана на нелинейной адресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций:

a=h1(key) + ih2(key).

Опишем алгоритмы вставки и поиска для метода линейное опробование.

Вставка

  • i = 0

  • a = h(key) + ic

  • Если t(a) = свободно, то t(a) = key, записать элемент, стоп – элемент добавлен

  • i = i + 1, перейти к шагу 2

Поиск

  • i = 0

  • a = h(key) + ic

  • Если t(a) = key, то стоп – элемент найден

  • Если t(a) = свободно, то стоп – элемент не найден

  • i = i + 1, перейти к шагу 2.

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

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

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

Существует подход, который свободен от перечисленных недостатков. Его суть состоит в том, что для элементов хеш-таблицы добавляется состояние “удалено”. Данное состояние в процессе поиска интерпретируется как “занято”, а в процессе записи – как “свободно”.

Сформулируем алгоритмы вставки поиска и удаления для хеш-таблицы, имеющей три состояния элементов.

Вставка

  1. i = 0

  2. a = h(key) + ic

  3. Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп – элемент добавлен

  4. i = i + 1, перейти к шагу 2

Удаление

  • i = 0

  • a = h(key) + ic

  • Если t(a) = key, то t(a) =удалено, стоп – элемент удален

  • Если t(a) = свободно, то стоп – элемент не найден

  • i = i + 1, перейти к шагу 2

Поиск

  • i = 0

  • a = h(key) + ic

  • Если t(a) = key, то стоп – элемент найден

  • Если t(a) = свободно, то стоп – элемент не найден

  • i = i + 1, перейти к шагу 2

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

^ Переполнение таблицы и рехеширование

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

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



Рис.4.5. Циклический переход к началу таблицы

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

Вставка

  • i = 0

  • a = (h(key) + ci) mod n

  • Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп – элемент добавлен

  • i = i + 1, перейти к шагу 2

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

Вставка

  • i = 0

  • a = ((h(key) + ci) div n + (h(key) + ci) mod n) mod n

  • Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп – элемент добавлен

  • i = i + 1, перейти к шагу 2

  • a = ((h(key) + ci) div n + (h(key) + ci) mod n) mod n

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

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

Рассмотрим алгоритм вставки, реализующий предлагаемый подход.

Вставка

  • i = 0

  • a = ((h(key) + ci) div n + (h(key) + ci) mod n) mod n

  • Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп – элемент добавлен

  • Если i > m , то стоп – требуется рехеширование

  • i = i + 1, перейти к шагу 2

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

Удаление

  • i = 0

  • a = ((h(key) + ci) div n + (h(key) + ci) mod n) mod n

  • Если t(a) = key, то t(a) =удалено, стоп – элемент удален

  • Если t(a) = свободно или i>m, то стоп – элемент не найден

  • i = i + 1, перейти к шагу 2

Поиск

  • i = 0

  • a = ((h(key) + ci) div n + (h(key) + ci) mod n) mod n

  • Если t(a) = key, то стоп – элемент найден

  • Если t(a) = свободно или i>m, то стоп – элемент не найден

  • i = i + 1, перейти к шагу 2

Оценка качества хеш-функции

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

Если число элементов таблицы достаточно велико, то график строится не для отдельных адресов (рис.4.6.), а для групп адресов. Например, все адресное пространство разбивается на 100 фрагментов, и подсчитывается число попаданий адреса для каждого фрагмента. Большие неравномерности свидетельствуют о высокой вероятности коллизий в отдельных местах таблицы. Разумеется, такая оценка является приближенной, но она позволяет предварительно оценить качество хеш-функции и избежать грубых ошибок при ее построении.

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



Рис. 4.6. Распределение коллизий в адресном пространстве таблицы

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

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

Пример

: ключ – 10 символов, 1-й большая латинская буква

2-10 малые латинские буквы

var i:integer; s:string[10];

begin

s[1]:=chr(random(90-65)+65);

for i:=2 to 10 do s[i]:=chr(random(122-97)+97);

end.

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

Рассмотрим более общий случай. Допустим, необходимо сгенерировать ключ из m символов с кодами в диапазоне от n1 до n2.

Генерация ключа из m символов c кодами в диапазоне от n1 до n2 (диапазон непрерывный):

for i:=1 to m do str[i]:=chr(random(n2-n1)+n1);

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

Генерация ключа из m символов c кодами в диапазоне от n1 до n4 (диапазон имеет разрыв от n2 до n3):



n1 n2 n3 n4

for i:=1 to m do

begin

x:=random((n4 - n3) + (n2 – n1));

if x<=(n2 - n1) then str[i]:=chr(x + n1)

else str[i]:=chr(x + n1 + n3 – n2)

end;

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

Пример

: ключ 7 символов

  1. 3 большие латинские (коды 65-90)

  2. 2 цифры (коды 48-57)

  3. 2 малые латинские (коды 97-122)

var

key: string[7];

begin

for i:=1 to 3 do key[i]:=chr(random(90-65)+65);

for i:=4 to 5 do key[i]:=chr(random(57-48)+57);

for i:=6 to 7 do key[i]:=chr(random(122-97)+97);

end.

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

^ Организация данных для ускорения поиска по вторичным ключам

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

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

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

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

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

^ Инвертированные индексы

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

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

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

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

^ Битовые карты

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

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



Рис.4.7. Метод организации таблицы с инвертированными индексами



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

в виде битовых карт

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


^ 5. Представление графов и деревьев

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

Дадим теперь более формально основное определение теории графов. Граф G есть упорядоченная пара (V,E), где V – непустое множество вершин, E – множество пар элементов множества V, пара элементов из V называется ребром. Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным.

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

Важным частным случаем графа является дерево. Деревом называется орграф, для которого:

1) существует узел, в который не входит ни одной дуги. Этот узел называется корнем;

2) в каждую вершину, кроме корня, входит одна дуга.

С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся (рис 5.1).

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

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



Рис.5.1. Бинарное дерево



а) б)

Рис.5.2. Полное (а) и неполное (б) бинарные деревья

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



а) б)

Рис.5.3. Строго (а) и не строго (б) бинарные деревья

Представление бинарных деревьев

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

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



Рис.5.4. Представление бинарного дерева в виде списковой структуры

Приведем пример программы, которая осуществляет создание и редактирование бинарного дерева, представленного в виде списковой структуры (рис.5.4):

program bin_tree_edit;

type node=record

                name: string;

                left, right: pointer;

       end;

var

        n:integer;

        pnt_s,current_s,root: pointer;

        pnt,current:^node;

        s: string;

procedure node_search (pnt_s:pointer; var current_s:pointer);

{Поиск узла по содержимому}

var

         pnt_n:^node;

begin

pnt_n:=pnt_s; writeln(pnt_n^.name);

if not (pnt_n^.name=s) then

         begin

                if pnt_n^.left <> nil then

                           node_search (pnt_n^.left,current_s);

               if pnt_n^.right <> nil then

                          node_search (pnt_n^.right,current_s);

         end

else current_s:=pnt_n;

end;

procedure node_list (pnt_s:pointer);

{Вывод списка всех узлов дерева}

var

          pnt_n:^node;

begin

pnt_n:=pnt_s; writeln(pnt_n^.name);

if pnt_n^.left <> nil then node_list (pnt_n^.left);

if pnt_n^.right <> nil then node_list (pnt_n^.right);

end;

procedure node_dispose (pnt_s:pointer);

{Удаление узла и всех его потомков в дереве}

var

           pnt_n:^node;

begin

if pnt_s <> nil then

          begin

                  pnt_n:=pnt_s; writeln(pnt_n^.name);

                  if pnt_n^.left <> nil then

                           node_dispose (pnt_n^.left);

                  if pnt_n^.right <> nil then

                           node_dispose (pnt_n^.right);

                 dispose(pnt_n);

         end

end;

begin

new(current);root:=current;

current^.name:='root';

current^.left:=nil;

current^.right:=nil;

repeat

            writeln('текущий узел -',current^.name);

            writeln('1 – присвоить имя левому потомку');

            writeln('2 – присвоить имя правому потомку');

            writeln('3 – сделать узел текущим');

            writeln('4 – вывести список всех узлов');

            writeln('5 – удалить потомков текущего узла');

            read(n);

            if n=1 then

            begin {Создание левого потомка}

                     if current^.left= nil then new(pnt)

                     else pnt:= current^.left;

                     writeln('left ?');

                     readln;

                     read(s);

                     pnt^.name:=s;

                     pnt^.left:=nil;

                     pnt^.right:=nil;

                    current^.left:= pnt;

             end;

            if n=2 then

             begin {Создание правого потомка}

                       if current^.right= nil then new(pnt)

                      else pnt:= current^.right;

                      writeln('right ?');

                      readln;

                      read(s);

                      pnt^.name:=s;

                      pnt^.left:=nil;

                      pnt^.right:=nil;

                      current^.right:= pnt;

             end;

             if n=3 then

             begin {Поиск узла}

                     writeln('name ?');

                     readln;

                     read(s);

                     current_s:=nil; pnt_s:=root;

                     node_search (pnt_s, current_s);

                     if current_s <> nil then current:=current_s;

             end;

             if n=4 then

             begin {Вывод списка узлов}

                    pnt_s:=root;

                    node_list(pnt_s);

             end;

             if n=5 then

             begin {Удаление поддерева}

                       writeln('l,r ?');

                       readln;

                       read(s);

                       if (s='l') then

                                  begin {Удаление левого поддерева}

                                  pnt_s:=current^.left;

                                  current^.left:=nil;

                                  node_dispose(pnt_s);

                                 end

                      else

                                begin {Удаление правого поддерева}

                                pnt_s:=current^.right;

                                current^.right:=nil;

                                node_dispose(pnt_s);

                                 end;

             end;

until n=0

end.

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

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



Рис.5.5. Представление бинарного дерева в виде массива

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как адрес = 2к-1+i-1, где k – номер уровня вершины, i – номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков:

адрес_L = 2к+2(i-1);

адрес_R = 2к+2(i-1)+1.

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

^ Прохождение бинарных деревьев

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

Прямой порядок прохождения бинарного дерева (рис 5.6.) можно определить следующим образом:

  • попасть в корень;

  • пройти в прямом порядке левое поддерево;

  • пройти в прямом порядке правое поддерево.



Рис.5.6. Прямой порядок прохождения бинарного дерева

Прохождение бинарного дерева в обратном порядке (рис.5.7) можно определить в аналогичной форме:

  • пройти в обратном порядке левое поддерево;

  • пройти в обратном порядке правое поддерево;

  • попасть в корень.



Рис.5.7. Обратный порядок прохождения бинарного дерева



Рис.5.8. Представление симметрично прошитого бинарного дерева

в виде массивов

Определим еще один порядок прохождения бинарного дерева, называемый симметричным:

  • пройти в симметричном порядке левое поддерево;

  • попасть в корень;

  • пройти в симметричном порядке правое поддерево.

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

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

Такие структуры данных получили название прошитых бинарных деревьев. Указатели, или адреса, определяющие порядок обхода, называют нитями. При этом в соответствии с порядком прохождения вершин различают правопрошитые, левопрошитые и симметрично прошитые бинарные деревья (рис 5.8.).

Алгоритмы на деревьях
1. Сортировка с прохождением бинарного дерева


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

  1. построение дерева;

  2. прохождение дерева.

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

Для создания очередного узла происходят сравнения элемента со значениями существующих узлов начиная с корня.

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

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



Рис.5.9. Сортировка по возрастанию с прохождением бинарного дерева

2. Сортировка методом турнира с выбыванием

Приведем другой алгоритм сортировки, основанный на использовании бинарных деревьев. Данный метод получил название турнира с выбыванием. Пусть мы имеем исходный массив 10, 20, 3, 1, 5, 0, 4, 8.

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

Дерево строится от листьев к корню (рис. 5.10). Для двух соседних узлов строится общий предок до тех пор, пока не будет создан корень. В узел-предок заносится значение, являющееся наименьшим из значений в узлах-потомках.

В результате построения такого дерева наименьший элемент попадает сразу в корень. Далее начинается извлечение элементов из дерева. Извлекается значение из корня. Данное значение является первым элементом в результирующем массиве. Извлеченное значение помещается в отсортированный массив и заменяется в дереве на специальный символ (рис. 5.11).



Рис. 5.10. Построение дерева сортировки



Рис. 5.11. Замена извлекаемого элемента на специальный символ



Рис. 5.12. Повторное заполнение дерева сортировки

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

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

В результате получим отсортированный массив

0, 1, 3, 4, 5, 8, 10, 20



Рис.5.13. Извлечения элементов из дерева сортировки

Применение бинарных деревьев для сжатия информации

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

Рассмотрим следующий пример. Имеется текстовая строка S, состоящая из десяти символов:

^ S = ABCCCDDDDD.

При кодировании одного символа одним байтом для строки потребуется 10 байт.

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

A 00

B 01

C 10

D 11

S = 00, 01, 10, 10, 10, 11, 11, 11, 11, 11       (20 бит)

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

Одним из таких методов является кодирование Хафмена. Метод основан на использовании кодов различной длины для различных символов. Для максимально повторяющихся символов используют коды минимальной длины.

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

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



Рис. 5.14. Построение кодовой таблицы

Тогда для строки S будет получен следующий код:

S=11011110101000000.

Длина кода составляет 17 бит, что меньше по сравнению с укороченным кодом.

Теперь рассмотрим процесс декодирования (рис 5.15). Алгоритм распаковки кода можно сформулировать следующим образом:

Распаковка

1. i:=0, j:=0;

2. если i>n, то стоп – строка распакована, иначе i:=i+1;

3. node:= root;

4. если b(i)=0, то node:=left(node), иначе node:=right(node);

5. если left(node)=0 и right(node)=0, то j:=j+1, s(j):= str(node), перейти к шагу 2, иначе i:=i+1, перейти к шагу 4.

В алгоритме корень дерева обозначен как root, а left(node) и right(node) обозначают левый и правый потомки узла node.

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



Рис. 5.15. Процесс распаковки кода

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

Представление выражений с помощью деревьев

С помощью деревьев можно представлять произвольные арифметические выражения (рис. 5.16). Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу – операция. В общем случае дерево при этом может оказаться не бинарным (рис. 5.17).

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



Рис. 5.16. Представление арифметического выражения

произвольного вида в виде дерева



Рис. 5.17. Представление арифметического выражения

в виде бинарного дерева

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

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

Пример: (1+10)*5



Рис.5.18. Вычисление арифметического выражения с помощью бинарного дерева

Пример:



Рис.5.19. Представление логического выражения

в виде бинарного дерева

Представление сильноветвящихся деревьев

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

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

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

^ Применение сильноветвящихся деревьев

Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы (рис 5.21). Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью – непустым каталогам.

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

Для облегчения этой задачи сделаем списки потомков двунаправленными. Для этого достаточно ввести дополнительный указатель на предыдущий узел ”last”. С целью упрощения перемещения по дереву от листьев к корню введем дополнительный указатель на предок текущего узла “up”. Общими с традиционными способами представления являются указатели на список потомков узла “down” и следующий узел “next”.



Рис. 5.20. Представление сильноветвящихся деревьев в виде списков



Рис. 5.21. Представление логической структуры каталогов и файлов

в виде сильноветвящегося дерева

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

program dir_tree;

uses dos;

type node=record

               name: string[50]; {Имя каталога/файла}

               size: longint; {Размер файла (байт) }

               node_type: char; {Тип узла (файл –'f' / каталог-'c')}

               up,down: pointer; {Указатели на предка и список потомков}

              last,next: pointer; {Указатели на соседние узлы}

       end;

var

      n,i,l:integer;

      root, current_root: pointer;

      pnt, current:^node;

       s : searchrec;

      str: string;

procedure create_tree(local_root:pointer);

{Отображение физического оглавления диска в логическую структуру}

var

        local_node, local_r_node, local_last : ^node;

procedure new_node;

{Создание нового узла в дереве каталогов и файлов}

begin

new(local_node);

local_node^.last:=local_last;

if not(local_last=nil) then local_last^.next:=local_node;

local_node^.next:=nil;

local_node^.down:=nil;

local_node^.up:=local_r_node;

if local_r_node^.down=nil then

local_r_node^.down:=local_node;

local_node^.name:=local_r_node^.name+'\'+s.name;

if s.attr and Directory = 0 then local_node^.node_type:='f'

else local_node^.node_type:='c';

local_node^.size:=s.size;

local_last:=local_node;

end;

begin {Собственно процедура}

local_r_node:=local_root;

local_last:=nil;

findfirst(local_r_node^.name+'\*.*',anyfile,s);

if doserror = 0 then

       begin

       if (s.name<>'.') and (s.name<>'..') and

(s.attr and VolumeID = 0)

       then new_node;

       while doserror=0 do begin

               findnext(s);

               if (doserror = 0) and (s.name<>'.') and (s.name<>'..') and (s.attr and VolumeID = 0)

               then new_node;

        end

        end;

        if not (local_r_node^.down=nil) then

        begin

        local_node:=local_r_node^.down;

        repeat

               if local_node^.node_type='c' then

create_tree(local_node);{Рекурсия}

               local_node:=local_node^.next

        until local_node=nil

end

end;

procedure current_list;

{Вывод оглавления текущего каталога}

begin

current:=current_root;

writeln('текущий каталог - ', current^.name);

if current^.node_type='c'then

begin

pnt:=current^.down;

i:=1;

repeat {Проходим каталог в дереве}

        writeln (i:4,'-',pnt^.name);

        pnt:=pnt^.next;

        i:=i+1

until pnt=nil

end;

end;

procedure down;

{Навигация в дереве каталогов. Перемещение на один уровень вниз}

begin

current:=current_root;

if not (current^.down=nil) then

        begin

        current:= current^.down;

        writeln('номер в оглавлении'); readln; read(l);

        i:=1;

       while (i
       begin

               current:=current^.next;

               i:=i+1

      end;

      if (current^.node_type='c') and not (current^.down=nil)

      then current_root:= current;

      end;

end;

procedure up;

{Навигация в дереве каталогов. Перемещение на один уровень вверх}

begin

current:=current_root;

if not (current^.up=nil) then current_root:=current^.up;

end;

procedure count;

{Расчет числа файлов и подкаталогов иерархической структуры каталога}

var

        n_files, n_cats :integer;

procedure count_in (local_root : pointer);

var

        local_node, local_r_node: ^node;

begin

local_r_node:=local_root;

if not (local_r_node^.down=nil) then

         begin

         local_node:=local_r_node^.down;

         repeat

                  if local_node^.node_type='f' then

                              n_files:=n_files+1

                  else

                  begin

                              n_cats:=n_cats+1;

                              count_in (local_node)

                 end;

                 local_node:=local_node^.next

         until local_node=nil

         end

end;

begin {Собственно процедура}

n_files:=0; n_cats:=0;

count_in (current_root);

writeln ('файлы : ',n_files, ' каталоги: ', n_cats);

end;

procedure count_mem;

{Расчет физического объема иерархической структуры каталога}

var

        mem :longint;

procedure count_m_in (local_root : pointer);

var

        local_node, local_r_node: ^node;

begin

local_r_node:=local_root;

if not (local_r_node^.down=nil) then

         begin

          local_node:=local_r_node^.down;

          repeat

                     if   local_node^.node_type='f' then

                               mem:=mem+local_node^.size

                     else

                                count_m_in (local_node);

         local_node:=local_node^.next

         until local_node=nil

         end

end;

begin  {Собственно процедура}

mem:=0;

count_m_in (current_root);

writeln ('mem ', mem, ' bytes');

end;

{----------основная программа----------}

begin

new(current);

{Инициализация корня дерева каталогов и указателей для навигации}

root:=current; current_root:=current;

writeln('каталог ?'); read(str); writeln(str);

current^.name:=str;

current^.last:=nil; current^.next:=nil;

current^.up:=nil; current^.down:=nil;

current^.node_type:='c';

{Создание дерева каталогов}

create_tree(current);

if current^.down=nil then current^.node_type:=' ';

repeat

{ Интерактивная навигация }

           writeln ('1-список');

           writeln('2-вниз');

           writeln('3-вверх');

           writeln('4-число файлов');

           writeln('5-объем');

           readln(n);

           if n=1 then current_list;

           if n=2 then down;

           if n=3 then up;

           if n=4 then count;

           if n=5 then count_mem;

until n=0

end.

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

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

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

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

^ Представление графов

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



Рис. 5.22. Представление графа в виде списочной структуры

Очень распространенным является матричный способ представления графов (рис. 5.23). Для представления ненаправленных графов обычно используют матрицы смежности, а для ориентированных графов – матрицы инцидентности. Обе матрицы имеют размерность n*n, где n –число вершин в графе. Вершины графа последовательно нумеруются.

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

Правила построения матрицы инцидентности аналогичны правилам построения матрицы инцидентности. Разница состоит в том, что единица в позиции m (i,j) означает выход дуги из вершины i и вход дуги в вершину j.

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



Рис. 5.23. Матричное представление графа

Алгоритмы на графах

В некоторых матричных алгоритмах обработки графов используются так называемые матрицы путей (рис. 5.24). Определим понятие пути в ориентированном графе. Под путем длиной k из вершины i в вершину j мы будем понимать возможность попасть из вершины i в вершину j за k переходов, каждому из которых соответствует одна дуга. Одна матрица путей m k содержит сведения о наличии всех путей одной длины k в графе. Единичное значение в позиции (i,j) означает наличие пути длиной k из вершины i в вершину j.

Матрица m1 полностью совпадает с матрицей инцидентности. По матрице m 1 можно построить m 2 . По матрице m 2 можно построить m 3 и т. д. Если граф является ациклическим, то число матриц путей ограничено. В противном случае матрицы будут повторяться до бесконечности с некоторым периодом, связанным с длиной циклов. Матрицы путей не имеет смысла вычислять до бесконечности. Достаточно остановиться в случае повторения матриц.



Рис. 5.24. Матрицы путей

Если выполнить логическое сложение всех матриц путей, то получится транзитивное замыкание графа (рис. 5.25):

M tr = m 1 OR m 2 OR m 3

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

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

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



Рис. 5.25. Транзитивное замыкание в графе

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

Сформулируем алгоритм в матричном виде:

  • для i от 1 до n выполнить шаги 1-2;

  • если строка M(i ,*) = 0, то обнулить столбец i;

  • если столбец M(*, i) = 0, то обнулить строку i;

  • если матрица изменилась, то выполнить шаг 1;

  • если матрица нулевая, то – стоп, граф ациклический, иначе матрица содержит вершины, входящие в циклы.

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






страница3/7
Дата конвертации17.11.2013
Размер1,66 Mb.
ТипУчебное пособие
1   2   3   4   5   6   7
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы