Csatolt lista létrehozása PHP-ban

Egy csatolt lista, valamint függvények a csomópontok kiírására, rendezésére, megtalálására és törlésére:

<?php

class CsomoPont {

    public $adat;

    public $kovetkezo;

    public function __construct($adat) {

        $this->adat = $adat;

        $this->kovetkezo = null;

    }

}

function kiirCsatoltListat($fej) {

    $jelenlegi = $fej;

    while ($jelenlegi != null) {

        echo $jelenlegi->adat . " ";

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    echo "\n";

}

function rendezCsatoltListat($fej) {

    $adatok = [];

    $jelenlegi = $fej;

    while ($jelenlegi != null) {

        $adatok[] = $jelenlegi->adat;

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    sort($adatok);

    $rendezettFej = new CsomoPont($adatok[0]);

    $akt = $rendezettFej;

    for ($i = 1; $i < count($adatok); $i++) {

        $akt->kovetkezo = new CsomoPont($adatok[$i]);

        $akt = $akt->kovetkezo;

    }

    return $rendezettFej;

}

function torolCsomopontot($fej, $celAdat) {

    $jelenlegi = $fej;

    $elozo = null;

    while ($jelenlegi != null && $jelenlegi->adat != $celAdat) {

        $elozo = $jelenlegi;

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    if ($jelenlegi == null) {

        echo "A csomópont nem található.\n";

        return $fej;

    }

    if ($elozo != null) {

        $elozo->kovetkezo = $jelenlegi->kovetkezo;

    } else {

        $fej = $jelenlegi->kovetkezo;

    }

    return $fej;

}

// Példa csatolt lista létrehozása

$fej = new CsomoPont(4);

$fej->kovetkezo = new CsomoPont(2);

$fej->kovetkezo->kovetkezo = new CsomoPont(1);

$fej->kovetkezo->kovetkezo->kovetkezo = new CsomoPont(3);

// Csatolt lista kiírása

echo "Eredeti lista:\n";

kiirCsatoltListat($fej);

// Csatolt lista rendezése

$rendezettFej = rendezCsatoltListat($fej);

echo "Rendezett lista:\n";

kiirCsatoltListat($rendezettFej);

// Csomópont törlése

$torlendoAdat = 2;

$fej = torolCsomopontot($fej, $torlendoAdat);

echo "A(z) $torlendoAdat értékű csomópontot töröltük:\n";

kiirCsatoltListat($fej);

?>

A CsomoPont osztály létrehoz egy csomópontot. A kiirCsatoltListat függvény kiírja a csatolt lista elemeit. A rendezCsatoltListat függvény rendez egy csatolt listát, a torolCsomopontot függvény pedig megtalálja és törli a megadott értékű csomópontot. Az eredményeket a kiirCsatoltListat függvény segítségével írjuk ki.

Egy csatolt listát mutatok be PHP-ban, valamint függvényeket a csomópontok kiírására, rendezésére és törlésére:

<?php

class CsomoPont {

    public $adat;

    public $kovetkezo;

    public function __construct($adat) {

        $this->adat = $adat;

        $this->kovetkezo = null;

    }

}

function kiirCsatoltListat($fej) {

    $jelenlegi = $fej;

    while ($jelenlegi != null) {

        echo $jelenlegi->adat . " ";

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    echo "\n";

}

function rendezCsatoltListat($fej) {

    if ($fej == null || $fej->kovetkezo == null) {

        return $fej;

    }

    $pivot = $fej->adat;

    $kisebbek = $nagyobbak = [];

    $jelenlegi = $fej->kovetkezo;

    while ($jelenlegi != null) {

        if ($jelenlegi->adat < $pivot) {

            $kisebbek[] = $jelenlegi->adat;

        } else {

            $nagyobbak[] = $jelenlegi->adat;

        }

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    $kisebbek = rendezCsatoltListat($kisebbek);

    $nagyobbak = rendezCsatoltListat($nagyobbak);

    $rendezettFej = new CsomoPont($pivot);

    $akt = $rendezettFej;

    foreach ($kisebbek as $kisebb) {

        $akt->kovetkezo = new CsomoPont($kisebb);

        $akt = $akt->kovetkezo;

    }

    foreach ($nagyobbak as $nagyobb) {

        $akt->kovetkezo = new CsomoPont($nagyobb);

        $akt = $akt->kovetkezo;

    }

    return $rendezettFej;

}

function torolCsomopontot($fej, $celAdat) {

    if ($fej == null) {

        return null;

    }

    while ($fej != null && $fej->adat == $celAdat) {

        $fej = $fej->kovetkezo;

    }

    $jelenlegi = $fej;

    $elozo = null;

    while ($jelenlegi != null) {

        if ($jelenlegi->adat == $celAdat) {

            $elozo->kovetkezo = $jelenlegi->kovetkezo;

        } else {

            $elozo = $jelenlegi;

        }

        $jelenlegi = $jelenlegi->kovetkezo;

    }

    return $fej;

}

// Példa csatolt lista létrehozása

$fej = new CsomoPont(4);

$fej->kovetkezo = new CsomoPont(2);

$fej->kovetkezo->kovetkezo = new CsomoPont(1);

$fej->kovetkezo->kovetkezo->kovetkezo = new CsomoPont(3);

// Csatolt lista kiírása

echo "Eredeti lista:\n";

kiirCsatoltListat($fej);

// Csatolt lista rendezése

$fej = rendezCsatoltListat($fej);

echo "Rendezett lista:\n";

kiirCsatoltListat($fej);

// Csomópont törlése

$torlendoAdat = 2;

$fej = torolCsomopontot($fej, $torlendoAdat);

echo "A(z) $torlendoAdat értékű csomópontot töröltük:\n";

kiirCsatoltListat($fej);

?>

Rendezés; rendezCsatoltListat függvény egy egyszerű változata a quicksort rendezésnek a csatolt lista elemeire alkalmazva. A torolCsomopontot függvény megtalálja és törli a megadott értékű csomópontot a csatolt listából. Az eredményeket a kiirCsatoltListat függvény segítségével írjuk ki.