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

Национальный технический университет Украины

«Киевский политехнический институт»

Факультет информатики и вычислительной техники

Кафедра вычислительной техники

Киев 2000

Динамическое распределение памяти. Списковые структуры. Технические характеристики предлагаемого модуля для работы с односвязным списком. Листинг модуля Dinamo. Листинг программы, при написании которой был использован модуль Dinamo.

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

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

Первый элемент Последний элемент

В схеме каждый элемент разбит на два логических поля: Curr – обозначает все содержательные данные, и Next – указатель на следующий элемент списка. У последнего элемента указатель установлен в Nil, что используется для инициализации не распределенных динамических переменных. Данный список называется односвязным, поскольку движение от элемента к элементу в нем происходит только в одном направлении. Односвязный список использован в модуле Dinamo как один из вариантов работы с динамическими структурами.

Как происходит работа с элементами односвязного списка, например, вставка нового элемента? Лучше всего это можно проиллюстрировать следующим рисунком на примере односвязного списка из трех элементов.

Х

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

В данной программе для работы с динамически распределяемой областью используются процедуры New(Var P : Pointer) и Dispose(Var P : Pointer). Первая позволяет создать в Heap-области новую динамическую переменную, используя при этом все свободное количество памяти, которое требуется для значения заданного типа данных. Процедура Dispose освобождает динамическую переменную, выделенную для Р по соответствующему вызову New. После вызова Dispose любые обращения к значению Р^ могут привести к ошибкам. То есть, каждому вызову New должен соответствовать вызов Dispose.

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

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

В данном модуле реализованы все основные функции, которые необходимы для качественной работы с данными, а именно: создание, вставка, поиск, удаление и просмотр информации, содержащейся в односвязном списке.

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

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

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

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

Данный модуль удобен в использовании, управление отдельными процедурами требует определенной предварительной типизации.

Листинг программы program dinamo11;

uses Crt, Graph;

type

pitem = ^adresses;

adresses = record

inf : string;

next : pitem;

prev : pitem;

end;

var

tcurr, tfirst, tlast, dont, temp : pitem;

r: char;

adre: string;

a : integer;

Procedure Novoe;

begin

if tfirst=Nil then

begin

new(tcurr);

writeln('Адрес');

readln(adre);

tcurr^.inf:=adre;

tcurr^.next:=nil;

tfirst:=tcurr;

end

else

begin

writeln ('adresses');

readln(adre);

new(tcurr^.next);

tcurr:=tcurr^.next;

tcurr^.inf:=adre;

end;

tcurr^.next:=nil;

dont:=tcurr;

end;

Procedure Prosm;

begin

tcurr:=tfirst;

while tcurr <> nil do

begin

writeln(tcurr^.inf);

repeat

r:=readkey;

until r in [#32];

tcurr:=tcurr^.next;

end;

tcurr:=dont;

repeat

until keypressed;

end;

Procedure Poisk;

begin

a:=0;

writeln ('Chto iskat?');

readln(adre);

tcurr:=tfirst;

while tcurr <> nil do

begin

if tcurr^.inf<>adre then

tcurr:=tcurr^.next

else

begin

writeln (tcurr^.inf);

tcurr:=nil;

a:=1;

end;

end;

if a=0 then

begin

writeln ('Not found');

end;

tcurr:=dont;

repeat

until keypressed;

end;

Procedure Vstavka;

begin

a:=0;

writeln ('Posle chego vstavka?');

readln(adre);

if adre='-' then

begin

new(temp);

writeln ('Chto?');

writeln ('adresses');

readln(adre);

temp^.inf:=adre;

temp^.next:=tfirst;

tfirst:=temp;

end

else

begin

tcurr:=tfirst;

begin

while tcurr<>nil do

begin

if tcurr^.inf<>adre then tcurr:=tcurr^.next

else

if (tcurr^.next=nil) and (a=0) then

begin

Novoe;

a:=1;

tcurr:=nil;

end

else

if (tcurr<>nil) and (a=0) then

begin

new(temp);

writeln ('Chtooo?');

writeln ('adresses');

readln(adre);

temp^.inf:=adre;

temp^.next:=tcurr^.next;

tcurr^.next:=temp;

tcurr:=dont;

a:=1;

end;

end;

end;

end;

if a=0 then writeln ('Not found');

repeat

until keypressed;

tcurr:=dont;

end;

Procedure Deleting;

begin

writeln ('Chto deletet?');

readln(adre);

tcurr:=tfirst;

temp:=tfirst;

while tcurr <> nil do

begin

if tcurr^.inf<>adre then

begin

temp:=tcurr;

tcurr:=tcurr^.next;

end

else

begin

if tcurr=tfirst then

begin

tfirst:=temp^.next;

tcurr:=dont;

end

else

if tcurr^.next=nil then

begin

temp^.next:=tcurr^.next;

tcurr:=temp;

tcurr^.next:=nil;

dont:=tcurr;

end

else

begin

temp^.next:=tcurr^.next;

tcurr:=temp;

end;

end;

end;

tcurr:=dont;

writeln ('Alles');

repeat

until keypressed;

end;

begin {programmka}

tfirst:=nil;

repeat

{clrscr;}

writeln('(С)оздавать, (П)росмотр, (У)даление, По(и)ск, (B)ставка');

repeat

r:=readkey;

until r in ['c','g','b','d','e', #27];

case r of

'c' : Novoe;

'g' : Prosm;

'b' : Poisk;

'd' : Vstavka;

'e' : Deleting;

end;

until r=#27;

{dispose(tcurr);

dispose(temp);}

end.

Модуль DINAMO

unit Dinamo;

Interface

uses Crt;

type

pitem=^tlist;

tlist=record

inf:pointer;

next:pitem;

end;

taction=procedure(p:pointer);

t_test=function(p:pointer):boolean;

Function New_item(p:pointer):pitem;

Function Make_item(dont:pitem; p:pointer):pitem;

Procedure Prosm(first:pitem;act:taction);

Function Find(first:pitem; test:t_test; act:taction):pitem;

Procedure Deleting(first:pitem;test:t_test);

Function Deleting_f_end(first:pitem; test:t_test):pitem;

Function Insert_head(first:pitem;p:pointer):pitem;

Procedure Insert(first:pitem;test:t_test; p:pointer);

Implementation

Function New_item(p:pointer):pitem;

var tcurr :pitem;

begin

new(tcurr);

tcurr^.inf:=p;

tcurr^.next:=nil;

end;

Function Make_item(dont:pitem;p:pointer):pitem;

var tcurr:pitem;

begin

new(tcurr^.next);

tcurr:=dont;

tcurr:=tcurr^.next;

tcurr^.inf:=p;

tcurr^.next:=nil;

end;

Procedure Prosm(first:pitem; act:taction);

var tcurr: pitem;

begin

tcurr:=first;

while tcurr <> nil do

begin

act(tcurr^.inf);

tcurr:=tcurr^.next;

end;

end;

Function Find(first:pitem; test:t_test; act:taction):pitem;

var tcurr:pitem;

begin

tcurr:=first;

while tcurr <> nil do

begin

if test(tcurr^.inf)=false then

tcurr:=tcurr^.next

else

begin

if test(tcurr^.inf)=true then

begin

act(tcurr^.inf);

tcurr:=tcurr^.next;

end;

end;

end;

end;

Procedure Deleting(first:pitem; test:t_test);

var tcurr,temp:pitem;

begin

tcurr:=first;

temp:=first;

while tcurr <> nil do

begin

if test(tcurr^.inf)=false then

begin

temp:=tcurr;

tcurr:=tcurr^.next;

end

else

begin

if tcurr=first then

begin

first:=temp^.next;

end

else

begin

temp^.next:=tcurr^.next;

tcurr:=temp;

end;

end;

end;

end;

Function Deleting_f_end(first:pitem; test:t_test):pitem;

var tcurr,temp : pitem;

begin

tcurr:=first;

temp:=first;

while tcurr <> nil do

begin

if test(tcurr^.inf)=false then

begin

temp:=tcurr;

tcurr:=tcurr^.next;

end

else

if tcurr^.next=nil then

begin

temp^.next:=tcurr^.next;

tcurr:=temp;

tcurr^.next:=nil;

end;

end;

end;

Function Insert_head(first:pitem;p:pointer):pitem;

var tcurr, temp :pitem;

begin

new(temp);

temp^.inf:=p;

temp^.next:=first;

first:=temp;

end;

Procedure Insert(first:pitem;test:t_test; p:pointer);

var tcurr, temp : pitem;

begin

if test(tcurr^.inf)=true then

begin

new(temp);

temp^.inf:=p;

temp^.next:=tcurr^.next;

tcurr^.next:=temp;

end;

end;

begin

end.

Программа, использующая модуль DINAMO

program DODAVANNYA;

uses Dinamo, Crt;

type

pdata=^tdata;

tdata=record

a:string[20];

end;

var

r: char;

dont,first,ptemp: pitem;

b:string[20];

tmp :pdata;

Procedure Novoe;far;

begin

new(tmp);

writeln('Vvedite zifru');

read(b);

if first=nil then

begin

with tmp^ do a:=b;

dont:=new_item(tmp);

first:=new_item(tmp);

end

else

begin

with tmp^ do a:=b;

dont:=make_item(dont,tmp);

end;

end;

Procedure Print(p:pointer);far;

begin

with pdata(p)^ do

begin

writeln(a);

writeln('<>< <>< <><');

end;

repeat

r:=readkey;

until r in [#32]

end;

Function test(p:pointer):boolean;far;

var t : boolean;

begin

with pdata(p)^ do t:=a=b;

end;

Procedure ToBeFound;far;

begin

new(tmp);

writeln('What must I to find?');

read(b);

Find(first,test,Print);

repeat

until keypressed;

end;

Procedure Vstav;far;

begin

new(tmp);

writeln('Posle chego?');

read(b);

if b = 'h' then

begin

writeln('Chto?');

readln(b);

with tmp^ do a:=b;

first:=Insert_head(first,tmp);

end

else

begin

ptemp:=Find(first,test,Print);

if ptemp<>nil then

begin

writeln('Chto?');

readln(b);

with tmp^ do a:=b;

Insert(ptemp,test,tmp);{Type mismatch}

end;

if ptemp=nil then

begin

writeln('Chto?');

readln(b);

with tmp^ do a:=b;

dont:=new_item(tmp);

end;

end;

end;

begin {programmka}

first:=nil;

repeat

{clrscr;}

writeln('(С)оздавать, (П)росмотр, (У)даление, По(и)ск, (B)ставка');

repeat

r:=readkey;

until r in ['c', 'g','b','d','e', #27];

case r of

'c' : Novoe;

'g' : Prosm(first,Print);

'b' : ToBeFound;

'd' : Vstav;

{'e' : Delet; }

end;

until r=#27;

dispose(tmp);

end.