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

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

программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается (элемент «разрушается»).

Поскольку элементы динамической структуры

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

динамической структуры устанавливается через указатели, содержащие адреса элементов в памяти. Такое представление данных в памяти называется связным.

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

поля для связи с другими элементами, видимые только для программиста — разработчика ПО.

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

• размер структуры ограничивается только объемом памяти компьютера;

• при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей.

С другой стороны, такие структуры обладают рядом недостатков:

• работа с указателями требует высокой квалификации программиста;

• на указатели расходуется дополнительная память;

• дополнительный расход времени на доступ к элементам связной структуры. Связные линейные списки

Линейные связные списки являются простейшими динамическими структурами данных. Они являются упорядоченными множествами, содержащими переменное число элементов, на

которые не накладываются ограничения по длине.

На рис. 3.10 приведена структура односвязного списка. Здесь поле INF — информационное поле, содержащее данные, NEXT — указатель на следующий элемент списка. Голова списка — указатель на начало списка. Указатель на следующий элемент последнего элемента списка содержит значение nil, это является признаком последнего элемента.

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

которого содержит два указателя: на следующий и предыдущий элементы. Структура линейного двусвязного списка приведена на рис. 3.11, где поле NEXT — указатель на следующий элемент, поле PREV — указатель на предыдущий элемент. Первый и последний элементы такого списка содержат nil в указателе на предыдущий и последующий элементы соответственно.

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

Урок 20.

Предмет: Технология разработки программных продуктов.

Тема :Модульное программирование.

Цели:

Образовательная

Ознакомление с модульным программированием.

Развивающая:

Развивать умение слушать других, делать выводы и обобщать полученные знания

Воспитательная:

Воспитывать чувство значимости предмета в профессиональной деятельности, аккуратности в работе

Межпредметные связи:

- Английский язык

- Операционные системы

- Информационные технологии

- Основы алгоритмизации и программирования

Оборудование: доска, мел, письменные принадлежности, проектор, ПК

Тип урока: комбинированный

Метод обучения: Объяснительно иллюстративный

Ход урока:

1.Организационный момент

- Проверка готовности кабинета

- Объявление темы

2. Постановка цели урока

3.Повторение пройденного материала

Структуры данных.

Классификация структур данных

Простые структуры данных

Статические структуры данных

Динамические структуры данных

Полустатические структуры данных

4.Сообщение новых знаний

Понятие модуля

Основные характеристики программного модуля

Модульная структура программных продуктов

5. Восприятие и осознание учащимися нового материала

6. Осмысление обобщение и систематизация знаний

7. Подведение итогов урока и постановка домашнего задания

Выучить содержимое темы

Гагарина Л.Г. стр. С.94-101

Ответить на вопросы: