Методические разработка для самостоятельного изучения тем: "Динамические структуры данных" и "" Создание баз данных в Delphi для лабораторных работ по дисциплине "Основы алгоритмизации и программирования"
методическая разработка на тему

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное агентство по образованию

ВОРОНЕЖСКИЙ   ЭНЕРГЕТИЧЕСКИЙ   ТЕХНИКУМ

Методическое пособие для самостоятельного изучения по предмету:

«Основы алгоритмизации и программирования»

На тему:

«Динамические стрктуры данных и работа с ними»

Для студентов специальности

230103 “Автоматизированные системы обработки информации и управлении”

III курс

Методическое пособие разработано преподавателем

Паниной Н.В

Динамические структуры данных

Структура оперативной памяти

Рассмотрим общую схему использования оперативной памяти программами на Turbo Pascal.

На персональном компьютере адреса задаются совокупностью двух шестнадцатеричных слов, которые называются сегментом и смещением. Сегмент – это участок памяти, имеющий длину 64 Кбайт (65536 байт) и начинающийся с физического адреса, кратного 16 (0, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу.

Параграфом называется  непрерывный фрагмент памяти, объемом в 16 байт. Сегмент адресует с точностью до параграфа, смещение с точностью до байта. Поэтому, абсолютный адрес образуется следующим образом: сегмент*16 + смещение.

В начале любой программы, выполняемой в среде DOS, операционная система формирует  префикс сегмента программы (PSP).  PSP занимает 256 байт памяти и его адрес хранится в переменной PrefixSeg модуля System. PSP содержит характеристики программы, используемые   MS DOS при загрузке программы в оперативную память, например, размер программы, параметры вызова.

За PSP следует кодовый сегмент головной программы, ее exe-файл.

Далее расположены кодовые сегменты модулей в      порядке, обратном их следованию в операторе uses.      Последний кодовый  

сегмент занимает библиотека времени выполнения (модуль System). Размер кодового сегмента не может превышать  64 Кбайт, количество кодовых сегментов ограничено имеющейся оперативной памятью.

     Верхняя граница памяти DOS

Сегмент данных содержит значения всех типизированных констант, собранных компилятором из всех описаний программы, независимо от уровня вложенности. Далее хранятся глобальные переменные, описанные во внешнем блоке. Память под эти объекты выделяется статически на основе подсчета суммарного объема, необходимого для хранения типизированных констант и глобальных переменных. Размер сегмента данных составляет 64 Кбайт. Сегмент данных адресуется посредством регистра DS (Data Segment). Регистр DS никогда не изменяется во время выполнения программы  Содержимое этого регистра может быть получено с помощью стандартной функции  Dseg   модуля System.

Сегмент стека используется для управления локальными переменными подпрограмм. Сегмент стека адресуется специальным регистром SS (Stack Segment), значение которого не изменяется во время выполнения программы. Другой регистр процессора  SP(Stack Pointer)  всегда показывает адрес свободной области сегмента стека. Значение этого регистра меняется в процессе вызова подпрограмм и выхода из них. Значения регистров SS  и SP можно просмотреть, используя соответственно стандартные  функции  Sseg и Sptr. Для просмотра содержимого всех регистров процессора можно воспользоваться командой Register пункта Debug. Для просмотра содержимого стека используется команда Call Stack  пункта Debug. В раскрывающемся при этом окне будет показана последовательность процедур,  вызываемых используемой программой, а также имена процедур и значения передаваемых им параметров. Размер сегмента стека не превышает 64 Кбайт, размер по умолчанию 16 Кбайт.  Управлять размером стека можно директивой компилятора $M.

Оверлейный  буфер используется стандартным  модулем Overlay  для хранения оверлейного кода. Оверлейный режим  работы состоит  в размещении  всех модулей или их части  на жестком диске и последовательной загрузке  модулей  в оперативную память  по мере их надобности. Размер оверлейного буфера  по умолчанию соответствует размеру наибольшего оверлея в программе. Если в программе нет оверлеев, размер оверлейного буфера равен нулю. Размер оверлейного буфера может быть увеличен с помощью программы OvrSetbuf модуля Overlay.

За оверлейным буфером располагается динамическая область памяти, называемая кучей.  Куча занимает всю или часть свободной памяти, оставшейся после загрузки программы.  Размер кучи можно установить  с помощью директивы компилятора  {$M стек, min кучи, max  кучи}.

Для работы с указателями и адресами используются следующие  функции:

Addr(x): pointer – возвращает адрес заданного объекта x;

Cseg: word – возвращает текущее значение регистра CS;

Dseg: word – возвращает текущее значение регистра  DS;

Ofs(x): word – возвращает смещение заданного объекта;

Ptr(Seg, Ofs: word): pointer – преобразует сегмент Seg и смещение Ofs в значение типа указатель.

Seg(x): word – возвращает сегмент для заданного объекта;

Sptr: word – возвращает текущее значение регистра PS;

Sseg: word – возвращает текущее значение регистра SS.

Параметр стек – определяет размер сегмента стека в байтах. По умолчанию размер стека 16384 байта. Максимальный размер – 65538 байт; Min кучи –  минимальный требуемый размер кучи в байтах; по умолчанию 0 байт; Max кучи – максимальное размер  кучи в байтах; по умолчанию  655360 байт, то есть, вся доступная память, это значение не должно быть меньше наименьшего размера кучи. Все значения задаются в десятичной или шестнадцатеричной формах. Следующие директивы эквивалентны: {$M 16384, 0, 65536}   {$M $4000, $ 0,  $A000}  Если указанный минимальный объем не доступен, то программа не будет выполняться.

Управление размещением переменных в динамической памяти осуществляет монитор кучи, являющийся одной из управляющих программ модуля System. Для реализации программ распределения динамической памяти монитор кучи использует следующие переменные:

HeapOrg  – указатель начала кучи;

HeapPtr   – текущий указатель кучи;

FreePtr    – указатель списка свободных блоков

HeapError – указатель установки обработки ошибок кучи;

FreeMin – минимальный размер списка свободных блоков.

        Верхняя граница памяти DOS

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

1. Куча пуста. Это состояние возможно в начале выполнения программы или после полной очистки. Тогда монитор кучи заполняет кучу последовательно в порядке поступления запросов на выделение памяти. При каждом выделении памяти монитор кучи передвигает указатель кучи вверх  на размер запрошенной области.

   2. Куча фрагментирована, т.е., в процессе работы образовались освобожденные участки (дырки). Монитор кучи, следуя принципу оптимального использования памяти, просматривает список свободных блоков и выбирает из них такой участок, чтобы разница между размерами свободного и запрашиваемого участков была минимальна.

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

Когда куча заполнена полностью, то очередной запрос к выделению памяти останавливает программу и выдается сообщение об ошибке с номером 203 (HeapOverlov error). В этом случае нужно увеличить память директивой $M и перезапустить программу. Максимальный размер запрашиваемой памяти, которая может быть размещена в куче, составляет 65521 байт, так как этот участок должен целиком содержаться в одном сегменте.

Рассмотрим организацию списка свободных блоков. Когда участок памяти освобождается, то информация  об его расположении в куче помещается в список свободных блоков, который растет  от верхней границы кучи (навстречу указателю кучи) по мере поступления информации об освобожденных участках. Перед выделением памяти монитор кучи проверяет список свободных блоков на наличие в нем блока, размер которого равен или больше размера запрашиваемого блока. Список свободных блоков может содержать до 8191 адресов. Переполнение списка свободных блоков возможно, если освободить без повторного использования 8191 полностью несмежный блок, что маловероятно. При освобождении несмежных блоков список свободных блоков увеличивается (растет вниз). Если между указателем списка свободных блоков FreePtr и текущим указателем кучи HeapPtr нет свободного места, то возникает ошибка.

Динамические структуры данных

          Статические и динамические переменные

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

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

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

{Тип ukaz  ссылается (указывает) на переменную}                                          {типа ctack}

type ukaz= ^ stack;    

          stack = record

          inf: integer;    {Информационное поле}

          next: ukaz;     {Поле ссылки}

          end;

var r: ukaz;

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

Пусть переменная r имеет тип  ukaz. Тогда после обращения к процедуре new(r) будет создана указанная переменная, в которой предусмотрено информационное поле и поле ссылки. В информационном поле будет размещаться переменная заданного типа. В поле ссылки будет находиться адрес той переменной, за которой следует данная.  Через r^ обозначается сама указанная переменная. Тогда r^.inf – соответствует информационному полю, а  r^. next – полю ссылки.

Пусть имеется некоторая исходная ситуация:

     Здесь  r и w переменные типа ukaz. Причем изначально r содержит адрес переменной со значением 10, а w – адрес переменной со значением 30. Рассмотрим следующие действия:

1.   w: = r. В этом случае  w содержит теперь адрес переменной со значением 10 и картинка приобретает следующий вид:

2. w^: = r^. Одна указанная переменная присваивается другой. На место указанной переменной, указывающей на значение 40, заслана переменная, указывающая на  значение 15.

3.  w^. inf: = r^.inf. Информационное поле переменной w становится равным информационному полю переменной r.

4. w^. next: = r^. next. Поле ссылки переменной w становится равным полю ссылки переменной r.

Основные процедуры и функции для работы с динамическими переменными

Процедура New(r)  резервирует фрагмент памяти в куче  для размещения новой переменной, причем r – указатель на переменную того типа, который нужно создать.  Физически r содержит адрес первого байта памяти, где записана переменная. Сам по себе указатель занимает в памяти всего 4 байта, а данные, на которые он указывает, могут занимать в памяти много килобайт. Каждая отдельная процедура new может разместить только одну динамическую переменную.  

Процедура Dispose(r) освобождает участок памяти, занятый объектом с указателем r и помещает адрес освобожденного участка и его длину в список свободных блоков.

Процедура Mark(r)   позволяет получить адрес динамически распределенной памяти, соответствующий указателю R.

Процедура Release(R) освобождает всю область динамической памяти, начиная с адреса, полученного в результате выполнения процедуры Mark.

Процедура GetMem(r, i)  выделяет  для динамической переменной  байт.

Процедура FreeMem(r, i)  освобождает   байт динамически распределенной памяти, выделенных процедурой GetMem.

Функция MaxAvail   возвращает размер в байтах  максимального  непрерывного участка свободной памяти в куче. Результат имеет тип LongInt.

Функция MemAvail возвращает размер в байтах общего свободного участка кучи. Результат имеет тип LongInt.

 Динамика выделения памяти в куче

Рассмотрим фрагмент программы:

var p1,p2,p3,p4,p5: ^real;

begin

new(p1);

new(p2);

mark(p5);

new(p3);

new(p4);

Этому фрагменту программы соответствует следующая структура динамической памяти:

                     Младшие адреса памяти

                      Старшие адреса памяти

Процедура Mark () как бы помечает кучу перед размещением динамической переменной ,  копируя значения текущего указания кучи () в указатель .

Если выполнить процедуру Release (), то структура кучи будет такой:

При этом освобождается вся память, выделенная после обращения к процедуре Mark. Если выполнить Release (HeapOrg), то куча будет очищена полностью, так как указатель HeapOrg содержит адрес начала кучи.

В случае произвольного освобождения динамической памяти удобнее использовать Dispose и FreeMem. При этом, если освобождаемый участок не является последним (верхним) в куче, то куча становится фрагментированной, причем адрес и размер этого свободного участка записывается в список свободных блоков для дальнейшего использования.

Если будет выполнена та же начальная последовательность процедур New, а затем Dispose (), то в середине кучи появится дырка.

                     Младшие адреса памяти

                      Старшие адреса памяти

Если сделать New (), то это опять приведет к выделению той же области памяти. С другой стороны Dispose () увеличивает размер свободного участка, так как  и  были соседними. Этот свободный участок сольется со свободной памятью кучи, так как последний значащий указатель кучи – это . При этом указатель кучи переместится на первый байт после конца последнего занятого участка, и куча будет находиться в том же состоянии, в каком она была бы при выполнении процедуры Release ():

Линейные списки. Способы создания и обработки        

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

- легкость реализации и небольшой расход памяти;

- простая связь между номером элемента  и адресом ячейки , в которой этот элемент хранится , где  – адрес ячейки, где хранится первый элемент,  – количество байт, требуемых для хранения  одного элемента данного типа;

 - возможность представления многомерных массивов.

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

Связанное распределение – это такой тип организации последовательности, при котором каждому элементу последовательности   ставится в соответствие указатель , отмечающий ячейку, в которую записан элемент последовательности . Существует также указатель , который указывает на начальную ячейку последовательности:

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

Разновидности связанных списков.     Если элемент указывает на , то такой список называется  циклическим. 

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

Стек – последовательность, у которой все включения и выключения элементов происходят только в ее левом конце, называемом вершиной стека. Стек работает по правилу:  “Первый пришел – последний ушел”.

Работа со стеком.

type            ukaz = ^stack;

                    stack = record

                    inf: integer;

                    next: ukaz

                    end;

var top, kon, newel: ukaz;   value: integer;

procedure sozd;     {Помещение элементов в стек}

begin

             top: = nil;          

             while true do

                    begin

                         read (value);

                         If value = 9999 then exit;

                         new(kon); {Выделение памяти для}

                                          {хранения текущего элемента}

   {Заполнение информационного поля}

                         kon^ . inf: = value; }

                     {В поле ссылки каждого элемента }

  {помещаем адрес элемента, за которым}

  {он следует; для элемента, вводимого}

  {первым,  этот адрес будет равным nil}  

                         kon^ . next: = top;

               {Запоминаем текущую вершину стека}

                         top: =  kon;

                    end;   {while}

 end;  {конец процедуры sozd}

procedure dob;     {Добавляет новые элементы}

                             {в уже  существующий стек,}

                             {адрес вершины которого }

                             {должен быть известен}

begin

         while true do

                    begin

                             read (value);

                             if (value = 9999) then exit;

                             new (newel);  

                             newel^ . next: = top;

                             newel^ . inf: = value;

                             top: = newel;

                   end;

end;

procedure udal;     {Удаляется один элемент из}

                              {стека; указатель вершины}

                             {стека перемещается к}

                             {следующему элементу} 

begin

        top:= top^.next;    

end;

procedure writ;     {Вывод элементов стека}

                             {на экран}

begin

         kon:=top;

         while kon<> nil do

                 begin

                          writeln(kon^ . inf);

                         kon: = kon^ . next;

                end;

end;

bеgin   {Головная программа}          

          sozd;

          writ;  

          dob;

          writ;    

               udal;    

               writ;

 end.

Вот как будет выглядеть стек, в который записаны  последовательно числа 3, 15, 7:

   – адреса, по которым элементы стека размещены в динамической области памяти. Адрес вершины стека хранится в переменной  .

Рассмотрим механизм удаления из стека элемента, находящегося в любом месте стека. Допустим, что надо удалить элемент со значением .

Алгоритм удаления элемента применительно к рассмотренной схеме стека,  состоит из следующих шагов:

- определение адреса удаляемого элемента ();

- сохранение адреса элемента, предшествующего удаляемому ();

- замена поля ссылки элемента, предшествующему удаляемому элементу, на поле ссылки удаляемого элемента ().

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

В этом случае после определения адреса удаляемого элемента необходимо провести дополнительный анализ:

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

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

Далее приведен текст программы, реализующий алгоритм удаления заданного элемента из стека.

type

ukaz=^stek;

stek=record

inf: integer;

next:ukaz;

end;

var

    v,w,flag,flag1:integer;

    kon,top,t1,t:ukaz;

begin {Создание стека}

        top:=nil;

        while true do

                 begin

                         writeln('Введите очередной член ряда');

                         readln(v);

                         if(v=9999) then break;

                         new(kon);

                         kon^.inf: = v;

                         kon^.next: = top;

                         top:=kon;

           end;

{Вывод элементов стека на экран}

    kon:=top;

    while kon<> nil do

     begin

              write(kon^.inf,' ');

              kon:=kon^.next;

      end;

             kon: = top;flag: = 0; t1: = top; t: = kon; flag1: = 0;

             writeln('Введите значение удаляемого элемента');

             readln(w);

 while kon<>nil do

      begin

              if(kon^.inf=w) then

{Удаление группы одинаковых элементов из начала}

{стека}

                              begin

                                        if (flag=0) then

                                              begin

                                                       t1:=kon^.next;

                                                       kon:=t1;

                                              end

              else

{Удаление группы одинаковых элементов из}

{середины и конца стека}

                    begin

                            if  (flag1=0) then

                                               begin

                                                      t^.next: = kon^.next;

                                                      kon:=kon^.next;

                                                      flag:=1;

                                              end

                             else begin

                                             t^.next:=kon^.next;

                                             t:=kon;

                                             kon:=kon^.next;

                                             flag:=1;

                                             flag1:=1;

                                     end;

                     end;

     end

                     else begin

                                     t:=kon;

                                     kon:=kon^.next;

                     flag:=1;

            end;  

  end;

{Вывод на экран результирующего стека}      

kon:= t1;

      while kon<> nil do

          begin

                   write(kon^.inf,' ');

                   kon:=kon^.next;

          end;

end.

Очередь  - это последовательность, в которой все включения элементов производятся на правом конце списка (в конце очереди), а исключения производятся на левом конце (в начале очереди). Очередь работает в режиме “Первый пришел – первый ушел”. Поэтому при работе с очередью необходимо хранить как адрес первого элемента очереди, так  и адрес последнего (right, left).

Механизм формирования очереди (3, 15, 7) можно по шагам представить так:

1.

2.

3.

type

       ukaz = ^stack;

       stack = record

       inf: integer;

       next: ukaz

       end;

var  pp, kon, newel, right, left: ukaz;  value: integer;

procedure sozd; {Организация очереди}

begin

          read (value);  

          if (value =9999) then exit;

          new(kon);     kon^.next: = nil;

          kon^.inf: = value;  

          right: = kon;    

          left: = kon;

          while true do

                    begin

                              read (value);  

                              if value = 9999 then exit;

                              new(kon);      kon^ . next: = left;  

                              kon^ . inf:    = value;        left: = kon;

                     end;

end;

{Добавление новых элементов в уже существующую очередь.} {Добавление происходит справа}

procedure dob;

begin

   while true do

        begin

               read (value);

               If value = 9999 then exit;

               new (newel);

               right^.next: = newel;

               newel^ . next: = nil;

               newel^ . inf: = value;  

               right = newel;

          end;

end;

{Удаление элемента из очереди, удаление происходит слева}

procedure udal;

begin

        left: = left^.next:

end;

{Вывод на экран элементов очереди}

procedure writ;

begin

         pp: = top;

         while pp <> nil do

          begin

                   writeln(pp^ . inf);

                   pp: = pp^ . next;

          end;

 end;

 bеgin            

    sozd;       dob;        udal;       writ;

 end.

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

Структура двусвязного списка циклического может быть представлена так:

type        ukaz = ^Stack;

                stack = record

                inf: integer;

{Левое и правое поля ссылок}

                nextRight, nextLeft: ukaz;

                end;

var  point,  kon, nt, newel, right, left: ukaz;

value: integer;

procedure sozd; {Организация двусвязной очереди}

begin {Запись первого элемента в очередь}

         read (value);

         if (value =9999) then exit;

         new(kon);

         kon^ . inf:=value;  

         kon^.nextRight: = nil;

         kon^.nextLeft: = nil;

         right: = kon;

         nt: = kon;

{Запись элементов в очередь, начиная со }

{второго}

         while true do

               begin

                      read (value);

                      if  value = 9999 then exit;

                      new(kon);

                      kon^ . inf:= value;

                      kon^ . nextRight: = nt;

                      nt^. nextLeft: = kon;

                end;

         nt^ .nextLeft: = nil;

         left: = nt;        

end;

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

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

 {список после   элемента,             на который} 

{указывает значение point}

procedure dob;

begin

      read (value);

      if value = 9999 then exit;

      new (newel);

      newel^ . inf: = value;

      newel^ . nextRight: = point^. nextRight;

      newel^ . nextLeft = point;  

      point^. nextRight ^. nextLeft: = newel;

      point^. nextRight: = newel;

 end;

              {Удаление элемента из двусвязной очереди.}

              {Из списка удаляется элемент, следующий}

              { за элементом, на который указывает}

              {значение point}

procedure udal;

begin

     point^. nextRight:=point^. nextRight^ . nextRight;

     point^. nextRight^ .nextLeft: = point;

end;

bеgin    

        sozd;

        dob;

        udal;  

end.

 Нелинейные списки. Способы создания и обработки        

Деревья.  Конечное корневое дерево T  формально  определяется как непустое конечное множество упорядоченных узлов, таких, что существует выделенный узел, называемый корнем дерева, а остальные узлы разбиты на  поддеревьев , , …,. Узлы, не имеющие поддеревьев, называются листьями; остальные узлы называются внутренними узлами.

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

Важной разновидностью корневых деревьев является класс бинарных деревьев.

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

Различие между деревом и бинарным деревом:

- дерево не может быть пустым, а бинарное дерево может быть пустым;

-  каждый  узел дерева может иметь произвольное число поддеревьев, а каждая вершина бинарного дерева может иметь 0, 1, 2 поддерева;

- в  бинарном дереве существует различие между левым и правым поддеревьями.

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

Если  двоичное дерево организовано так, что для каждой вершины   справедливо утверждение, что все ключи левого поддерева    меньше ключа   , а все ключи правого поддерева  больше его, то такое дерево будем называть деревом поиска. В таком дереве легко обнаружить заданный элемент, для этого достаточно, начав  с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины.  Дерево поиска для заданной последовательности целых чисел  23, 17, 26,  32,  18,  6,  2,  5,  8,  29,  146 имеет вид:

program derp;

type ukaz = ^nod;

nod=record

inf: char;

count:integer;

left,right: ukaz;

end;

var r,p,d: ukaz;

ch:char;

{Формирование дерева поиска}

Procedure Sozd(var d:ukaz; ch:char);

begin

     if d=nil then

                     begin

                     new(d);

                     d^.left: = nil;

                     d^.right: = nil;

                     d^.inf: = ch;

                     d^.count: = 1;

                end

         else

             begin

                  if ch

                  else if ch >d^.inf then sozd(d^.right,ch)

                  else

                      begin

                           d^.count:=d^.count+1;

                           writeln('Элементы повторяются');

                      end;

             end;

end;

{Поиск в дереве заданного узла}

{Функция возвращает адрес найденного узла}

{Если заданного узла в дереве нет, то возвращается nil}

function find(var d:ukaz;ch:char): ukaz;

begin

      if d=nil then find:=nil

      else

          if ch

      else

          if ch >d^.inf then find:=find(d^.right,ch)

      else

          find:=d;

end;

{Обход дерева поиска и вывод на экран значения его узлов}

Procedure obxod(var d:ukaz);

var i: integer;

begin

     if d<>nil then

                   begin

                        obxod(d^.left);

{Символ на экран выводится столько раз, сколько он встречается в последовательности}

                        for i:=1 to d^.count do

                        write(d^.inf,' ');

                        obxod(d^.right);

                   end;

end;

begin

      d:=nil;

      repeat

      writeln('Введите символ режима работы ');

      writeln(‘+ - формирование дерева);

      writeln(‘-  - удаление элемента из дерева’);

      writeln(‘> - обход дерева и вывод на экран значения его узлов);

      readln(ch);

      if ch in['+','-','>']  then

      case  ch of

'+':  begin

          writeln(‘Введите очередной символ,')

          writeln(‘символ вводится со знаком +’);

          readln(ch);

          if ch in ['a'..'z'] then sozd(d,ch);

      end;

'-': begin

          writeln(‘Введите удаляемый символ,')

          writeln(‘символ вводится со знаком -’);

          readln(ch);

{Удаление элемента имитируется инкрементированием}

{счетчика p^.count}

          p:=find(d,ch);

          if p <>nil then begin

                                           if p^.count>0 then

                                           p^.count:=p^.count-1;

                                   end;

     end;  

'>': begin

          obxod(d);

          writeln;

     end;

     end; {end case}

     until ch='*';

end.

Контрольные вопросы  и упражнения

1. Что такое статические и динамические переменные?

2. Что представляет собой ссылочная переменная, указанная переменная, информационное поле и поле ссылки?

3. Чем отличается использование процедур New(R) и  GetMem(R,i)?;

4. Объясните механизм действия процедуры Release(R).

5. Как определить размер наибольшего непрерывного участка кучи? Как определить размер общего свободного пространства кучи?

Следующие эадачи (6-30) решить для случая реализации списка в виде стека, очереди и двусвязного списка.

6. Сформировать список, содержащий вещественные числа. Найти:

- среднее арифметическое элементов этого списка;

- поменять местами первый и последний элемент списка;

- заменить в списке все вхождения заданного элемента  на элемент  .

7. Сформировать список, содержащий символьные переменные:

- проверить, упорядочены ли элементы списка по алфавиту;

- удалить из списка элементы с заданным значением;

8. Сформировать список, содержащий строковые переменные:

- подсчитать количество слов в списке, которые начинаются и оканчиваются одной и той же литерой;

- переставить местами два заданных слова.

9. Сформировать список, содержащий строковые переменные:

- подсчитать количество слов в списке, которые начинаются с той же литеры, что и следующее слово;

- удалить из списка элементы с заданным значением.

10. Сформировать списка, содержащий строковые переменные:

- подсчитать количество слов, совпадающих с последним словом в списке;

- размесить рядом с заданными элементами их копию.

11. Сформировать список, содержащий вещественные числа:

- определить является ли заданный список пустым;

- вставить элемент в список перед заданным элементом.

12. Сформировать список, содержащий целые числа:

- сформировать новый список, который будет содержать положительные элементы исходного списка;

- не создавая нового списка, разместить сначала положительные элементы списка, а затем все остальные.

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

14. Сформировать два списка, содержащих целые числа:

-   проверить их на равенство;

-   определяет, входит ли список  в список ;

15. Сформировать список :

-    перенести  в начало  списка  его последний элемент;

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

16. Сформировать список :

-  перенести в конец  списка  его первый элемент;

- в списке  из каждой группы подряд идущих равных элементов оставить только один.

17. Сформировать список, состоящий из символьных переменных:

- вставить в этот список пару новых элементов перед последним элементом;

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

18.  Описать процедуру, которая объединяет два упорядоченных по неубыванию списка  и   в один упорядоченный по неубыванию список.

19. Разработать рекурсивную процедуру или функцию, которая:

-  находит максимальный элемент списка;

- удаляет из списка все вхождения заданного элемента.

20. Разработать рекурсивную процедуру или функцию, которая:

- удваивает каждое вхождение заданного элемента в список;

- находит среднее арифметическое значение элементов списка.

21.  Многочлен  можно представить в виде списка, элементами которого являются коэффициенты при степенях многочлена. Используя такое представление:

-  проверить на равенство два многочлена;

- вычислить значение многочлена  при заданном .

22. Используя раннее рассмотренное представление многочлена:

- построить многочлен, являющийся производной исходного многочлена;

- найти сумму двух многочленов; предусмотреть приведение подобных членов.

23. Сформировать список, состоящий из целых чисел:

- описать процедуру, которая в списке  заменяет первое вхождение  списка  (если такой есть) на список ;

- проверяет, есть ли в списке  хотя бы два одинаковых элемента;

24. Разработать процедуры и функции, предварительно выбрав для представления данных соответствующую списковую структуру, для решения следующих задач:

- определить, симметричен ли заданный во входном файле текст (за ним следует точка);

- дана последовательность из не менее чем двух различных натуральных чисел, за которой следует 0. Напечатать в обратном порядке все числа между наибольшим и наименьшим числами этой последовательности;

25.   Разработать процедуры и функции, предварительно выбрав для представления данных соответствующую списковую структуру, для решения следующих задач:

-  дана непустая последовательность непустых слов из букв; между соседними словами – запятая, за последним словом  - точка; напечатать все слова максимальной длины;

-  дана непустая последовательность слов, в каждом из которых от 1 до 12 строчных латинских букв; между словами  - пробел, за последним словом  - точка; напечатать эти слова по алфавиту, указав для каждого из них число его вхождений в эту последовательность;

 решить предыдущую задачу в предположении, что максимальная длина слов не известна;

26. Дано произвольное натуральное число n. Напечатать все цифры десятичной записи числа n!;

27. Одно из возможных представлений «длинного» текста – это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки; используя данное представление текста, описать:

-  функцию для подсчета числа строк в тексте ;

- процедуру, меняющую местами -ю и -ю строки текста.

28. Используя введенное в задаче 27  представление «длинного» текста, разработать:

-  процедуру, заменяющую -ю строку текста на копию -той строки;

- процедуру, удаляющую -ю строку из текста.

29. Используя введенное в задаче 27  представление «длинного» текста, разработать:

  -  процедуру, добавляющую после -й строки копию -й строки;

-  процедуру,  печатающую построчно текст;

30. Разработайте структуру связанного списка, имеющего только один указатель на каждый узел, но позволяющую, тем не менее, перемещаться по списку вперед и назад.  

31.Составить процедуру подсчета числа узлов заданного бинарного дерева.

32. Для заданного бинарного дерева описать процедуру или функцию, которая:  определяет число вхождений элемента  в дерево .

33. Вычислить среднее арифметическое всех элементов непустого бинарного дерева.

34. Заменить в бинарном дереве   все отрицательные элементы на их абсолютные величины.

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОРОНЕЖСКИЙ   ЭНЕРГЕТИЧЕСКИЙ   ТЕХНИКУМ

Методическое пособие для самостоятельного изучения по предмету:

«Основы алгоритмизации и программирования»

На тему:

«Программирование в DELPHI»

Для студентов специальности

230103 “Автоматизированные системы обработки информации и управлении”

III курс

Методическое пособие разработано преподавателем

Паниной Н.В

2010

ОСНОВЫ РАБОТЫ С БАЗАМИ ДАННЫХ В DELPHI

1. Создание базы данных и таблиц

1.1. Создание псевдонима базы данных

При работе с таблицами локальных БД (в число которых входят таблицы СУБД Paradox и dBase) сама база данных размещается в каталоге на диске и хранится в виде набора файлов. Для хранения одной таблицы создается отдельный файл. Такие же отдельные файлы создаются для хранения индексов таблицы и мемо-полей.

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

Обращение к БД из утилит и программы осуществляется по псевдониму базы данных. Псевдоним должен быть зарегистрирован в файле конфигурации конкретного компьютера при помощи утилиты BDE Administrator. Необходимо присвоить какой-то псевдоним (например, BIBL) создаваемой БД. Для этого поступают следующим образом.

• Запустить утилиту  BDE Administrator (Пуск, Программы, Borland Delphi 7, BDE Administrator).
• Выбрать в главном меню окна утилиты пункты Object, New (или выбрать вкладку Databases, вызвать на дереве Database контекстное меню, выбрать пункт New, щелкнуть по кнопке ОК).
• В появившемся окне оставить тип создаваемой БД без изменений (STANDARD) и щелкнуть по кнопке ОК.
• В левом поле окна администратора заменить имя Standard1 на имя псевдонима (например, BIBL), в строке PATH щелкнуть по кнопке … и выбрать созданную ранее папку (например, TABLES).
• Для запоминания псевдонима в левом окне администратора БД на имени псевдонима щелчком правой кнопки мыши вызвать контекстное меню и выбрать пункт Apply (применить), в появившемся диалоговом окне щелкнуть по кнопке ОК (рис.1).
• Закрыть окно утилиты BDE Administrator: создание псевдонима завершено и к нему можно обращаться из других утилит и приложений. Однако каталог, на который ссылается псевдоним БД, еще пуст. Необходимо создать в нем таблицы БД.

Рис. 1 Окно BDE Администратора

1.2. Установка рабочей директории

Для установки рабочей директории необходимо запустить утилиту Database Desktop (DBD) (Пуск, Программы, Borland Delphi 7, Database Desktop). Затем  выбирают пункты меню File, Working Directory, с помощью кнопки BROWSE выбирают каталог для размещения файлов базы данных (например, созданную папку TABLES) и в выпадающем списке Aliases выбирают имя псевдонима. После этого щелкают по кнопке ОК.

Создание таблиц базы данных. 

Создание таблицы. Таблицы Paradox 7 создаются с помощью утилиты Database Desktop. Для создания таблицы запускают утилиту Database Desktop, выбирают пункты меню File, New, Table. В появившемся окне Create Table оставляют без изменений тип создаваемой таблицы (Paradox 7) и нажимают кнопку ОК. После этого появится окно определения структуры таблицы БД (рис. 2).

Рис. 2 Пример описания структуры таблицы

Каждая строка таблицы описывает одно поле. Назначения столбцов:

• Field Name – имя поля (английские буквы);
• Type – тип поля (например, А – символьное длиной до 255 символов, N – число с плавающей точкой до 15 значащих цифр, S – денежный формат, I – целочисленные значения, D – дата, + - автоинкрементное поле и т.д.);
• Size – размер поля (для строковых полей);
• Key – содержит звездочку «*», если поле входит в состав первичного ключа (выставляется клавишей пробел).

Типы полей. В таблицах Paradox могут использоваться типы данных, представленные в табл. 1.

Таблица 1

Типы данных

Продолжение табл. 1

1.3. Контроль за содержимым полей

По умолчанию сразу после открытия окна редактирования структуры таблицы в списке Table properties выбран пункт Validity Checks, что позволяет контролировать содержимое полей.

С помощью флажка Required Field можно задать обязательность  для заполнения текущего поля.

С помощью полей Minimum Value и Maximum Value можно задать минимальное и максимальное значения для числовых полей.

В строке Default Value можно указать значение поля по умолчанию. При вводе новой записи это значение появится в поле.

1.4. Выбор языкового драйвера таблицы

Для отображения русского текста без искажения при вводе информации в символьные поля необходимо установить драйвер для русского языка.

• В диалоговом окне описания таблицы в списке Table properties необходимо выбрать Table Language.
• Щелкнуть по кнопке Modify.
• В появившемся окне в списке Language выбрать Pdox ANSI Cyrillic.

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

1.5. Парольная защита

Любая таблица Paradox может быть полностью или частично защищена от несанкционированного доступа. Для этого в списке Table properties выбирают пункт Password Security, щелкают по кнопке Define. В открывшемся диалоговом окне задают пароль, который может содержать от 1 до 15 любых символов, в том числе и пробелы. Пароль чувствителен к регистру букв. С помощью кнопки Auxiliary Password вызывают дополнительное окно, в котором можно уточнить, какие поля и как защищаются.

1.6. Сохранение таблицы

Для запоминания таблицы в окне описания таблицы щелкают по кнопке Save As. В появившемся окне задают имя таблицы  и выбирают созданную вами папку для размещения таблиц.

1.7. Установление связей между таблицами          (определение ссылочной целостности)

Ссылочная целостность – это особый механизм, способствующий поддержанию непротиворечивых сведений в таблицах БД, связанных реляционными отношениями.

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

• Открыть подчиненную таблицу (выбрать пункты меню File, Open, Table, выбрать таблицу).
• Выбрать режим изменения структуры таблицы (Table, Restructure).
• В диалоговом окне в выпадающем списке Table Properties выбрать Referential Integrity  и щелкнуть по кнопке Define.
• В появившемся диалоговом окне в списке Fields показаны поля выбранной таблицы, а в списке Tables – таблицы базы данных. Сначала указывают поле связи для подчиненной таблицы: выбирают в списке Fields поле связи и нажимают кнопку с изображением стрелки вправо. Название выбранного поля будет записано в поле Child Fields (поле внешнего ключа дочерней таблицы). Выбирают в списке Tables  главную таблицу и нажимают кнопку с изображением стрелки влево. В поле Parents Key (ключ родительской таблицы) будут показаны поля из первичного ключа главной таблицы.
• Переключатели Update rules определяют вид каскадных воздействий на дочернюю таблицу при изменении значения поля связи в главной таблице или при удалении в ней записи: Cascade – разрешены каскадные изменения и удаления подчиненных записей в дочерней таблице; Prohibit – запрещены изменения полей связи или удаление записи в родительской таблице, если для данной записи есть связанные записи в дочерней таблице. Обычно выбирают переключатель Cascade и щелкают по кнопке ОК (рис. 3).
• Будет запрошено имя связи. Вводят имя связи и нажмите кнопку ОК.
• Сохраняют изменения в дочерней таблице, щелкнув по кнопке Save.
• Выйти из режима реструктуризации (кнопка Cancel) и закрыть окно DBD.

Аналогичным образом создают связь для каждой пары связываемых таблиц.

Рис. 3  Окно связывания таблиц

1.8. Создание меню приложения

Создание меню приложения осуществляется следующим образом.

1. Запустить Delphi (Пуск, Программы, Borland Delphi, Delphi). Автоматически откроется форма 1.
2. На панели компонентов  перейти во вкладку Standard, выбрать компоненту Mainmenu и поместить ее на форму.
3. На компоненте вызывают контекстное меню и выбирают пункт Menu Designer…. Открывается диалоговое окно, в котором формируют элементы меню. Для текущего элемента меню необходимо задать подпись.
4. На панели Object (Инспектора объектов) в поле Caption набирают название текущего пункта меню (например, Редактирование) и нажимают клавишу Enter.
5. Выделяют новый пункт меню (пустой), появившийся справа, и повторяют действия п. 4.

6. Для создания меню второго уровня выделяют щелчком пункт меню первого уровня и нажимают на клавиатуре стрелку вниз. В поле Caption вносят название пункта и нажимают клавишу Enter. Эти действия повторяют для каждого пункта меню второго уровня (рис.4).

Рис. 4 Форма, содержащая меню

6. После создания меню закрывают окно Menu Designer и сохраняют форму. Для сохранения выбирают пункты меню File, Save All, выбирают папку, где должны сохраняться модули.

         Привязка пункта меню к форме. Пункты меню должны быть привязаны к вызову определенных форм.

1. Привязка пункта «Выход» к соответствующему действию:

в режиме редактирования осуществить двойной щелчок по пункту «Выход»;

в открывшейся процедуре набрать Form1.Close;

сохранить произведенные действия.

2. Привязка пункта меню к вызову соответствующей формы:

• создать новую форму (кнопка NewForm, 4-я слева на панели инструментов);
• на панели Инспектора объектов в поле Name можно ввести более информационное имя (например, Form2_Raz_zn) и нажать Enter;
• вызвать список модулей кнопкой ViewUnit (1-я слева) и выбрать в списке unit1, в тексте процедуры найти слово implementation, для доступа к модулю unit2 ниже этого слова набрать uses unit2;
• переключиться на главную форму;
• дважды щелкнуть по привязываемому пункту меню и в открывшейся процедуре ввести:   имя формы. ShowModal; (например:  Form2_Raz_zn.ShowModal;);
• Проверить вызов формы при выборе пункта меню (кнопка Запуск на панели инструментов или F9).
• Выход из режима запуска – закрыть окно первой формы.

Редактирование внешнего вида формы. Можно осуществить следующие действия по редактированию формы:

в строке Caption задают подпись на русском языке;

в строке Bordericons для biMaximize выбирают False – это означает запрет на распахивание окна;

в строке Position задают способ выравнивания формы на экране (например, по центру – poDesktopCenter);

в строке Color выбирают цвет заливки формы;

вставка картинки на форму – вкладка Additional, кнопка Image, свойство Picture, кнопка Load, осуществляют выбор файла с картинкой. Для вставленной картинки в панели свойств можно установить в строке stretch значение True (установка размера картинки по размеру формы); в строке transparent значение True (установка прозрачного фона для картинки).