Izpitno vprašanje RAČ2PRA 6301

Iz MaFiRaWiki

Vprašanje

Sestavi algoritem, ki zlije dve urejeni zaporedji predstavljeni v linearnem kazalčnem seznamu. Pri tem ne prestavljaj elementov.

Odgovor

  1. public static LinSez zlij(LinSez sez1, LinSez sez2){
  2. //ce je en seznam prazen vrnemo drugega
  3. if(sez1.prazen()) return sez2;
  4. if(sez2.prazen()) return sez1;
  5. //nastavimo vozla za sprehod po seznamih
  6. Vozel s1 = sez1.vrniPrviVozel();
  7. Vozel s2 = sez2.vrniPrviVozel();
  8. //nastavimo zacetek zlitega seznama
  9. Vozel zliti = new Vozel<Integer>();
  10. if(s1.vrniPodatek() < s2.vrniPodatek()){
  11. zliti = s1;
  12. s1 = s1.vrniNasled();
  13. }
  14. else {
  15. zliti = s2;
  16. s2 = s2.vrniNasled();
  17. }
  18.  
  19. // tukaj bomo hranili manjsega izmed vozlov
  20. Vozel manjsi = new Vozel();
  21. //zadnji vozel zlitega seznama
  22. Vozel konec = zliti;
  23.  
  24. while(s1 != null && s2 != null){
  25. //primerjamo tekoca elementa iz obeh seznamov
  26. //manjsega dodamo v zliti seznam
  27. if(s1.vrniPodatek() < s2.vrniPodatek()){
  28. manjsi = s1;
  29. s1 = s1.vrniNasled();
  30. }
  31. else{
  32. manjsi = s2;
  33. s2 = s2.vrniNasled();
  34. }
  35.  
  36. konec.nastaviNasled(manjsi);
  37. konec = manjsi;
  38. }
  39.  
  40. //preostali seznam dodamo na konec zlitega seznama
  41. if(s1==null) konec.nastaviNasled(s2);
  42. else konec.nastaviNasled(s1);
  43. return new LinSez(zliti);
  44. }
Osebna orodja