Muodosta kahden joukon leikkaus

Takaisin JHAVEPOP harjoituksiin

Joukon esittäminen linkitetyn listan avulla

Tässä harjoituksessa jokainen käsiteltävä joukko on talletettu linkitettyä listaa käyttäen. Joukko tarkoittaa ryhmää alkioita (tässä tapauksessa kirjaimia), jossa sama alkio ei ikinä esiinny kahta kertaa. Vaikka alkiot ovatkin linkitetyssä listassa jossakin järjestyksessä, järjestyksellä ei ole merkitystä, kun listan sisältämää alkioryhmää käsitellään joukkona. Esimerkiksi joukko {1, 2} voidaan esittää linkitetyllä listalla joko 1 -> 2 tai 2 -> 1. Linkitetty lista, jossa ei ole yhtään alkiota kuvaa tyjää joukkoa.

Ongelman kuvaus

Kirjoita C++-ohjelma, joka muodostaa kahden joukon s1 ja s2 (s kuten set) leikkauksen, ja tallettaa sen joukoksi s1. Joukkoa s2 ei muuteta. Kahden joukon leikkaus tarkoittaa joukkoa, joka sisältää täsmälleen ne alkiot, jotka kuuluvat kumpaankin alkuperäisistä joukoista.



Kuten alla esitellyistä testitapauksista huomaat, voit olettaa, että joukot s1 ja s2 annetaan linkitettyinä listoina samannimisten osoittimien päässä. Huomaa, että harjoituksessa on määriteltynä myös ylimääräiset osoittimet p1, p2 ja prev1, joita voit käyttää apuna. Tässä harjoituksessa ei ole tarkoitus määritellä muita osoittimia.

Varmista, että kirjoittamasi ohjelmakoodi toimii oikein kaikissa erilaisissa tapauksissa, oli joukkoina mitä tahansa. Seuraavat 10 testitapausta helpottavat ohjelmasi testaamista. Kirjoita ohjelmakoodisi valmiiksi ja kopioi se sitten vuorotellen jokaiseen seuraavista JHAVEPOP testeistä kokeillaksesi sen toimintaa eri tilanteissa.

Testitapaus #1

Kuvaus: s1 on tyhjä joukko.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #2

Kuvaus: s2 on tyhjä joukko.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #3

Kuvaus: Molemmat joukoista s1 ja s2 ovat tyhjiä.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #4

Kuvaus: Joukko s1 sisältää vain yhden alkion, joka on myös joukossa s2.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #5

Kuvaus: Joukko s1 sisältää vain yhden alkion, joka ei ole joukossa s2.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #6

Kuvaus: Joukoilla s1 ja s2 ei ole yhteisiä alkioita, eli niiden leikkaus on tyhjä joukko.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #7

Kuvaus: Joukko s1 on sama kuin joukko s2.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #8

Kuvaus: Joukon s1 ensimmäinen alkio kuuluu leikkaukseen, mutta viimeinen alkio ei kuulu.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #9

Kuvaus: Joukon s1 viimeinen alkio kuuluu leikkaukseen, mutta ensimmäinen alkio ei kuulu.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #10

Kuvaus: Satunnainen tapaus, jossa osa alkioista kuuluu leikkaukseen ja osa ei.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?
Takaisin JHAVEPOP harjoituksiin