бирюльки

АНТОН ПАЛАГИН AKA TONY

Спецвыпуск: Хакер, номер #071, стр. 071-008-3

ЛИСТИНГ

определение элемента (узла) графа

template< class T >

struct Graph

{

T elem; //Текущий элемент

std::list< Graph *> edges; //Указатели на связанные элементы графа

};

[бинарное дерево,]

оно же двоичное дерево. Часто используется в алгоритмах поиска. Каждый узел в дереве формирует свое поддерево. У каждого узла может быть только два дочерних узла — правый и левый. Соответственно, каждый узел (за исключением конечных, самых нижних узлов) такого дерева имеет одно входящее и два исходящих ребра. Главным алгоритмом для деревьев является алгоритм его обхода (Traverse), который позволяет найти наиболее оптимальный маршрут к нужным данным. Бинарное дерево лежит в основе алгоритма отбрасывания невидимых полигонов BSP (binary space partitioning), используемого в играх. Аналогично двунаправленному списку, каждая вершина бинарного дерева ссылается на правый и левый элементы, но в случае дерева эти элементы являются дочерними для узла, а не равноправными, как в случае списка.

ЛИСТИНГ

определение элемента (узла) бинарного дерева

template< class T >

struct BiTree

{

T elem; //Текущий элемент

BiTree * left; //Указатель на левый дочерний элемент

BiTree * right; //Указатель на правый дочерний элемент

};

[октарное дерево,]

оно же octree. Это способ разбиения трехмерного пространства (space partitioning), который используется при разработке игр для отбрасывания объектов, не попадающих в поле зрения камеры (frustum camera's view). Из названия понятно, что узел такого дерева имеет восемь дочерних элементов. Суть метода заключается в том, что трехмерный куб (пространство) бьется на восемь меньших равных кубов. Каждый подкуб бьется еще на восемь меньших и т.д. Таким образом получается октарное дерево, каждый узел которого имеет восемь дочерних элементов. Если перейти от трехмерного пространства к двухмерному, то может быть использовано не октарное, а квадовое дерево. То есть квадрат разбивается на четыре части (как бы половинка октарного дерева). В структуре, определяющей узел октарного дерева, достаточно поменять число 8 на 4, чтобы перейти от октарного к квадовому.

ЛИСТИНГ

определение элемента (узла) октарного дерева

template< class T >

struct OcTree

{

T elem; //Текущий элемент

OcTree * childs[8]; //Дочерние элементы

};

WWW.SGI.COM/TECH/STL/INDEX.HTML

РУКОВОДСТВО ДЛЯ ПРОГРАММИСТА ПО STL (НА АНГЛИЙСКОМ)

HTTP://RU.WIKIPEDIA.ORG/WIKI/СПИСОК_СТРУКТУР_ДАННЫХ

ЧТО ДУМАЕТ ПО ПОВОДУ СТРУКТУРЫ ДАННЫХ ВИКПЕДИЯ

WWW.ALLMATH.RU/GRAF.ZIP

ГРАФОМАНИЯ

WWW.GAMEMAKER.WEBSERVIS.RU/ARTICLES/OCTREE/OCTREE.HTM

ПОЗНАВАТЕЛЬНО ОБ OCTREE

АНАЛОГОМ СИ-МАССИВА ЯВЛЯЕТСЯ КОНТЕЙНЕР STL VECTOR

ПРАВИЛЬНЫЙ ВЫБОР КОНТЕЙНЕРА, ХРАНЯЩЕГО ТВОИ ДАННЫЕ, ГАРАНТИРУЕТ ЭФФЕКТИВНОЕ И БЕЗОПАСНОЕ ВЫПОЛНЕНИЕ КОДА

СТЕК ПОХОЖ НА ЖЕНСКИЙ ЧУЛОК, В КОТОРОМ ХРАНЯТСЯ ЛУКОВИЦЫ