4.3. Индивидуальные задания
Написать программу формирования ОПЗ и расчета полученного выражения. Разработать удобный интерфейс ввода исходных данных и вывода результатов. Работу программы проверить на конкретном примере (табл. 4.1).
Таблица 4.1
Выражение |
a |
b |
c |
d |
e |
Результат |
1. a/(b– c)*(d+e) |
8.6 |
2.4 |
5.1 |
0.3 |
7.9 |
– 26.12 |
2. (a+b)*(c– d)/e |
7.4 |
3.6 |
2.8 |
9.5 |
0.9 |
– 81.89 |
3. a– (b+c*d)/e |
3.1 |
5.4 |
0.2 |
9.6 |
7.8 |
2.16 |
4. a/b– ((c+d)*e) |
1.2 |
0.7 |
9.3 |
6.5 |
8.4 |
– 131.006 |
5. a*(b– c+d)/e |
9.7 |
8.2 |
3.6 |
4.1 |
0.5 |
168.78 |
6. (a+b)*(c– d)/e |
0.8 |
4.1 |
7.9 |
6.2 |
3.5 |
2.38 |
7. a*(b– c)/(d+e) |
1.6 |
4.9 |
5.7 |
0.8 |
2.3 |
– 0.413 |
8. a/(b*(c+d))– e |
8.5 |
0.3 |
2.4 |
7.9 |
1.6 |
1.151 |
9. (a+(b/c– d))*e |
5.6 |
7.4 |
8.9 |
3.1 |
0.2 |
0.666 |
10. a*(b+c)/(d– e) |
0.4 |
2.3 |
6.7 |
5.8 |
9.1 |
– 1.091 |
11. a– (b/c*(d+e)) |
5.6 |
3.2 |
0.9 |
1.7 |
4.8 |
– 17.51 |
12. (a– b)/(c+d)*e |
0.3 |
6.7 |
8.4 |
9.5 |
1.2 |
– 0.429 |
13. a/(b+c– d*e) |
7.6 |
4.8 |
3.5 |
9.1 |
0.2 |
1.173 |
14. a*(b– c)/(d+e) |
0.5 |
6.1 |
8.9 |
2.4 |
7.3 |
– 0.144 |
15. (a+b*c)/(d– e) |
9.1 |
0.6 |
2.4 |
3.7 |
8.5 |
– 2.196 |
16. a– b/(c*(d – e)) |
1.4 |
9.5 |
0.8 |
6.3 |
7.2 |
14.594 |
Задание №5. Нелинейные списки
Цель работы: изучить алгоритмы обработки данных с использованием нелинейных структур в виде дерева.
5.1. Краткие теоретические сведения
Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации.
Дерево состоит из элементов, называемых узлами (вершинами), которые соединены между собой направленными дугами (рис. 5.1). В случае XY вершина X называется предком (родителем), а Y – потомком (сыном, дочерью).
Дерево имеет единственный узел, не имеющий предков (ссылок на этот узел), который называется корнем. Любой другой узел имеет ровно одного предка, т.е. на каждый узел дерева имеется ровно одна ссылка. Узел, не имеющий сыновей, называется листом (например узел Y).
Внутренний узел – это узел, не являющийся ни листом, ни корнем. Порядок узла равен количеству его узлов-сыновей. Степень дерева – максимальный порядок его узлов. Высота (глубина) узла равна числу его предков плюс один. Высота дерева – это наибольшая высота его узлов.
Рис. 5.1
Бинарное дерево поиска
Наиболее часто для работы со списками используются бинарные (имеющие степень 2) деревья (рис. 5.1).
В дереве поиска ключи расположены таким образом, что значения ключа у левого сына имеет значение меньшее, чем значение предка, а правого сына – большее.
Сбалансированными, или AVL-деревьями, называются деревья, для каждого узла которых высóты его поддеревьев различаются не более чем на 1.
Дерево по своей организации является рекурсивной структурой данных, поскольку каждое его поддерево также является деревом. В связи с этим действия с такими структурами чаще всего описываются с помощью рекурсивных алгоритмов.
При работе с бинарным деревом простейшего вида, т.е. ключами которого являются целые числа (уникальные, т.е. не повторяются), необходимо использовать структуру следующего вида:
struct Tree {
int info;
Tree *left, *right;
} *root; // root указатель корня
В общем случае при работе с деревьями необходимо уметь:
– сформировать дерево (добавить новый элемент);
– обойти все элементы дерева (например, для просмотра или выполнения некоторой операции);
– выполнить поиск элемента с указанным значением в узле;
– удалить заданный элемент.
Формирование дерева поиска состоит из двух этапов: создание корня, являющегося листом, и добавление нового элемента (листа) в найденное место. Для этого используется функция формирования листа:
Tree* List(int inf) {
Tree *t = new Tree; // Захват памяти
t -> info = inf; // Формирование информационной части
t -> left = t -> right = NULL; // Формирование адресных частей
return t; // Возврат созданного указателя
}
1. Первоначально (root = NULL) создаем корень (первый лист дерева):
root = List (StrToInt(Edit1->Text));
2. Иначе (root != NULL) добавляем информацию (key) в нужное место:
void Add_List(Tree *root, int key) {
Tree *prev, *t; // prev – указатель предка нового листа
bool find = true;
t = root;
while ( t && find) {
prev = t;
if( key == t->info) {
find = false; // Ключ должен быть уникален
ShowMessage("Dublucate Key!");
}
else
if ( key < t -> info ) t = t -> left;
else t = t -> right;
}
if (find) { // Нашли нужное место
t = List(key); // Создаем новый лист
if ( key < prev -> info ) prev -> left = t;
else prev -> right = t;
}
}