Задания по программированию (М3)

Занятие 6-8. Динамическая память

  1. Напишите программу, которая генерирут два вектора в 30000-мерном пространстве и находит третий вектор - их сумму. Проследите, как меняется объем свободной динамической памяти в процессе работы программы (в начале, при выделении памяти под переменные, в конце). Запустите программу как из оболочки Турбо Паскаль, так и в виде отдельного приложения. Меняется ли количество доступной динамической памяти?

  2. Напишите программу, которая работает с линейным списком (стек или очередь). Необходимо обеспечить добавление элементов в список, его просмотр, удаление элементов.


 

Линейные списки (справочный материал)

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

Элемент линейного списка - это запись, состоящая из 2-х частей:

  1. Блок данных
  2. Указатель на следующий элемент

Графически это изображается следующим образом:

В программе элемент линейного списка можно описать, например, так: 

type  PElem = ^TElem;
      TElem = record
                data: string[20];
                next: PElem;
              end;

В данном случае роль блока данных выполняет поле data. Заметим, что при описании типа PElem мы ссылаемся на пока еще не определенный тип TElem. При описании элементов линейных списков такое предварительное описание допускается (как исключение).

Линейные списки позволяют реализовать многие динамические структуры данных. К числу основных таких структур относят стек и очередь. Рассмотрим базовые приемы работы с данными структурами.

Для работы со стеком необходимо описать тип его элементов (как это сделано выше), описать две переменные типа PElem: Top (указатель на "верх" стека) и p (служебная переменная).

Добавление элементов в стек. Выполняется в три этапа:

  1. Выделение памяти для элемента, определение значения блока данных.
  2. Присвоение указателю нового элемента текущего значения указателя на начало стека.
  3. Присвоению указателю на начало стека адреса вновь созданного элемента.

Графически эти операции можно проиллюстрировать так:

Соответствующая часть программы: 

New(p);
p^.data := 'строка данных';
p^.next := Top;
top := p;

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

Удаление элементов из стека. Также выполняется в три этапа:

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

Графически эти операции можно проиллюстрировать так:

Соответствующая часть программы: 

p := Top;
Top := Top^.next;
Dispose(p);

Чтение элемента из стека. Заключается в обращении к соответствующим полям записи top^. Например, в рассматриваемом примере верхний элемент списка вывести на экран можно так: 

WriteLn(top^.data);

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

p := Top;
while p<>NIL do begin
  WriteLn(p^.data);
  p := p^.next;
end;

Работа с очередью производится аналогичным образом. Отличие заключается в том, что необходима еще одна переменная - указатель на конец линейного списка (Bottom), необходимый для осуществления добавления элементов (их необходимо добавлять в конец очереди). Чтение, удаление и просмотр элементов - в точности, как у стека.

 

 


Сергеев А.Н. КАГИ ВГПУ. Октябрь 2003