Matematické Fórum

gladiator01

Ahoj,
potřebovala bych poradit jak udělat sjednocení a průnik dvou množin (množiny jsou realizované pomocí pole).

Díky za případnou pomoc.

Třída:

Code:

class Set {
    TypPrvku *pole;
    int pocetPrvku;
    int maxPrvku;
  public:
    Set(TypPrvku mp=20);
    ~Set();
  
    void odeber(TypPrvku);
    bool jeTam(TypPrvku) const;
    void vloz(TypPrvku);
    
    friend Set operator+(Set, Set );  // sjednocení    
    friend Set operator*(Set, Set );  // průnik
   
    void prunik(Set b1, Set b2);
    void sjednoceni(Set b1, Set b2);
    
    Set(const Set&);
    Set& operator=(const Set&); 
    friend ostream& operator+=(Set&, TypPrvku);
    friend ostream& operator<<(ostream&, const Set&);
    
    Set* serad(TypPrvku*);
    Set* odstranDuplicity(TypPrvku p);
};

Little John · 09. 05. 2009 22:10

Ahoj,

co třeba:

Code:

Set Set::operator + (Set a, Set b)    // sjednocení
{
        Set tmp(a.pocetPrvku + b.pocetPrvku) ;    // výsledná množina bude mít nejvýš |a| + |b| prvků

        for(unsigned int i = 0 ; i < a.pocetPrvku ; i++)        // vložíme prvky z a
                tmp.vloz(a.pole[i]) ;

        for(unsigned int i = 0 ; i < b.pocetPrvku ; i++)        // vložíme prvky z b
                tmp.vloz(b.pole[i]) ;

        for(unsigned int i = 0 ; i < tmp.pocetPrvku ; i++)        // odstraníme duplicity
                odstranDuplicity(i) ;                                        // předpokládám že funkce odstraňuje právě n-1 výskytů n-násobných prvků

        return tmp ;                // hotovo
}

Set Set::operator * (Set a, Set b)    // průnik
{
        Set tmp((a.pocetPrvku > b.pocetPrvku) ? a.pocetPrvku : b.pocetPrvku) ;    // průnik -> nejvýše max(|a|, |b|) prvků

        for(unsigned int i = 0 ; i < a.pocetPrvku ; i++)                        // ke každému prvku z a
                for(unsigned int j = 0 ; j < b.pocetPrvku ; j++)                // hledáme v b
                        if(a.pole[i] == b.pole[j])                                                // stejný
                        {
                                tmp.vloz(a.pole[i]) ;                                        // a když ho najdeme, vložíme ho do průniku. Pak pokračujeme s prohledáváním a
                                j = b.pocetPrvku ;                // continue by asi bylo slušnější, nejsem si ale jist jestli by neopakovalo vnitřní cyklus místo vnějšího
                        }

        return tmp ;        // hotovo
}

Možná bych ještě změnil pocetPrvku a maxPrvku na typ unsigned int, protože v C++ určitě z pole prvky se zápornými indexy nikdo tahat nechce. :-)

Také by bylo vhodné použít předávání odkazem. Ušetří se tím cesta čtyř intů přes zásobník.
Deklarace by pak vypadala asi takto:

Code:

Set Set::operator + (const Set &a, const Set &b) ;
Set Set::operator * (const Set &a, const Set &b) ;

Obdobně by se změnila definice. Tělo funkcí by zůstalo naprosto beze změny.

gladiator01

Děkuji.

Matematické Fórum

#1 27. 04. 2009 14:00 — Editoval gladiator01 (27. 04. 2009 17:34)

sjednocení, průnik množin c++

Code:

#2 09. 05. 2009 22:10

Re: sjednocení, průnik množin c++

Code:

Code:

#3 09. 05. 2009 23:12 — Editoval gladiator01 (09. 05. 2009 23:13)

Re: sjednocení, průnik množin c++

Zápatí