Izpitno vprašanje RAČ2PRA 6600

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Sestavi algoritem, ki iz linearnega seznama, v katerem hranimo cela števila, naredi dva seznama. V prvem so liha števila in v drugem soda števila. Pri tem ne sme narediti prelagati elementov!

Odgovor

Seznam pregledujemo po elementih. Sode vklučujemo v seznam sodih, lihe pa v seznam lihih. Vodimo tudi kazalce na prvi element sodih, prvi element lihih, zadnji element sodih, zadnji element lihih. Glej komentarje v algoritmu.

Algoritem

(lihi, sodi) = lihaSoda(LinSez seznam){
 
LinSez sodi = new LinSez();       
LinSez lihi = new LinSez(); 
 
Vozel trenutni = seznam.vrniPrviVozel();  //kaže na katerem mestu smo - zdaj kaže ne prvi vozel
Vozel sodo_zac = null;     //zacetek seznama sodih
Vozel liho_zac = null;     //zacetek seznama lihih
Vozel sodo_kon = null;     //konec seznama sodih
Vozel liho_kon = null;     //konec seznama lihih
 
//če je seznam prazen, vrnemo prazen LinSez sodih in prazen LinSez lihih
if (trenutni == null) {     
   return (lihi, sodi );
}
//seznam ni prazen
else {
    while(trenutni != null) {
        //če je element lih, ga dodamo k lihemu seznamu
        if(trenutni.vrni podatek() % 2 == 1) {
            //če je prvi v lihem seznamu, nastavimo začetek lihega seznama
            if(liho_zac == null) {
               liho_zac = trenutni;  //nastavimo kazalec na začetek lihih
               liho_kon = trenutni;  //nastavimo kazalec na konec lihih
               lihi.nastaviPrvega(liho_zac);  //nastavimo tako, da LinSez lihi kaže na prvega lihega
            }
            else {
                //priključimo ga k prejšnjemu lihemu
                liho_kon.nastaviNasled(trenutni);
                liho_kon = trenutni; //tale je trenutno zadnji
            }
        //če je element sod, ga dodamo k sodim 
        else {
            //če je prvi v sodem seznamu, nastavimo začetek sodega seznama
            if(sodo_zac == null) {
               sodo_zac = trenutni;  //nastavimo kazalec na začetek sodih
               sodo_kon = trenutni:  //nastavimo kazalec na konec sodih
               sodi.nastaviPrvega(sodo_zac);  //nastavimo tako, da LinSez sodi kaže na prvega sodega
            }
            else {
                //priključimo k prejšnjemu sodemu
                sodo_kon.nastaviNasled(trenutni);
                sodo_kon = trenutni; //tale je trenutno zadnji
            }
         }
         trenutni = trenutni.vrniNasled();
    }
    //ce seznam lihih ni prazen, ga končamo
    if (liho_zac != null) {
        liho_kon.nastaviNasled(null);
     }
    //ce seznam sodih ni prazen, ga končamo
    if (sodo_zac != null) {
        sodo_kon.nastaviNasled(null);
     }
     return(lihi, sodi);
}
Osebna orodja