Zbiorowy typ danych

Typ zbiorowy to typ danych w określonym języku programowania udostępniający wartości i operacje na zbiorach.

Pojęcie typu zbiorowego

Typ ten jest więc komputerową implementacją matematycznego pojęcia zbioru i operacji teoriomnogościowych. Zwykle jednak typ zbiorowy ma dość ograniczone możliwości, głównie co do ilości elementów zbiorów, co wynika głównie z fizycznej reprezentacji w pamięci wartości typu zbiorowego. Bardziej zaawansowana implementacja zbiorów wymaga więc indywidualnego zaprogramowania typu i operacji dla określonych potrzeb. Wartości typu zbiorowego reprezentowane są w kodzie źródłowym za pomocą literałów zbiorowych.

Stosunkowo niewiele języków oferuje w swoim standardzie typ zbiorowy, najbardziej znanym z takich języków jest Pascal. Współczesne implementacje wielu języków i biblioteki programistyczne, wprowadzają typ zbiorowy także do tych języków, w których nie było takiego typu danych.

Typ zbiorowy w językach programowania

Borland Pascal

Typ zbiorowy może zostać zdefiniowany jako zbiór wartości pewnego typu nazywanego typem bazowym. Język nakłada istotne ograniczenia:

• typ bazowy musi być typem porządkowym
• liczba elementów nie może przekroczyć 256 (co wynika ze sposobu reprezentacji typu porządkowego w pamięci komputera omówionej dalej)
• liczby porządkowe typu bazowego muszą należeć do przedziału od 0 do 255 (wyklucza to więc np. typ integer jako typ bazowy, natomiast dopuszczalne są Byte, Char, typ okrojony, typ wyliczeniowy).

Definicja typu zbiorowego ma postać:

 type identyfikator_typu=set of typ_bazowy;

W Pascalu typ zbiorowy jest reprezentowany w pamięci jako tablica bitów. Bit na odpowiedniej pozycji, w porównaniu do typu bazowego, oznacza w zależności od wartości tego bitu czy dany element należy do zbioru (bit ustawiony na 1), czy nie (bit ustawiony na 0). Za pracą 1) (część I.C, str. 1112), można podać, że:

• liczba bajtów zajęta przez zbiór wynosi: (Max div 8)-(Min div 8)
• numer bajta, w którym jest określony bit odpowiadający elektowi o rozpatrywanym numerze porządkowym N: (N mod 8)-(Min div 8)
• numer bitu w bajcie: (N mod 8),

gdzie:

• div: operator dzielenia całkowitoliczbowego
• mod: operator reszty z dzielenia całkowitoliczbowego
• Max: maksymalny numer porządkowy
• Min: minimalny numer porządkowy.

Do operowania na wartościach typu zbiorowego w Borland Pascalu służą:

• operatory teoriomnogościowe
  • suma zbiorów '+'
  • różnica zbiorów '-'
  • iloczyn zbiorów '*'

Wymaga się aby oba argumenty były typami zbiorowymi o zgodnych typach bazowych, wynik jest typu zbiorowego.

• operatory relacji
  • równość zbioru: '='
  • nierówność zbioru: '<>'
  • zawieranie zbioru: '<='
  • zawieranie zbioru: '>='
• operator zawierania elementu w zbiorze 'in'

Wynik operatorów relacji i zawierania jest typu logicznego.

Modula 2

Typ zbiorowy definiuje się podobnie jak w Pascalu jak zbiór wartości pewnego typu bazowego:

 identyfikator_typu=SET OF typ_bazowy

Typ bazowy musi być typem wyliczeniowym lub okrojonym. Ograniczenia co do ilości elementów zależne są od implementacji. Dostępne są operacje:

• INCL(zbiór, element) – dołączenie elementu do zbioru
• EXCL(zbiór, element) – usunięcie elementu ze zbioru.

W języku występuje również predefiniowany zbiór BITSET, który jest zbiorową impelemtacją typu bitowego.

Operacje:

• suma zbiorów '+'
• różnica zbiorów '-'
• iloczyn zbiorów '*'
• różnica symetryczna '/'
• przynależność do zbioru 'IN'

Icon

W języku Icon predefiniowany jest typ zbioru znaków, o oznaczniku 'cset'. Język dostarcza następujące operacje na zbiorach:

• rozmiar zbioru: *zbiór
• dopełnienie zbioru: ~zbiór
• iloczyn: z1**z2
• suma: z1++z2
• różnica: z1--z2.

Należy zauważyć, że zbiór znaków reprezentowany przez literały takie jak 'a', 'aa', 'aaaa', jest tym samym zbiorem jednoelementowym. Inna wartość jednak będzie łańcucha znaków powstałego z konwersji każdego z ww. literałów.

Język Icon, jako sukcesor języka Snobol jest w dużej mierze nastawiony na przetwarzanie napisów. Stąd wbudowany mechanizm automatycznej konwersacji zbioru znaków na łańcuch znaków.

Wbudowane zbiory znaków reprezentowane są przez słowa kluczowe:

• zbiór wszystkich 256 znaków: &cset
• zbiór 128 znaków ASCII: &ascii
• zbiór małych liter: &lcase
• zbiór dużych liter: &ucase.

Bibliografia

• AndrzejA. Marciniak AndrzejA., Borland Pascal 7.0 z elementami programowania, Biblioteka Użytkownika Mikrokomputerów, Poznań: Nakom, 1994, ISBN 83-85060-53-7, ISSN 0867-6011 [dostęp 2019-06-16] .brak strony (książka)
• NiklausN. Wirth NiklausN., JaninaJ. Mincer-Daszkiewicz JaninaJ., Modula 2, Biblioteka Inżynierii Oprogramowania, Warszawa: Wydawnictwa Naukowo-Techniczne, 1987, ISBN 83-204-0828-8 [dostęp 2019-06-16] .brak strony (książka)
• Ralph E.R.E. Griswold Ralph E.R.E., Madge T.M.T. Griswold Madge T.M.T., PawełP. Gizbert-Studnicki PawełP., Icon, Biblioteka Inżynierii Oprogramowania, Warszawa: Wydawnictwa Naukowo-Techniczne, 1987, ISBN 83-204-0871-7 [dostęp 2019-06-16] .brak strony (książka)