Основы программирования
Основы программирования
Национальный технический университет
Украины
«Киевский политехнический институт»
Факультет информатики и вычислительной
техники
Кафедра вычислительной техники
Киев 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];
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;
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;
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
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;
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;
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.