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

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

файловый тип


 

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

34966. Совокупное предложение (две модели). Неценовые факторы совокупного предложения 116.5 KB
  Закон совокупного предложения при более высоком уровне цен у производителей возникают стимулы увеличения объема производства и соответственно увеличивается предложение изготовляемых товаров. Неценовые факторы совокупного предложения: Изменение цен на ресурсы: Наличие внутренних ресурсов Цены на импортные ресурсы Господство на рынке Изменение в производительности объем производства общие затраты Изменения правовых норм: Налоги с предприятий и субсидии Государственное регулирование Совокупное предложение: классическая и...
34967. Совокупный спрос. Неценовые факторы совокупного спроса 84 KB
  Совокупный спрос. Неценовые факторы совокупного спроса Совокупный спрос общий платежеспособный спрос на все товары и услуги производимые в экономике. Совокупный спрос реальный объем производимой в обществе продукции по сути ВВП который потребители готовы приобрести при каждом данном уровне цен в экономике. При расчете ВВП по потоку расходов выделялись четыре расходующие группы предъявляющие спрос на национальном рынке: население бизнес государство иностранные потребители.
34968. Способы измерения ВВП 29 KB
  Способы измерения ВВП ВВП рассчитывается 3 методами: По доходам ВВП = Национальный доход амортизация косвенные налоги субсидии чистый факторный доход изза границы ЧДиФ или чистый факторный доход иностранцев работающих на территории данной страны ЧДФ где: Национальный доход = заработная плата арендная плата процентные платежи прибыль корпораций Данная формула характеризует ВВП по доходам в Системе национальных счетов ООН версия 2008 года. По расходам где ВВП = Конечное потребление Валовое накопление капитала...
34969. Структура прибыли в микроэкономике 37 KB
  Прибыль = Выручка Затраты Бухгалтерская прибыль это часть общего дохода фирмы после возмещения всей стоимости факторов производства от внешних поставщиков разница между доходами и внешними издержками Нормальная прибыль часть внутренних издержек фирмы является свидетельством самоокупаемости фирмы или безубыточности Чистая экономическая прибыль меньше бухгалтерской прибыли на величину внутренних издержек включает нормальную прибыль разница между доходами и экономическими издержками.
34970. Сущность и виды экономических систем 43 KB
  Во всех экономических системах для производства требуются экономические ресурсы а результаты хозяйственной деятельности распределяются обмениваются и потребляются. В то же время в экономических системах есть также элементы которые отличают их друг от друга: социальноэкономические отношения; организационноправовые формы хозяйственной деятельности; хозяйственный механизм; система стимулов и мотиваций участников; экономические связи между предприятиями и организациями. Современная рыночная экономическая система Отличительные черты:...
34971. Теории стоимости 60.5 KB
  Многие западные экономисты отрицают трудовой характер стоимости. Они акцентируют внимание на полезности потребительной стоимости товара как на главном мотиве к обмену. Трудовая теория стоимости Согласно этой теории в основе стоимости лежит общественно необходимое рабочее время затраты труда на производство товара при этом труд подразумевается не конкретный а абстрактный упрощённый и усреднённый для текущих типичных условий производства Адам Смит сделал значительный шаг вперёд в объяснении природы стоимости.
34972. Требования к бюджету 39.5 KB
  часто возникает ситуация когда доходы бюджета налоговые и неналоговые не покрывают все необходимые для соответствующего уровня бюджетной системы расходы. В мировой практике существуют следующие виды дефицита госбюджета: циклический дефицит спад деловой активности и сокращение налоговых поступлений. структурный дефицит положительное либо отрицательное сальдо бюджета при наличии естественного уровня безработицы при наличии естественного уровня ВВП при ставках налога и трансфертных платежей определенных законодательством. Источники...
34973. Теория и практика налогообложения 27 KB
  Субъект налога физическое или юридическое лицо которое согласно действующему законодательству обязано уплачивать налог. Объект налога доход или имущество с которого начисляется налог. Ставка налога размер налоговых начислений на единицу объекта налога. Пропорциональные ставки предполагают равное в процентном отношении обложение различных по своему денежному выражению объектов налога.
34974. Фискальная политика, ее цели и инструменты 24.5 KB
  Фискальная политика это политика регулирования правительством прежде всего совокупного спроса. Стимулирующая фискальная политика применяется при спаде имеет целью сокращение рецессионного разрыва выпуска и снижение уровня безработицы и направлена на увеличение совокупного спроса совокупных расходов. Сдерживающая фискальная политика используется при буме имеет целью сокращение инфляционного разрыва выпуска и снижение инфляции и направлена на сокращение совокупного спроса совокупных расходов.