Muodosta kahden joukon erotus

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) erotuksen, ja tallettaa sen joukoksi s1. Joukkoa s2 ei muuteta. Joukkojen erotus s1 - s2 tarkoittaa joukkoa, joka sisältää kaikki ne joukon s1 alkiot, jotka eivät kuulu joukkoon s2.



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 erotus on täsmälleen sama kuin joukko s1.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #7

Kuvaus: Joukko s1 on sama kuin joukko s2, eli erotus on tyhjä joukko.

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #8

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

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #9

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

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Testitapaus #10

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

Alkutilanne:

Lopputilanne:

Valmiina testaamaan?

Takaisin JHAVEPOP harjoituksiin