13.4 Программная реализация
В основе программной реализации лежит контейнер древовидного списка (см. раздел
«Организация древовидного списка»). Перечислим константы:
-
Тип узла И
#define AND_NODE 1
Тип узла ИЛИ
#define OR_NODE 2
Описание структуры узда дерева И-ИЛИ
typedef struct //описание узла
{
int
type; //тип узла
int
var; //количество вариантов
void*
data; //данные
} KruAOTreeNode;
Описание структуру дерева И-ИЛИ
typedef
struct
//
заголовок дерева
{
NodeTreeList *root; //корень
int size; //кол-во узлов
int
var; //кол-во вариантов
} KruAOTree;
Функция инициализация структуры дерева И-ИЛИ
void
InitKruAOTree(KruAOTree *aot)
{
aot->root=NULL;
aot->size=0;
aot->var=0;
}
Функция создание узла дерева
KruAOTreeNode* CreateKruAOTreeNode(int type,void* data)
{
KruAOTreeNode *n=new KruAOTreeNode;
if(n==NULL)
return NULL;
n->var=0;
n->data=data;
n->type=type;
return
n;
}
Функция вывода узла дерева И-ИЛИ в случае, когда по указателю data хранится
строка символов
void OutputKruAOTreeNode(void *n)
{
printf("%d %d
%s\n",((KruAOTreeNode*)n)->type, ((KruAOTreeNode*)n)->var,(char*)((KruAOTreeNode*)n)->data);
//printf("%s\n",(char*)((KruAOTreeNode*)n)->data);
}
Функция удаления узла дерева И-ИЛИ в случае, когда по указателю data хранится
строка символов
void DeleteKruAOTreeNode(void *n)
{
delete
[]((KruAOTreeNode*)n)->data;
delete
(KruAOTreeNode*)n;
}
Функция создания узла дерева И-ИЛИ по описанию в name. Структура name должна
быть следующей:
<Символ типа узла><строка>
<Символ типа узла> может быть
1) A - для И-узла;
2) O - для ИЛИ-узла.
Эта функция используется при трансляции скобочной записи дерева в древовидный
список
void* CreateKruAOTreeNode(char *name)
{
KruAOTreeNode *n=new KruAOTreeNode;
if(n==NULL)
return NULL;
if(*name==’A’)
n->type=AND_NODE;
else
n->type=OR_NODE;
n->var=0;
char
*s=new char[strlen(&name[1])+1];
strcpy(s,&name[1]);
n->data=s;
return
n;
}
Функция рекурсивного подсчета вариантов в дереве И-ИЛИ
int CountVarAOTree(NodeTreeList *node)
{
KruAOTreeNode *d;
int
res;
if(node==NULL)
return 0;
d=(KruAOTreeNode*)node->data;
if(node->down!=NULL)
{
NodeTreeList *t=node->down;
if(d->type==AND_NODE)
res=1; else res=0; //установить
начальные значения для res
while(t!=NULL)//для всех сыновей
{
if(d->type==AND_NODE)
res=res*CountVarAOTree(t);//рекурсивный подсчет для узла И
else res=res+CountVarAOTree(t); //рекурсивный подсчет для узла ИЛИ
t=t->right;
}
}
else
res=1;//это лист
d->var=res; //установить значение var для данного узла
return
res;
}
Функция обхода узлов варианта с заданным номером, node - корень дерева, number
номер варианта, func - указатель на функцию обработки узла. Функция работает по
алгоритму перечисления вариантов дерева И-ИЛИ
void ForEachVarAOTree(NodeTreeList *node, int number, void
(*func)(void*))
{
KruAOTreeNode *d;
int
res;
if(node==NULL)
return;
d=(KruAOTreeNode*)node->data;
if(func!=NULL)
func(d); //вызов функции
if(node->down!=NULL)
{
NodeTreeList *t=node->down;
if(d->type==AND_NODE)
res=1; else res=0;
while(t!=NULL)
{
KruAOTreeNode
*td=(KruAOTreeNode*)t->data;
if(d->type==AND_NODE)//для всех И-узлов
{
ForEachVarAOTree(t,number%td->var,func);
number/=td->var;
}
else
//для одного ИЛИ-узла
{
if(number<td->var)
{
ForEachVarAOTree(t,number,func);
break;
}
number-=td->var;
}
t=t->right;
}
}
}
Функция обхода узлов и обработки листьев варианта с заданным номером, node -
корень дерева, number-номер варианта, func - указатель на функцию обработки
листа. Функция работает по алгоритму перечисления вариантов дерева И-ИЛИ.
void ForEachVarAOTreeLeaf(NodeTreeList *node, int number, void
(*func)(void*))
{
KruAOTreeNode *d;
int
res;
if(node==NULL)
return;
d=(KruAOTreeNode*)node->data;
if(node->down==NULL)//это лист
{
if(func!=NULL)
func(d);//вызов функции
}
else
{
NodeTreeList *t=node->down;
if(d->type==AND_NODE)
res=1; else res=0;
while(t!=NULL)
{
KruAOTreeNode
*td=(KruAOTreeNode*)t->data;
if(d->type==AND_NODE)//для всех И-узлов
{
ForEachVarAOTree(t,number%td->var,func);
number/=td->var;
}
else
//для одного ИЛИ-узла
{
if(number<td->var)
{
ForEachVarAOTreeLeaf(t,number,func);
break;
}
number-=td->var;
}
t=t->right;
}
}
}
Тестовая функция для показа организации и работы с деревьями И-ИЛИ
void TestKruAOTree()
{
//
конструирование дерева
TranslateStateTreeList tsv; //создаем структуру
InitTranslateStateTreeList(&tsv,20,CreateKruAOTreeNode);
//инициализируем
//трансляция
описание дерева И-ИЛИ
//
в древовидный список
NodeTreeList
*ao_tree=TranslateAscizToTreeList(&tsv,
"A1._node-1
(O1.1_node-2(
A1.1.1_node-4,
O1.1.2._node_5(
A1.1.2.1_node-9,
O1.1.2.2._node_10),
A1.1.3_node-6),
O1.2_node-3(
A1.2.1_node-7,
A1.2.2_node-8)");
//подсчет
количества вариантов
int
nvar=CountVarAOTree(ao_tree);
printf("++++ var
=%d\n",nvar);
//левосторонний
обход дерева И-ИЛИ печать узлов
ForEachTreeListLeftNode(ao_tree,OutputKruAOTreeNode);
printf("+++++++++++++++++\n");
//левосторонний
обход дерева И-ИЛИ печать листьев
ForEachTreeListLeftLeaf(ao_tree,OutputKruAOTreeNode);
//перечисление
вариантов в дереве и печать
for(int num=0; num<nvar; num++)
{
ForEachVarAOTree(ao_tree,num,OutputKruAOTreeNode);
printf("________%d\n",num);
}
//очищение
динамической памяти
DeleteTranslateStateTreeList(&tsv);
DeleteSubTreeList(ao_tree,DeleteKruAOTreeNode);
while(!kbhit());
}
Листинг работы тестовой программы
++++ var =8
1 8 1._node-1
2 4 1.1_node-2
1 1 1.1.1_node-4
2 2 1.1.2._node_5
1 1 1.1.2.1_node-9
2 1 1.1.2.2._node_10
1 1 1.1.3_node-6
2 2 1.2_node-3
1 1 1.2.1_node-7
1 1 1.2.2_node-8
+++++++++++++++++
1 1 1.1.1_node-4
1 1 1.1.2.1_node-9
2 1 1.1.2.2._node_10
1 1 1.1.3_node-6
1 1 1.2.1_node-7
1 1 1.2.2_node-8
1 8 1._node-1
2 4 1.1_node-2
1 1 1.1.1_node-4
2 2 1.2_node-3
1 1 1.2.1_node-7
169
________0
1 8 1._node-1
2 4 1.1_node-2
2 2 1.1.2._node_5
1 1 1.1.2.1_node-9
2 2 1.2_node-3
1 1 1.2.1_node-7
________1
1 8 1._node-1
2 4 1.1_node-2
2 2 1.1.2._node_5
2 1 1.1.2.2._node_10
2 2 1.2_node-3
1 1 1.2.1_node-7
________2
1 8 1._node-1
2 4 1.1_node-2
1 1 1.1.3_node-6
2 2 1.2_node-3
1 1 1.2.1_node-7
________3
1 8 1._node-1
2 4 1.1_node-2
1 1 1.1.1_node-4
2 2 1.2_node-3
1 1 1.2.2_node-8
________4
1 8 1._node-1
2 4 1.1_node-2
2 2 1.1.2._node_5
1 1 1.1.2.1_node-9
2 2 1.2_node-3
1 1 1.2.2_node-8
________5
1 8 1._node-1
2 4 1.1_node-2
2 2 1.1.2._node_5
2 1 1.1.2.2._node_10
2 2 1.2_node-3
1 1 1.2.2_node-8
________6
1 8 1._node-1
2 4 1.1_node-2
1 1 1.1.3_node-6
2 2 1.2_node-3
1 1 1.2.2_node-8
_______7
|