Kurzusok
/
Tcl
Tcl
/
Feladatok
/
Láncolt lista
Láncolt lista

Láncolt lista

Közepes

Bevezetés

Egy forgalmas vasúti hálózat menetrendtervező rendszerének fejlesztésén dolgozol.

Arra kértek, hogy prototípust készíts a menetrendtervező rendszer vonatútvonalaihoz. Minden útvonal azoknak a vasútállomásoknak a sorából áll, ahol az adott vonat megáll.

Utasítások

A csapatod úgy döntött, hogy a menetrendben szereplő minden vonatútvonalat kétszeresen láncolt listával ábrázol. A vonat útvonalán minden állomást egy-egy csomópont képvisel a láncolt listában.

Nem kell az állomások érkezési és indulási idejével foglalkoznod. Minden állomást egyszerűen egy szám ábrázol.

Az útvonalak bővíthetők: új állomásokat adhatsz az útvonal elejére vagy végére. Rövidíthetők is, ha eltávolítod az állomásokat az útvonal elejéről vagy végéről.

Néha bezárnak egy állomást, és ilyenkor el kell távolítani az útvonalról, akkor is, ha nem az útvonal elején vagy végén van.

Az útvonal hosszát nem az méri, hogy milyen messzire utazik a vonat, hanem az, hogy hány állomáson áll meg.

Note

A láncolt lista alapvető adatszerkezet a számítástechnikában, és gyakran más adatszerkezetek megvalósításához használják. Ahogy a neve is sugallja, olyan csomópontok listája, amelyek össze vannak kapcsolva egymással. Olyan „csomópontok” listája, ahol minden csomópont a szomszédjához vagy a szomszédaihoz kapcsolódik. Egy egyszeresen láncolt listában minden csomópont csak az őt követő csomópontra mutat. Egy kétszeresen láncolt listában minden csomópont kapcsolódik az előtte lévő és az utána következő csomóponthoz is.

Ha mélyebbre szeretnél ásni a láncolt listák világában, nézd meg ezt a cikket, amely szép ábrák segítségével magyarázza el őket.

Megvalósítási megjegyzések

Egy kétszeresen láncolt lista megvalósítását fogod megírni.

Valósíts meg egy Node-ot, amely egy értéket, valamint a következő és az előző csomópontra mutató mutatókat tárol.

Ezután valósíts meg egy LinkedList-et, amely hivatkozásokat tárol az első és az utolsó csomópontra, és tömbhöz hasonló felületet kínál az elemek hozzáadásához és eltávolításához:

  • push (érték beszúrása a végére);
  • pop (érték eltávolítása a végéről);
  • shift (érték eltávolítása az elejéről);
  • unshift (érték beszúrása az elejére);
  • delete (az első egyező csomópont eltávolítása)

Hogy a megvalósítás egyszerű maradjon, a tesztek nem foglalkoznak hibás esetekkel. Pontosabban: a pop és a shift soha nem hívódik meg üres listán.


Forrás

Klasszikus számítástudományi téma
Szerkesztés GitHubon A hivatkozás új ablakban vagy lapon nyílik meg
Tcl Exercism

Készen állsz elkezdeni a(z) Láncolt lista feladatot?

Iratkozz fel az Exercism-re, hogy megtanuld és elsajátítsd a(z) Tcl nyelvet 135 feladat segítségével, valódi emberi mentorálással, mindez ingyen.