Radomíra Duží L06615
Datový typ množina Množina slouží k uložení prvků stejného bázového ordinárního typu. Bázové typy - jsou typy, jejichž hodnot mohou prvky množiny nabývat. Nesmí obsahovat více než 256 přípustných hodnot ani hodnoty záporné, číselné hodnoty tvoří celá čísla. Jedná se o typy byte (čísla), char(znaky), boolean, mohou to být také výčtové typy.
Deklarace množiny
set of ...
Příklady deklarací: (Obecně) Type název = set of bázový typ; Type Mnozina = set of byte; Type Znaky = set of char; Type Cisla = 1..10 Výčtový typ: Type vycet = (cervena, modra, zluta) var barva : set of vycet; Deklarace proměnné typu množina: var mnozina: set of bázový typ; V paměti počítače jsou množiny reprezentovány jako posloupnost bitů, každému prvku množiny je v paměti počítače vyhrazen 1 bit, hodnota 1 je užita, je-li prvek v odpovídajícím ordinárním pořadí uložen v množině, v opačném případě se hodnota rovná 0. 1
0
0
1
Konstrukce množiny: Hodnoty do množiny přiřazujeme pomocí hranatých závorek: mnozina:= [] - prázdná množina mnozina:= [1,2,3,4,5] mnozina:= [1..5] (množina, jejíž prvky mohou nabývat hodnot 1 až 5) mnozina:= [1,2, 4..8,15] (množina s prvky 1,2, 4 až 8, 15) mnozina:= [cervena, modra, zluta] mnozina:= [‘A’,’E’,’I’,’O’,’U’] Operace s množinami: Operace na množinách: 1. union (A,B,C)
do C přiřadí sjednocení A a B
2. intersection (A,B,C)
do C přiřadí průnik A a B
3. difference (A,B,C)
do C přiřadí množinový rozdíl A - B
4. member (x,A)
vrátí TRUE, když prvek x patří do množiny, jinak vrátí FALSE
5. makenull (A)
vytvoří prázdnou množinu A
6. insert (x,A)
vloží prvek x do množiny A
7. delete (x,A)
odstraní prvek x z množiny A, pokud v ní takový prvek existuje
8. min (A), max (A)
vrací minimální (resp. maximální) hodnotu prvku v množině A
9. equal (A,B)
vrátí TRUE, pokud A=B, jinak vrátí FALSE
10. assign (A,B)
do množiny A přiřadí hodnotu B
Implementace množiny uspořádaným lineárním seznamem V případě implementace množiny uspořádaným lineárním seznamem předpokládáme, že množinu tvoří jednotlivé prvky seznamu. V podstatě vytváříme uspořádaný seznam, do nějž je nutné vkládat prvky ve správném pořadí (prvek s nejnižší hodnotou na začátek seznamu, prvek s nejvyšší hodnotou pak na jeho konec). Prvek s určitou hodnotou se v seznamu může vyskytovat pouze jedenkrát. Deklarace type ukaz = ^mnozina; mnozina = record
hodn: Integer; dalsi: ukaz
end; var pA, pB, pC: ukaz;
// pA, pB - pro vytvoření dvou množin, pC - výsledná množina (operace sjednocení, průnik)
Vytvoření prázdné množiny procedure TForm1.FormCreate(Sender: TObject); begin pA:=nil;
// jestliže je ukazatel na prvek
pB:=nil;
nastaven na nil, lze předpokládat, že
end; Vkládání prvků do množiny procedure Vloz(var p: ukaz; x: Integer); var q, r: ukaz;
je seznam (množina prvků) prázdný // prvky vkládáme na konkrétní pozici v seznamu
begin if p=nil then begin
// vložení prvku do prázdného seznamu
new(q); q^.hodn:=x; q^.dalsi:=nil; p:=q end else if x< p^.hodn then
// je-li prvek menší, než aktuální
begin
prvek, vložíme menší prvek před
new(q); q^.hodn:=x; q^.dalsi:=p;
aktuální prvek
p:=q end else if x=p^.hodn then else
// prvek se stejnou hodnotou nemůžeme vložit vícekrát...
begin q:=p; while (q^.dalsi<>nil) and (x>q^.hodn) do q:=q^.dalsi;
// je-li prvek větší než aktuální prvek, vložíme ho za daný prvek
if x>q^.hodn then begin new(r); r^.hodn:=x; r^.dalsi:=nil; q^.dalsi:=r end else if x<>q^.hodn then begin new(r); r^.hodn:=q^.hodn; q^.hodn:=x; r^.dalsi:=q^.dalsi; q^.dalsi:=r end end Sjednocení množin
// výsledná množina (C) obsahuje všechny prvky, které se vyskytují v daných množinách (A, B) . Najdeme-li v nich prvek se stejnou hodnotou, bude se ve sjednocení množin vyskytovat pouze 1x.
procedure sjednoceni(pA, pB: ukaz; var C: ukaz); begin c:=pA; while pb<>nil do
begin Vloz(C, pb^.hodn); pb:=pb^.dalsi end Průnik
// výsledná množina (C) obsahuje pouze ty prvky, které mají mají stejnou hodnotu a vyskytují se zároveň v množině A a B.
procedure prunik(pA, pB: ukaz; var C: ukaz); begin c:=nil; while pa<>nil do begin while (pb<>nil) and (pb^.hodn<pa^.hodn) do pb:=pb^.dalsi; if pb^.hodn=pa^.hodn then Vloz(C, pb^.hodn); pa:=pa^.dalsi end volání procedury pro vkládání prvků a jejich výpis procedure TForm1.Button1Click(Sender: TObject); begin Vloz(pA, StrToInt(Edit1.text));
// prvky množiny vložíme formuláře
Edit1.Clear;
pomocí komponenty Edit
Button2Click(Sender); end; procedure TForm1.Button2Click(Sender: TObject); var q: ukaz; begin q:=pA; Memo1.Lines.Clear; while q<>nil do begin Memo1.Lines.Add(IntToStr(q^.hodn));
// prvky množiny zobrazíme pomocí
q:=q^.dalsi
komponenty Memo
end end; volání procedur sjednocení a průnik a jejich výpis procedure TForm1.Button6Click(Sender: TObject); var q: ukaz; begin sjednoceni (pA, pB, pC); Memo3.Lines.Clear; q:=pC; while q<>nil do begin Memo3.Lines.Add(IntToStr(q^.hodn)); q:=q^.dalsi end ; end; procedure TForm1.Button7Click(Sender: TObject); var q: ukaz; begin prunik (pA, pB, pC); Memo3.Lines.Clear; q:=pC; while q<>nil do begin Memo3.Lines.Add(IntToStr(q^.hodn)); q:=q^.dalsi end; end;
