Тема «Ссылочный тип и динамические структуры данных»

Данная тема содержит материал повышенной трудности. Если учащиеся недостаточно подготовлены и не усвоили предшествующие темы, то изучать данную тему нецелесообразно.

В начале обсуждения напомните учащимся различия между статическими и динамическими структурами данных. Далеко не всегда размер структуры очевиден заранее. Приведите примеры, связанные с самой простой из структур данных — массивом.

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

2. При моделировании очереди, в которую приходят и из которой уходят покупатели, попытка использовать массив для записи, например, номера находящегося в очереди покупателя (и с исключением этого номера, когда соответствующий покупатель ушел) и попытка организовать массив также наталкивается на трудности: неопределенная длина этого массива и проблема исключения информации из него. Что значит «исключить»? — первое предложение учащихся обычно таково: заменить нулем, но это не значит исключить.

Манера описывать в таких случаях упорядоченную однородную линейную структуру данных как массив «с запасом» не соответствует логике таких задач, и в ряде случаев при разработке профессиональных программ вступает в противоречие с ограничениями, налагаемыми Паскалем на максимальный объем памяти, отводимый компилятором под массивы (64 Кбайт).

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

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

К этому времени учащиеся уже изучали файлы, которые на самом деле являются динамическими объектами. Однако на практике файлы данных хранятся на внешнем носителе, что накладывает отпечаток на их использование в программах. Для размещения же динамических объектов в ОЗУ используются переменные особого (ссылочного) типа — указатели.

Далее объясните, что такое указатель, какие значения он может принимать и как ссылочный тип технически определяется в программе. Поясните операции сравнения, которые можно проводить над ссылками, и в чем состоит их смысл, введите операции «взятие указателя» и «разыменование».

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

Тут же обсудите проблему ограниченности памяти в «куче», неспособность Турбо Паскаля отследить исчерпание памяти (без специальных усилий программиста) и использование в этих целях специальных средств (функций Maxavail и SizeOf), а также процедуру «очистки мусора» (Dispose).

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

Итак, на простых примерах «из жизни» можно показать полезность следующих динамических структур:

• стек (учащиеся скорее всего с этим понятием знакомы из базового курса информатики);

• линейный список с произвольным доступом (например, список учащихся класса, который может обновляться путем удаления фамилии одного учащегося с последующим смыканием списка, или, наоборот, в который можно вставить фамилию нового ученика на нужное место по алфавиту с раздвижением списка);

• очередь, в которой удаление происходит только через голову списка, а вставка — только через хвост.

Облегчают понимание условные графические изображения структур (рис. 15.8).

Рис. 15.8. Иллюстрация стека и очереди

Методика программирования списков включает ряд задач: связывание компонент, смещение ссылок и т.д. Элементы таких структур методически удобнее всего представлять в виде двухкомпонентных записей. В каждой записи одно из полей — содержательное, второе — для хранения ссылки на другой компонент. Обратите внимание учащихся, что при традиционном хранении элементов в регулярной структуре (массиве) этого не требуется, поскольку каждый элемент «знает», между какими он стоит.

Рассмотрите возможную методику объяснения создания стека. Итак, задача — создать цепочку связанных динамических переменных — целых, например:

Программа может включать две процедуры: добавление очередного элемента в стек и извлечение последнего добавленного элемента (вспомним принцип организации стека: «первым пришел — последним ушел»). Целесообразно, чтобы при каждом действии программа выводила на экран текущее состояние стека. Задание это является достаточно сложным, хотя программы получаются весьма лаконичными.

Заданиями для самостоятельного выполнения могут быть различные варианты программирования нелинейных структур. Простейшая из них — двоичное дерево, схематически изображенное на рис. 15.9, а.

Для ее реализации средствами Паскаля каждый элемент приходится представлять записью с тремя полями: одно — содержание, два — ссылки, рис. 15.9, б. Таким же способом можно реализовать структуру типа «направленный граф» и некоторые другие.

Рис. 15.9. Структура типа «двоичное дерево»

Требования к знаниям и умениям

Учащихся

Тема «Алгоритмы.

Не нашли, что искали? Воспользуйтесь поиском по сайту: