Предыдущая страница реферата | 1  2  3  4  5



Нетрудно подсчитать что b(1)=1, b(2)=2, b(3)=b(0)b(2) + b(1)b(1) + b(2)b(0) , полагая b(0)=1, получаем, что b(3)=2+1+2=5. Соответственно b(4)=5+2+2+5=14, b(5)=14+5+4+5+14=42. 

 В общем случае b(n)=C(n, 2n) / (n+1) = (2*n!) / (n! * n!)

Определение.

Дерево называется совершенным (или полностью сбалансированным) если любой путь в нем от корня к листу не более чем на единицу отличается от длины самого длинного пути в этом дереве.

Следствие.

Совершенное дерево из n вершин имеет минимальную высоту среди всех деревьев, имеющих n вершин.

 Подсчитаем высоту совершенного бинарного дерева из n вершин. Пусть в нем i ярусов. (Ярусом назовем множество вершин равно отстоящих от корня дерева.) Тогда число вершин в дереве можно выразить следующим соотношением:

1 + 2 + 2^2 +...+ 2^i = n.

Отсюда получаем 2^i -1=n, i=log2 (n+1) - 1. Или в приближенно log n. Отметим, что число совершенных деревьев составляет лишь малую часть общего числа деревьев. Например, при n=4 их всего 4.

 Совершенные деревья интересны, например, тем что сложность доступа от корню к любому листу практически одна и та же. Здесь под сложностью доступа мы понимаем длину пути от корня к листу.

3.4. Стек

Стеком называется линейное дерево. В отличии от деревьев для операций со стеком есть ограничения. Доступ в стеке возможен только к корню дерева, которое в случае стека называется окном стека. Поэтому чтобы посмотреть элемент или изъять его или добавить новый - все это можно сделать только через корень.  Примеры стека: подносы в столовой, патроны в обойме.

 Основные операции: добавить элемент в стек, изъять элемент.

3.5. Очередь

Очередь - это линейное дерево, но в отличие от стека добавить элемент в очередь можно только в корень дерева, который в случае очереди называется хвостом или концом очереди, а изъять элемент из очереди можно только со стороны листа, который называется головой очереди.

 Пример: банальная очередь в магазине, в столовой. Основные операции изъять элемент, добавить элемент.

3.6. Таблица

Упорядоченное множество пар (ключ,тело).

Примеры:

 функция может быть представлена как пара (аргумент, результат),

 таблица с записями о людях. В такой таблице ФИО - ключ, данные о человеке - тело. Мы здесь не будем подробно останавливаться на таблицах, так как им будет посвящено особое место в курсе.

4. Структура данных хранения (СДХ)

 В Pascal можно выделить две базовые структуры хранения: вектор из записей и список. С идей списка мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать заранее число компонентов в структуре. Однако, как мы увидим позднее связывание статических элемнтов памяти посредством ссылок в цепочки позволяет динамически упралять не только числом компонентов, но и структурой в целом. Например, когда мы заранее не знаем степень вершин в графе.

 На базовый характер этих структур так же указывает и то, что в их терминах можно описать все остальные структуры данных в Pascal. Более этого, важно помнить и то, что "за кулисами Pascal" стоит ЭВМ с ее структурой памяти. которая есть вектор из слов - адресуемой единице памяти. памяти.

Скачали данный реферат: Bochkarjov, Shubin, Максимов, Fil'chenkov, Чувикова, Kodica.
Последние просмотренные рефераты на тему: банк рефератов, доклади, реферат на тему народы, культура реферат.





Предыдущая страница реферата | 1  2  3  4  5