Основы программирования (стр. 1 из 2)
Национальный технический университет Украины
«Киевский политехнический институт»
Факультет информатики и вычислительной техники
Кафедра вычислительной техники
Киев 2000
Динамическое распределение памяти. Списковые структуры. Технические характеристики предлагаемого модуля для работы с односвязным списком. Листинг модуля Dinamo. Листинг программы, при написании которой был использован модуль Dinamo.
В языке программирования Паскаль, как и в других языках, всегда много используются переменные. В Паскале все переменные, которые мы используем в программе, должны быть заранее описаны, то есть, должен быть указан их тип: целое число, строка и т.п. Но зачастую не возможно заранее знать, какого типа переменная нам будет нужна. Для этих целей и служат динамические переменные, или указатели. Для их создания следует перед идентификатором вставить специальный символ ^. Прежде чем в программе можно будет использовать динамические переменные, следует выделить память, куда будут накапливаться значения соответствующего типа. Только после этого указатель будет содержать корректный адрес памяти. Размещение динамических переменных производится в специальной области памяти Heap. Динамические переменные ничем не отличаются от обычных переменных. Над ними можно производить все действия, что и с обычными переменными. Для работы с динамическим распределением памяти очень удобно использовать связанные структуры данных, например односвязные списки.
Простейшим примером списка является массив, в котором последовательно расположены все его элементы. Но у такого представления есть существенный недостаток – требуется заранее точно указать количество элементов массива. Поэтому лучше воспользоваться более гибким механизмом – динамическими переменными. Наглядно это выглядит так:
Первый элемент Последний элемент
 |
 |
 |
В схеме каждый элемент разбит на два логических поля: Curr – обозначает все содержательные данные, и Next – указатель на следующий элемент списка. У последнего элемента указатель установлен в Nil, что используется для инициализации не распределенных динамических переменных. Данный список называется односвязным, поскольку движение от элемента к элементу в нем происходит только в одном направлении. Односвязный список использован в модуле Dinamo как один из вариантов работы с динамическими структурами.
Как происходит работа с элементами односвязного списка, например, вставка нового элемента? Лучше всего это можно проиллюстрировать следующим рисунком на примере односвязного списка из трех элементов.
 |
Как мы видим, первым действием указателю нового элемента присваивается значение указателя второго элемента (на последний элемент списка), вторым действием разрывается связь между вторым и последним элементом, а вместо этого указатель второго элемента связывается с новым элементом списка.
В данной программе для работы с динамически распределяемой областью используются процедуры New(VarP : Pointer) и Dispose(VarP : Pointer). Первая позволяет создать в Heap-области новую динамическую переменную, используя при этом все свободное количество памяти, которое требуется для значения заданного типа данных. Процедура Dispose освобождает динамическую переменную, выделенную для Р по соответствующему вызову New. После вызова Dispose любые обращения к значению Р^ могут привести к ошибкам. То есть, каждому вызову New должен соответствовать вызов Dispose.
В разработке предложенной программы и модуля также был использован процедурный тип данных. Процедурные типы данных позволяют интерпретировать процедуры и функции как объекты, которые можно использовать при определении переменных и передаче параметров. В программе при вызове такой переменной с соответствующими ей параметрами происходит выполнение назначенной ей процедуры или функции. Синтаксис записи описания процедурного типа соответствует синтаксису обычного заголовка процедуры либо функции.
Технические характеристики предлагаемого модуля для работы с односвязным списком.
В данном модуле реализованы все основные функции, которые необходимы для качественной работы с данными, а именно: создание, вставка, поиск, удаление и просмотр информации, содержащейся в односвязном списке.
В процедуре, которая позволяет создавать новые записи, возможен непосредственный ввод информации с клавиатуры. Это обеспечивает некоторую мобильность программы.
Процедура вставки обеспечивает запись нового, введенного с клавиатуры, элемента в то место списка, которое пользователь считает необходимым.
Процедура удаление также обеспечивает удаление элемента, предварительно найденного в списке, в каком бы месте списка он не находился.
Просмотр обеспечивает последовательный, начиная с первого элемента, просмотр всех элементов, содержащихся в списке. Управление просмотром осуществляется клавишей "пробел".
Данный модуль удобен в использовании, управление отдельными процедурами требует определенной предварительной типизации.
Листинг программы programdinamo11;
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