Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 425

9.3.5. Множества

Ситуацию иллюстрирует рис. 9.11. В данном случае даже не потребо­валось вводить расстановочное поле как структуру данных.

Множество — это тип данных, значения которого представляют множе­ства значений другого, ранее определенного типа, называемого базовым ти­пом множества. Особенностью конструктора setofТ является то, что опре­деляемые с его помощью объекты в высшей степени зависят от количества элементов в типе Т и, в принципе, не содержат в себе в качестве компонент значения базового типа. В данном отношении конструктор множеств отлича­ется от ранее рассмотренных нами конструкторов, которые интегрировали значения базовых типов в определяемые ими структуры данных. Правда, самое тупое из приходящих на ум представлений множества: перечень всех элементов данного множества ({3Н1,..., знп} : Т) — конечно, содержало бы эти элементы. Но недостатки данного представления очевидны (тем не менее, в одном из упражнений Вам предлагается найти случаи, когда такое представление множества оптимально, и подумать, как его организовать в таких случаях).

Другое представление множества естественно подсказывается изоморф­ной алгебре множеств математической структурой функций М : Т —>{О, I}. Поскольку функция на конечном множестве, в свою очередь, — то же самое, что массив, то множество может быть представлено как массив булевских значений.

Просим извинения у любителей С/С++/С#, но примитивная логическая структура этих языков не позволяет выразить данную идею столь же просто и ясно. А в какие ловушки ведут попытки держаться слишком близко к деталям реализации, мы уже видели.

Поскольку операции алгебры множеств над множествами А и В сво­дятся к логическим операциям над значениями предикатов х е А х е В, вычисление объединений, пересечений и других операций булевой алгебры сводится к циклу по всем элементам Т с применением соответствующих булевых операций к их элементам. Проверка равенства множеств, включе­ния одного множества в другое и подсчет числа элементов множества также производится за один проход по массиву.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама