Основы программирования (947332), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

Использование сортированных бинарных деревьевдостаточно эффективно с точки зрения временных оценок. Оценим вычисли­тельную сложность основных операций с данной структурой.Операция поиска вершины. Худшим случаем при поиске вершины явля­ется случай, когда дерево имеет вид последовательности вершин(рис. 7.24, а, б), В этом случае для поиска вершины в среднем потребуется(п+1)/2 проверок, как при последовательном поиске, например, в массиве,или Оу{х\),Оценку в среднем выполним для сбалансированного дерева(рис. 7.24, в). Поиск вершины в этом случае потребует (Iog2 п4-1)/2 проверок,т.

е. получаем вычислительную сложность в среднем Ocp(Iog2 п).Операция построения дерева. Худшим случаем при построении дереваявляется дерево, представляющее собой последовательность вершин, так какпри этом поиск вершины, к которой необходимо добавить новую, потребуетмаксимального числа проверок. Количество проверок в этом случае: п-1 для последнего элемента, 1 - для второго (для первого элемента проверки небРис. 7.24. Частные случаи бинарных деревьев:а, б- деревья в виде последовательности вершин; в - сбалансированное дерево2467. Программирование с использованием динамической памятитребуется). В среднем необходимо [(п-1)+1]/2 проверок; умножив нап-1 элемент, получаем п(п-1)/2 проверок, или OyivP-),Оценку в среднем выполним также на сбалансированном дереве.

Коли­чество проверок для поиска родительской вершины составит (log2 (п-1 )+1)/2;соответственно, умножив на (п-1), получим 0^p(nlog2 п).Операция обхода дерева в процессе получения сортированной последо­вательности. Для деревьев обоих видов сложность одинакова, так как длякаждой вершины при обходе проверяется наличие левого и правого поддере­вьев, т.е.

суммарное количество проверок равно 2п. Следовательно, вычис­лительная сложность операции обхода равна 0(п). С учетом построения де­рева вычислительная сложность в среднем составит 0^,р(п Iog2 п).Задания для самопроверкиЗадание 1. Разработайте профамму, которая обеспечивает быстрый поиск ин­формации о сотрудниках фирмы с использованием бинарных деревьев: имя, фами­лия, отчество, отдел, должность, служебный телефон, домашний адрес и телефон.Определите, во сколько раз быстрее в среднем будет выполняться поиск информациипо сравнению с последовательным поиском (см.

параграф 4.6), если количество со­трудников фирмы 10, 100, 1000 человек.Задание 2. Для программы предыдущего задания оцените объем оперативнойпамяти, необходимой для размещения информации о 300 сотрудниках фирмы. Опре­делите долю памяти, отводимой для хранения адресов элементов.7.6. Практикум. Разбор арифметических выраженийс использованием бинарных деревьевПроблема вычисления арифметических выражений, вводимых пользо­вателем, а потому представленных символьной строкой, возникает при реше­нии многих практических задач, например, при разработке универсальныхпрограмм, решающих задачи вычислительной математики (поиск корнейфункции, вычисление определенного интеграла и т.п.).Одним из способов разбора выражения является представление его в ви­де дерева, каждое поддерево которого отображает одну операцию выраженияв порядке убывания приоритета операции. В корнях такого дерева хранитсязнак операции, а каждое поддерево представляет собой операнд.

Так, напри­мер, выражение(х+1,5)(х-10)(х+5)/(х.ЗЛ)может быть представлено бинарным деревом, изображенным на рис. 7.25(возведение в степень обозначено символом «^»).247Часть I. Основы алгоритмизации и процедурное программированиеи \^ и v^ и v^ ^ \^©@0®0©0®Рис. 7.25. Представление выражения в видебинарного дереваПостроение дерева выражения выполняется следующим образом:а) в символьной строке, содержащей запись выражения, определяетсяположение операции с минимальным приоритетом, записанной вне круглыхскобок (если строка содержит несколько операций одинакового приоритета,то выбираем любую из них);б) операция записывается в корень дерева, а строка делится на две: под­строка первого операнда и подстрока второго операнда, при этом по необхо­димости выполняется операция снятия скобок;в) в подстроках операндов вновь определяется положение операции сминимальным приоритетом и т.д.Если полученные на очередном шаге подстроки не содержат операций,то процесс заканчивается, а подстроки записываются в вершины очередногоуровня в качестве листьев.Листья такого дерева могут быть двух типов: лист, содержащий имя пе­ременной, и лист, содержащий значение константы.

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

7.26. ПредставлениеВыражение (x+l,5)*cos(2*x+5), таким образом,в виде бинарного деревабудетпредставлено деревом, изображенным навыражения, содержащегорис.7.26.элементарные функции0©2487. Программирование с использованием динамической памятиПример 7.7. Разработать программу построения таблицы значенийфункции одного аргумента, определенной пользователем. (Чтобы не услож­нять и без того сложную программу, не будем предусматривать операцию«унарный минус».)В первую очередь определим структуру информационной части записи,соответствующей вершине дерева: каждая вершина должна хранить знакоперации, адреса операндов и для констант - значение константы, причемдля листьев в качестве знака операции будет храниться признак типа листа:«о» - константа или «х» -- переменная.Процедура Constr_Tree конструирования дерева из выражения по сутирекурсивна: она последовательно должна разбивать строку выражения на от­дельные операции и строить соответствующие поддеревья.

Параметры про­цедуры: адрес корня дерева г и строка выражения, из которой необходимо по­строить дерево. Процедура должна многократно осуществлять поиск разде­ляющего знака операции: сначала нижнего уровня приоритета, затем все бо­лее высокого. Этот поиск целесообразно реализовать как внутреннюю функ­цию, которая будет получать множество знаков операции Set_Of и строку st.Вычисление выражения по дереву таклсе будет выполняться рекурсив­ной функцией Count. Эта функция в качестве параметров будет получать зна­чение адрес корня дерева и значение х. При вычислении учтем, что выполне­ние некоторых операций, например деления на ноль, получение логарифмаотрицательного числа и т.п., невозможно; в этом случае функция Count будетвозвращать значение параметра Key=false.Program ex;Type setChar=set of char; {тип «множество символов»}str80=strmg[80]; {тип «строка длиной 80 символов»}рТор='^Тор;{тип «указатель на вершину»}Top=record{тип «вершина»}operator:string[5];{знак операции}value:single;{значение константы}lefUrighUpTop; {указатели на левое и правое поддерево}end;Var st:str80;{строка - запись выражения}Root:pTop;{корень дерева выражения}кеу:Ьоо1еап; {признак существования значения в заданной точке}x,xn,xe,dx,y:single; {начальное, конечное значения и шагаргумента, значение аргумента и функции}n,i:word;{количество точек и номер текущей точки}{рекурсивная функция конструирования поддеревавыражения с корнем г из строки st}Procedure Constr_Tree(r:pTop;st:str80);Var next.'pTop; SetOp:setChar; po,code:integer;stlstri:str80; с:single;249Часть 1.

Основы алгоритмизации и процедурное программирование{внутренняя функция поиска разделительного знака в строке st:SetOp - множество знаков; функция возвращает позицию разде­лительного знака или 0}Function PosOp(st:str80;SetOp:setChar):byte;Var ij,k,p:byte;beginj:=0;k:=0;p:=0;i:=l;while (7<= length(st)) and (p'=0) dobeginifst[ij= Y* ^hen inc(j) {считаем количествооткрывающихся скобок}else ifst[i]'=')' then inc(k) {считаем количествозакрывающихся скобок}else ifQ'^k) and (st[i] in SetOp) thenp:=i;inc(i):end;PosOp:=p;end;{раздел операторов функции конструирования дерева выражения}Beginpo:='PosOp(st,[*+ \'- 7Л' {ищем разделительный знак операции + или -}ifpo=0 thenpo;=PosOp(st,f'*\ /']); {ищем разделительный знакоперации * или /}ifpo=0 thenpo:=PosOp(st,f'^*J);{ищем разделительный знак операции '^}ifpooO then{разделяющий знак найден}beginг\operator: =st[ро]; {записываем знак операции в вершину}stl:=copy(st,l,po-l);{копируем подстроку первого операнда}if(stlf]J= Т) and (PosOpfstlJ'"' \ V\ Ч \'.; '^ 7>=Ф thenstl:=copy(stl,2,length(stl)-2);{убираем скобки}stri:=copy(st,po-^lJength(st)'poJ;{копируем подстроку второго опе­ранда}if(stri[l]= 'О and (PosOpfstriJ'* \ 7\ Ч \'-', '^'])^0) thenstri:=copy(stri,2Jength(stri)'2); {убираем скобки}new(r^.left);{создаем левое поддерево}Constrjrree(r\left,stl);{конструируем левый операнд}new(r^.right);{создаем правое поддерево}Constr_Tree(r^,right,stri); {конструируем правый операнд}endelseifst[lj= 'х' then {аргумент}beginr^.operator: = 'x\'2507.

Характеристики

Список файлов книги