CSharp - Verižni seznam

CSharp - Verižni seznam

Avtor: Matija Lokar

Več o projektu...

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

Je množica elementov, kjer vsak element vsebuje tudi kazalec (povezavo, referenco) na element

Grafična predstavitev

(verizni_2.png)

LinkedList v C#

  • Ta verižni seznam je nekoliko drugačen!
  • Dvojno povezan verižni seznam
  • Poznamo kazalca na predhodnika in naslednika

  • Dejansko bomo mi uporabljali LinkedListNode (no, različico, ki pozna le naslednika, ne pa tudi prednika)

    • Torej omejili se bomo na posamezne vozle in ročno skrbeli za njihovo povezovanje

Elementi ver. seznama

  • Elementi - vozli
  • Vozel - objekt

  • Komponente

    • Prostor za podatke
    • Referenca na naslednjega
public class Vozel<T> {
  private T podatek; // hranimo podatke tipa T
  private Vozel<T> naslednji; // referenca na naslednjega
  // konstruktorji
  // Lastnosti: Vsebina, Nasl

Lastnosti

public T Vsebina {
    get { return this.podatek; }
    set { this.podatek = value; }
}
public Vozel<T> Nasl
{
    get { return this.naslednji; }
    set { this.naslednji = value; }
}

public Vozel()
{
    this.Vsebina = default(T);
        // kot je privzeta vrednost za tip T
    this.Nasl = null;
}
(verizni_5.png)

Nekaj primerov

  • 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 dodaj nov vozel na začetek
    • Sedaj pa še na konec
  • Sestavi metodo, ki izpiše vsebino vseh vozlov v verigi

1. primer

Vozel<int> prvi = new Vozel<int>();
Vozel<int> drugi = new Vozel<int>();
Vozel<int> tretji = new Vozel<int>();
prvi.Vsebina = 12;
drugi.Vsebina = 42;
drugi.Nasl = prvi;
tretji.Vsebina = 13;
tretji.Nasl = drugi;

Vozel<int> zac = tretji;
prvi = null; drugi = null; tretji = null; // znebimo se naslovov
Console.WriteLine(zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine(zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine(zac.Nasl.Nasl.Vsebina); // vsebina tretjega v verigi

zac.Vsebina = 111;
zac.Nasl.Nasl.Vsebina = 1;
Console.WriteLine(zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine(zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine(zac.Nasl.Nasl.Vsebina); // vsebina tretjega v verigi

Dodaj na začetek

// dodaj na začetek
 Vozel<int> nov = new Vozel<int>();
 nov.Vsebina = 1000;
 // povežemo
 nov.Nasl = zac;
 // dobili smo nov začetek
 zac = nov;

Testni program

Vozel<int> prvi = new Vozel<int>();
Vozel<int> drugi = new Vozel<int>();
Vozel<int> tretji = new Vozel<int>();
prvi.Vsebina = 12;
drugi.Vsebina = 42;  drugi.Nasl = prvi;
tretji.Vsebina = 13; tretji.Nasl = drugi;

Vozel<int> zac = tretji;
prvi = null; drugi = null; tretji = null; // znebimo se naslovov
Console.WriteLine("vsebina prvega v verigi: " + zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine("vsebina drugega v verigi: " + zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine("vsebina tretjega v verigi: " + zac.Nasl.Nasl.Vsebina); // vsebina tretjega
// dodaj na začetek
Vozel<int> nov = new Vozel<int>(); nov.Vsebina = 1000;
// povežemo
nov.Nasl = zac;
// dobili smo nov začetek
zac = nov;
Console.WriteLine("vsebina prvega v verigi: " + zac.Vsebina); // vsebina prvega v verigi
Console.WriteLine("vsebina drugega v verigi: " + zac.Nasl.Vsebina); // vsebina drugega v verigi
Console.WriteLine("vsebina tretjega v verigi: " + zac.Nasl.Nasl.Vsebina); // vsebina tretjega
// sedaj imamo še četrtega
Console.WriteLine("vsebina četrtega v verigi: " + zac.Nasl.Nasl.Nasl.Vsebina); // vsebina četrtega
(verizni_9.png)

Izpiši

  • Izpišemo vsebino verižnega seznama na začetek katerega kaže zacSez

  • Ideja:

    • Vzamemo kazalec s katerim se premikamo po verigi

    • Naslednji v verigi:

      • kjeSmo = kjeSmo.Nasl;

    • Konec:

      • kjeSmo == null
(verizni_10.png)

IzpisVerige

public static void IzpisVerige<T>(Vozel<T> zacSez)
{
    // izpišemo vsebino verige, na katere začetek kaže zacSez
    Vozel<T> kjeSmo; // kazalec za premikanje
    kjeSmo = zacSez;
    Console.Write("Začetek: ");
    while (zacSez != null) // do konca seznama
    {
        Console.Write(zacSez.Vsebina + " -> ");
        zacSez = zacSez.Nasl; // na naslednji vozel
    }
    Console.WriteLine("KONEC");
}

Dodaj vsebino tabele na začetek

public static Vozel<T> VstaviTab<T> (T[] pod)
{
    // Sestavi novo verigo, kamor vstavi podatke iz tabele pod
    Vozel<T> prvi = null; // začetek verige
    for (int i = 0; i < pod.Length; i++)
    {
        Vozel<T> nov = new Vozel<T>(); // vozel za nove podatke
        nov.Vsebina = pod[i]; nov.Nasl = prvi; // dodamo na začetek
        prvi = nov; // nov začetek
    }
    return prvi;
}

In še test

int[] podatki = { 11, 23, 34, 45, 555, 67 };
Vozel<int> verigaŠtevil = VstaviTab(podatki);
// izpis
Console.WriteLine("Prvi izpis: ");
IzpisVerige(verigaŠtevil);
// in še enkrat
Console.WriteLine("še drugi izpis: ");
IzpisVerige(verigaŠtevil);
(verizni_13.png)

Razred Vozel – dodatni konstruktorji

public Vozel(T x) : this(){
  this.Vsebina = x;
}
(verizni_14.png)

Razred Vozel – dodatni konstruktorji

public Vozel(V v) : this(){
    this.Nasl = v;
}
(verizni_15.png)

Razred Vozel – dodatni konstruktorji

public Vozel(Vozel v, T x):this(x) {
    this.Nasl = v;
}
(verizni_16.png)

Konstruktorji razreda Vozel

(verizni_17.png)

Še en zgled

  • Sestavi metodo sestaviVerigo<int>(int 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!

In še en par

  • Funkcija izpisiSode(prvi) , ki izpiše vse sode vrednosti v verigi vozlov. Kot parameter sprejme kazalec na prvi vozel v tej verigi.
  • Funkcija stakni(prvaVeriga, drugaVeriga) , ki doda drugo verigo na konec prve, ter kot rezultat vrne kazalec na prvi vozel v novi verigi.

In en malo bolj "zares"

  • Dana je veriga vozlov, na katere začetek kaže vvPrvi. Iz te verige bi radi naredili novo, ki bi imela podatke v verigi vozlov razvrščene ravno v obratnem vrstnem redu.

  • Dana je veriga, na katere začetek kaže vsZačetek. Radi bi jo spremenili tako, da bi se sedaj kazalci v verigi "obrnili". Seveda bi novi začetek te verige kazal na prej zadnji vozel.

    • Lahko ustvarjamo nove objekte
    • Ne smemo narediti nobenega novega vozla

Predstavitev sklada in vrste

  • Kako bi s pomočjo verižnega seznama predstavili sklad in vrsto?
  • Seveda tako, da bo hitro, neomejeno glede velikosti, …

  • Ideja:

    • Sklad:

      • Vse se dogaja na vrhu sklada

        • To je začetek ver. seznama
      • potrebujemo le kazalec na prvega

    • Vrsta

      • Le z enim kazalcem bo počasno

        • Zakaj
      • Kazalec na prvi in zadnji element
0%
0%