4797

Множественный тип данных. Множества

Лекция

Информатика, кибернетика и программирование

Множественный тип данных. Множества. Конечные множества как вычислительные структуры. Предварительное распределение памяти и контроль типов. Ввод/вывод и внешние вычислительные структуры. Файловый тип данных. Последовательные файлы. Файлы прямого до...

Русский

2012-11-27

67 KB

11 чел.

Множественный тип данных. Множества.

Конечные множества как вычислительные структуры.

Предварительное распределение памяти и контроль типов.

Ввод/вывод и внешние вычислительные структуры.

Файловый тип данных. Последовательные файлы.

Файлы прямого доступа.

Множества

Множественный тип

Еще одним сложным стандартным типом данных, определенным в языке Паскаль, является множественный тип. Значением множественного типа данных является множество, состоящее из однотипных элементов. Тип элемента множества называется базовым типом. Базовым типом может быть скалярный или ограниченный тип. Таким образом, множество значений множественного типа - это множество всех подмножеств базового типа, включая и пустое множество. Если базовый тип содержит N элементов, соответствующий множественный тип будет содержать 2N элементов.

Характерное отличие множественного типа - определение на нем наиболее распространенных теоретико-множественных операций и отношений. Это делает множественный тип похожим на простые типы данных. Множественные типы описываются в разделе типов следующим образом :

Type < имя типа > = Set of < базовый тип>

Например,

 а) Type Beta = Set of 100..200;

 б) Type Glas = Set of char ; {Vowel}

 в) Type Color = (red, orange, yellow, green, light_blue, blue, violet);

Paint = Set of Color;

 г) Type TwoDigNum = Set of 10..99;

Var A, B: Beta;

llet, flet: Glas;

last, first: Paint;

 Sinit: TwoDigNum;

Конструктор множества

Множества строятся из своих элементов с помощью конструктора множества. Конструктор представляет собой перечисление через запятую элементов множества или отрезков базового типа, заключенное в квадратные скобки [ , ]. Пустое множество обозначается через [].

 

конструктор


 Элемент

 конструктора

 

Например:

[ ] - пустое множество

[2, 5 ..7] - множество {2, 5, 6, 7}

['A'..'Z', 'O'..'9'] - множество, состоящее из всех прописных латинских букв и цифр

[i + j .. i + 2*j] - множество, состоящее из всех целых чисел между i + j и i + 2j

Отметим, что если в выражении [v1..v2]  v1 > v2, множество [v1 .. v2] - пустое.

Операции и отношения

К операндам - однотипным множествам А и В применимы следующие операции:

А + В - объединение А В

А * В - пересечение А В

А - В - разность А \ В

Между А и В определены также отношения порядка и равенства

А = В,   А <> В,   А < В, А <= В,   А > В,   А >= В;

Отношения порядка интерпретируются как теоретико-множественные включения.

Если А - множество и х - элемент базового типа, то определено отношение принадлежности  х  in  A - x принадлежит A ( x A ).

Каждое из отношений, описанных выше, по-существу является операцией, результат которой имеет тип Boolean. Таким образом, если Init - переменная типа Boolean, возможно присваивание Init := A < B. Возможны такие сравнения

( А = В ) = ( С = D ).

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

А := А * [1 .. 10] + B ;  B := (А + B)*['A' .. 'Z'] ;

Примеры

При реализации языка размеры множеств всегда ограничены константой, зависящей от реализации. Обычно эта константа кратна длине машинного слова. Это происходит потому, что множества реализованы в виде логических (двоичных) векторов следующим образом: каждой координате двоичного вектора однозначно соответствует один из элементов базового типа. Если элемент a принадлежит представляемому множеству A, то значение координаты вектора, соответствующее a, равно 1. В противном случае значение соответствующей координаты равно 0.

Например, если множество A описано как Set of 0..15, то его представляет 16-ти мерный двоичный вектор, координаты которого перенумерованы от 0 до 15, и i-той координате соответствует элемент i базового типа.

Базовый тип :   0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15

Двоичный вектор :    0  0  1  1  0  1  0  1  0  0   0   1     0    1    0    0

Представленное множество :   A = [2, 3, 5, 7, 11, 13]

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

For X := 'A' to 'Z' do

    If (X ='A') or (X ='E') or  (X ='I') or (X ='O') or (X='U')

        then Statement1

        else Statement2

лучше написать

 For X := 'A' to 'Z' do

   If X in ['A','E','I','O','U']

                then Statement1

                else Statement2

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

В системе Turbo-Паскаль максимальное количество элементов в множестве равно 256. Таким образом, в качестве базового типа можно выбрать, например, Char или отрезок 0..255. В заключение раздела приведем пример программы, использующей множественные типы данных.

Пример. Построить множество всех простых чисел из отрезка 2..n  (n 255).

Метод, с помощью которого мы это сделаем, известен как "Решето Эратосфена". Суть этого метода в следующем: Пусть Prime - строимое множество простых чисел и Grating - множество, называемое решетом. Алгоритм начинает работу с Prime = []; Grating = [2..n].

 Шаг основного цикла:

 а. Наименьший элемент Grating поместить в Prime;

 б. Удалить из Grating все числа, кратные этому элементу;

 Алгоритм заканчивает работу при Grating = []

 Program EratosfenGrating;

   Const n = 255;

      Var Grating, Prime: set of 2 .. n ;

             i, Min : integer ;

 Begin

   Grating := [2 .. n] ; Prime := [] ; Min := 2;  {инициализация}

   While Grating <> [] do begin  {основной цикл}

      While not(Min in Grating) do  {поиск наименьшего элемента в решете}

         Min := Min + 1;

         Prime := Prime + [Min] ;  {пополнение множества простых чисел}

         For i := 1 to n div Min do  {исключение кратных из решета}

           Grating := Grating - [i*Min];

    end;

    Writeln('Primes: ');   {вывод множества простых чисел}

     For i := 1 to n do  

        If i in Prime then write(i, ', ')

 End.

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

Предварительное распределение памяти и контроль типов.

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

1.Распределения памяти. Распределение (резервирование) памяти для переменных, описанных в разделе переменных, производит компилятор на этапе генерации кода. Для каждой переменной в ОЗУ отводится определенное место. Размер этой части памяти определяется типом переменной.

2.Правильной интерпретации действий над данными. Например, сложение целых чисел интерпретируется не так, как сложение вещественных чисел или строк.

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

Ввод/вывод и внешние вычислительные структуры.

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

Проблема исследования и реализации внешних вычислительных структур в значительной степени повлияла на широкое распространение ОО подхода к проектированию ВС. В современных системах программирования ВУ во всем своем многообразии описываются как виртуальные объекты, взаимодействующие друг с другом в соответствии со своими протоколами. Но сначала были файлы.   

 

Файловый тип. Файлы.

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

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

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

В результате выполнения программы происходит преобразование одного текстового файла (называемого Input) в другой текстовый файл (называемый Output). Оба эти файла являются стандартными и служат для ввода/вывода данных.

Над файлами можно выполнять два явных вида действий:

1.Просмотр (чтение) файла.

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

Файлы, с которыми работает программа, должны быть описаны в программе. Часть файлов (представляющих собой физические устройства) имеет в операционной системе стандартные имена. Например, для чтения данных с клавиатуры и вывода результатов на экран монитора мы пользуемся стандартными файлами Input и Output. Файл - принтер имеет имя Prn:

Имена нестандартных файлов, используемых в программе, необходимо описывать в разделе переменных. Описание файлового типа соответствует диаграмме:

 

 

Файл, компоненты которого являются символами, называется текстовым и имеет стандартный тип Text:

Type Text = File of Char;

Примеры:    

Type

ExtClass = File of Person;CardList = File of Integer;

Var

F : Text;

Data : File of real;

List1, List2 : CardList;

Class10A, Class10B : ExtClass;

Для работы с нестандартными файлами имя файла должно быть отождествлено с реально существующим объектом - внешним устройством. Именно, если нам необходимо обработать данные из файла, находящегося на магнитном диске и имеющего (внешнее) имя D:\ExtName.dat, мы должны сообщить системе, что работая с файлом IntName (читая из него данные или записывая в него данные), мы работаем с файлом ExtName.dat, находящимся на диске D:.

Для отождествления внутреннего имени файла со внешним именем используется процедура Assign(< внутреннее имя >, < 'внешнее имя'>).

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

Процедура Rewrite(<имя файла>) - открывает файл для записи. Если файл ранее существовал, все данные, хранившиеся в нем, уничтожаются. Файл готов для записи первой компоненты.

Процедура Reset(<имя файла>) - открывает файл для чтения. Файл готов для чтения из него первой компоненты.

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

Для обмена данными с файлами используют процедуры Read и Writе.

Процедура Read(<имя файла>, <список ввода>) читает данные из файла (по умолчанию имя файла - Input). Список ввода - это список переменных.

Процедура Write(<имя файла>, <список вывода>) записывает данные в файл (по умолчанию имя файла - Output). Список вывода - это список выражений.

Если F - файл типа Text, то в списке ввода/вывода допустимы переменные/выражения типа Integer, Real, Char, String[N]. В других случаях типы всех компонент списка должны совпадать с типом компоненты файла.

При работе с файлами применяют стандартные логические функции:

Eof(F) (end of file) - стандартная функция - признак конца файла. Если файла F исчерпан, то Eof(F) = True, в противном случае Eof(F) = False.

Eoln(F) (End of line) - стандартная функция - признак конца строки текстового файла. Если строка текстового файла F исчерпана, то Eoln(F) = True, в противном случае Eoln(F) = False. Функция Eoln определена только для файлов типа Text. Обычно в программах используют либо текстовые файлы, либо файлы, компонентами которых являются структурированные данные (например, записи).

Следует помнить, что данные файловых типов нельзя использовать в качестве компонент других структур данных. Например, нельзя определить массив, компонентами которого являются файлы, запись, полем которой является файл.

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

Пусть F - файл записей вида (поле ключа, поле данных). Требуется сформировать файл G, содержащий те компоненты F, ключи которых удовлетворяют условию: значение ключа - целое число из интервала ]Max, Min [.

Program FileForm;

    Type Component = Record

              Key: Integer; { поле ключа }

              Data: String[20] { поле данных}

            End;

OurFile = File of Component;

     Var F, G : OurFile;

Max, Min : Integer;

X: Component;

  Function Correct(var U: Component): Boolean;

    begin

      Correct := (U.Key < Max) and (U.Key > Min)

     end;

  Begin

    Read(Max, Min);

    Assign(F, 'D:InpFile.dat');  {определено значение F }

    Assign(G, 'D:OutFile.dat');  {определено значение G }

    Reset(F);   {файл F открыт для чтения}

    Rewrite(G);   {файл G открыт для записи}

    While not(Eof(F)) do begin  {цикл чтения F - записи G}

      Read(F, X);  

      If Correct(X) then Write(G, X)

     end;

    Close(G)   {файл G закрыт}

   End;


Элемент конструктора

[

 ]

,

Выражение

Выражение

 Выражение

..

 File

of

Тип компоненты

файловый тип


 

А также другие работы, которые могут Вас заинтересовать

80191. Явление вариантности форм родительного падежа множественного числа в современном русском языке 159.62 KB
  В данной работе при анализе языкового материала были использованы такие общенаучные способы исследования, как наблюдение и эксперимент. Основной общенаучный метод анализа – описательный. Наиболее распространенный способ научного исследования – это наблюдение. Под лингвистическим наблюдением в свою очередь понимаются правила и техника выделения из текста (или потока речи) того или иного факта и включение его в изучаемую систему.
80192. Методы анализа линейных цепей 136 KB
  Все электрические цепи состоящие из сопротивлений емкостей индуктивностей и соединительных проводов линейны. Анализ отклика линейной цепи на известное входное воздействие сводится при этом к известной в математике задаче решения линейного дифференциального уравнения nго порядка с постоянными коэффициентами. Порядок n этого уравнения в радиотехнике принято называть порядком линейной цепи системы.
80193. Нелинейные и параметрические цепи 143.5 KB
  Наиболее часто используют метод анализа нелинейных цепей основанный на линеаризации характеристик НЭ при фильтрации высших гармоник сигнала на выходе цепи. В результате первой операции в безынерционном НЭ происходит такое преобразование формы входного сигнала при котором в его спектре появляются новые гармонические составляющие. Вторую операцию осуществляет линейный фильтр выделяя нужные спектральные составляющие преобразованного входного сигнала. Кусочнолинейная аппроксимация характеристики Нелинейный резонансный усилитель мощности...
80194. Генерация сигналов. Модуляция и детектирование сигналов 138 KB
  Колебательной системой или устройством с самовозбуждением называют динамическую систему преобразующую энергию источника постоянного тока в энергию незатухающих колебаний причем основные характеристики колебаний амплитуда частота форма колебаний и т. Процесс получения переменных сигналов требуемой формы и частоты называют генерированием электрических колебаний. Автогенератор часто просто генератор устройство преобразующее энергию постоянного тока в энергию электрических колебаний требуемой частоты и формы. Автогенератор можно...
80195. Типы и основные характеристики линий связи 357.5 KB
  Типы и основные характеристики линий связи Принципы построения радиоэлектронных систем связи Любую техническую систему действие которой основано на непосредственном использовании высокочастотных электромагнитных колебаний радиодиапазона для сбора передачи извлечения обработки или хранения информации называют радиотехнической системой упрощенно радиосистемой. Линией связи называют физическую среду космическое пространство свободное пространство воздух в нейтральном или ионизированном состояниях земная поверхность морская вода...
80197. Элементная база линейных цепей 163.43 KB
  Таким образом анализируемая RС-цепь при малых τα может осуществлять линейную операцию дифференцирования поданного на нее сигнала. Чтобы определить частотный коэффициент передачи дифференцирующей цепи, запишем комплексную амплитуду тока
80198. Усиление сигналов. Типы и параметры усилителей 99.11 KB
  Во многих радиоэлектронных устройствах имеют место колебания, частоты которых близки к нулю. Для усиления медленно меняющихся во времени сигналов применяют усилители постоянного тока (УПТ). Современные УПТ в основном выполняют в виде интегральных микросхем
80199. Цифровая модуляция. Виды цифровой модуляции 80.5 KB
  число различных его элементов которые преобразуются в последовательность элементов посылок сигнала {Unt} путем воздействия кодовых символов на высокочастотное несущее колебание UНt. Долгое время не находила практического применения изза сложности восстановления в приемнике опорного несущего колебания строго синфазного с несущей частотой принимаемого сигнала. Так как на практике при приеме сигнала сложно определить абсолютное значение начальной фазы то проще определять относительный фазовый сдвиг между двумя соседними символами....