yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Основы программирования

11. СПИСКИ

1. Понятия о динамической памяти, указателях и динамических переменных. Различают обычную (статическую) и динамическую организации памяти компьютера. В оперативной памяти компьютера можно разместить ограниченное количество данных, в частности, переменных. Для переменных, объявленных в разделе var, система резервирует определенный объем памяти, даже если не все они будут использованы в программе. Память, предоставленная переменным, освобождается лишь после выполнения программы. Однако, на практике встречаются задачи, где заранее неизвестно сколько переменных нужно для их решения, и, следовательно, какой объем памяти следует зарезервировать. В этом случае, а также, если заранее известно, что данных будет много, применяют динамическую организацию памяти. Принцип динамической организации памяти заключается в том, что переменные занимают память по необходимости, обрабатываются и в нужный момент освобождают память. Такие переменные называются динамическими.

Для работы с динамическими переменными используют тип данных - указатель. Если имя статической переменной задает адрес данного в оперативной памяти, то указатель на динамическую переменную указывает лишь тип данного, а не его расположение в памяти. Тип данных указатель описывают с помощью символа ^ в разделе type так:

type <название типа> = ^<базовый тип>;

Конкретные указатели на динамические переменные объявляют в разделе var:

var <список указателей на переменные> : <имя типа>;

Пример. Рассмотрим описания типов указателей и объявление указателей на динамические переменные:

type

UkazNaCelye = ^integer;

UkazNaMassyv = ^array [1..100] of real;

UkazNaZapys = ^Zapys;

var

cl, c2 : UkazNaCelye;

masl, mas2 : UkazNaMassyv;

zapl, zap2 : UkazNaZapys;

На этапе компиляции память для массивов и записей здесь не резервируется, но сам указатель будет занимать в памяти 4 байта. Память для данных, о возможности появления которых предупреждает указатель, будет предоставлена на этапе выполнения программы с помощью процедуры new:

new(<yкaзaтeль на переменную>);

Только теперь образовалась динамическая переменная,- имя ко­торой имеет такой вид:

<указатель на переменную>^

Различают операции над указателем на динамическую переменную и операции над самой динамической переменной.

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

Над указателями определены две операции переадресации

<указатель 1> := <указатель 2>;

<указатель> := nil;

а также процедуры new и dispose.

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

В результате выполнения второй команды переадресации указатель становится свободным — nil. Он не будет указывать ни на какое конкретное данное.

После обработки динамической переменной память можно освободить с помощью процедуры

dispose (<указатель на динамическую переменную>) .

Пример.  Рассмотрим программу Ukazateli и ее графическую иллюстрацию на рис. 1.

program Ukazateli;

var  cl, c2 : ^Integer; {Объявляем два указателя}

begin

new(c1);                     {Резервируем память для целого числа}

new(c2);                     {Резервируем память для целого числа}

c1^:=5;                       {Переменной c1^ присваиваем значение 5}

c2^:=7;                       {Переменной с2^ присваиваем значение 7} ,

writeln(c1^,c2^);                    {Выводим 5 и 7}

c1:=c2                                               {Переадресация}

writeln(c1^,c2^);                    (Выводим 7 и 7}

c2:=nil;                                  {Указатель с2 зануливаем}

{Память, предоставленную для с2, освобождаем}

dispose(c2)

writeln(cl^)                             {Выводим 7}

end.

Справка. С помощью динамических переменных можно решить задачу поочередной обработки одной программой некоторого количества больших массивов (если все массивы ввести в память одновременно невозможно). Задачу решают так. Объявляют нужное количество указателей на массивы, например, var masl, mas2,... : ^array... Создают массив new(masl) и обрабатывают динамические переменные masl^[l], masl^[2], ..., masl^[i], ... Освобождают память: dispose(masl). Создают и обрабатывают элементы второго массива mas2^[i] и т.д.

2. Понятие о списке. Рассмотрим структуру данных - однонаправленный список.

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

type                <имя элемента списка> = ^<запись>;

<запись> = record

                                        <поле данного 1> : <тип данного 1>;

                                     <поле данного n>:<тип данного n>;

                                                <поле указателя> <имя элемента списка>

end;

Пример. Рассмотрим файл, в котором находятся данные о реках и назовем его reki.pas (см. задачу из п. 10). Тип записи о реке назовем reka и поставим ему в соответствие элемент списка такого типа:

type

elspyska =^reka;

reka = record

imia : string[ll];

dl : integer;

pi : longint;

sled : elspyska;

end;

var element, pervyj, predyd, novyj : elspyska;

Здесь element — указатель на текущий элемент списка, element^- динамическая переменная типа запись, element^.dl — динамическая переменная типа integer, которая получает значения длины реки, a element^.sled - указатель на следующий элемент списка. Отсюда вытекает, что element^, sled^, dl — это длина следующей реки, a element^.sled^.sled - указатель на далее следующую реку и т.д.

Задача 1. На диске имеется файл данных. К нему необходимо добавить еще одно данное. На базе старого файла создать новый файл с этим данным в начале.

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

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

Программа SpisokRek решает поставленную задачу и демонстрирует основные приемы обработки списка. Элементы списка обрабатывают друг за другом с помощью цикла. Сначала с помощью цикла создают список и вводят в него данные из файла. Специфика цикла в этой программе такая: после его завершения будет создан лишний (последний) элемент. Его следует ликвидировать, заранее объявив еще один указатель (на предыдущий элемент списка) и приняв predyd^.sled := nil. Существенное преимущество списков состоит именно в том, что удалить зафиксированный, то есть выбранный в соответствии с условием некоторой задачи, элемент можно с помощью одной команды переадресации вида

Predyd^.sled := zafix^.sled.

Выводим список на экран. Создаем новый элемент списка и вводим в его поля данные, например, так:

Днепр (делаем пять пропусков и нажимаем клавишу ввода),

2201 (нажимаем клавишу ввода),

504000 (нажимаем клавишу ввода).

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

novyj^.sled := zafix^.sled;

zafix^.sled := novyj;

Найдите в программе место, где новый элемент записывается в список перед первым. Таким образом вносят изменения в список, снова пересматривают его на экране и выводят в файл reki2.pas. Убедитесь, что файл создан правильно. Не выходя из среды, средствами меню File и Open откройте файл reki2.pas и просмотрите его.

Рассмотрите программу SpisokRek. Выполните программу и поэкспериментируйте с ней.

program SpisokRek;

uses Crt;

type

elspyska = ^reka;

reka = record

imia : string[ll];

dl : integer;

pi : longint;

sled : elspyska;

end;

var

element, pervyj, predyd, novyj : elspyska;

Myfile, Myfile2 : text;

procedure SozdatSpysok(var Myfile : text);

begin

new(element);

pervyj := element;

while not eof(Myfile) do

begin

predyd := element;

with element^ do

readln (Myfile, imia, dl, pi);

new(element^. sled);

element := element^.sled

end;

{Удаляем последний лишний элемент}

predyd ^.sled := nil;

end;

procedure VyvestyNaEkran;

begin

writeln('Создан такой список:');

writeln;

element := pervyj;

while element <> nil do

begin

with element^ do

writeln(imia:ll, dl:8, pi: 12);

element := element^.sled

end;

end;

procedure SozdatNovyjElement;

begin

new(novyj);

writeln;

writeln ('Создаем новый элемент');

with novyj^ do

begin

write('Bведитe название — 11 символов: ');

readln(imia);

write('Введите длину реки: ');

readln(dl);

write('Введите площадь бассейна: ');

readln(pl)

end;

writeln

end;

procedure VyvestyvFile (var Myfile : text);

begin

element := pervyj;

while element <> nil do

begin

with element^ do

writeln(Myfile, imia:ll, dl:8, pl:12);

element := element^.sled

end;

writeln;

writeln ('Список занесен в файл. Конец работы')

end;

begin                          {Основная программа}

clrscr;

assign(Myfile, 'reki.pas');

assign(Myfile2, 'reki2.pas');

reset(Myfile);

SozdatSpysok (Myfile);

VyvestyNaEkran;

SozdatNovyjElement;

{Добавляем в список новый элемент и делаем его первым}

element := pervyj;

novyj ^.sled := element;

pervyj := novyj;

VyvestyNaEkran;

rewrite(Myfile2);

VyvestyvFile(Myfile2);

close(Myfile);

close(Myfile2);

repeat until keypressed

end.

Задание 1. Модифицируйте задачу 1 так, чтобы ,в начале нового файла было дописано три записи.

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

Очередь - это структура данных, в которой элемент, записанный первым, считывают первым. Здесь действует принцип первый пришел - первый ушел, хорошо известный в быту: очередь за билетами, очередь на обслуживание и т.п.

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

Задание 2. Решите задачу № 21, применив список с целью добавления в файл нового элемента после элемента с номером і mod 5 + 1, где і - номер варианта.

Задание 3. Решите задачу № 22, применив структуру данных список.

 

 

19