====== Структура данных «множество» ======
Шпак Вячеслав 10в1 
====== План работы ======
  * Сбор информации (22.01.09г - )
  * Обработка и форматирование информации( - )
  * Разработка сайта( - )
  * Создание презентации в Microsoft Office PowerPoint 2007 ( - )
====== Логическая структура. ======

__//**Множество**//__ - //такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть [[http://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B9%D1%82|byte]], [[http://msdn.microsoft.com/ru-ru/library/7sx7t66b.aspx|char]] и производные от них типы.// ====== Физическая структура. ======


Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт. 

Число байтов, выделяемых для данных типа множество, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества. 

Номер байта для конкретного элемента Е вычисляется по формуле: 

      ByteNumber = (E div 8)-(min div 8), 
номер бита внутри этого байта по формуле: 

      BitNumber = E mod 8
 ''Программный пример '' 
     const max=255; min=0; E=13;
     var  S : set of byte;
          ByteSize, ByteNumb, BitNumb  : byte;
     begin
        S:=[];                 {    обнуление множества         }
        S:=S+[E];              {    запись числа в множество    }
        ByteSize:=(max div 8)-(min div 8)+1;
        Bytenumb:=(E div 8)-(min div 8);
        BitNumb:=E mod 8;
        writeln(bytesize);     {     на экране 32               }
        writeln(bytenumb);     {     на экране 1                }
        writeln(bitnumb);      {     на экране 5                }
     end. 

===== Числовые множества =====
 
 Стандартный числовой тип, который может быть базовым для формирования множества - тип [[http://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B9%D1%82|byte]]. 

Множество хранится в памяти как показано в таблице. 


{{:tema:tab33.gif|}}



где @S - адрес данного типа множество. 

Бит поля установлен в 1, если элемент входит в множество, и в 0 - если не входит. 

    Например,  S : set of byte;   S:=[15,19];
    Содержимое памяти при  этом будет следующим:
   @S+0 - 00000000     @S+2  - 00001000
   @S+1 - 10000000     .  .  . .  .  .
                       @S+31 - 00000000

=====  Символьные множества   =====

 

Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов. 

     Например, S : set of char;  S:=['A','C'];
В этом случае представление множества S в памяти выглядит следующим образом : 

   @S+0 - 00000000        .  .  .  .  .  .
   .  .  .  .  .  .       @S+31 - 00000000
   @S+8 - 00001010


=====  Множество из элементов перечислимого типа  =====

 Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от количества элементов в перечислимом типе.

     Пример:
      Type
         Video=(MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA);
      Var
         S : set of Video;
В памяти будет занимать :
ByteSize = (9 div 8)-(0 div 8)+1=2 байта
При этом память для переменной S будет распределена как показано на рис. 
{{:tema:pic38.gif|}}
=====  Распределение памяти для переменной типа set of Video  =====

 


Если выполнить оператор S:=[CGA,SVGA], содержимое памяти при этом будет: 

  
             @S+0  - 10000010
             @S+1  - 00000000

=====  Множество от интервального типа  =====

 

Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от количества элементов, входящих в объявленный интервал. 

     Например,
       type    S=10..17;
       var     I:set of S;
Это не значит, что первый элемент будет начинаться с 10-того или 0-ого бита, как может показаться на первый взгляд. Как видно из формулы вычисления смещения внутри байта 10 mod 8 = 2, смещение первого элемента множества I начнЯтся со второго бита. И, хотя множество этого интервала свободно могло поместиться в один байт, оно займЯт (17 div 8)-(10 div 8)+1 = 2 байта. 

В памяти это множество имеет представление как на рис.

{{:tema:pic39.gif|}}


===== Представление переменной типа set of S  =====

 


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

     Например, Type  S = 510..520;
               Var   I : S;
               begin  I:=[512];  end.
     Представление в памяти переменной I будет:
     @i+0 - 00000000    @i+1 - 00000001

===== Операции над множествами =====

 

Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции: 

1) Объединение множеств: S2+S3. Результатом является множество, содержащее элементы обоих исходных множеств. 
2) Пересечение множеств: S2*S3. Результатом является множество, содержащее общие элементы обоих исходных множеств. 
3) Проверка на вхождение элемента в множество: a in S1. Результатом этой операции является значение логического типа - true, если элемент a входит в множество S1, false - в противном случае.