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

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

µ § на µ §,

дающему в итоге

µ §.

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

1.2 Динамические информационные структуры

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

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

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

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

Значением указателя является адрес ячейки, начиная с которой будет размещена в памяти соответствующая динамическая величина.

На этой схеме р. - имя указателя; звездочкой изображено значение указателя, а стрелка отражает тот факт, что значением указателя является адрес объекта (ссылка на объект), посредством которого объект и доступен в программе.

В некоторых случаях возникает необходимость в качестве значения указателя принять «пустую» ссылку, которая не связывает с указателем никакого объекта. Такое значение в Паскале задается служебным словом nil и принадлежит любому ссылочному типу. Результаты выполнения оператора p:=nil можно изобразить следующим образом:

Процедура new(i) выполняет две функции:

1) резервирует место в памяти для размещения динамического объекта соответствующего типа с именем i;

2) указателю i присваивает адрес динамического объекта i.

Однако, узнать адрес динамической переменной с помощью процедуры writeln (i) нельзя.

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

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

Если в процессе выполнения программы некоторый динамический объект р^, созданный в результате выполнения оператора new(p), становится ненужным, то его можно уничтожить (очистить выделенное ему место в памяти) с помощью стандартной процедуры dispose(p). В результате выполнения оператора вида dispose(p) динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти становится свободным, а значение указателя р становится неопределенным (но не равным nil).

Если до вызова процедуры dispose(p) имел пустое значение nil, то это приведет к «зависанию» программы.

Если же до вызова этой процедуры указатель р не был определен, то это может привести к выходу из строя операционной системы.

Значение одного указателя можно присвоить другому указателю того же типа. Можно также указатели одинакового типа сравнивать друг с другом, используя отношения «=» или «о».

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

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

а) неопределенное заранее число элементов;

б) необходимость хранения в оперативной памяти.

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

Другая подобная структура - стек. Его моделью может служить трубка с запаянным концом, в которую вкатывают шарики. При этом реализуется принцип «последним вошел - первым вышел». Возможное количество элементов в стеке не фиксировано.

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

а) связывание последующих компонентов стека;

б) смещение ссылок при каждом движении по стеку.

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

(элементу, который пришел первым, ссылаться не на что, о чем свидетельствует «пустая ссылка» nil).

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

Type

List = ^Spisok; - Однонаправленный

Spisok = record

Info: Integer; - Информационное поле

Next: List; - Ссылка на следующий элемент

end;

ListTwo = ^SpisokTwo; - Двунаправленный

SpisokTwo = record

Info: Integer; - Информационное поле

Next: ListTwo; - Ссылка на следующий элемент

Prev: ListTwo; - Ссылка на предыдущий элемент

end;

Создание списка

procedure CreateLists; - процедура создания списка

begin

X := Random(101); Определяем значение первого элемента

Uk := nil; Указателям присваиваем nil.

q := nil;

AddToList (X, Uk); Добавляем элемент Х в список.

q := Uk; Формируем указатель на начало списка.

for i := 1 to 9 do Добавляем оставшиеся элементы в список.

begin

X := Random(101);

AddToList (X, q);

end;

ListBegin := Uk; Определяем указатель списка.

end;

Уничтожение списка

procedure DestroyList (PointerBegin: List); Процедура уничтожения списка

(PointerBegin – указатель на начало списка).

begin

while PointerBegin <> nil do Если указатель не nil, то

begin

q := PointerBegin;

PointerBegin := PointerBegin ^.Next; Ссылка на следующий.

if q <> nil then Dispose(q); Уничтожение.

end;

end;

Добавление элемента в список

procedure AddToList(X: Integer; var PointerEndList: List);

Добавить элемент в конец списка

(PointerEndList - указатель на последний элеменBЀ списка)

begin

if PointerEndList = nil then

Если первый элемент еще не существует или список пуст, то

begin

New(PointerEndList); Создаем новую переменную

PointerEndList ^.Info := X; Инф. Части присваиваем элем. Х

PointerEndList ^.Next := nil; Ссылке на следующий - nil

end

else иначе добавляем в список

begin

New(PointerEndList ^.Next); Создаем новую ссылку

PointerEndList := PointerEndList ^.Next;

Указателю присвоить ссылку на след. элемент

PointerEndList ^.Info := X;

PointerEndList ^.Next := nil;

end;

end;

Удаление элемента из списка.

procedure DeleteFromList(Position: Integer);

Удаляет элемент под номером Position

begin

q := ListBegin; Присваивается ссылка на первый элемент

if q <> nil then Если список не пуст, то

begin

if Position = 0 then Если позиция = 0, то удаляем первый элемент

begin

ListBegin := q^. Next;

if q <> nil then Dispose(q);

end

else

begin

i := 0;

while (i < Position - 1) and (q <> nil) do

Ищем элемент после которого нужно удалить

begin

q := q^. Next;

Inc(i);

end;

r := q^. Next;

if r <> nil then Если удаляемый элемент существует, то удаляем его

begin

q^. Next := r^. Next;

if r <> nil then Dispose(r);

end

end;

end

end;

Глава 2. Разработка факультативного курса «Динамические типы данных»

2.1 Методические рекомендации по введению факультативного курса в школе

В системе школьных факультативов необходимо изучение информатики с большей полнотой. Это требует в свою очередь особенно тщательного отбора материала который может быть хорошо усвоен учащимися за ограниченное количество часов.

Разработанный нами факультатив рассчитан на 14 часов.

Задачи факультатива:

1. Ввести понятие линейного списка, однонаправленного и двунаправленного списка, циклического списка, стека, дека и очереди;

2. Сформировать познавательный интерес у учащихся к информатике;

3. Развить у учащихся творческие способности.

Цель первого урока – дать учащимся на качественном уровне необходимый подготовительный материал, который включает в себя:

1. Определение линейного списка.

2. Операции со списками.

3. Виды списков.

4. Связанное распределение.

5. Динамические переменные.

На 2 – 6 уроках учащиеся знакомятся со списками более глубже. Седьмой урок итоговый. Учащимся предлагается тестовая программа, в которой они отвечают на вопросы и оценивают результаты полученных знаний. В целом же факультатив рассчитан на семь двух часовых занятий.

Общая структура факультатива такова:

Конспекты уроков

Тема: «Очередь»