//BSF
Queue<int> kolejka = new Queue<int>(); //kolejka
List<int> wyniki = new List<int>();
kolejka.Enqueue(start); //dodanie pierwszego
bool[] odwiedzone = new bool[tab.GetLength(0)];
while (kolejka.Count != 0)
{
int pobrany = kolejka.Dequeue();
if (odwiedzone[pobrany] == false)
{
odwiedzone[pobrany] = true;
for (int i = 0; i<tab.GetLength(1); i++)
{
if (tab[pobrany, i] != 0)
{
kolejka.Enqueue(i);
}
}
wyniki.Add(pobrany);
}
}
}


//BSF
Queue<int> kolejka = new Queue<int>(); //kolejka
List<int> wyniki = new List<int>();
kolejka.Enqueue(start); //dodanie pierwszego
bool[] odwiedzone = new bool[G.Count];
while (kolejka.Count != 0)
{
int pobrany = kolejka.Dequeue();
if (odwiedzone[pobrany - 1] == false)
{
odwiedzone[pobrany - 1] = true;
for (int i = 0; i<G[pobrany - 1].Count ; i++)
kolejka.Enqueue(G[pobrany - 1][i]);
wyniki.Add(pobrany);
}
}

//Inicjacja dijkstry
L := {s}; R := V-{s};
w[s] := 0;
dla każdego v R wykonaj
jeżeli(v, s) E to
w[v] := w((v, s))
w przeciwnym przypadku
w[v] := ∞;
//właściwe obliczenia
dla i := 1 aż do n-1 wykonaj
początek bloku
u := wierzchołek z R o minimalnej wadze w[u];
R := R - {u};
L := L + {u};
dla każdego v N(u) ∩ R wykonaj
jeżeli w[u] + w((u, v)) < w[v] to
w[v] := w[u] + w((u, v));
koniec bloku
//dla każdego v V, w[v] = w*(v)


//Inicjacja - macierz sasiedztwa dijkstry
dla i := 1 aż do n wykonaj
w[vi := A[i, s];
r[i] := 1;
r[s] := 0;
//właściwe obliczenia
dla i := 1 aż do n-1 wykonaj
początek bloku
u := MinR;
r[u]:=0;
dla i := 1 aż do n wykonaj
jeżeli r[i] = 1 to
jeżeli w[u]+A[u, i] <w[i] to
w[i] := w[u] + A[u, i];
koniec bloku
//dla każdego v V, w[v] = w*(v)

//wstawianie do drzewa bst
static void Wstaw(Drzewo drzewo, Węzeł węzeł)
{
    if (drzewo.korzeń == null) drzewo.korzeń = węzeł;
    else
    {
        Węzeł tmp = drzewo.korzeń;
        while (tmp != null)
        {
            if (tmp.wartość > węzeł.wartość)
            {
                if (tmp.lewy != null) tmp = tmp.lewy;
                else
                {
                    tmp.lewy = węzeł; return;
                }
            }
            else
            {
                if (tmp.prawy != null) tmp = tmp.prawy;
                else
                {
                    tmp.prawy = węzeł; return;
                }
            }
        }
    }
}

static Węzeł WyszukajRekurencyjnie(Węzeł korzeń, int wartość)
{
    if (korzeń == null) return null;
    if (korzeń.wartość == wartość) return korzeń;
    if (korzeń.wartość > wartość) return WyszukajRekurencyjnie(korzeń.lewy, wartość);
    else return WyszukajRekurencyjnie(korzeń.prawy, wartość);
}

static void UsuńIteracyjnieL(Drzewo drzewo, int wartość)
{
    if (drzewo.korzeń == null) return;
    Węzeł tmp = drzewo.korzeń;
    Węzeł rodzic = null;
    while (tmp != null)
    {
        if (tmp.wartość == wartość)
        {
            // tylko jedno dziecko albo wcale
            if (tmp.lewy == null)
            {
                if (rodzic == null) // usuwamy korzeń
                {
                    drzewo.korzeń = tmp.prawy;
                }
                else
                {
                    if (rodzic.lewy == tmp) rodzic.lewy = tmp.prawy;
                    else rodzic.prawy = tmp.prawy;
                }
            }
            else if (tmp.prawy == null)
            {
                if (rodzic == null) // usuwamy korzeń
                {
                    drzewo.korzeń = tmp.lewy;
                }
                else
                {
                    if (rodzic.lewy == tmp) rodzic.lewy = tmp.lewy;
                    else rodzic.prawy = tmp.lewy;
                }
            }
            else if (tmp.lewy != null && tmp.prawy != null)
            {// krok w lewo
                Węzeł qRodzic = tmp;
                Węzeł q = tmp.lewy;
                while (q.prawy != null) // teraz do oporu w prawo
                { qRodzic = q; q = q.prawy; }
                // usuwamy q z jego miejsca a na jego miejsce
                // wstawiamy lewego potomka (moze byc null)
                if (qRodzic.prawy == q) qRodzic.prawy = q.lewy;
                else qRodzic.lewy = q.lewy;
                // teraz q przenosimy na miejsce tmp
                if (rodzic == null) // usuwamy korzeń
                { drzewo.korzeń = q; }
                else
                {
                    if (rodzic.lewy == tmp) rodzic.lewy = q;
                    else rodzic.prawy = q;
                }
                // na koniec wstawiamy potomkow tmp jako potomkow q
                q.lewy = tmp.lewy;
                q.prawy = tmp.prawy;
            }
            return;
        }
        rodzic = tmp; // szukamy dalej
        if (tmp.wartość > wartość) tmp = tmp.lewy;
        else tmp = tmp.prawy;
    }
    return; // nie znaleziono
}


WywazDrzewo(Węzeł węzeł)
Jeżeli węzeł == null lub węzeł.waga == 1 to
 zakończ;
Podzial(węzeł, węzeł.waga / 2);
WywazDrzewo(węzeł.lewy);
WywazDrzewo(węzeł.prawy);
ObliczWagi(Węzeł węzeł)
Jeżeli węzeł != null to
 Jeżeli węzeł.prawy == null oraz węzeł.lewy == null to
 węzeł.waga = 1;
w przeciwnym przypadku
węzeł.waga = ObliczWagi(węzeł.lewy)+ ObliczWagi(węzeł.prawy)+ 1;
zwróć węzeł.waga;
w przeciwnym przypadku zwróć 0;

class Węzeł
{
    Dane wartość; // tutaj klucz
    int waga;
    Węzeł lewy;
    Węzeł prawy;
}

Podzial(Węzeł węzeł, int liczba)
Jeżeli węzeł.lewy == null to wl = 0;
w przeciwnym przypadku
wl = węzeł.lewy.waga;
Jeżeli wl > Liczba to
 Podzial(węzeł.lewy, liczba);
 ObrotPrawo(węzeł);
 ObliczWagi(węzeł);
w przeciwnym przypadku
 Jeżeli wl<Liczba to
 Podzial(wezeł.prawy, liczba-wl-1);
 ObrotLewo(węzeł);
 ObliczWagi(węzeł);
// wl == liczba jest OK

Naprawianie kopca – pseudokod(rekurencja)
Napraw(w) // w indeks korzenia naprawianego poddrzewa
 n = liczba elementów w całym kopcu
 lewy = 2 * w + 1 // indeks lewego dziecka
prawy = 2 * w +2 // indeks prawego dziecka
 if (lewy<n) // jeżeli są dzieci, chociażby tylko lewe
 największy = w
 if(kopiec[lewy]>kopiec[największy])
 największy = lewy//Jeżeli lewe dziecko ma wartość większą
 if(prawy<n && kopiec[prawy]> kopiec[największy])
 największy = prawy//Jeżeli prawe dziecko ma wartość większą
 if (największy != w)
 // zamień korzeń z większym dzieckiem
 tmp=kopiec[w]
 kopiec[w] = kopiec[największy]
 kopiec[największy]=tmp
 Napraw(największy) // rekurencja


Naprawianie kopca – pseudokod(iteracja)
Napraw(w) // w indeks korzenia naprawianego poddrzewa
 n = liczba elementów w całym kopcu
 while (2* w+1< n) // dopóki są dzieci, chociażby tylko lewe
 lewy = 2 * w +1 // indeks lewego dziecka
 prawy = 2 * w +2 // indeks prawego dziecka
 największy = w
 if(kopiec[lewy]>kopiec[największy])
 największy = lewy//Jeżeli lewe dziecko ma wartość większą
 if(prawy<n && kopiec[prawy]> kopiec[największy])
 największy = prawy//Jeżeli prawe dziecko ma wartość większą
 if (największy != w)
 tmp=kopiec[w] // zamień korzeń z większym dzieckiem
 kopiec[w] = kopiec[największy]
 kopiec[największy]=tmp
 w = największy
 else
 break // zakończ pętlę

Naprawianie kopca – rekurencja(C#)
 static void Napraw(int[] kopiec, int węzeł)
{
    int wielkość = kopiec.Length;
    int największy = węzeł; // korzeń drzewa
    int lewe = 2 * węzeł + 1;
    int prawe = 2 * węzeł + 2;
    // dopóki są dzieci
    if (lewe < wielkość && kopiec[lewe] > kopiec[największy])
    {
        największy = lewe;
    }
    if (prawe < wielkość && kopiec[prawe] > kopiec[największy])
    {
        największy = prawe;
    }
    if (największy != węzeł) // zamiana
    {
        int pomoc = kopiec[węzeł];
        kopiec[węzeł] = kopiec[największy];
        kopiec[największy] = pomoc;
        Napraw(kopiec, największy);
    }
}

Naprawianie kopca – iteracja(C#)
static void Napraw(int[] kopiec, int węzeł)
{
    int wielkość = kopiec.Length;
    int największy = węzeł; // korzeń drzewa lub poddrzewa
    while (węzeł <= (wielkość - 1) / 2) // dopóki są dzieci
    {
        int lewe = 2 * węzeł + 1;
        int prawe = 2 * węzeł + 2;
        if (lewe < wielkość && kopiec[lewe] > kopiec[największy])
        {
            największy = lewe;
        }
        if (prawe < wielkość && kopiec[prawe] > kopiec[największy])
        {
            największy = prawe;
        }
        if (największy != węzeł)
        {
            int pomoc = kopiec[węzeł];
            kopiec[węzeł] = kopiec[największy];
            kopiec[największy] = pomoc;
            węzeł = największy; // w następnej iteracji
        }
        else break;// nie bylo potrzeby naprawiać
    }
}

static void Buduj(int[] kopiec)
{
    int wielkość = kopiec.Length;
    for (int i = (wielkość / 2 - 1); i >= 0; i--)
        Napraw(kopiec, i);
}


Sortowanie przez kopcowanie(C#)
static void Napraw(int[] kopiec, int węzeł, int wielkość)
{
    int największy = węzeł; // korzeń drzewa
    int lewe = 2 * węzeł + 1;
    int prawe = 2 * węzeł + 2;
    // dopóki są dzieci
    if (lewe < wielkość && kopiec[lewe] > kopiec[największy])
    {
        największy = lewe;
    }
    if (prawe < wielkość && kopiec[prawe] > kopiec[największy])
    {
        największy = prawe;
    }
    if (największy != węzeł)
    {
        int pomoc = kopiec[węzeł];
        kopiec[węzeł] = kopiec[największy];
        kopiec[największy] = pomoc;
        Napraw(kopiec, największy, wielkość);
    }
}
Algorytmy i Struktury Danych 22
static void Sortuj(int[] dane)
{
    Buduj(dane);
    int wielkość = dane.Length;
    while (wielkość > 1)
    {
        // zamieniamy największy element z ostatnim
        int największy = dane[0];
        dane[0] = dane[wielkość - 1];
        dane[wielkość - 1] = największy;
        // naprawiamy zmniejszony kopiec
        wielkość = wielkość - 1;
        Napraw(dane, 0, wielkość);
    }
}
static void Buduj(int[] kopiec)
{
    int wielkość = kopiec.Length;
    for (int i = (wielkość / 2 - 1); i >= 0; i--)
        Napraw(kopiec, i, kopiec.Length);
}
Dodajemy parametr wielkość w metodzie Napraw,
aby pracować tylko z tą częścią tablicy, która
tworzy kopiec(wówczas musimy uwzględnić to w
metodzie buduj)

//drzewo
// pre-order
 static void Wypisuj(Węzeł węzeł)
{
    Console.Write("(" + węzeł.wartość);
    if (węzeł.dzieci.Count > 0)
    {
        for (int i = 0; i < węzeł.dzieci.Count; i++)
        {
            Wypisuj((Węzeł)węzeł.dzieci[i]);
        }
    }
    Console.Write(")");
}

// post-order
static void WypisujPost(Węzeł węzeł)
{
    // najpierw wypisujemy potomków
    if (węzeł.dzieci.Count > 0)
    {
        for (int i = 0; i < węzeł.dzieci.Count; i++)
        {
            WypisujPost((Węzeł)węzeł.dzieci[i]);
        }
    }
    // potem rodzica
    Console.Write(" " + węzeł.wartość);
}
static int Wysokość(Węzeł węzeł)
{
    int wysokość = 0;
    for (int i = 0; i < węzeł.dzieci.Count; i++)
    {
        Węzeł następnik = (Węzeł)węzeł.dzieci[i];
        wysokość = Math.Max(wysokość, Wysokość(następnik) + 1);
    }
    return wysokość;
}// zwraca wynik

Reprezentacja dowiązaniowa drzewa - uwagi
 Reprezentacja dowiązaniowa jest przydatna gdy
chcemy do krawędzi przyporządkować wagi, wówczas
wygodnie jest dodać dodatkową klasę Krawędź.
17 Algorytmy i Struktury Danych
class Krawędź
{
    public Węzeł węzeł;
    public int waga;
    public Krawędź(Węzeł węzeł, int waga)
    {
        this.węzeł = węzeł;
        this.waga = waga;
    }
}
class Drzewo
{
    public Węzeł korzeń;
}
class Węzeł
{
    public String wartość;
    public List<Krawędź> dzieci;
    public Węzeł(String wartość)
    {
        this.wartość = wartość;
        dzieci = new List<Krawędź>();
    }
}

Uwagi o implementacji obiektowej
 Implementacja obiektowa z jednej strony jest wygodna
ale z drugiej strony wymaga jednoznacznej identyfikacji
węzłów.
18 Algorytmy i Struktury Danych
class Drzewo<T> where T : IEquatable<T>
{
    // klasa pomocnicza Węzeł
    class Węzeł
    {
        public T wartość;
        public List<Węzeł> dzieci;
        public Węzeł(T wartość)
        {
            this.wartość = wartość;
            this.dzieci = new List<Węzeł>();
        }
    }
    Węzeł korzeń;
    // metody
}
public bool DodajKorzeń(T korzeń)
{
    if (this.korzeń == null)
    {
        this.korzeń = new Węzeł(korzeń);
        return true;
    }
    return false; // korzeń już jest
}

Uwagi o implementacji obiektowej(2)
 Identyfikacji węzłów mogłaby dokonywać pomocnicza
prywatna metoda Znajdź.Zakładamy, że węzeł jest
jednoznacznie określony przez przechowywaną wartość
(a typ T jest Equatable)
19 Algorytmy i Struktury Danych
Węzeł Znajdź(Węzeł węzeł, T wartość)
{
    if (węzeł.wartość.Equals(wartość)) return węzeł;
    if (węzeł.dzieci.Count > 0)
    {
        for (int i = 0; i < węzeł.dzieci.Count; i++)
        {
            Węzeł szukany = Znajdź(węzeł.dzieci[i], wartość);
            if (szukany != null) return szukany;
        }
    }
    return null;
}

Uwagi o implementacji obiektowej(3)
 Wówczas nowy element dodaje się do znalezionego
węzła przechowującego podaną wartość.Poniższa
metoda aż dwa razy wywołuje Znajdź.Taka metoda jest
kosztowna.
20 Algorytmy i Struktury Danych
 public bool Dodaj(T rodzic, T dziecko)
{
    if (korzeń == null) return false;
    Węzeł parent = Znajdź(korzeń, rodzic);
    if (parent == null) // nie ma takiego węzła nie ma gdzie doczepić dziecka
        return false;
    if (Znajdź(korzeń, dziecko) != null) // takie dziecko juz jest
        return false;
    parent.dzieci.Add(new Węzeł(dziecko));
    return true;
}

Uwagi o implementacji obiektowej(4)
 Wypisywanie i inne operacje są raczej proste.
21 Algorytmy i Struktury Danych
 public void WypiszPre()
{
    if (korzeń == null)
    {
        Console.WriteLine("drzewo jest puste");
    }
    WypisujPre(korzeń);
}
void WypisujPre(Węzeł węzeł)
{
    Console.Write(węzeł.wartość + " ");
    if (węzeł.dzieci.Count > 0)
    {
        for (int i = 0; i < węzeł.dzieci.Count; i++)
            WypisujPre((Węzeł)węzeł.dzieci[i]);
    }
}

Reprezentacja „rodzicielska” drzewa z korzeniem
na tablicy
 Przykładowe kody w C#.
class Drzewo
{
    const int n = 100;
    int[] rodzice = new int[n];
    string[] etykiety = new string[n];
    int m = 0;
    public Drzewo(string korzeń)
    {
        rodzice[0] = -1;
        etykiety[0] = korzeń;
        m = 1;
    }
    public int Dodaj(string etykieta, int rodzic)
    {
        rodzice[m] = rodzic;
        etykiety[m] = etykieta;
        return m++;
    }
    //…
}
Reprezentacja „rodzicielska”
wypisywanie pre-order i post-order
Algorytmy i Struktury Danych 24
 public void WypiszPre() // pre-order
{
    WypisujPre(0);
    Console.WriteLine();
}
public void WypisujPre(int k)
{
    Console.Write("(" + etykiety[k]);
    for (int i = 0; i < m; i++)
        if (rodzice[i] == k) WypisujPre(i);
}
public void WypiszPost() // post-order
{
    WypisujPost(0);
    Console.WriteLine();
}
public void WypisujPost(int k)
{
    for (int i = 0; i < m; i++)
        if (rodzice[i] == k) WypisujPost(i);
    Console.Write(" " + etykiety[k]);
}


Wypisywanie drzewa binarnego
Algorytmy i Struktury Danych 33
// in-order
static void WypisujIn(Węzeł węzeł)
{
    if (węzeł == null) return;
    WypisujIn((Węzeł)węzeł.lewy);
    Console.Write(węzeł.wartość + " ");
    WypisujIn((Węzeł)węzeł.prawy);
}
static int Wysokość(Węzeł węzeł)
{
    int wysokość = 0;
    if (węzeł == null) return 0;
    if (węzeł.lewy != null)
        wysokość = Math.Max(wysokość, Wysokość(węzeł.lewy) + 1);
    if (węzeł.prawy != null)
        wysokość = Math.Max(wysokość, Wysokość(węzeł.prawy) + 1);
    return wysokość;
}// Zwraca wynik
// pre-order
static void WypisujPre(Węzeł węzeł)
{
    if (węzeł == null) return;
    Console.Write(węzeł.wartość + " ");
    WypisujPre((Węzeł)węzeł.lewy);
    WypisujPre((Węzeł)węzeł.prawy);
}
// post-order
static void WypisujPost(Węzeł węzeł)
{
    if (węzeł == null) return;
    WypisujPost((Węzeł)węzeł.lewy);
    WypisujPost((Węzeł)węzeł.prawy);
    Console.Write(węzeł.wartość + " ");
}


static public Lista Dodaj(Lista l, int liczba) //Do głowy
{
    Lista tmp = new Lista(); // nowy węzeł
    tmp.dane = liczba;
    tmp.następny = l; //dotychczasowa głowa staje się "następny"
    return tmp; // dodany element staje się głową
}


 Sprawdzanie czy lista jest pusta i obliczanie ile elementów zawiera.
static public bool CzyPusta(Lista l)
{
    return l == null;
}
// obliczamy rozmiar przechodząc przez wszystkie elementy listy
static public int PodajRozmiar(Lista l) // aż dojedziemy do nulla
{
    int licznik = 0;
    for (Lista tmp = l; tmp != null; tmp = tmp.następny)
        licznik++;
    return licznik;
}
 Usuwanie elementu najłatwiejsze jest od początku listy.
static public Lista Usuń(Lista l) //Z głowy
{
    if (l != null) // sprawdzamy, czy lista nie jest pusta
        return l.następny;
    else return l;
}


 Odczytywanie wartości i-tego elementu(błąd gdy i-ty element nie istnieje).
static public int Podaj(Lista l, int i) //i-ty element
{
    int licznik = 0;
    for (Lista tmp = l; tmp != null; tmp = tmp.następny)
        if (licznik++ == i) return tmp.dane;
    throw new Exception("indeks poza zakresem!");
}
 Sprawdzanie czy lista zawiera szukaną wartość(zwracamy indeks elementu
albo -1 gdy nie znaleziono).
static public int CzyZawiera(Lista l, int n) //element o wartości n
{
    int licznik = 0;
    for (Lista tmp = l; tmp != null; tmp = tmp.następny, licznik++)
        if (tmp.dane == n) return licznik;
    return -1;
}

static public Lista Dodaj(Lista L, int n, int i)
{
    if (i == 0) return Dodaj(L, n); // jak i zero to na początek
    int licznik = 0;
    for (Lista tmp = L; tmp != null; tmp = tmp.następny, licznik++)
        if (licznik == i - 1)
        {
            Lista l = new Lista();
            l.dane = n;
            l.następny = tmp.następny;
            tmp.następny = l;
            return L;
        }
    throw new Exception("indeks poza zakresem!");
}


static public Lista Usuń(Lista L, int i) //usuwa element na i-tej pozycji
{
    if (i == 0) return Usuń(L);
    int licznik = 0;
    for (Lista tmp = L; tmp.następny != null; tmp = tmp.następny, licznik++)
        if (licznik == i - 1)
        {
            tmp.następny = tmp.następny.następny;
            return L;
        }
    throw new Exception("indeks poza zakresem!");
}

Implementacja obiektowa listy dowiązaniowej
Algorytmy i Struktury Danych 26
public class Węzeł
{
    public int dane;// w węźle przechowujemy liczbę
    public Węzeł następny; // oraz referencję do następnego
}
class Lista
{
    Węzeł głowa = null;
    public bool CzyPusta()
    {
        return głowa == null;
    }
    public int PodajRozmiar()
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            licznik++;
        return licznik;
    }
    public void Dodaj(int liczba) //Do głowy
    {
        Węzeł tmp = new Węzeł(); // nowy węzeł
        tmp.dane = liczba;
        tmp.następny = głowa; //głowa staje się "następny"
        głowa = tmp;// dodany element staje się głową
    }
    public void Usuń() //Z głowy
    {
        if (głowa != null) // sprawdzamy, czy lista nie jest pusta
            głowa = głowa.następny;
    }
    public int Podaj(int i) //i-ty element
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny)
            if (licznik++ == i) return tmp.dane;
        throw new Exception("indeks poza zakresem!");
    }
    public int CzyZawiera(int n) //element o wartości n
    {
        int licznik = 0;
        for (Węzeł tmp = głowa; tmp != null; tmp = tmp.następny, licznik++)
            if (tmp.dane == n) return licznik;
        return -1;
    }
    //…
}


mplementacja obiektowa listy na tablicy
Algorytmy i Struktury Danych 29
class Lista
{
    int[] dane = new int[pojemność];
    int rozmiar = 0;
    const int pojemność = 1000; // stała
    public bool CzyPusta()
    {
        return rozmiar == 0;
    }
    public int PodajRozmiar()
    {
        return rozmiar;
    }
    public void Dodaj(int liczba) //na koniec
    {
        if (rozmiar == pojemność)
            throw new Exception("brak miejsca!");
        dane[rozmiar] = liczba;
        rozmiar++;
    }
    public void Usuń() //z końca
    {
        if (rozmiar > 0) rozmiar--;
    }
    public int Podaj(int i) //i-ty element
    {
        if (i >= 0 && i < rozmiar) return dane[i];
        throw new Exception("indeks poza zakresem!");
    }
    public int CzyZawiera(int n) //element o wartości n
    {
        for (int i = 0; i < rozmiar; i++)
        {
            if (dane[i] == n) return i;
        }
        return -1;
    }
    //łączy dwie listy "dokleja" do pierwszej drugą
    public void Dołącz(Lista LB)
    {
        if (rozmiar + LB.rozmiar > pojemność)
            throw new Exception("brak miejsca!");
        for (int i = 0; i < LB.rozmiar; i++)
            dane[i + rozmiar] = LB.dane[i];
        rozmiar += LB.rozmiar;
    }
    //…
}

Implementacja stosu z dowiązaniami
class Stos
{
    Węzeł wierzchołek = null;
    public bool CzyPusty()
    {
        return wierzchołek == null;
    }
    public void Połóż(int liczba) //na wierzchołek
    {
        Węzeł tmp = new Węzeł(); // nowy węzeł
        tmp.dane = liczba;
        tmp.następny = wierzchołek;//dotychczasowy wierzchołek staje się "następny"
        wierzchołek = tmp;// dodany element staje się wierzchołkiem
    }
    //…
}


mplementacja stosu z dowiązaniami c.d.
public int Zdejmij() //Z wierzchołka
{
    int v;
    if (wierzchołek != null) // sprawdzamy, czy stos nie jest pusty
    {
        v = wierzchołek.dane;
        wierzchołek = wierzchołek.następny;
    }
    else
    {
        throw new Exception("stos pusty!");
    }
    return v;
}
public int Podejrzyj() //co na wierzchołku
{
    if (wierzchołek != null) // sprawdzamy, czy stos nie jest pusty
    {
        return wierzchołek.dane;
    }
    else
    {
        throw new Exception("stos pusty!");
    }
}


Implementacja tablicowa stosu
class StosT
{
    int wierzchołek = 0; const int rozmiar = 100;
    int[] dane = new int[rozmiar];
    public bool CzyPusty()
    {
        return wierzchołek == 0;
    }
    public void Połóż(int liczba) //na wierzchołek
    {
        if (wierzchołek < rozmiar) dane[wierzchołek++] = liczba;
        else throw new Exception("stos pełny!");
    }
    public int Zdejmij() //Z wierzchołka
    {
        if (wierzchołek != 0) // sprawdzamy, czy stos nie jest pusty
            return dane[--wierzchołek];
        else throw new Exception("stos pusty!");
    }
    public int Podejrzyj() //co na wierzchołku
    {
        if (wierzchołek != 0) // sprawdzamy, czy stos nie jest pusty
            return dane[wierzchołek - 1];
        else throw new Exception("stos pusty!");
    }
}

Implementacja stosu w.NET - przykłady
Stack myStack = new Stack();
myStack.Push(22);
 myStack.Push(33);
 myStack.Push(44);
 Console.WriteLine(myStack.Peek());
 Console.WriteLine();
 while (myStack.Count>0)
 Console.Write(myStack.Pop()+" ");
Algorytmy i Struktury Danych 40
Stack<int> myStack = new Stack<int>();
myStack.Push(22);
 myStack.Push(33);
 myStack.Push(44);
 Console.WriteLine(myStack.Peek());
 Console.WriteLine();
 while (myStack.Count > 0)
 Console.Write(myStack.Pop() + " ");


    Implementacja kolejki z dowiązaniami
class KolejkaS
{
    Węzeł głowa = null; Węzeł ogon = null;
    public static bool CzyPusta(KolejkaS q)
    {
        return q.głowa == null;
    }
    public static int Usuń(KolejkaS q) //Z początku
    {
        if (q.głowa != null) // sprawdzamy, czy kolejka nie jest pusta
        {
            int v = q.głowa.dane; q.głowa = q.głowa.następny;
            if (q.głowa == null) q.ogon = null;
            return v;
        }
        else throw new Exception("kolejka pusta!");
    }
    //…
}
Algorytmy i Struktury Danych 42
public class Węzeł
{
    public int dane;// w węźle przechowujemy liczbę
    public Węzeł następny; // oraz referencję do następnego
}
Implementacja kolejki z dowiązaniami c.d.
 public static int Podejrzyj(KolejkaS q) //co na początku ?
{// sprawdzamy, czy kolejka nie jest pusta
    if (q.głowa != null) return q.głowa.dane;
    else throw new Exception("kolejka pusta!");
}
//dodaje element o wartości n na koniec
public static void Dodaj(KolejkaS q, int n)
{
    Węzeł l = new Węzeł();
    l.dane = n; l.następny = null;
    if (q.głowa == null) q.głowa = q.ogon = l;
    else { q.ogon.następny = l; q.ogon = l; }
    return;
}

Implementacja tablicowa kolejki FIFO(1)
class KolejkaT
{
    int głowa = 0;
    int ogon = 0;
    const int rozmiar = 30;
    int[] dane = new int[rozmiar];
    public bool CzyPusta()
    {
        return ogon == głowa;
    }
    public int Usuń() //Z początku
    {
        if (głowa != ogon) // sprawdzamy, czy kolejka nie jest pusta
        {
            return dane[głowa++];
        }
        else throw new Exception("kolejka pusta!");
    }
    Implementacja tablicowa kolejki FIFO(2)
 public int Podejrzyj() //na początku
    {
        if (głowa != ogon) // sprawdzamy, czy kolejka nie jest pusta
        {
            return dane[głowa];
        }
        else throw new Exception("kolejka pusta!");
    }
    public void Dodaj(int n) //dodaje element o wartości n na koniec
    {
        if (ogon < rozmiar)
        {
            dane[ogon++] = n;
        }
        // tutaj mógłbym próbować przeorganizować kolejkę
        else throw new Exception("nie ma miejsca!");
        return;
    }

    Implementacja cykliczna tablicowa kolejki(1)
class KolejkaC
    {
        int głowa = 0; int ogon = 0;
        const int rozmiar = 10;
        int[] dane = new int[rozmiar];
        int licznik = 0;
        public bool CzyPusta()
        {
            return licznik == 0;
        }
        public int Usuń() //Z początku
        {
            if (licznik != 0) // sprawdzamy, czy kolejka nie jest pusta
            {
                int v = dane[głowa];
                głowa = (głowa + 1) % rozmiar;
                licznik--;
                return v;
            }
            else
                throw new Exception("kolejka pusta!");
        }


        Implementacja cykliczna tablicowa kolejki(2)
public int Podejrzyj() //co na początku
        {
            if (licznik != 0) // sprawdzamy, czy kolejka nie jest pusta
            {
                return dane[głowa];
            }
            else
                throw new Exception("kolejka pusta!");
        }
        public void Dodaj(int n) //dodaje element o wartości n na koniec
        {
            if (licznik == rozmiar)
                throw new Exception("zakres przekroczony!");
            dane[ogon] = n;
            ogon = (ogon + 1) % rozmiar;
            licznik++;
            return;
        }
    }


    Implementacja kolejki w.NET - przykłady
Queue myQueue = new Queue();
    myQueue.Enqueue(22);
 myQueue.Enqueue(33);
 myQueue.Enqueue(44);
 Console.WriteLine(myQueue.Peek());
 Console.WriteLine();
 while (myQueue.Count > 0)
 Console.Write(myQueue.Dequeue() + " ");
Algorytmy i Struktury Danych 51
Queue<int> myQueue = new Queue<int>();
    myQueue.Enqueue(22);
 myQueue.Enqueue(33);
 myQueue.Enqueue(44);
 Console.WriteLine(myQueue.Peek());
 Console.WriteLine();
 while (myQueue.Count > 0)
 Console.Write(myQueue.Dequeue() + "

        Sortowanie kubełkowe – kod w C#
static void Kubelkowe(int[] D, int m)
    {
        int N = D.Length; int min = D[0]; int max = D[0];
        for (int i = 1; i < N; i++)
        { if (min > D[i]) min = D[i]; if (max < D[i]) max = D[i]; }
        // tworzymy m kubelkow bardzo pojemnych
        int[,] kubelki = new int[m, N + 1];
        for (int i = 0; i < m; i++) kubelki[i, N] = 0; // zerujemy liczni ki kubelkow
                                                       // dodajemy do odpowiednich kubelkow wartości elementów sortowanego zbioru
        for (int i = 0; i < N; i++)
        {
            int num = ((D[i] - min) * m) / (max - min + 1);
            kubelki[num, kubelki[num, N]++] = D[i];
        }
        // sortowanie w kubełkach
        for (int i = 0; i < m; i++) SortujWKubelku(kubelki, i);
        int j = 0; // laczenie kubelkow
        for (int i = 0; i < m; i++)
            for (int k = 0; k < kubelki[i, N]; k++)
            { D[j] = kubelki[i, k]; j++; }
    }
    Algorytmy i Struktury Danych 54
static void SortujWKubelku(int[,] L, int m)
    {
        // sortowanie m-tego kubelka przez wstawianie
        int k, j;
        int M = L[m, L.GetLength(1) - 1]; // ilosc elementow
        for (int i = 1; i < M; i++)
        {
            k = L[m, i]; j = i;
            while (j > 0 && L[m, j - 1] > k)
            { L[m, j] = L[m, j - 1]; j--; }
            L[m, j] = k; // wstawiam w odpowiednie miejsce
        }
    }

    Sortowanie kubełkowe z listami – kod w C#
static void Kubelkowe(int[] D, int m)
    {
        int N = D.Length;
        int min = D[0];
        int max = D[0];
        for (int i = 1; i < N; i++)
        {
            if (min > D[i]) min = D[i];
            if (max < D[i]) max = D[i];
        }
        // tworzymy m kubelkow
        List<int>[] kubelki = new List<int>[m];
        for (int i = 0; i < m; i++) kubelki[i] = new List<int>();
        // dodajemy do odpowiednich kubelkow wartości elementów
        for (int i = 0; i < N; i++)
        {
            int num = ((D[i] - min) * m) / (max - min + 1);
            kubelki[num].Add(D[i]);
        }

        Algorytmy i Struktury Danych 57
 // sortowanie w kubełkach
 for (int i = 0; i < m; i++)
            kubelki[i].Sort();
        // laczenie kubelkow
        int j = 0;
        for (int i = 0; i < m; i++)
            for (int k = 0; k < kubelki[i].Count; k++)
            {
                D[j] = kubelki[i][k];
                j++;
            }
    }

    Laboratorium 9 - Drzewa.Drzewa binarne.
drzewo dowiązaniowe
[code csharp]

using System;
using System.Collections;

// klasa pomocnicza Węzeł
class Węzeł
{
    public String wartość;
    public ArrayList dzieci;
}

// klasa Drzewo
class Drzewo
{
    public Węzeł korzeń;
}

class Program
{
    static Węzeł UtwórzWęzeł(String wartość)
    {
        Węzeł węzeł = new Węzeł();
        węzeł.wartość = wartość;
        węzeł.dzieci = new ArrayList();
        return węzeł;
    }

    static void InicjujWęzeł(Węzeł węzeł, String wartość)
    {
        węzeł.wartość = wartość;
        węzeł.dzieci = new ArrayList();
    }

    static void DodajWęzeł(Węzeł węzeł, Węzeł dziecko)
    {
        węzeł.dzieci.Add(dziecko);
    }

    // pre-order
    static void Wypisuj(Węzeł węzeł)
    {
        Console.Write("(" + węzeł.wartość);
        if (węzeł.dzieci.Count > 0)
        {
            for (int i = 0; i < węzeł.dzieci.Count; i++)
            {
                Wypisuj((Węzeł)węzeł.dzieci[i]);
            }
        }
        Console.Write(")");
    }

    // post-order
    static void WypisujPost(Węzeł węzeł)
    {
        // najpierw wypisujemy potomków
        if (węzeł.dzieci.Count > 0)
        {
            for (int i = 0; i < węzeł.dzieci.Count; i++)
            {
                WypisujPost((Węzeł)węzeł.dzieci[i]);
            }
        }
        // potem rodzica
        Console.Write(" " + węzeł.wartość);
    }


    static int Wysokość(Węzeł węzeł)
    {
        int wysokość = 0;
        for (int i = 0; i < węzeł.dzieci.Count; i++)
        {
            Węzeł następnik = (Węzeł)węzeł.dzieci[i];
            wysokość = Math.Max(wysokość, Wysokość(następnik) + 1);
        }
        return wysokość;
    }// Zwraca wynik


    static void Main()
    {
        Drzewo drzewo = new Drzewo();

        drzewo.korzeń = UtwórzWęzeł("F");
        Węzeł wB = UtwórzWęzeł("B");
        Węzeł wA = UtwórzWęzeł("A");
        Węzeł wC = UtwórzWęzeł("C");
        Węzeł wD = UtwórzWęzeł("D");
        Węzeł wE = UtwórzWęzeł("E");
        Węzeł wG = UtwórzWęzeł("G");
        Węzeł wH = UtwórzWęzeł("H");
        Węzeł wI = UtwórzWęzeł("I");

        DodajWęzeł(wD, wC);
        DodajWęzeł(wD, wE);
        DodajWęzeł(wB, wA);
        DodajWęzeł(wB, wD);

        DodajWęzeł(wI, wH);
        DodajWęzeł(wG, wI);

        DodajWęzeł(drzewo.korzeń, wB);
        DodajWęzeł(drzewo.korzeń, wG);

        Wypisuj(drzewo.korzeń);
        Console.WriteLine();
        WypisujPost(drzewo.korzeń);
        Console.WriteLine();
        Console.WriteLine("wysokość = " + Wysokość(drzewo.korzeń));

        Console.ReadKey();
    }
}

Laboratorium 9 - Drzewa.Drzewa binarne.
drzewo binarne
[code csharp]

using System;
using System.Collections;

// klasa pomocnicza Węzeł
class Węzeł
{
    public String wartość;
    public Węzeł lewy;
    public Węzeł prawy;
}

// klasa Drzewo
class Drzewo
{
    public Węzeł korzeń;
}

class Program
{
    static Węzeł UtwórzWęzeł(String wartość)
    {
        Węzeł węzeł = new Węzeł();
        węzeł.wartość = wartość;
        return węzeł;
    }

    static void InicjujWęzeł(Węzeł węzeł, String wartość)
    {
        węzeł.wartość = wartość;
    }

    static void DodajLewy(Węzeł węzeł, Węzeł dziecko)
    {
        węzeł.lewy = dziecko;
    }
    static void DodajPrawy(Węzeł węzeł, Węzeł dziecko)
    {
        węzeł.prawy = dziecko;
    }

    // pre-order
    static void WypisujPre(Węzeł węzeł)
    {
        if (węzeł == null) return;
        Console.Write(węzeł.wartość + " ");
        WypisujPre((Węzeł)węzeł.lewy);
        WypisujPre((Węzeł)węzeł.prawy);
    }

    // post-order
    static void WypisujPost(Węzeł węzeł)
    {
        if (węzeł == null) return;
        WypisujPost((Węzeł)węzeł.lewy);
        WypisujPost((Węzeł)węzeł.prawy);
        Console.Write(węzeł.wartość + " ");
    }

    // in-order
    static void WypisujIn(Węzeł węzeł)
    {
        if (węzeł == null) return;
        WypisujIn((Węzeł)węzeł.lewy);
        Console.Write(węzeł.wartość + " ");
        WypisujIn((Węzeł)węzeł.prawy);
    }

    static int Wysokość(Węzeł węzeł)
    {
        int wysokość = 0;
        if (węzeł == null) return 0;
        if (węzeł.lewy != null)
            wysokość = Math.Max(wysokość, Wysokość(węzeł.lewy) + 1);
        if (węzeł.prawy != null)
            wysokość = Math.Max(wysokość, Wysokość(węzeł.prawy) + 1);
        return wysokość;
    }// Zwraca wynik


    static void Main()
    {
        Drzewo drzewo = new Drzewo();

        drzewo.korzeń = UtwórzWęzeł("F");
        Węzeł wB = UtwórzWęzeł("B");
        Węzeł wA = UtwórzWęzeł("A");
        Węzeł wC = UtwórzWęzeł("C");
        Węzeł wD = UtwórzWęzeł("D");
        Węzeł wE = UtwórzWęzeł("E");
        Węzeł wG = UtwórzWęzeł("G");
        Węzeł wH = UtwórzWęzeł("H");
        Węzeł wI = UtwórzWęzeł("I");

        DodajLewy(wD, wC);
        DodajPrawy(wD, wE);
        DodajLewy(wB, wA);
        DodajPrawy(wB, wD);

        DodajLewy(wI, wH);
        DodajPrawy(wG, wI);

        DodajLewy(drzewo.korzeń, wB);
        DodajPrawy(drzewo.korzeń, wG);

        WypisujPre(drzewo.korzeń);
        Console.WriteLine();
        WypisujPost(drzewo.korzeń);
        Console.WriteLine();
        WypisujIn(drzewo.korzeń);
        Console.WriteLine();
        Console.WriteLine("wysokość = " + Wysokość(drzewo.korzeń));

        Console.ReadKey();
    }
}


[/code]

code csharp]

using System;
using System.Collections;


// klasa Drzewo
class Drzewo
{
    public string[] drzewo = new string[31];
    public int ilość = 0;
}

class Program
{
    static void DodajWęzeł(Drzewo d, string s)
    {
        d.drzewo[d.ilość++] = s;
    }

    // pre-order
    static void WypisujPre(Drzewo d, int i)
    {
        if (i >= d.ilość) return;
        Console.Write(d.drzewo[i] + " ");
        WypisujPre(d, 2 * i + 1);
        WypisujPre(d, 2 * i + 2);
    }

    // post-order
    static void WypisujPost(Drzewo d, int i)
    {
        if (i >= d.ilość) return;
        WypisujPost(d, 2 * i + 1);
        WypisujPost(d, 2 * i + 2);
        Console.Write(d.drzewo[i] + " ");
    }

    // in-order
    static void WypisujIn(Drzewo d, int i)
    {
        if (i >= d.ilość) return;
        WypisujIn(d, 2 * i + 1);
        Console.Write(d.drzewo[i] + " ");
        WypisujIn(d, 2 * i + 2);
    }

    static int Wysokość(Drzewo d)
    {
        int wysokość = 0, p = d.ilość / 2;
        while (p > 0)
        {
            p = p / 2;
            wysokość++;
        }
        return wysokość;
    }// Zwraca wynik


    static void Main()
    {
        Drzewo drzewo = new Drzewo();
        DodajWęzeł(drzewo, "A");
        DodajWęzeł(drzewo, "B");
        DodajWęzeł(drzewo, "D");
        DodajWęzeł(drzewo, "E");
        DodajWęzeł(drzewo, "C");
        DodajWęzeł(drzewo, "H");
        DodajWęzeł(drzewo, "I");
        DodajWęzeł(drzewo, "K");
        DodajWęzeł(drzewo, "F");
        DodajWęzeł(drzewo, "G");
        DodajWęzeł(drzewo, "L");
        DodajWęzeł(drzewo, "M");
        DodajWęzeł(drzewo, "J");

        WypisujPre(drzewo, 0);
        Console.WriteLine();
        WypisujPost(drzewo, 0);
        Console.WriteLine();
        WypisujIn(drzewo, 0);
        Console.WriteLine();
        Console.WriteLine("wysokość = " + Wysokość(drzewo));

        Console.ReadKey();
    }
}

[/code]