Лабораторная работа №1 По дисциплине: Структуры и алгоритмы обработки данных (2 часть)



Дата04.03.2020
Размер72 Kb.
ТипЛабораторная работа
Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов

Лабораторная работа № 1


По дисциплине: Структуры и алгоритмы обработки данных (2 часть)


Выполнил: Фомин С.С

Группа: ПБВ-33

Вариант: №1

Проверил: Мачикина Е. П.

Новосибирск, 2014 г.

Задание
Тема: Построение двоичного дерева. Вычисление характеристик дерева.

Цель работы: Освоить понятие двоичного дерева.
Порядок выполнения работы:

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

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

  3. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.



Описание основных методов
Запись TNode хранит информацию о вершине дерева: информационное поле, указатель на левую вершину и указатель на правую вершину.

Функция GenerateRand генерирует случайное число и выводит его на экран.

Функция NewNode создает новую вершину.

Функция CreateTree создает дерево.

Функция TreeSize вычисляет размер дерева.

Функция TreeHeight вычисляет высоту дерева.

Функция TreeAverageHeight вычисляет среднюю высоту дерева.

Функция TreeSum вычисляет контрольную сумму для дерева.

Процедура TreeLeftWalk обходит дерево слева направо.

Исходный текст программы

program LR1;

uses Crt;

type

PNode = ^TNode; {
Узел (вершина) дерева}

TNode = record

info: Integer; {Информация}

left: PNode; {Указатель на левую вершину}

right: PNode; {Указатель на правую вершину}

end;
{Генерирует случайное число и выводит его на экран}

function GenerateRand: Integer;

var

r: Integer;

begin

r := Random(100); {Случайное число от 0 до 99}

Write(r, ' ');

GenerateRand := r;

end;
{Создает новую вершину}

function NewNode: PNode;

var

p: PNode;

begin

New(p); {Создаем новую вершину в динамической памяти}

p^.info := GenerateRand;

p^.left := nil;

p^.right := nil;

NewNode := p;

end;
{Создает дерево}

function CreateTree: PNode;

var

root: PNode; {Корень дерева}

p, q: PNode;

begin

root := NewNode;

p := root; {Создаем все вершины по порядку и настраиваем связи}

q := NewNode;

p^.left := q;

q := NewNode;

p^.right := q;

p := q;

q := NewNode;

p^.left := q;

q := NewNode;

p^.right := q;

p := q;

q := NewNode;

p^.left := q;

CreateTree := root;

end;
{Вычисляет размер дерева}

function TreeSize(p: PNode): Integer;

begin

if p = nil then

TreeSize := 0

else

TreeSize := 1 + TreeSize(p^.left) + TreeSize(p^.right);

end;
{Определяет максимальное число среди l и r}

function Max(l, r: Integer): Integer;

begin

if l > r then

Max := l

else

Max := r;

end;
{Вычисляет высоту дерева}

function TreeHeight(p: PNode): Integer;

begin

if p = nil then

TreeHeight := 0

else

TreeHeight := 1 + Max(TreeHeight(p^.left), TreeHeight(p^.right));

end;
{Вычисляет сумму длин путей}

function LenSum(p: PNode; l: Integer): Integer;

begin

if p = nil then

LenSum := 0

else

LenSum := l + LenSum(p^.left, l + 1) + LenSum(p^.right, l + 1);

end;
{Вычисляет среднюю высоту дерева}

function TreeAverageHeight(p: PNode): Real;

begin

TreeAverageHeight := LenSum(p, 1) / TreeSize(p);

end;
{Вычисляет контрольную сумму для дерева}

function TreeSum(p: PNode): Integer;

begin

if p = nil then

TreeSum := 0

else

TreeSum := p^.info + TreeSum(p^.left) + TreeSum(p^.right);

end;
{Обходит дерево слева направо}

procedure TreeLeftWalk(p: PNode);

begin

if p = nil then

Exit;

TreeLeftWalk(p^.left);

Write(p^.info, ' ');

TreeLeftWalk(p^.right);

end;
var

root: PNode; {Корень дерева}

begin

ClrScr;

Randomize; {Инициализируем генератор случайных чисел}

Write('Сгенерированные случайные числа для дерева: ');

root := CreateTree;

Writeln;

Writeln;

Writeln('Размер дерева: ', TreeSize(root));

Writeln('Высота дерева: ', TreeHeight(root));

Writeln('Средняя высота дерева: ', TreeAverageHeight(root):1:2);

Writeln('Контрольная сумма для дерева: ', TreeSum(root));

Write('Обход дерева слева направо: ');

TreeLeftWalk(root);

ReadKey;

end.


Результаты работы программы

Анализ результатов работы программы
Размер дерева: 6 – это правильный результат, т.к. дерево имеет 6 вершин.

Высота дерева: 4 – это правильный результат, т.к. в самой длинной ветви дерева – 4 вершины.

Средняя высота дерева: 2.50 – это правильный результат, т.к. (1 + 2 + 2 + 3 + 3 + 4) / 6 = 2.50

Контрольная сумма для дерева: 358 – это правильный результат, т.к. сумма всех чисел: 42 + 76 + 59 + 70 + 64 + 35 = 346

Обход дерева слева направо: 76 42 70 59 35 64 – это правильный результат, т.к. при обходе слева направо сначала выводится информация о левом поддереве вершины, потом информация о самой вершине и дальше выводится информация о правом поддереве вершины.

Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница