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

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

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

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

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

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

Киев 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.