ы опять получили переполнение, при обработке которого узел, содержащий элементы 8, 10 и 12 разделится на два узла: узел с элементом 8 и узел с элементом 12, - а средний элемент 10 будет вынесен на верхний уровень. И теперь дерево примет такой вид:Теперь мы получили переполнение в корне дерева. Как мы оговаривали ранее этот случай надо обработать отдельно. Это связано с тем, что здесь мы должны будем создать новый корень, в который во время деления будет вынесен средний элемент:Теперь полученное дерево не имеет переполнения.В этом случае, как и при поиске, время обработки страницы поиска есть величина постоянная, пропорциональная размеру страницы, а значит, сложность алгоритма добавления в B-дерево будет также T(h), где h - глубина дерева.Итак, как мы заметили с самого начала, у B-деревьев есть своя сфера применения: хранение настолько больших массивов информации, что их невозможно целиком разместить в выделяемой оперативной памяти, но требуется обеспечить быстрый доступ к ним.В таких случаях B-деревья являются хорошим средством программно ускорить доступ к данным.Ярким примером практического применения B-деревьев является файловая система NTFS, где B-деревья применяются для ускорения поиска имен в каталогах. Если сравнить скорость поиска в этой файловой системе и в обычной FAT на примере поиска на жестком диске большого объема или в каталоге, содержащем очень много файлов, то можно будет констатировать превосходство NTFS. А ведь поиск файла в каталоге всегда предшествует запуску программы или открытию документа.B-деревья обладают прекрасным качеством: во всех трех операциях над данными (поиск/удаление/добавление) они обеспечивают сложность порядка T(h), где h - глубина дерева. Это значит, что чем больше узлов в дереве и чем сильнее дерево ветвится, тем меньшую часть узлов надо будет просмотреть, чтобы найти нужный элемент. Попробуем оценить T(h).Число элементов в узле есть величина вероятностная с постоянным математическим ожиданием MK. Математическое ожидание числа узлов равно:,где n - число элементов, хранимых в B-дереве. Это дает сложность T(h)=T(log(n)), а это очень хороший результат.Поскольку узлы могут заполняться не полностью (иметь менее NumberOfItems элементов), то можно говорить о коэффициенте использования памяти. Эндрю Яо доказал, что среднее число узлов после случайных вставок при больших n и NumberOfItems составит N/(m*ln(2))+F(n/m2), так что память будет использоваться в среднем на ln(2)*100%.В отличие от сбалансированных деревьев B-деревья растут не вниз, а вверх. Поэтому (и из-за разной структуры узлов) алгоритмы включения/удаления принципиально различны, хотя цель их в обоих случаях одна - поддерживать сбалансированность дерева.Идея внешнего поиска с использованием техники B-деревьев была предложена в 1970 году Р.Бэйером и Э.Мак-Крэйтом и независимо от них примерно в то же время М.Кауфманом. Естественно, что за это время было предложено ряд усовершенствований B-деревьев, связанных с увеличением коэффициента использования памяти и уменьшением общего количества расщеплений.Одно из таких усовершенствований было предложено Р.Бэйером и Э.Мак-Крэйтом и заключалось в следующем. Если узел дерева переполнен, то прежде чем расщеплять этот узел, следует посмотреть, нельзя ли «перелить» часть элементов соседям слева и справа. При использовании такой методики уменьшается общее количество расщеплений и увеличивается коэффициент использования памяти.|
| program PTree;{$APPTYPE CONSOLE}typeTInfo = Byte;PItem = ^Item;Item = recordKey: TInfo;Left, Right: PItem;end;TTree = classprivateRoot: PItem;publicconstructor Create;procedure Add(Key: TInfo);procedure Del(Key: TInfo);procedure View;procedure Exist(Key: TInfo);destructor Destroy; override;end;//---------------------------------------------------------constructor TTree.Create;beginRoot := nil;end;//---------------------------------------------------------procedure TTree.Add(Key: TInfo);procedure IniTree(var P: PItem; X: TInfo); //создание корня дереваbeginNew(P);P^.Key :=X;P^.Left := nil;P^.Right := nil;end;procedure InLeft (var P: PItem; X : TInfo); //добавление узла слеваvar R : PItem;beginNew(R);R^.Key := X;R^.Left := nil;R^.Right := nil;P^.Left := R;end;procedure InRight (var P: PItem; X : TInfo); //добавить узел справаvar R : PItem;beginNew(R);R^.Key := X;R^.Left := nil;R^.Right := nil;P^.Right := R;end;procedure Tree_Add (P: PItem; X : TInfo);var OK: Boolean;beginOK := false;while not OK do beginif X > P^.Key then //посмотреть направоif P^.Right <> nil //правый узел не nilthen P := P^.Right //обход справаelse begin //правый узел - лист и надо добавить к нему элементInRight (P, X); //и конецOK := true;endelse //посмотреть налевоif P^.Left <> nil //левый узел не nilthen P := P^.Left //обход слеваelse begin //левый узел -лист и надо добавить к нему элементInLeft(P, X); //и конецOK := trueend;end; //цикла whileend;beginif Root = nilthen IniTree(Root, Key)else Tree_Add(Root, Key);end;//-------------------------------------------------------------procedure TTree.Del(Key: TInfo);procedure Delete (var P: PItem; X: TInfo);var Q: PItem;procedure Del(var R: PItem);//процедура удаляет узел имеющий двух потомков, заменяя его на самый правый//узел левого поддереваbeginif R^.Right <> nil then //обойти дерево справаDel(R^.Right)else begin//дошли до самого правого узла//заменить этим узлом удаляемыйQ^.Key := R^.Key;Q := R;R := R^.Left;end;end; //Delbegin //Deleteif P <> nil then //искать удаляемый узелif X < P^.Key thenDelete(P^.Left, X)elseif X > P^.Key then Delete(P^.Right, X) | //искать в правом поддеревеelse begin//узел найден, надо его удалить//сохранить ссылку на удаленный узелQ := P;if Q^.Right = nil then//справа nil//и ссылку на узел надо заменить ссылкой на этого потомкаP := Q^.Leftelseif Q^.Left = nil then//слева nil//и ссылку на узел надо заменить ссылкой на этого потомкаP := P^.Rightelse //узел имеет двух потомковDel(Q^.Left);Dispose(Q);endelseWriteLn('Такого элемента в дереве нет');end;beginDelete(Root, Key);end;//-------------------------------------------------------------procedure TTree.View;procedure PrintTree(R: PItem; L: Byte);var i: Byte;beginif R <> nil then beginPrintTree(R^.Right, L + 3);for i := 1 to L doWrite(' ');WriteLn(R^.Key);PrintTree(R^.Left, L + 3);end;end;beginPrintTree (Root, 1);end;//-------------------------------------------------------------procedure TTree.Exist(Key: TInfo);procedure Search(var P: PItem; X: TInfo);beginif P = nil then beginWriteLn('Такого элемента нет');end elseif X > P^. Key then //ищется в правом поддеревеSearch (P^. Right, X)elseif X < P^. Key thenSearch (P^. Left, X)elseWriteLn('Есть такой элемент');end;beginSearch(Root, Key);end;//-------------------------------------------------------------destructor TTree.Destroy;procedure Node_Dispose(P: PItem);//Удаление узла и всех его потомков в деревеbeginif P <> nil then beginif P^.Left <> nil thenNode_Dispose (P^.Left);if P^.Right <> nil thenNode_Dispose (P^.Right);Dispose(P);end;end;beginNode_Dispose(Root);end;//-------------------------------------------------------------procedure InputKey(S: String; var Key: TInfo);beginWriteLn(S);ReadLn(Key);end;varTree: TTree;N: Byte;Key: TInfo;beginTree := TTree.Create;repeatWriteLn('1-Добавить элемент в дерево');WriteLn('2-Вывести узлы дерева');WriteLn('3-Проверить существование узла');WriteLn('4-Выход');ReadLn(n);with Tree do begincase N of1: beginInputKey('Введите значение добавляемого элемента', Key);Add(Key);end;2: View;3: beginInputKey('Введите элемент, существование которого вы хотите проверить', Key);Exist(Key);end;end;end;until N=4;Tree.Destroy; end. | | |
2.2 ОБРАБОТКА ТЕКСТОВЫХ ФАЙЛОВРазработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество слов, которые содержат определённое количество согласных. Привожу исходный текст программы:Program file;uses crt;labelfin;Const mn=['б','в','д','ж','з','к','л','м','н','п','р','с','т','ф','х','ц','ч','ш','щ'];Var f3:text;i,j,ch,sl:integer;name:string;s:char;wrd :string;dbase:string;BeginclrScr;writeln('vvedite imya faila');readln(name);assign(f3,name);reset(f3);s:=' ';sl:=0;ch:=0;while not eof(f3) dobeginreadln(f3,wrd);i:=1;While i<=length(wrd) dobeginif wrd[i]<>' ' then sl:=sl+1;while (wrd[i]<>' ') and (i<=length(wrd)) do inc(i);inc(i)end;end;close(f3);reset(f3);while not eof(f3) dobeginwhile not eoln(f3) dobegin read(f3,s);if (s in mn) then ch:=ch+1;end;end;wrd:='c:\den.txt';assign(f3,wrd);{$I-}append(f3);{$I+}if IOResult <> 0then begin{$I-}rewrite(f3);{$I+}if IOResult <> 0thenbeginwriteln('ERROR!');goto fin;end;end;write(f3,' kol-vo slov --',sl,' kol-vo soglasnih --',ch,'');writeln('chislo slov: ',sl,' chiso soglasnih: ',ch);close(f3);fin:readkey;End. Приложение к выполненным программам1. Обработка текстовых файлов¦ Ввод данных ¦¦ Запись в файл ¦¦ Считывание файла ¦¦ Обработка данных ¦¦ Вывод результата ¦+------ Выход ------+Ввод данных:Я хочу есть и спать, ещё я бы поиграл в комп.Запись в файлTEXT.pasВывод результата:chislo slov: 11 chiso soglasnih: 17Содержание выходного файла DEN.txt:kol-vo slov --11 kol-vo soglasnih --172. Вставка элемента в В-дерево1-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa331-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa221-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa441-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod1Vvedite znacgenie dobavlayemogo elementa111-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod2443322111-Dobavit element v derevo2-Vivesti uzli dereva3-Provtrit sushestvovanie uzla4-vihod ЗАКЛЮЧЕНИЕБыла выполнена курсовая работа по предмету «Структуры и алгоритмы компьютерной обработки данных» на тему «Алгоритмы преобразования ключей (расстановка)». В данной курсовой работе рассмотрены теоретические вопросы и выполнены практические задания, которые соответствуют выданному заданию.В данной курсовой работе можно выделить 3 основных части, которые соответствуют следующим статусам:1. Теоретическая часть;2. Теоретическая + практическая часть;3. Практическая часть;В курсовой представлена вся необходимая информация по данной курсовой, использована как научная литература, так и возможности всемирной сети Internet. Выполнены практические задания, и использованием знаний и умений программировать на алгоритмических языках высокого уровня Turbo Pascal, Borland Delphi. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ1. Hellerman H. Digital Computer System Principles. McGraw-Hill, 1967. 2. Ершов А.П. Избранные труды. Новосибирск: ВО «Наука», 1994. 3. Кнут Д. Искусство программирования, т.3. М.: Вильямс, 2000. 4. Peterson W.W. Addressing for Random-Access Storage // IBM Journal of Research and Development. 1957. V.1, N2. Р.130--146. 5. Morris R. Scatter Storage Techniques // Communications of the ACM, 1968. V.11, N1. Р.38--44. 6. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2000. 7. Чмора А. Современная прикладная криптография. М.: Гелиос АРВ, 2001. 8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. 9. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985. 10. Керниган Б., Пайк Р. Практика программирования. СПб.: Невский диалект, 2001. 11. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995. Размещено на Allbest.ru
Страницы: 1, 2, 3, 4
|
