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

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

файловый тип


 

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

26478. Морфофункциональная характеристика кожного покрова 36.5 KB
  3 составляющих: кожа cutis слизистая оболочка tunica mycosa выстилает изнутри органы пищеварения дыхания размножения мочевыделения производные кожного покрова: железы потовые сальные молочные волосы перья чешуя мякиши роговые образования рога копыта когти СUTIS: epidermis располагается с поверхности представлен многослойным плоским ороговевающим эпителием dermis собственно кожа дерма соединительная ткань subcutis подкожный слой соединительная ткань epidermis 2060мкм эктодермальное происхождение...
26479. Морфофункциональная характеристика мякиша 32 KB
  Морфофункциональная характеристика мякиша МЯКИШИ torus упругие утолщения кожного покрова которые служат для опоры конечности о землю и обеспечивает амортизацию обладают большой чувствительностью осязание имеют хорошо развитый подкожный слой липоциты эласт. волокна располагаются на автоподиях Лошадь запястье пальмарно заплюсна плантарно каштаны пясть плюсна шоры пальцевый мякиш стрелка внутри копыта Собака на грудной запястные пястные пальцевые на тазовой плюсневые пальцевые Свинья КРС...
26480. СПЛАНХНОЛОГИЯ 24.5 KB
  Внутренние органы оъединяют в 3 аппарата: пищеварительный: система органов пищеварения пищеварительный канал пищеварительные железы вспомогательный аппарат жевательные мышцы челюсти зубы мышцы брюшного пресса и т. дыхательный: система органов дыхания дыхательные пути носовая полость глотка гортань трахея органы дыхания лёгкие вспомогательный аппарат органы дыхыхательной распираторики грудная клетка диафрагма мышцы брюшного пресса мочеполовой: почки мочевыводящие...
26481. МЫШЦЫ ГРУДНОЙ КЛЕТКИ 39.5 KB
  cerratus dorsalis craniflis i caudalis e поверхностная мышцы прикрывает мускулатуру позвоночного столба лежит дорсально в области холки в области поясницы закрепление различно у разных видов = инспиратор слабо развит у КРС экспираторнаиболее хорошо выражен у лошади и собаки иннервация венральные ветви спинномозговых нервов межрёберные закрепляется широким апоневрозом на остистых отростках грудных позвонков 58 поясничных позвонков 15 закрепляются зубцами на верхней трети и теле рёбер Л 512 КРС 58...
26483. ГОЛОВНОЙ МОЗГ (ENCEPHALON) – высший отдел ЦНС 40 KB
  С дорсальной поверхности располагается ромбовидная ямка дно Iv мозгового желудочка vixii пара ЧМН С вентральной поверхности 2 пирамидальных пути tractus pyramidalis lateralis et medialis соединяют кору ГМ и СМ Впереди трапециевидное тело corpus trapecioideus тройничный нерв подъязычный XII пара каудально перекрещивающиеся пиромидальные пути функции продолговатого мозга : центр сердечнососудистой деятельности и дыхания центр защитных рефлексов рвота понос слезоотделение чихание кашель центр пищеварительной...
26484. Распорядительная документация. Подготовка и оформление приказов 40.5 KB
  Основанием для издания приказа являются: нормативные документы государственных или муниципальных органов; решения совета директоров общих собраний акционеров; производственная необходимость. Подготовка приказа включает следующее: изучения существа вопроса; сбор необходимых сведений; подготовка проекта приказа; согласование проекта; подписание руководителем. Приказы оформляются на общем бланке предприятия или на бланке приказа. Датой приказа является дата его подписания руководителем.
26485. Справочно-информационная документация. Справка. Виды справок 44 KB
  Справки бывают двух основных видов: справки подтверждающие работу учебу оплату труда место проживания и т. составляемые по запросам граждан; справки по производственным вопросам составляемые по запросу руководства. Справки по запросам граждан работников выдает руководство организации с указанием специальности должности квалификации периода работы и размера заработной платы ст. Справки по запросам граждан работников как правило оформляются на бланках справок формата А5 имеющих адресные данные предприятия и трафаретный...
26486. Современное деловое письмо. Виды и оформление служебного письма 881.5 KB
  Виды и оформление служебного письма.д По содержанию и назначению письма могут быть: инструкционные содержащие указания и разъяснения подведомственным организациям; гарантийные дающие гарантии выполнения какихлибо обязательств оплаты сроков и т.; информационные содержащие полезную для адресата информацию а также просьбы напоминания предложения; рекламные рекламирующие товары и услуги; коммерческие содержащие конкретные предложения по заключению сделок; рекламационные содержащие претензии по качеству товаров или услуг;...