Необхідність структурування даних. Послідовне і зв ' язне розподілення даних в пам ' яті ЕОМ. Статичні і динамічні структуры даних.

Проектирование структур данных Проектирование структур данных – разработка представления абстрактных структур данных в памяти ЭВМ. Основные учитываемые факторы: размерность структуры данных и степень ее «динамичности»; вид хранимой информации каждого элемента данных; связи элементов данных; время хранения данных структуры («время жизни»); набор операций над элементами данных и структурами в целом. Принципиальные решения, принимаемые в процессе проектирования: Использование внутренней или внешней памяти. Способ распределения памяти. Способ выделения памяти.

Использование внутренней или внешней памяти Недостатки внешней памяти: большая трудоемкость операции доступа к блоку данных; простой метод последовательного доступа неэффективен для решения задачи поиска элемента данных. для постоянного хранения данных; для обработки данных только в случае невозможности или потенциальной опасности размещения большого объема данных во внутренней памяти. Внешняя память используется:

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

Способы распределения памяти Последовательное распределение памяти

Способы распределения памяти Связное распределение – организация логической последовательности элементов данных посредством указателей. Достоинства: отсутствие ограничений на размер структуры данных и простота его изменения; простота представления динамически меняющихся структур данных. простота представления нелинейных структур данных. Недостатки: доступ к элементам строго последовательный; дополнительные затраты памяти на указатели; большая сложность реализации и отладки программ Элемент структуры данных в общем виде состоит из двух полей: информационного поля (поля данных) и поля указателей.

Способы распределения памяти Связное распределение памяти Удаление узла y 4 и его смена y 5, а также вставка узла y 2А

Способ выделения памяти Статическое выделение – при заранее предсказуемом размере данных и «времени жизни», сравнимом с временем выполнения программы (подпрограммы для локальных данных). Динамическое выделение – при незначительном «времени жизни» или при значительном и непредсказуемом количестве операций включения/исключения элементов данных. К этой группе относят: массивы, матрицы, множества, строки, записи. К этой группе относят: линейные и разветвленные связные списки, графы, деревья, стеки, очереди.