Прохождение списков и деревьев

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

typedef struct BOOK {

struct BOOK * succ;

MY_BOOKS bookinf;

} T_NBOOKS;

T_NBOOKS * search (T_NBOOKS * list, char * keystr)

{

while (list!= NULL)

if (strcmp(list -> bookinf.author, keystr) ==0) // в качестве ключа используется

return list; // фамилия автора книги

else

list = list -> succ;

return NULL;

}

В рекурсивном варианте функции заголовок функции тот-же, что и в предыдущем случае, а тело функции отличается:

{

if (list == NULL)

return NULL;

else

if (strcmp(list -> bookinf.author, keystr))

return search(last -> succ, keystr);

else

return list;

}

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

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

Пусть имеется дерево следующего вида:

1

2 3

4 5 6 7

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

1 NULL

2 3 NULL

4 5 6 7 NULL

NULL NULL NULL NULL

Рассмотрим процедуру обхода дерева, используя стратегию «слева-направо и вначале в глубину». Следует отметить, что существуют и другие стратегии, например обход дерева по уровням или справа-налево и т.д.

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

Соответствующие изменения в определение функции предлагается внести в качестве упражнения!

Запись, используемая для представления узлов дерева:

typedef struct NODE{

struct NODE * subtree;

struct NODE * succ;

void * data; // ссылка на данные

} T_NODE;

void treeSearch(T_NODE * treePtr) // treePtr – узел, с которого начинается обход

{ // это может быть и вершина дерева

T_NODE *next;

next = treePtr -> subtree;

if (next!= NULL)

treeSearch (next);

next = treePtr -> succ;

if (next!= NULL)

treeSearch (next);

}

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

Вопросы для самоконтроля

• В чем состоит отличие списков от стеков и очередей?
• Что из себя представляет последовательное представление списков, стеков и очередей?
• Что из себя представляет связанное представление списков, стеков и очередей?
• Что из себя представляет последовательно-распределенное представление списков, стеков и очередей?
• Охарактеризуйте однонаправленные линейные списки!
• Охарактеризуйте двунаправленные линейные и циклические списки!
• Как можно представить деревья общего вида в программе?
• Какие два типа процедур используются для обхода списков?
• Модифицируйте функцию обхода дерева для поиска элемента по ключу!
• Разработайте нерекурсивную функцию обхода дерева!

Вопросы для самостоятельного изучения

• Может ли определение записи (объединения) включать поле такого-же типа, что и сама запись?
• Чем отличаются сети и графы (орграфы) от деревьев?

Лекция 14. Функции ввода/вывода, управление файлами и директориями

Категории функций ввода/вывода

Функции ввода/вывода реализуются библиотечными функциями Турбо-си и делятся на две группы:

· потоковые

· префиксные.

Отличие определяется организацией ссылок и потоками ввода/вывода. В первом случае используется дополнительная буферизация при вводе/выводе, помимо буферизации на уровне MS-DOS. Как для потоковых, так и для префиксных функций файлового ввода/вывода возможны два режима доступа: текстовый и двоичный. В текстовом режиме выполняется трансляция символов-

1) при вводе CR LF (BK ПС) в ‘\n’,

2) при выводе ‘\n’ в CR LF.

Кроме того, в этом режиме как только из файла считывается символ Ctrl-Z, считается, что достигнут конец файла (выполняется условие EOF). После этого не может быть считана информация, расположенная после этого символа. В двоичном режиме все символы равноправны в т.ч. ‘\n’ и им не предается никакой особый смысл.

Режим доступа задается при открытии файла посредством вызова соответствующих библиотечных функций, либо присваиванием значений констант O.BINARY (двоичный режим) или O.TEXT (текстовый режим) внешней переменной – fmode, описанный в файлах <fcutl.h> или <stdlib.h> и задающей режим доступа к файлу по умолчанию.

Пример

- fmode = O.BINARY; /* установка режима из программы*/

Доступ к файлам через поток ввода/вывода

Функции потокового ввода/вывода называют функциями стандартного ввода/вывода. Для каждого файла открытого для доступа через поток Турбо- Си создает структурную переменную типа FILE, определяемую в <stdio.h>, содержащую флаги состояния файла, состояние буфера файла, указатель начала буфере, префикс файла и т.д. Флаги состояния файла принимают одно из возможных значений, задаваемые символьными константами в файле <stdio.h>:

_ F_RDWR - файл открыт для чтения/записи

_ F_READ - файл открыт только для чтения

_ F_EOF - индикатор конца файла

_ F_ERR -индикатор ошибки ввода/вывода и т.д.

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

ferror (file_ptr) – не равно 0, если имеется ошибка ввода/вывода

feof (file_ptr) – не равно 0, если достигнут EOF

fileno (file_ptr) – возвращает префикс файла, где (file_ptr) ссылка на структурную переменную FILE

Префикс файла позволяет идентифицировать файл в префиксных операциях ввода/вывада.

Функция void clearer (FILE* file_ptr) сбрасывает биты поля flags. Это необходимо делать, если поле flags проанализировано в программе, выполняются следующие операции с потоком и необходим анализ нового состояния поля flags, например при повторении попыток чтения.

Не нашли, что искали? Воспользуйтесь поиском: