Izpitno vprašanje DIRI2005 6600

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vsebina

Vprašanje

|Vpr. 6600| 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š prelagati elementov.

Odgovor

Ideja

Ustvarim prvi linearni seznam za liha števila in drugega za soda. Ustvarim tudi tri pomožne kazalce in sicer: p - pomožni kazalec, ki kaže na trenutno obravnavan vozel pl - pomožni kazalec, ki kaže na trenutno zadnji prebrani vozel z lihim številom ps - pomožni kazalec, ki kaže na trenutno zadnji prebrani vozel s sodim številom Najprej pl postavimo na prvo liho število, ps pa na prvo sodo število v linearnem seznamu. S kazalcem p se pomikamo po celotnem seznamu. Če je število liho nanj usmerimo kazalec pl, drugače pa kazalec ps.

Algoritem

LinSez liha = new LinSez();  //linearni seznam za liha števila
LinSez soda = new LinSez();  //linearni seznam za soda števila
Vozel p = Vrni prvi vozel;   //pomožni kazalec, ki kaže na trenutni vozel
Vozel pl = null;             //pomožni kazalec, ki kaže na zadnji lihi vozel
Vozel ps = null;             //pomožni kazalec, ki kaže na zadnji sodi vozel 
 if (prazen()) = NAPAKA
 else {
   if (p.VrniPodatek %2 == 0)}  //če je v prvem vozlu sodo število
     ps = p                     //pomožni kazalec ps usmerim na prvi vozel
     while ((p.VrniPodatek %2 == 0) && (!p == null)){  
 //poiščem 1. vozel z lihim številom in kazalec pl usmerim nanj
       p = p.VrniNasled();
     }
     pl = p;
   }
   else {
     pl  = p 
     while ((p.VrniPodatek %2 == 1) && (!p == null)){ 
  //če je v prvem vozlu liho število, pomožni kazalec pl usmerim na prvi vozel. Poiščem prvi vozel v katerem je sodo število in kazalec ps usmerim nanj  
       p = p.VrniNasled();
     }
     ps = p;
   } 
   liha.nastavi_prvega(pl);  //vozel kamor kaže pl, je začetni vozel lin.seznama lihih števil
   soda.nastavi_prvega(ps);  //vozel kamor kaže ps, je začetni vozel lin.seznama sodih števil 
   p = VrniPrviVozel;        //pomožni kazalec p dam na začetek 
   while (! p == null) {     //pregledam celoten seznam
     if (p.VrniPodatek %2 ==0) {  //ko je trenutni podatek sodo število, kazalec ps usmerimo na ta vozel
       ps.NastaviNasled(p);
       ps = p;
     }
     else{
       ps.NastaviNasled(p);
       pl = p;
     }
     p = p.VrniNasled();
   }
   pl.NastaviNasled(null);   //zadnja vozla seznamov usmerimo na null
   ps.NastaviNasled(null);
}
Osebna orodja