Urejeni seznam/METARAM

Iz MaFiRaWiki

Urejen seznam je podatkovna struktura. V urejenem seznamu hranimo elemente, na katerih je definirana relacija urejenosti (jih torej lahko primerjamo po velikosti). Metode, ki jih linearni seznam pozna pa poskrbijo, da so elementi v njem tudi urejeni glede na to urejenost. Linearni seznam ponavadi implementiramo z verižnim seznamom, kar pa seveda ni edina možnost. Da pa bi bil seznam podatkovna struktura, velja med elementi neka urejenost.

V Linearnem seznamu imamo (vsaj) naslednje metode:

  1. metoda Vstavi sprejme podatek in številski indeks, ter ravno na to na mesto z tem indeksom zapiše podatek (preko prejšnjega).
  2. metoda Vrini sprejme podatek in številski indeks, ter nato vse elemente v seznamu, desno od indeksa premakne za 1 v desno. Na mesto določeno z indexom pa zapiše podatek.
  3. Vrni sprejme številski indeks in vrne podatek, ki ima tisti indeks v seznamu.
  4. metoda Odstrani sprejme številski indeks in potem vse elemente seznama, ki so desno

Primer:

  • Urejen seznam: (1, 5, 9, 24, 67, 255, 753)
  • vstavimo podatek: 364
  • (1, ...); (1, 5, ...); (1, 5, 9, ...); (1, 5, 9, 24, ...); (1, 5, 9, 24, 67,...); (1, 5, 9, 24, 67, 255, ...); (1, 5, 9, 24, 67, 255, 753)
  • (1, 5, 9, 24, 67, 255, 364, 753)

Problem; ko vstavljamo nov zelo velik podatek, preiščemo cel seznam. Če je seznam že urejen, lahko uporabimo metodo razpolavljanja.


primer programa SeznamP

  1. public class SeznamP<T extends Element> extends Seznam<T> //dedujemo iz razreda Seznam
  2. //elementi so podrazredi razreda Element
  3. public SeznamP(String ime) { //konstruktor - za neko ime naredi seznam
  4. super(ime);
  5. }
  6. public void dodaj(T el) {
  7. Clen nov = new Clen(el); //naredimo nov objekt vsebujoc element
  8. if(zacetek == null || el.manjsi(zacetek.element)) { //ce je seznam prazen ali
  9. nov.naprej = zacetek; //je element manjsi od prvega
  10. zacetek = nov; //vrinemo element na zacetek
  11. }
  12. else { //drugace poiscemo pravo mesto za vstavljanje
  13. Clen pom = zacetek; //naredimo clen, ki kaze na zacetek
  14. while(pom.naprej != null && pom.naprej.element.manjsi(el)) //dokler ni na koncu seznama
  15. pom = pom.naprej; //ali ne najde manjsega -> naj se pomika naprej
  16. nov.naprej = pom.naprej;
  17. pom.naprej = nov; //vstavi novi element
  18. }
  19. velikost++;
  20. }
  21. }

  1. class TestSeznam {
  2. public static void main(String[] args) {
  3. SeznamP<int> s = new SeznamP<int>();
  4. s.dodaj(57);
  5. System.out.println(s);
  6. }
  7. }
Osebna orodja