21. Нелинейные структуры данных. Деревья. Спецификация двоичных деревьев. Реализация. Основные операции.

Двоичные (бинарные) деревья – это деревья со степенью не более двух.

По степени вершин двоичные деревья бывают:

– с т р о г и е – вершины дерева имеют степень нуль (у листьев) или два (у узлов);

– н е с т р о г и е – вершины дерева имеют степень нуль (у листьев), один или два (у узлов).

В общем случае на k-м уровне двоичного дерева может быть до вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (т. е. вершин на каждом k-м уровне), называется п о л н ы м .

Реализация

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

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

Для любой вершины, имеющей индекс j в массиве, можно вычислить адреса левого и правого потомков:

адрес_левого = 2*j

адрес_правого = 2*j+1

Основные операции

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

22. Файлы. Организация.

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

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

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

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

Организация

Существуют несколько способов организации данных в виде файлов:

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

– хешированные файлы (Основная идея этого метода подобна методу цепочек.);

– индексированные файлы(поддерживает файлы в отсортированном (по значению ключа) порядке);

– B-деревья.