Структуры хранения данных и знаний.

Одной из важнейших структур, с помощью которых представляются и хранятся в оперативной памяти компьютера анализируемые в лингвистическом процессоре данные, является дерево. Дерево – это структура данных, представляющая из себя граф, у которого одна из вершин определена как корневая.

На языке C дерево может быть представлено в виде следующих структур

struct Node // Структура для описания вершины
{
char* name; // Имя вершины (или др. информация)
……………….
Arc* parent; // Указатель на дугу, идущую от родительской вершины
Arc** children; // Указатель на массив исходящих дуг
int nNumOfChildren; // Число исходящих дуг
}

struct Arc // Структура для хранения дуги
{
char* name; // Имя дуги (или др.информация)
………………..
Node* Prev; // Указатель на вершину-родитель
Node* Next; // Указатель на дочернюю вершину
}

struct Tree // Структура для описания дерева
{
Node* root; // Указатель на корневую вершину дерева
}

Очень удобной для хранения и зачастую удобной для обработки формой хранения дерева является линейная скобочная запись или, что то же самое, запись дерева в виде фреймов (от английского frame – рамка). Линейная скобочная запись строится на основе того или иного обхода вершин дерева. Рекурсивная процедура обхода нашего дерева может иметь вид:

void tree_order (Node* nd)
{
for (int i=0; i
{
Node* cur_node =nd->children[i];
tree_order(cur_node);
}
}

Рассмотрим скобочную линейную структуру для следующего дерева:

Линейная скобочная структура должна иметь вид:

R0(A)(R1(B)(R4(E)R5(F))R2(C)R3(D)(R6(G)))

Таким образом, алгоритм будет таким:

// Строка для результирующей линейной скобочной структуры, размер 10000
// взят для примера.

char* out_str=(char*)malloc(10000*sizeof(char));
strcpy(out_str,””);

// вызов процедуры
// Tree tr1; - входящее дерево

tree_order(out_str, tr1.root);

// сама процедура:
void tree_order (char* str1, Node* nd)
{
strcat(nd->parent.name);
strcat(str1,”(“);
strcat(nd.name);
strcat(str1,”)“);
if(nNumOfChildren>0)
strcat(str1,”(“);

for (int i=0; i
{
Node* cur_node =nd->children[i];

tree_order(str1, cur_node);
}

if(nNumOfChildren>0)
strcat(str1,”)“);

}

Дата добавления: 2015-07-15