Однонаправленный связный список. Основные операции Ответ: Односвязный список однонаправленный связный список



Дата20.05.2022
өлшемі14.63 Kb.
#458129
түріУказатель
миапр


Структуры данных:
[ ] Однонаправленный связный список. Основные операции
Ответ:
Односвязный список (однонаправленный связный список)
Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL.
1. Односвязный линейный список (ОЛС).
Каждый узел ОЛС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
2. Односвязный циклический список (ОЦС).
Каждый узел ОЦС содержит 1 поле указателя на следующий узел. Поле указателя последнего узла содержит адрес первого узла (корня списка).
[ ] Двунаправленный связный список. Основные операции
Ответ:
Двусвязный линейный список (ДЛС).
Каждый узел ДЛС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит нулевое значение (указывает на NULL). Поле указателя на предыдущий узел первого узла (корня списка) также содержит нулевое значение (указывает на NULL).
Двусвязный циклический список (ДЦС).
Каждый узел ДЦС содержит два поля указателей: на следующий и на предыдущий узел. Поле указателя на следующий узел последнего узла содержит адрес первого узла (корня списка). Поле указателя на предыдущий узел первого узла (корня списка) содержит адрес последнего узла.
Операции
создание списка;
печать (просмотр) списка;
вставка элемента в список;
удаление элемента из списка;
поиск элемента в списке;
проверка пустоты списка;
удаление списка.
[ ] Кольцо. Основные операции
[ ] Очередь (FIFO). Основные операции
Ответ
Машинное представление очереди FIFO и реализация операций При представлении очереди вектором в статической памяти в дополнение к обычным для дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в очереди). При включении элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу. При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель уменьшается на единицу
[ ] Стек (LIFO). Основные операции
Ответ
Стек — динамическая линейная структура данных, хранящая последовательность элементов, в которой размещение новых и удаление существующих происходит с одного конца, называемого вершиной стека (top).

[ ] Хэш-таблица. Структура и основные операции


Ответ
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.


[ ] Деревья. Бинарное дерево поиска. Основные операции

[ ] Деревья. Обход дерева в ширину


[ ] Деревья. Обход дерева в глубину
[ ] Графы. Основные понятия графов. Списки смежности
[ ] Графы. Типы графов. Матрицы смежности
Методы принятия решений:
[ ] Признаки объектов, пространство признаков. Классы, свойства классов. Решающее правило и решающая функция.
[ ] Линейная регрессия
[ ] Алгоритм к-средних

Достарыңызбен бөлісу:




©www.dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет