Структуры и типы данных

Задачи главы.

• 1. Изучить понятие структуры данных.
• 2. Получить представление об основных абстрактных структурах данных: линейном списке, стеке, очереди, бинарном дереве.
• 3. Изучить понятие указателя, способы описания и использования указателей в программах на ПАСКАЛЕ.
• 4. Научиться реализовывать в программах на ПАСКАЛЕ основные динамические структуры данных.
• 5. Научиться выбирать для представления данных в программе наиболее подходящую структуру.

После изучения главы 5 бакалавр должен:

знать

• • понятие структуры данных;
• • представление об основных абстрактных структурах данных: линейном списке, стеке, очереди, бинарном дереве;

уметь

• • описывать и использовать указатели в программах на ПАСКАЛЕ;
• • реализовывать в программах на ПАСКАЛЕ основные динамические структуры данных;

владеть

• навыками выбирать для представления данных в программе наиболее подходящую структуру.

Абстрактные типы данных: стек, линейный список, двоичное дерево

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

Память под данные выделяется либо на этапе компиляции (в этом случае необходимый объем должен быть известен до начала выполнения программы), либо во время выполнения программы. Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, то память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей.

Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями. Конкретная реализация динамической структуры может варьироваться, поэтому такие структуры называются абстрактными.