Multihalmaz

A multihalmaz

A multihalmaz egy olyan halmaz, ami értékeken túl multiplicitást (darabszámot) is tárol. A különbség szemléltetéséhez vegyük az alábbi példát:

van egy allatok = {"kenguru", "koala", "krokodil", "kecske"} halmazom, és egy allatokMulti = {("kenguru", 4), ("koala", 2), ("krokodil", 3), ("kecske", 42)} multihalmazom. Az allatokMultiban azon túl, hogy látom, hogy milyen állataim vannak, azt is látom, hogy ezekből az állatokból hány db van. Ha érkezik még kettő koala hozzám, akkor az allatok halmaz nem módosulna, viszont az allatokMulti igen. A ("koala", 2) értékéből ("koala", 4) lenne.

Ezt a lent látható módon valósítottuk meg C#-ban.

MultihalmazElem

    class MultihalmazElem
    {
        public int ertek, multi;
        public MultihalmazElem(int ertek, int multi)
        {
            this.ertek = ertek;
            this.multi = multi;
        }
        public override string ToString()
        {
            return $"{ertek} {multi}";
        }
    }

Létrehozás

    class Multihalmaz
    {
        int MaxDb = 100;
        int db;
        MultihalmazElem[] elemek;

        public Multihalmaz()
        {
            db = 0;
            elemek = new MultihalmazElem[MaxDb];
        }

        //...
    }

Beolvasás

    public void Beolvasas()
    {
        string[] sor = Console.ReadLine().Split();
        db = int.Parse(sor[0]);
        for (int i = 0; i < db; i++)
        {
            elemek[i] = new MultihalmazElem(int.Parse(sor[i * 2 + 1]), int.Parse(sor[i * 2 + 2]));
        }
    }

Rendezés

    public void Rendezes()
    {
        for (int i = 0; i < db - 1; i++)
        {
            for (int j = i + 1; j < db; j++)
            {
                if (elemek[i].ertek > elemek[j].ertek)
                {
                    MultihalmazElem tmp = elemek[i];
                    elemek[i] = elemek[j];
                    elemek[j] = tmp;
                }
            }
        }
    }

Kiírás

    public void Kiiras()
    {
        Console.WriteLine(db);
        for (int i = 0; i < db; i++)
        {
            Console.Write(elemek[i] + " ");
        }
        Console.WriteLine();
    }

Multihalmazba

    public void Multihalmazba(MultihalmazElem elem)
    {
        int i = 0;
        while (i < db && elemek[i].ertek != elem.ertek) i++;

        if (i < db) elemek[i].multi += elem.multi;
        else
        {
            elemek[db] = elem;
            db++;
        }
    }

Multihalmazból

    public void Multihalmazbol(MultihalmazElem elem)
    {
        int i = 0;
        while (i < db && elemek[i].ertek != elem.ertek) i++;

        if (i < db)
        {
            elemek[i].multi -= elem.multi;
            if (elemek[i].multi <= 0)
            {
                elemek[i] = elemek[db - 1];
                db--;
            }
        }
    }

Ürítés

    public void Urites()
    {
        db = 0;
    }

Eleme-e

    public bool ElemeE(int ertek)
    {
        int i = 0;
        while (i < db && elemek[i].ertek != ertek) i++;
        return i < db;
    }

Benne-e

    public bool BenneE(MultihalmazElem elem)
    {
        int i = 0;
        while (i < db && elemek[i].ertek != elem.ertek) i++;
        return i < db && elemek[i].multi >= elem.multi;
    }

Része-e

    public bool ReszeE(Multihalmaz masik)
    {
        if (db > masik.db) return false;

        int i = 0;
        while (i < db && masik.BenneE(elemek[i])) i++;
        return i >= db;
    }

Üres-e

    public bool UresE()
    {
        return db == 0;
    }

Unió

    public Multihalmaz Unio(Multihalmaz masik)
    {
        Multihalmaz unio = new Multihalmaz();
        for (int i = 0; i < db; i++) unio.Multihalmazba(elemek[i]);
        for (int i = 0; i < masik.db; i++) unio.Multihalmazba(masik.elemek[i]);
        return unio;
    }

Metszet

    public Multihalmaz Metszet(Multihalmaz masik)
    {
        Multihalmaz metszet = new Multihalmaz();
        for (int i = 0; i < this.db; i++)
        {
            int j = 0;
            while (j < masik.db && elemek[i].ertek != masik.elemek[j].ertek) j++;

            if (j < masik.db)
            {
                metszet.Multihalmazba(new MultihalmazElem(elemek[i].ertek, Math.Min(elemek[i].multi, masik.elemek[j].multi)));
            }
        }
        return metszet;
    }

Különbség

    public Multihalmaz Kulonbseg(Multihalmaz masik)
    {
        Multihalmaz kulonbseg = new Multihalmaz();
        for (int i = 0; i < this.db; i++)
        {
            int j = 0;
            while (j < masik.db && elemek[i].ertek != masik.elemek[j].ertek) j++;

            if (j >= masik.db) kulonbseg.Multihalmazba(elemek[i]);
            else if (elemek[i].multi > masik.elemek[j].multi)
            {
                kulonbseg.Multihalmazba(new MultihalmazElem(elemek[i].ertek, elemek[i].multi - masik.elemek[j].multi));
            }
        }
        return kulonbseg;
    }

További linkek