Содержание

Структура данных «множество»

Шпак Вячеслав 10в1

План работы

Логическая структура.

Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, 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. 

Числовые множества

Стандартный числовой тип, который может быть базовым для формирования множества - тип byte.

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

где @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 будет распределена как показано на рис.

Распределение памяти для переменной типа 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 байта.

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

Представление переменной типа 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 - в противном случае.