This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
courses:programming:extra_tasks [2017/03/23 09:39] pro100kot |
courses:programming:extra_tasks [2017/04/07 09:47] pro100kot |
||
---|---|---|---|
Line 61: | Line 61: | ||
**Идея:** | **Идея:** | ||
- | Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их когорого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать [[https://en.wikipedia.org/wiki/Linked_list|тут]]. Либо в какой-нибудь книге по структурам данных. | + | Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их которого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать [[https://en.wikipedia.org/wiki/Linked_list|тут]]. Либо в какой-нибудь книге по структурам данных. |
**Реализация** | **Реализация** | ||
Line 83: | Line 83: | ||
* Подумать как можно реализовать удаление n-го элемента списка. (int remove(struct node *root, int n);) | * Подумать как можно реализовать удаление n-го элемента списка. (int remove(struct node *root, int n);) | ||
+ | **Бинарное дерево поиска** | ||
+ | Подробнее, например, [[https://en.wikipedia.org/wiki/Binary_search_tree|тут]] | ||
+ | <code c treeNode.h> | ||
+ | struct node | ||
+ | { | ||
+ | int data; //полезные данные | ||
+ | struct node *left; //указатель на левого потомка | ||
+ | struct node *right; //указатель на правого потомка | ||
+ | }; | ||
+ | </code> | ||
+ | |||
+ | |||
+ | |||
+ | **Функции: ** | ||
+ | |||
+ | Реализуйте следующие функции: | ||
+ | * Вставка элемента в дерево | ||
+ | * Поиск элемента в дереве | ||
+ | * Определение высоты дерева | ||
+ | * Вывод элементов дерева в порядке их возрастания (ЛКП обход дерева) | ||
+ | * Вывод элементов дерева с отображением структуры. Например: <code>((5)10(15))20((25)30(35))</code> | ||
+ | * Удаление всех элементов дерева | ||
+ | * Удаление заданного элемента - рекомендую подумать и попробовать реализовать самостоятельно | ||
+ | |||
+ | Для удобства, рекомендуется использовать отдельную функцию для создания узла: | ||
+ | <code c createNode.h> | ||
+ | struct node* createNode(int n, struct node *left, struct node *right) | ||
+ | { | ||
+ | struct node *cur = malloc(sizeof(struct node)); | ||
+ | cur->left = left; | ||
+ | cur->right = right; | ||
+ | cur->data = n; | ||
+ | return cur; | ||
+ | } | ||
+ | </code> | ||