- 1 курс
- 2 курс
- 3 курс
- 4 курс
- 5 курс
- 6 курс
Old
Old
This is an old revision of the document!
Задачи на массивы (в задачах следует полагать, что на вход программе сначала подается количество элементов N, а после - N чисел. Массив создавать динамически.)
Строки:
Линейный односвязный список
Структуры: Способ представления данных инкапсулирующий в себя данные различных типов. Кратко можно почитать тут либо в какой-нибудь книге в духе “Руководство для начинающих (Шилдт)”. Важно понимать, что данные-поля структуры в памяти представляются подряд, в порядке их объявления.
Идея: Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их которого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать тут. Либо в какой-нибудь книге по структурам данных.
Реализация Каждый узел линейного односвязного списка хранит в себе данные (которые подразумеваются под фразой “хранится в списке”) и указатель на следующий элемент списка. Таким образом, узел списка может иметь вид:
struct node { int data; //полезные данные struct node *next; //указатель на следующий элемент };
Из этого следует то, что для всех операций со списком (в том числе и хранения его) достаточно знать только указатель на его первый элемент.
Функции: вам предлагается реализовать список и следующий набор функций (не обязательно все) для работы со списком (в списке хранятся целые числа). Не забывайте, что качество превыше количества, поэтому если сложно, то реализовать сколько сможете. Функции приведены в порядке возрастания сложности. В этом же порядке и реализовывать :
Бинарное дерево поиска
Подробнее, например, тут
struct node { int data; //полезные данные struct node *left; //указатель на левого потомка struct node *right; //указатель на правого потомка };
Функции:
Реализуйте следующие функции:
((5)10(15))20((25)30(35))
Для удобства, рекомендуется использовать отдельную функцию для создания узла:
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; }