Verižni seznam (tudi povezani seznam, linearni seznam)

Verižni seznam (tudi povezani seznam, linearni seznam)

Avtor: Matija Lokar

Več o projektu...

Grafična predstavitev

(slide2.jpg)

ZELO POMEMBNO

  • Ločiti med verižnim seznamom kot zaporedjem vozlov in verižnim seznamom kot podatkovno strukturo
  • Najprej bomo na verižni seznam gledali izključno kot na zaporedje vozlov!

Elementi ver. seznama

  • Elementi - vozli
  • Vozel - objekt

  • Sestavni deli

    • Prostor za podatke
    • Referenca (kazalec) na naslednjega

Vozel.py

class Vozel :
  def __init__(self, kaj=None, kam=None):
    self.podatek = kaj
    self.naslednji  = kam

  def __str__(self):
    return str(self.podatek)

Vozel

Konstruktorji razreda Vozel

  • “Goli” vozel

    • prvi = Vozel.Vozel()

  • “Osamljeni” vozel

    • sam = Vozel.Vozel(“Nimam naslednika”)

  • “Follow me”

    • takojGlavni = Vozel.Vozel(“Moja vsebina”, tiSiMojNaslednji)

Veriga treh

  • Ustvarimo tri samostojne vozle

    • prviSam = Vozel.Vozel("ABC")
    • drugiSam = Vozel.Vozel("123")
    • tretjiSam = Vozel.Vozel(333)

  • Povežimo

    • drugiSam.naslednji = prviSam
    • tretjiSam.naslednji = drugiSam

  • Ustvarimo tri vozle in jih takoj povežimo med sabo

    • prvi = Vozel.Vozel("abc")
    • drugi = Vozel.Vozel("123", prvi)
    • tretji = Vozel.Vozel(33,drugi)

Izpis

  • Izpišimo vsebino vseh treh, če poznamo referenco le na prvega

    • zacetek = tretji
    • print('Peš')
    • print(zacetek.podatek)
    • print(zacetek.naslednji.podatek)
    • print(zacetek.naslednji.naslednji.podatek)

  • Spremeni vsebino prvega v verigi

    • zacetek.podatek = "Drugače "
    • print('Po spremembi')
    • print(zacetek.podatek)
    • print(zacetek.naslednji.podatek)
    • print(zacetek.naslednji.naslednji.podatek)

Še nekaj primerov

  • Spremeni vsebino tretjega

    • zacetek.naslednji.naslednji.podatek = 42

  • 2.primer

    • V obstoječo verigo treh vozlov na začetek dodaj nov vozel
    • Sedaj pa še na konec

  • Sestavi metodo, ki izpiše vsebino vseh vozlov v verigi

    •  def izpisi(prvi) :
          pom = prvi
          while pom != None :
              print(pom.podatek)
              pom = pom.naslednji

Razred Vozel - metode

def nastaviPodatek(self, pod):
  '''Vozlu spremeni podatek na pod'''
  self.podatek = pod

(slide10.jpg)

def vrniPodatek(self):
  '''vrne podatek, ki je v vozlu'''
  return self.podatek

nastaviNasled, vrniNasled

def nastaviNasled(self, mojNasled) :
  '''Vozlu nastavi novega naslednika'''
  self.naslednji = mojNasled

(slide11.jpg)

def vrniNasled(self):
  ''' Vrne kazalec na naslednji vozel '''
  return self.naslednji

(slide12.jpg)
Metode razreda Vozel

Primeri od prej

  • Naredimo primere od prej, a tokrat "zares" (z uporabo metod)

  • 1. primer

    • Ustvarimo tri vozle in jih povežimo med sabo
    • Izpišimo vsebino vseh treh, če poznamo referenco le na prvega
    • Spremeni vsebino prvega
    • Spremeni vsebino tretjega

  • 2.primer

    • V obstoječo verigo treh vozlov na začetek dodaj nov vozel
    • Sedaj pa še na konec
  • Sestavi metodo, ki izpiše vsebino vseh vozlov v verigi

Koda

import Vozel

prvi = Vozel.Vozel("abc")
drugi = Vozel.Vozel("123", prvi)
tretji = Vozel.Vozel(33,drugi)

zacetek = tretji

print('Peš')
print(zacetek.vrniPodatek())
print(zacetek.vrniNasled().vrniPodatek())
print(zacetek.vrniNasled().vrniNasled().vrniPodatek())

print('Peš, a s pomočnikom')
pomoc = zacetek
print(pomoc.vrniPodatek())
pomoc = pomoc.vrniNasled()
print(pomoc.vrniPodatek())
pomoc = pomoc.vrniNasled()
print(pomoc.vrniPodatek())

def izpisi(prvi) :
    pom = prvi
    while pom != None :
        print(pom.vrniPodatek())
        pom = pom.vrniNasled()

print('Z metodo:')
izpisi(zacetek)

Še en zgled

  • Sestavi funkcijo sestaviVerigo(n), ki sestavi verigo n vozlov z vrednostmi od ena do n.
  • Funkcija vrne referenco (kazalec) na prvi vozel v verigi.
  • Vozel z vrednostjo 1 naj bo na začetku, vozel z vrednostjo n pa na koncu verige - povezani morajo torej biti kot 1->2->3->...->(n-1)->n.
  • Dvakrat zapored izpiši to verigo!
0%
0%