4797

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

Лекция

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

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

Русский

2012-11-27

67 KB

12 чел.

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

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

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

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

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

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

Множества

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

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

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

файловый тип


 

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

35088. Формирование лихорадочных реакций в фило- и онтогенезе 74.33 KB
  Интеграция температурных сигналов и температуры самого гипоталамуса формирует эффекторные импульсы проходящие преимущественно по симпатическим нервам и определяющие состояние обмена веществ интенсивность периферического кровообращения дрожь одышку. Особое место в биохимии опухолей занимает изучение обмена углеводов и выработки энергии. Нарушение регуляции обмена веществ основного обмена ТИПИЧЕСКИЕ НАРУШЕНИЯ ОБМЕНА ВЕЩЕСТВ. НАРУШЕНИЯ РЕГУЛЯЦИИ ОБМЕНА ВЕЩЕСТВ Обмен веществ или метаболизм в организме определяется наследственными...
35089. Інформаційне забезпечення юридичної діяльності 3.25 MB
  Вступ В розділах посібника користувачі зможуть отримати поглибленні знання: зі створення інформаційних систем ділового та юридичного призначення у середовищі СУБД MS Access зі створювання електронних шаблонів з полями форм для юридичних та інших документів зі створення серійних документів на основі злиття табличних даних та зразка основного документа зі створювання та використовування макросів для автоматизації підготовки документів у MS Word та MS Excel. До виконання завдань необхідно обов'язково ознайомитися з теоретичними основами баз...
35090. Виды кишечных швов 21.68 KB
  В основе большинства операций на желудочно-кишечном тракте лежит кишечный шов. Под термином кишечный шов подразумевают все виды швов накладываемых на стенку полого органа желудочно-кишечного тракта пищевод желудок кишечник а также и на другие полые органы имеющие брюшинный покров мышечную оболочку подслизистый слой и слизистую оболочку жёлчный и мочевой пузырь. Главные требования к кишечному шву: кишечный шов должен быть прочным т. после наложения шва...
35091. ПРОЕКТ СОЗДАНИЯ МОЛОДЕЖНОГО ТУРА С ВКЛЮЧЕНИЕМ АНИМАЦИОННЫХ ПРОГРАММ В ТУРФИРМЕ «WORLD TRAVEL» 903 KB
  Турфирма World Travel является туроператором организующим преимущественно развлекательные туры за рубеж: в Египет Турцию Болгарию; а также на территории курортных районов России. World Travel обеспечивает высокий уровень обслуживания клиентов благодаря: высокому профессионализму команды; собственным чартерным рейсам; собственному автобусному парку; прямым связям с крупнейшими российскими и зарубежными туристскими фирмами отелями и авиакомпаниями. Турфирма предлагает своим клиентам спектр туристских услуг: отдых экскурсионные...
35092. Расчет главной балки 1.26 MB
  Подбор сечения балки настила. Расчёт главной балки. Компоновка сечения главной балки. Изменение сечения главной балки по длине пролета.
35093. Здоровье ребенка и здравый смысл его родственников 1.91 MB
  Евгений Комаровский ЗДОРОВЬЕ РЕБЕНКА И ЗДРАВЫЙ СМЫСЛ ЕГО РОДСТВЕННИКОВ Я полагаю что мы пришли после других для того чтобы делать лучше их чтобы не впадать в их ошибки в их заблуждения и суеверия. Зачем читать о правилах питания беременной женщины когда у ребенка запор Открываем главу про запор получаем необходимые сведения и с чувством глубокого удовлетворения пытаемся претворить в жизнь советы и рекомендации.
35094. Социальное влияние 6.33 MB
  Вопросы и упражнения Глава 3ВЛИЯНИЕ НА УСТАНОВКИ ЧЕРЕЗ ПОВЕДЕНИЕ:ДЕЙСТВИЯ СТАНОВЯТСЯ УБЕЖДЕНИЯМИ Систематический анализ: активное мышление порождает прочные установки Установки: независимые зависимости Установки переходят в поведение: у последней черты.
35095. Зубчатые передачи. Подрезание профиля зуба. Корригирование зубчатого колеса 340.5 KB
  В машиностроении принято малое зубчатое колесо с меньшим числом зубьев называть шестернёй а большое колесом. Зубчатые колёса обычно используются па́рами с разным числом зубьев с целью преобразования вращающего момента и числа оборотов валов на входе и выходе. А Поперечный профиль зуба Профиль зубьев колёс как правило имеет эвольвентную боковую форму. Однако существуют передачи с круговой формой профиля зубьев передача Новикова с одной и двумя линиями зацепления и с циклоидальной.
35096. Анализ хозяйственной деятельности предприятия 11.34 MB
  Переход к рыночной экономике требует от предприятий повышения эффективности производства конкурентоспособности продукции и услуг на основе внедрения достижений научнотехнического прогресса эффективных форм хозяйствования и управления производством преодоления бесхозяйственности активизации предпринимательства инициативы и т. Например чтобы понять сущность себестоимости продукции необходимо знать не только из каких элементов она состоит но и от чего зависит ее величина по каждой статье затрат. Чем...