Dinamikus listák 1

Linked listák - egy adat álló struktúra csomópontok, amelyek mindegyike tartalmazza mind a tényleges adatok és az egy vagy két linket ( „link”), hogy a következő, és / vagy az előző csomópont a listában. Számos típusú listák, íme néhány közülük: egyszerűen csatlakoztatható egyirányú, egyszerűen csatlakoztatható kétszeresen kötött gyűrű hordozója, kétszeresen kötött gyűrűt.

Egyszeresen láncolt lista egyirányú.

Egyszerűen csatlakozik az egyirányú lista hallgatólagos végrehajtása soros elrendezése meghatározott elemeket. Kezdve egy bizonyos csomópontra, úgy véljük, ez az első ezen az oldalon linkeket, hogy a következő, és így tovább. A legtöbb esetben az első csomópont üres, mert akkor könnyebb dolgozni a listán. A láncolt lista, minden egyes csomópont hivatkozás csak a következő elem, hogy van, amit nem tud mozogni, hogy a végén a lista kezdete előtt. Egyirányú lista végét egy NULL referencia.

Nézzük, hogy mit funkciók szükségünk lehet dolgozni a listán. Talán ez - a szervezet a listán, a kimeneti lista válogatás, kiegészíti egy új elemet a rendezett lista. Tehát először meg kell, hogy gondoskodjon maga a csomópont, a totalitás alkotja majd a listán.

Most el kell kezdenünk, hogy hozzon létre egy változó típusú lista, amely pont az első elem
listát.

lista * Start = új listát; // memóriát kiosztani az első elem
start-> következő = NULL; // ezen a ponton az első elem ugyanakkor az utolsó mellett utal NULL

Mint ahogy azt a memóriát az első tétel, csak meg kell csinálni, és minden további is.
Most tekintsük a részét a kódot, ami létrehoz egy listát.

lista * p_list = start;
A (int i = 0; i<20; i+=2)
lista * tmp = új listát; // memóriát lefoglalni
tmp-> elem = i; // itt minden világos
tmp-> következő = NULL; // beiktatunk egy csomópont a lista aljára, és így a következő = NULL
p_list-> következő = tmp; // most p_list-> következő pont a létrehozott node
p_list = p_list-> következő; // Vigye a mutatót az utolsó elem.
>

Itt mi most egy munka mutatót, hogy ne változtassa meg a start, amely mindig arra utal, hogy az első csomópont a listában. Kód végrehajtása után a lista a következőképpen néz ki:

Nézzük abból a konzol által készített lista alapján. Ehhez írjon külön funkció:

void show (lista * indítás) // beállítás - a lista tetején mutatót.
lista * p_list; // mutató munkás
p_list = start-> következő; // az elején, s utal a második csomópont a listában.
while (p_list! = NULL)
cout <tétel < p_list = p_list-> következő; // mozgassa a mutatót egy csomóponthoz.
>
>

lista * TMP = új listát; // memóriát kiosztani az új csomópont
tmp-> item = el;
tmp-> következő = p_list-> következő;
p_list-> következő = tmp; // Csomópont beszúrása után a csomópont által mutatott p_list
break;
>
p_list = p_list-> következő; // vigye a mutatót a következő elem.
if (p_list-> következő == NULL El> = p_list-> tétel) // ellenőrzése nem szükséges beilleszteni egy csomópontot a listából.
lista * tmp = új listát;
tmp-> item = el;
tmp-> következő = NULL; // Mivel beszúrni csomópont végén a lista következő elemére annak meg kell NULL
p_list-> következő = tmp; // betét csomópont a listában.
break;
>

Megpróbálják felhívni a diagram a behelyezhető elem a listában. Ez a házi)
Most levelet funkció, amely a lista rendezéséhez. Fogjuk használni az egyik legegyszerűbb rendezési algoritmusok - buborékos rendezést.

void sort (lista * indítás) // beállítás - a lista tetején mutatót.
lista * p_list; // mutató a kívül tsykla
lista * pp_list; // belső
A (p_list = start-> következő ;! p_list = NULL; p_list = p_list-> következő) // végigfut egy listát az összes csomópont
A (pp_list = start-> következő ;! pp_list-> következő = NULL; pp_list = pp_list-> következő) //, de itt csak a csomópont mellett amely rámutat, hogy a NULL
// normál átváltási értékeinek
if (pp_list-> Termék> pp_list-> next-> tétel)
int tmp;
tmp = pp_list-> elem; //
pp_list-> item = pp_list-> next-> elem;
pp_list-> next-> item = tmp;
>

És az utolsó funkció - eltávolítása egy elemet a listából:

void dell (lista * indítás, int el) // mutató az a lista tetején, és azt az értéket, amit keresnek a listán, ha megtaláljuk az eszközöket törölni.
lista * p_list = start-> következő; // pointer munkás, amelyet használni kell végigmenni a listán.
lista * prev = start; // mutató, amely mindig is az előző elem p_list.
while (p_list! = NULL) // fut Teljes lista
// ellenőrizni - akár a eltávolítása a szükségességét, hogy
if (p_list-> elem == el)
// timesign csomópont, amely rögzíti az értéket a törlendő csomópontra.
lista * tmp = új listát;
* Tmp = * p_list;
// most kell tennünk annak érdekében, hogy a következő eleme az előző csomópont mutat egy csomópontot, amely után p_list, azaz p_list-> következő
prev-> következő = p_list-> következő;
törli tmp;
>
Prev = p_list; // mozgatni előző mutatót egyik eleme
p_list = p_list-> következő; // csak mozog a következő.
>
>

Itt van, hogyan néz körül:

Az előnyök a dinamikus listákat, hogy mi is elég könnyen elem beszúrása, vagy távolítsa el a listából. A tömb kissé bonyolultabb. További előny, hogy a méret a listát meg lehet változtatni bármikor a program során.

De a lista megvan a hátránya. Az egyik legfontosabb az, hogy nem tudjuk, hogy hozzáférjenek a k-adik csomópont, valamint egy sor, a listákat kell mennünk az összes olyan elemet, amely megy a k. Továbbá, a csomópontokat a listában nem kerülnek egymás memória és a program fut egy kicsit lassabban, mint ha lenne egy tömb, ahol minden elem sorba vannak rendezve.

Ez minden), ha valakit érdekel ebben a témában, akkor később folytatható) Ismertesse a munka egyszerűen csatlakoztatva cirkuláris listán kétszeresen kapcsolódik, kétszeresen összekapcsolt gyűrűt.
Nyelvtani hiba) nem az én magyar anyanyelvű) készen áll hallgatni az összes megfigyelések).