14. Принцип работы со стеком на примере вычисления строки с формулой.
15. двусвязным списком называется список , если каждый элемент имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).
16.Иерархические списки и их свойства.- это несколько подсписков ранжированных по уровням так, что элементы подсписка уровня 0 являются головным элементом для подсписков уровня 1, и так далее. Элементы списка имеют компоненты головного элемента подсписка нижележащего. При реализации нужно учитывать: 1.кол-во уровней 2.кол-во разных типов подсписков, расположенных на одном уровне. Кол-во уровней велико и на каждом уровне могут располагаться несколько типов подсписков.
17. Ассоциативные списки и их свойства. список,который позволяет избежать избыточного дублирования данных
18. АТД «Дерево»: основные понятия.- совокупность элементов или узлов между которыми установлены иерархические отношения типа «отец – сын». Каждый элемент может иметь несколько потомков и только одного предка (кроме корня дерева – нет предка).У корня нет истинного предка, но может быть множество узлов не имеющих истинных потомков.Каждый элемент и потомок, и предок для самого себя. Узел – дерево. Дерево без узлов – пустое нулевое дерево. Лист – узел не имеющий истинных потомков. Длина пути – число на 1 меньше кол-ва узлов в пути. Высота дерева – высота корня. Высота узла – длина самого длинного пути из этого узла до какого-либо листа дерева. Глубина узла – длина от корня до этого узла. Неупорядоченное дерево – дерево в котором произвольный порядок следования потомков узлов. Упорядоченное дерево – дерево с определенным порядком следования потомков одного узла.Каждый узел можно сопоставлять с значением – метка узла.Поддерево – любой элемент в дереве со всеми своими потомками.
19.Двоичное дерево поиска — упорядоченное ориентированное дерево, у которого любой узел имеет не более двух прямых потомков,наз левым и правым сыном. Свойства: 1)у каждого узла может быть два потока 2) для меток узлов определенно отношение больше меньше 3) метки всех узлов уникальны 4) метка любого узла больше любого потока из левого поддерева, но меньше потока из правого
20. Деревья двоичного поиска. Описать алгоритм написать пример функции добавления узла в дерево. если дерево пустое,то создаем узел,и возвращаем его в качестве корня дерева. Для вставки узла в неупорядоченное дерево, неоходимо явно указать какой узел будет прямым предком для нового узла
TREENODE* insertNode(TREENODE* tree, int value)
{TREENODE* newNode=(TREENODE*)malloc(sizeof(TREENODE));
TREENODE* root=tree;
if(newNode!=NULL)
{newNode->data=value;newNode->left=NULL;newNode->right=NULL;}
Else puts("Error!");
if(root==NULL) return newNode;
while(root!=NULL){
if(value<root->data)
{if(root->left!=NULL) root=root->left;
else{root->left=newNode;break;}
}else if(value>root->data){if(root->right!=NULL)
root=root->right;else{root->right=newNode;break;}}
else{puts("Clone");break;}}return tree;}
21. Деревья двоичного поиска. Описать алгоритм и написать пример функции обхода узлов дерева. Существует три способа обхода 1.Симметричный (левый сын, корень, правый сын - ЛКП)
void inOrder(TREENODE* tree)
{
if(tree!=NULL)
{
inOrder(tree->left);
printf("%3d ",tree->data);
inOrder(tree->right);
}
}
2.Прямой (корень, левый сын, правый сын - КЛП)
void preOrder(TREENODE* tree)
{
if(tree!=NULL)
{
printf("%3d ",tree->data);
preOrder(tree->left);
preOrder(tree->right);
}
}
3.Обратный (левый сын, правый сын, корень - КПЛ)
void postOrder(TREENODE* tree)
{
if(tree!=NULL)
{
postOrder(tree->left);
postOrder(tree->right);
printf("%3d ",tree->data);
}
}
22. Деревья двоичного поиска. Описать алгоритм и написать пример функции поиска узла по его метке. Алгоритм поиска узла в ДДП строится на последовательном сравнении искомой метки с метками узлов, начиная с корня. Если искомая метка меньше, чем метка корня, то сравнение выполняется в таком же порядке с метками узлов его левого поддерева, если больше, то - с метками узлов его правого поддерева. Сравнение выполняется до тех пор, пока метка очередного узла не совпадет с искомой меткой или при необходимости перехода к левому или правому сыну соответствующая ссылка окажется равной NULL, что означает, что в дереве нет узла с указанной меткой.