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.
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.
Hogyan épül fel ez a feladat a C++ kurzuson
A láncolt listákat sokféleképpen meg lehet valósítani, és sokféle háttéradatszerkezet is szóba jöhet, de itt arra kérünk, hogy a saját láncolt listádat objektumorientált módon valósítsd meg.
A linked_list_test.cpp fájlban látni fogod, hogy egy sablonos List osztályt hívunk meg.
Ezt az osztályt a következő tagfüggvényekkel kell megírnod:
-
push hozzáad egy elemet a lista végéhez,
-
pop eltávolítja és visszaadja a lista utolsó elemét,
-
shift eltávolítja és visszaadja a lista első elemét,
-
unshift hozzáad egy elemet a lista elejére, és
-
count visszaadja a lista összes elemének számát.
Végül szeretnénk, ha a fent vázolt metódusok mellett megvalósítanád az erase metódust is.
Az erase egy argumentumot kap: azt az értéket, amelyet el kell távolítani a láncolt listából.
Ha az érték többször is szerepel, csak az első előfordulását távolítsd el.
Adja vissza, hogy törölt-e elemet vagy sem.
Bár ezt nem teszteljük, érdemes lehet kivételt dobni, ha a pop és a shift metódust üres List-en hívják meg.
Forrás
Klasszikus számítástudományi téma
