Matematické Fórum

↑ bella:

Nedestruktivní průnik (sjednocení) znamená, že obě ty struktury, jejichž průnik dělám, se mi zachovají a průnik si uložím do jiné proměnné. Tedy vlastně je zakázáno vstupní proměnné měnit. Destruktivní naopak znamená, že novou proměnnou mám vlastně zakázanou, tj. průnik musí být uložen v některé z proměnných, jejichž průnik dělám. Tedy je zakázáno alokovat nové proměnné.

Např. princip nedestruktivního průniku uspořádaných lin. spoj. seznamů:

Alokuju prázdný lin. spojový seznam; přečtu první prvky z obou seznamů; vždy, když narazím na stejnou položku v obou seznamech, zkopíruji ji do průniku; pokud jsou položky neshodné, můžu předpokládat, že jedna je (ve smyslu onoho uspořádání) "menší" než druhá - v tom seznamu se posunu na další prvek. Takto pokračuju, dokud nedojdu na konec jednoho seznamu.

A destruktivně:
Chci udělat průnik seznamů A,B a ukládat jej budu do A. Na začátku přečtu první položky obou seznamů. Položky budu procházet následovně: Dokud aktuální položka z A > aktuální položka z B, čtu další položku z B. Pokud na konci tohoto procesu je položka v A stejná jako položka v B, posunu se na další položku v A a opakuji. Pokud ale je položka v A < položka v B, pak položku v A smažu a posunu se na další položku v A. Pokračuji, dokud nedojdu na konec některého ze seznamů. Pokud dříve dojdu na konec seznamu B, pak všechny zbylé (neprojité) položky v A musím smazat.

↑ bella:

To je, myslím, nepodstatné. Můžeme ho klidně i smazat, ono to tolik práce navíc přece jen není : )) a na výsledném algoritmu se vlastně nic nezmění.