45. Понятие структуры данных. Состав элемента структуры.

СТРУКТУРА ДАННЫХ - совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.

В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.

СТАТИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность фиксированного количества переменных постоянной размерности с неизменным характером связей между ними И наоборот, если один из параметров структуры данных -количество переменных, их размерность или взаимосвязи между ними меняются во время работы программы, то такие структуры данных называются динамическими.

ДИНАМИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время работы программ.

46. Структуры данных: стек, очередь, список.

Стек. Имеет операции вставки и извлечения, параметры глубины и максимального размера. Обычно в памяти структура данных сама хранит указатель HEAD, чаще всего указывающий на элемент, который должен быть вставлен в последствии. Описание операций вставки и извлечения. LIFO. Две разных реализации стека — статическая и динамическая. В первом случае через массив, который мы создаем заблаговременно и работаем по нему посредством указателей. Второй случай — каждый элемент структуры данных хранит рядом с собой указатели на соседние элементы. Певый случай быстр, не требует дополнительной памяти на указатели, но съедает заданное число памяти согласно первой инициализации и имеет ограничение на размер, в то время как динамическая реализация ограничена только всей оперативной памятью.

Примеры стеков — ханойская башня (3 стека). Стек может быть использован в ряде других, не так очевидных задач, — организация сохранения данных в памяти при работе подпрограмм; пример рекурсивного разбора выражений.

Очередь. Аналогично — есть HEAD и TAIL, можно вставлять в один хвост, а извлекать только из другого. FIFO. Аналогично реализуется статически и динамически.

Списки. Как двусторонние стеки или двусторонние очереди. С каждым из хвостов можно делать операции извлечения и вставки.

Двусторонне-связанные списки. Картинка динамической реализации. Аналогично односторонне-связанные. Преимущества и недостатки.

Упорядоченные списки — делают определенные действия, чтобы сохранять упорядоченность на каждом выполнении операции.