Izpitno vprašanje RAČ2PRA 6400

Iz MaFiRaWiki

Vprašanje

Sestavi algoritem, ki vstavi nov element na začetek dvojno povezanega seznama, podanega s kazalcema na začetek in konec.

Odgovor

Za dvojno povezan linearni seznam velja:

  1. vozel ima referenco naprej in nazaj
  2. poznamo kazalec na prvi in zadnji element (enostavni pozna le kazalec na prvi element)
Da bi lahko vstavili nov element na začetek dvojno povezanega seznama, potrebujemo dva razreda in sicer:
  1. Vozel, potrebujemo zato, ker je element linearnega seznama. V razredu poskrbimo, da bo vozel imel referenci naprej in nazaj in prostor za podatke.
  2. DLinSez (Dvojni linearni seznam), poskrbimo, da poznamo kazalec na prvi in zadnji element in napišemo metode, ki jih želimo uporabljati nad dvojno povezanim linearnim seznamom.
Razred Vozel:
  1. public class DVozel {
  2. private DVozel naslednji;
  3. private DVozel prejsnji;
  4. private int podatek;
  5.  
  6. // konstruktorji
  7. public DVozel() {
  8. podatek = 0;
  9. naslednji = null;
  10. prejsnji = null;
  11. }
  12.  
  13. public DVozel(int x) {
  14. podatek = x;
  15. naslednji = null;
  16. prejsnji = null;
  17. }
  18.  
  19. // metode vrni, nastavi
  20. public void nastaviPodatek(int x) {
  21. this.podatek = x;
  22. }
  23.  
  24. public int vrniPodatek() {
  25. return podatek;
  26. }
  27.  
  28. public void nastaviNasled(DVozel v) {
  29. this.naslednji = v;
  30. }
  31.  
  32. public void nastaviPrejs(DVozel v) {
  33. this.prejsnji = v;
  34. }
  35.  
  36. public DVozel vrniNasled() {
  37. return this.naslednji;
  38. }
  39.  
  40. public DVozel vrniPrejs() {
  41. return this.prejsnji;
  42. }
  43. }

Razred DLinSez:

  1.  
  2. public class DLinSez
  3. {
  4.  
  5. protected DVozel prvi;
  6. protected DVozel zadnji;
  7. // konstruktor
  8. public DLinSez() {
  9. prvi = null;
  10. zadnji = null;
  11. }
  12.  
  13. //metoda, ki vstavi prvi vozel v linearni seznam
  14. public void vstavi_prvega(DVozel v) {
  15. v.nastaviNasled(prvi);
  16. v.nastaviPrejs(null);
  17. if (prvi != null)
  18. prvi.nastaviPrejs(v);
  19. else
  20. zadnji = v;
  21. prvi = v;
  22. }
  23.  
  24. //metoda, ki vstavi podatek v prvi vozel linearnega seznama
  25. public void vstavi_prvega(int x) {
  26. DVozel v = new DVozel(x);
  27. vstavi_prvega(v);
  28. }
  29.  
  30. //metoda, ki izpiše linearni seznam
  31. public void izpisi() {
  32. DVozel kje = new DVozel();
  33. kje = prvi;
  34. while (kje != null) {
  35. System.out.print(kje.vrniPodatek() + " ");
  36. kje = kje.vrniNasled();
  37. }
  38. System.out.println();
  39. }
  40. }

Razred za testiranje, DvojniLinSezTest:

  1.  
  2. public class DvojniLinSezTest {
  3. public static void main(String[] args) {
  4. // naredimo nov linearni seznam
  5. DLinSez mojLS = new DLinSez();
  6. mojLS.vstavi_prvega(4);
  7. mojLS.vstavi_prvega(3);
  8. mojLS.vstavi_prvega(2);
  9. mojLS.vstavi_prvega(1);
  10. mojLS.izpisi();
  11. }
  12. }

Rezultat vstavljanja elementov v dvojno povezan linearni seznam. Slika:

slika:DvojniLinSezRezultat.png

Osebna orodja