Исследование и программная реализация алгоритмов теории графов

1

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Сибирский государственный технологический университет

Факультет автоматизации и информационных технологий

Кафедра системотехники

Исследование и программная реализация алгоритмов теории графов

Руководитель:

Доррер А.Г.

Разработала:

Студент группы 23-01

Красноярск 2014



Задание для выполнения работы

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

Требуется:

Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий алгоритм.

Реализовать выбранный алгоритм на языке Delphi. Предусмотреть возможность ввода разнообразных входных данных.

Окончательный вариант программы обязательно должен отображать смысловую постановку задачи.

Приложить распечатки экранов.



Реферат

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

Размещение, словарь, двоичное дерево поиска, алгоритм, корень, потомок, обход дерева.

Объектом исследования данной работы является двоичное дерево поиска.

Цель работы - овладение навыками работы с алгоритмом построения и обхода двоичного дерева поиска.

Метод исследования - теория графов, алгоритмизация, язык программирования Delphi.



Содержание

Задание

Реферат

Введение

1. Теоретические сведения

1.1 Определение двоичного дерева поиска

1.2 Упорядоченность двоичного дерева

1.3 Алгоритм

2. Решение задачи

2.1 Входная и выходная информация

2.2 Текст программы

2.3 Протокол контрольного примера

Заключение

Библиографический список



Введение

Цель данной работы - реализовать добавление слова в словарь на основе заданного алфавита на языке программирования высокого уровня. Основной задачей является сортировка строк в словарном порядке. В качестве «инструмента» для выполнения данной задачи будет выступать двоичное дерево поиска.



1. Теоретические сведения

1.1 Определение двоичного дерева поиска

Для решения задачи сортировки мы будем использовать так называемое двоичное дерево поиска.

Двоичным деревом поиска называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами. В нашей задаче считается, что одной вершине соответствует только один элемент - слово. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. Двоичное дерево поиска позволяет выполнять следующие основные операции:

– Поиск вершины по ключу;

– Определение вершин с минимальным и максимальным значением ключа;

– Переход к предыдущей или последующей вершине, в порядке, определяемом ключами;

– Вставка вершины;

– Удаление вершины.

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

Двоичное дерево поиска может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.

При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.

1.2 Упорядоченность двоичного дерева

Если x - это произвольная вершина в двоичном дереве поиска, а вершина y находится в левом поддереве вершины x, то y.key<= x.key. Если x - это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y.key>= x.key. Из свойства следует, что если y.key == x.key, то вершина y может находиться как в левом, так и в правом поддереве относительно вершины x.

1.3 Алгоритм

Построение двоичного дерева поиска на основе исходного неотсортированного списка a₁, a₂, …, a_Nреализуется на основе следующего алгоритма:

1 Для множества, состоящего лишь из одного элемента a_i (n=1), a₁ просто представляет собой корень, в свою очередь деревоT₁ представляет собой дерево сортировки с одним единственным элементом a₁, который является вершиной этого дерева; увеличиваем nдо n+1.

2 Если n>N, где, тогда процедура заканчивается. В противном случае сравниваем a_nс корнем.

Если a_n?корня, то переходим к левому поддереву.

Если левое поддерево пусто, то добавляем a_nв качестве левого потомка корня, чтобы формировать следующее дерево сортировки T_n; увеличиваем nдо n+1 и повторяем шаг 2;

в противном случае повторяем шаг 2, использую левое поддерево.

В противном случае переходим к правому поддереву.

Если правое поддерево пусто, тогда добавляем a_n в качестве правого потомка корня, чтобы образовать следующее дерево сортировки T_n; увеличиваем n до n+1 и повторяем шаг 2;

В противном случае повторяем шаг 2, используя правое поддерево.

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

1 Обрабатываем левое поддерево;

2 Вносим в список корень;

3 Обрабатываем правое поддерево.

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



2. Решение задачи

2.1 Входная и выходная информация

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

Также задается целое число (hв тексте задания) - длина слова в словаре. Ограничение на длину слова - 99 символов.

Далее на вход подаются непосредственно слова. При наборе слова необходимо использовать только те символы, которые содержатся в заданном алфавите.

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

На рисунке 1 представлен внешний вид программы.

Рисунок 1 - Снимок экрана программы

2.2 Текстпрограммы

unit Unit1;

interface

uses

Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,

System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs,

Vcl.StdCtrls, Vcl.ComCtrls;

type

TForm1 = class(TForm)

ListBox1: TListBox;

Edit1: TEdit;

Button1: TButton;

GroupBox1: TGroupBox;

GroupBox2: TGroupBox;

Memo1: TMemo;

Button2: TButton;

Label1: TLabel;

Label3: TLabel;

Edit2: TEdit;

Label2: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

type

NumArr = array [1..64] of Integer;

TreePointer = ^tree;

tree = record

Word: NumArr;

left, right: TreePointer;

end;

functionSTree(root, r: TreePointer; Word: NumArr): TreePointer;

procedureInOrder(root: TreePointer);

functionPosInABC(C: Char; ABC: string): Integer;

function Str2Num(Str: string; ABC: string): NumArr;

function Num2Str(Arr: NumArr; ABC: string): string;

functionIsSmaller(Arr1, Arr2: NumArr): Boolean;

functionIsNotNil(Arr: NumArr): Boolean;

procedureGrowTree(root: TreePointer; FirstWord: NumArr);

functionReSymb(Str: string): Boolean;

public

{ Public declarations }

end;

var

Form1: TForm1;

Alphabet: string;

h: Integer;

implementation

{$R *.dfm}

{Возвращает True, если в строке есть повторяющиеся символы}

function TForm1.ReSymb(Str: string): Boolean;

var

I, J: Integer;

begin

Result := False;

for I := 1 to Length(Str)-1 do

for J := I+1 to Length(Str) do

ifStr[I] = Str[J] then

begin

Result := True;

Exit;

end;

end;

procedure TForm1.Button2Click(Sender: TObject);

var

i: Integer;

begin

if Button2.Tag = 0 then

begin

Button2.Caption := 'Сохранить';

Memo1.Enabled := True;

Edit2.Enabled := True;

Edit1.Enabled := False;

ListBox1.Enabled := False;

Button1.Enabled := False;

LIstBox1.Clear;

Button2.Tag := 1;

end

else

begin

Alphabet := '';

for i := 1 to Length(Memo1.Lines.Text) do

if Memo1.Lines.Text[i] <> ' ' then

Alphabet := Alphabet + Memo1.Lines.Text[i];

if Alphabet = '' then

MessageBox(0, 'Алфавитпуст', 'Ошибка', 0)

else

ifReSymb(Alphabet) then

MessageBox(0, 'Алфавитсодержитповторяющиесясимволы', 'Ошибка', 0)

else

ifStrToInt(Edit2.Text) > 0 then

begin

Button2.Caption := 'Редактировать';

Memo1.Enabled := False;

Edit2.Enabled := False;

Button2.Tag := 0;

Edit1.Enabled := True;

ListBox1.Enabled := True;

Button1.Enabled := True;

h := StrToInt(Edit2.Text);

Edit1.MaxLength := h;

end

else

MessageBox(0, 'Длина слова не может быть равной 0', 'Ошибка', 0);

end;

end;

{Трансформация строки в массив позиций алфавита}

function TForm1.Str2Num(Str: string; ABC: string): NumArr;

var

I: Integer;

begin

for I := 1 to h do

Result[I] := PosInABC(Str[i], ABC);

end;

{Трансформация массива позиций алфавита в строку}

function TForm1.Num2Str(Arr: NumArr; ABC: string): string;

var

I: Integer;

begin

Result := '';

for I := 1 to h do

Result := Result + ABC[Arr[I]];

end;

{Возвращает True, если в Arr нет нулей}

function TForm1.IsNotNil(Arr: NumArr): Boolean;

var

I: Integer;

begin

I := 1;

while (I < h) and (Arr[i] <> 0) do

Inc(I);

ifArr[i] = 0 then

Result := False

else

Result := True;

end;

{Возвращает True, если Arr1 < Arr2}

function TForm1.IsSmaller(Arr1, Arr2: NumArr): Boolean;

var

I: Integer;

begin

I := 1;

while (i < h) and (Arr1[I] = Arr2[I]) do

Inc(I);

if Arr1[I] > Arr2[I] then

Result := False

else

Result := True;

end;

{Возврат позиции символа в алфавите. 0 еслиотсутствует}

function TForm1.PosInABC(C: Char; ABC: string): Integer;

var

i: Integer;

begin

Result := 0;

i := 1;

while (i < Length(ABC)) and (C <> ABC[i]) do

Inc(i);

if C = ABC[i] then

Result :=i;

end;

{Восстановление списка из дерева}

procedure TForm1.InOrder(root: TreePointer);

begin

if root <> nil then

begin

InOrder(root^.left);

ListBox1.Items.Add(Num2Str(root^.Word, Alphabet));

InOrder(root^.right);

end;

end;

{Добавлениеэлемента в дерево}

function TForm1.STree(root, r: TreePointer; Word: NumArr): TreePointer;

begin

if r = nil then

begin

New(r);

r^.left := nil;

r^.right := nil;

r^.Word := Word;

ifIsSmaller(Word, root^.Word) then

root^.left := r

else

root^.right := r;

STree := r;

end

else

begin

ifIsSmaller(Word, r^.Word) then

STree :=STree(r, r^.left, Word)

else

STree :=STree(r, r^.right, Word);

end;

end;

{Выращиваниедерева}

procedure TForm1.GrowTree(root: TreePointer; FirstWord: NumArr);

var

dummy: TreePointer;

i: Integer;

Word: NumArr;

begin

root^.left := nil;

root^.right := nil;

root^.Word := FirstWord;

for i := 0 to ListBox1.Items.Count-1 do

begin

Word := Str2Num(ListBox1.Items.Strings[i], Alphabet);

dummy := STree(root, root, Word);

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i: Integer;

FirstW: NumArr;

rt: TreePointer;

begin

if Length(Edit1.Text) = h then

begin

FirstW := Str2Num(Edit1.Text, Alphabet);

ifIsNotNil(FirstW) then

begin

New(rt);

GrowTree(rt, FirstW);

{Составление списка по дереву}

ListBox1.Clear;

InOrder(rt);

Edit1.Text := '';

end

else

MessageBox(0, 'Некоторые символы не совпадают с алфавитом', 'Ошибка', 0);

end

else

MessageBox(0, PChar('Длина слова должна быть равна '+Edit2.Text),

'Ошибка', 0);

end;

end.

2.3 Протокол контрольного примера

Алфавит: “abcdefghijklmnopqrstuvwxyz”;

Длина слов в словаре: 4;

В таблице 1 представлен процесс добавления слов.

Таблица 1 - Добавление слов в словарь

Добавляемое слово	boom	head	here	boot	anna	body
Состояние словаря	boom	boom head	boom head here	boom boot head here	anna boom boot head here	anna body boom boot head here

На рисунке 2 представлен снимок экрана при прохождении контрольного примера.

Рисунок 2 - Контрольный пример



Заключение

В ходе выполнения работы был произведен библиографический поиск по теме двоичное дерево поиска. Был освоен алгоритмы построения и обхода дерева, а также осуществлена их реализация на языке программирования Delphi.



Библиографический список

1 ГОСТ 19.201-78. Техническое задание. Требования к содержанию и оформлению. - Введен с 01.01.80 // Единая система программной документации. - М., 1988.

2 СТП 3.4.104-01. Курсовое проектирование. Требования к выполнению и представлению. - Взамен СТП 17 - 87; Введен с 24.06.02. - Красноярск, СибГТУ, 2002.

3 СТП 3.4.204-01. Стандарт предприятия. Требования к оформлению текстовых документов. - Красноярск :СибГТУ, 2001.

4 ГОСТ 2.105-95. Общие требования к текстовым документам. - Взамен ГОСТ 2.105-79, ГОСТ 2.906-71; Введен с 01.07.96. - М.: Издательство стандартов, 1996. Группа ЕСКД.

5 Яркова, С.А. Методические указания: Рекомендации к написанию курсовых работ [Текст] / С.А. Яркова, Т.Н. Баринова, С.В. Трапезников. - Красноярск, 2006.

6 Иванилова, Т.Н. Дискретная математика: Сборник заданий для курсовых работ с примера выполнения для студентов специальностей 2204000 всех форм обучения [Текст]. - Красноярск, СибГТУ, 2004.

7 Акопов, Р. Двоичные деревья поиска [Электронный ресурс] / Информация находится в открытом доступе:http://www.rsdn.ru/article/alg/binstree.xml

8 Шилдт, Г. Энциклопедия TurboPascal [Электронный курс]/ Информация находится в открытом доступе http://www.cyberguru.ru/programming/pascal/turbopascal-encyclopaedia-page28.html

9 Логинов, Б.М. Лекции и упражнения по курсу «Введение в дискретную математику»[Текст]. - Калуга, 1998.

Размещено на Allbest.ru