1 Понятие структур данных и алгоритмов

Вид материала

Документы

Содержание Логическая структура. Физическая структура. Рис. 3.7. Многосвязная структура для представления матрицы A

Подобный материал:

• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• А. М. Горького математико-механический факультет кафедра алгебры и геометрии Библиотека, 334.84kb.
• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• Об использовании структур представления данных для решения возникающих задач; знать, 116.73kb.
• Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
• «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
• Утверждаю, 254.87kb.
• Язык описания алгоритмов начертательной геометрии adgl, 70.57kb.
• Программа дисциплины Математическое программирование Семестры, 10.84kb.
• Метод принятия решения в выборе варианта реализации алгоритмов при разнородных условиях, 70.86kb.

3.3. Множества

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

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

Физическая структура.

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

Рис. 3.7. Многосвязная структура для представления матрицы A

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

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

ByteNumber = (E div 8)-(min div 8),

номер бита внутри этого байта по формуле:

BitNumber = E mod 8

{===== Программный пример 3.3 =====}

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.

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

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

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

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

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

Например, S : set of byte; S:=[15,19];

Содержимое памяти при этом будет следующим:

@S+0 - 00000000 @S+2 - 00001000

@S+1 - 10000000 . . . . . .

@S+31 - 00000000

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

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

Например, S : set of char; S:=['A','C'];

В этом случае представление множества S в памяти выглядит следующим образом :

@S+0 - 00000000 . . . . . .

. . . . . . @S+31 - 00000000

@S+8 - 00001010

Таблица 3.3

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

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



Рис. 3.8. Распределение памяти для переменной типа set of Video

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

@S+0 - 10000010

@S+1 - 00000000

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

Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип 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 байта.

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



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

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

Например, Type S = 510..520;

Var I : S;

begin I:=[512]; end.

Представление в памяти переменной I будет:

@i+0 - 00000000 @i+1 - 00000001

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

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

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