- •1. Cтруктуры данных и алгоритмы
- •1.1. Понятие структур данных и алгоритмов
- •1.2. Информация и ее представление в памяти
- •1.3. Классификация структур данных
- •1.4. Операции над структурами данных
- •1.5. Структурность данных и технология программирования
- •2. Простые структуры данных
- •2.1. Числовые типы
- •2.1.1. Целые типы
- •2.1.2. Вещественные типы
- •1). Десятичное число 15.375;
- •2). Десятичное число -0.5;
- •3). Десятичное число -25.75;
- •4). Число 0.0;
- •5). Числа верхней и нижней границ положительного диапазона
- •2.1.3. Операции над числовыми типами
- •2.2. Битовые типы
- •2.3. Логический тип
- •2.4. Символьный тип
- •2.5. Перечислимый тип
- •2.6. Интервальный тип
- •2.7. Указатели
- •2.7.1. Физическая структура указателя
- •2.7.2. Представление указателей в языках программирования
- •2.7.3. Операции над указателями.
- •3. Статические структуры данных
- •3.1. Векторы
- •3.2. Массивы
- •3.2.1. Логическая структура
- •3.2.2. Физическая структура
- •3.2.3. Операции
- •3.3 Множества
- •3.3.1 Множества и математика
- •3.3.1.1 Способы задания множеств
- •3.3.1.2 Операции над множествами
- •3.3.1.3 Множественный тип и его свойства
- •3.3.1.4 Переменные и константы множественных типов
- •3.3.1.5. Выражения множественного типа
- •3.3.2. Представление множеств в памяти эвм
- •3.3.2.1. Числовые множества
- •3.3.2.2. Символьные множества
- •3.3.2.3. Множество из элементов перечислимого типа
- •3.3.2.4. Множество от интервального типа
- •3.3.2.5. Операции над множествами
- •3.4. Записи
- •3.4.1. Логическое и машинное представление записей
- •3.4.2. Операции над записями
- •3.5. Таблицы
- •3.6.2. О сложности алгоритмов
- •3.6.3. Сортировка подсчетом
- •3.6.4. Сортировка включением
- •3.6.4.1. Простое включение
- •3.6.4.2.Метод Шелла (модифицированный)
- •3.6.5. Сортировка извлечением
- •3.6.5.1.Простое извлечение
- •3.6.5.2.Древесная сортировка(модифицированный)
- •3.6.6. Сортировка обменами
- •3.6.6.1. Пузырьковая сортировка
- •3.6.6.2. Быстрая сортировка (Хоара) (модифицированный)
- •3.6.7. Сортировка слиянием
- •3.6.8. Сортировка распределением
- •3.6.8.1. Вырожденное распределение
- •3.6.8.2. Сортировка распределением
- •3.6.9. Сравнительный анализ
- •3.7. Операции логического уровня над статическими структурами. Поиск
- •3.7.1. Линейный (последовательный) поиск
- •3.7.2. Быстрый последовательный список
- •3.7.3. Дихотомический (бинарный) поиск
- •3.7.4. Интерполяционный поиск
3.3.1.4 Переменные и константы множественных типов
I. Описав типы множеств, можно описывать переменные множественных типов, например:
Var
m1:Simbol;
m2:Litera;
m3:Number;
m4:Diapazon;
m5:Name;
В процессе выполнения программы эти переменные могут приобретать значения конкретных множеств. При этом
1)элементами множества m1 могут быть любые символы таблицы кодов ASCII в любых сочетаниях,
2)элементами множества m2-любые символы из интервала ' а ' .. ' z ',
3)элементами множества m3-любые числа от 0 до 255 и т.д.
Любое из этих множеств может также быть пустым.
II. Любая константа множественного типа представляет собой конкретное множество. Она имеет вид перечня своих элементов, записанных через запятую в квадратных скобках. Порядок следования элементов в перечне может быть произвольным. Основные варианты таковы:
1.Элементы множества имеют вид отдельных значений, например:
[ ' с ', ' а ', ' е '], [76, 3, 20, 105];
2.Элементы множества имеют вид отрезков значений, например:
[5 .. 12], [' х ' .. ' z ', ' а ' .. ' d '];
Элементы множества имеют вид выражений, например:
[' s ', chr(109)], [Round(sin(1)), Abs(-7), 2+3];
В частном случае константа не содержит ни одного элемента, т.е. имеет вид [ ]. Такая запись соответствует пустому множеству.
Синтаксис записи констант допускает повторения и наложения элементов. В таком случае «лишние» элементы убираются из состава константы автоматически. Для отрезка значений допустимо указание сначала большего, а затем меньшего значения. Такой элемент считается пустым. Например, константа [7,5 .. 8,7] воспринимается просто как [5 .. 8], а константа [7.8 .. 5,7]- как [7].
Константа множественного типа могут фигурировать в составе описаний именованных и типизированных констант. Например:
Const
k=5;
m6=[' a ' .. ' k ', ' x ']; {именованная константа}
m7=Litera=[' с ', ' а ', ' е ']; {типизированная константа}
m8=[2*3, k] {именованная константа}
m9:Diapazon=[76, k, 10 .. 20]; {типизированная константа}
Данный пример показывает, что в качестве элементов множеств можно использовать именованные константы простых типов. Так множественные константы m8 и m9 используют в качестве элементов именованную константу k
Попытка включить в данном случае в множество типизированную константу или переменную приводит к ошибке.
Непосредственно в программе переменным и типизированным константам множественных типов могут присваиваться те или иные значения с помощью оператора присваиванияY:=X, где X- выражение множественного типа.
Пример выражения:
Const E=15;
Var S:Set Of Byte;
BitNumb: Byte;
Begin S:= [ ]; {обнуление множества}
S:=S+[E] {запись числа во множество}
BitNumb:=E mod 8; {определения остатка от деления на 8}
Writeln (BitNumb); {на экране ?7}
End.
3.3.1.5. Выражения множественного типа
Компонентами выражений множественного типа могут быть переменные и константы множественных типов, а также множества- функции(будут рассмотрены далее)
При построении выражений использовать бинарные операции
суммы «+»;
разности «-»;
пересечения «*» множеств.
Рассмотрим результаты выполнения этих операций на примерах с участием двух множеств mn1=[' а ' .. ' с '] и mn2=[' b ' .. ' d '];
1.Сумма mn1+mn2 дает результат [' а ' .. ' d '], т.е. каждый элемент суммы двух данных множеств принадлежит хотя бы одному из mn1 и mn2.
2.Разность mn1-mn2 дает результат =[' а '], т.е. разность двух данных множеств содержит элементы множества mn1, за исключением элементов, содержащихся в mn2.
3.Пересечение mn1*mn2 дает результат [' b ' .. ' с '], т.е. каждый элемент пересечения данных множеств принадлежит обоим данным множествам.
Как и в обычных арифметических выражениях, операции над множествами имеют приоритеты, а последовательностью их выполнения можно управлять с помощью круглых скобок. Наиважнейший приоритет у операции пересечения. Операции суммы и разноcти имеют равный приоритет и в составе выражения выполняются в порядке их записи. Рассмотрим примеры.
[2,3] - [2,3] * [2] = [3] -операция пересечения выполняется в первую очередь
1.2 ([2,3] - [2,3]) * [2] = [ ] -при использовании скобок
2.1 [2,3] + [2,3] - [2] = [3] , т.к. операции выполняются последовательно
2.2 [2,3] + ([2,3] - [2]) = [2,3] –при использовании скобок
Соответствующие по типу множества можно сравнивать между собой и таким образом строить отношения. Эти отношения можно обычным образом включать в состав логических выражений.
Рассмотрим результат сравнения на примерах с участием двух множеств
mn1=[' Х ', ' Y '] и mn2=[' Х ', ' Z ']
1.Отношение mn1=mn2 представляет собой условие совпадений множеств, когда любой элемент каждого из них одновременно принадлежит и другому множеству; для данного примера значение этого отношения FALSE;
2.Отношение mn1<>mn2 представляет собой условие несовпадения множеств, когда они отличаются хотя бы одним элементом; для данного примера значение этого отношения TRUE;
3.Отношение mn1 ≤ mn2 истинно, если множество mn1 является подмножеством множества mn2; для данного примера значение этого отношения TRUE;
4.Отношение <элемент>In<множество> истинно, если элемент принадлежит множеству; например, ' х ' In mn1 = TRUE, ' z ' In mn1 = FALSE.
