5.5 Дерево двоичного поиска

Пусть тип данных Inf допускает порядок (то есть данные этого типа можно сравнивать на «больше» и «меньше»).

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

Операции: Создать, Добавить, Найти, Обход.

Пример: 22,10,3,5,13,26,18,19,17,2,4,7,...

5.6 Реализация операций

Добавить(р:^Эл,i:Inf)

Если p=NIL то NEW(p);p^.кор=i;p^.лев=NIL;p^.прав=NIL

иначе

если i<p^.кор > то Добавить(p^.лев,i),

иначе Добавить(p^.прав,i)

Задачи

1. Заполнить дерево двоичного поиска из файла?

2. Найти элемент с заданной информационной частью в дереве двоичного поиска?

3. Что дает ЛКП обход дерева двоичного поиска?

Лекция 6

Повторение темы «Структуры данных»

Лекция 7

Программное окружение = пользовательские (авторские) программы, инструментальные средства, примитивы.

7.1 Примитивы

Примитивы – это подпрограммы, назначение которых – локализовать систмно-зависимые операции. Чтобы программу, работающую в одной операционной среде, использовать в другой операционной среде, необходимо «переписать» все системно-зависимые операторы. Как правило, это операции обращения к внешним устройствам. Для удобства такого «переписывания» зависящие от системы операции локализуют в отдельных подпрограммах (примитивах). В случае перехода в другую операционную среду достаточно «переписать» только эти подпрограммы. Вот пример из книги Г.Кернигана и Ф.Плоджера «Инструментальные средства программирования на языке Паскаль» («Ф и С», 1985).

Program primitiv;

Const _endfile_=-1; _endline_=-2;

Type character=-2..255;

var f,g:text;

function getc(var f:text):character;

var ch:char; c:character;

begin

if eof(f) then c:=_endfile_else

if eoln(f) then

begin

readln(f); c:=_endline_

end

else begin

read(f,ch);

c:=ord(ch)

end;

getc:=c;

end;

procedure putc(var f:text; c:character);

begin

if c<>_endfile_ then

if c=_endline_ then writeln(f) else write(f,chr(c))

end;

procedure copy(var f,g:text);

var c:character;

begin

c:=getc(f);

while c<>_endfile_ do

begin

putc(g,c);

c:=getc(f)

end;

close(g)

end;

begin {Тело программы}

assign(f,'primitiv.pas'); assign(g,'cop.pas');

reset(f); rewrite(g); copy(f,g);

end.

7.2 Инструментальные средства. Архивация файлов (пока без сжатия)

Файлы с любым базовым типом – file of byte.

Операции: создать, добавить, исключить, просмотреть.

Procedure addfile(arh,fl:string);

var A,B,F:File Of Byte; c:Byte;

begin

assign(A,arh); assign(F,fl); assign(B,’workfile.d’);

reset(A); reset(F); rewrite(B);

while not eof(A) do begin read(A,c);write(B,c) end;

while not eof(F) do begin read(F,c);write(B,c) end;

erase(A); rename(B,arh);

end;

Каковы недостатки такого «добавления»?

Как эти недостатки исправить?

• Уникальный разделитель

• Указание длины каждого файла

• Каталог содержимого всего архива

7.3 Программы хранения и обработки информации

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

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

Свойства алгоритмов хранения и обработки информации:

Корректность (однозначное восстановление из архива);

Надежность (восстановление после сбоя)