Tömbből lista
Definiálj listát, amelyik valós számokat tartalmaz! Írj függvényt, amelyik valós számokat tartalmazó tömböt vesz át paraméterként, és létrehoz egy újonnan létrehozott listát, amelybe a megadott számokat másolja! Egy másik függvénnyel gondoskodj a lista felszabadításáról is.
Ennek a feladatnak a megoldását fel tudod használni a többi feladatban a teszteléshez.
Egyszeresen láncolt lista másolása
Definiálj egy irányban láncolt lista elemeinek tárolására alkalmas adatstruktúrát, a lista
20 elemű int tömb adattaggal rendelkezik! Írj függvényt, amely paraméterként kapja egy ilyen
elemekből felépülő lista címét! A függvény adja vissza a lista másolatát (a másolt lista
kezdőelemének címét)! (Vagyis hozzon létre egy másik listát, amely ugyanazokat az adatokat
tartalmazza ugyanolyan sorrendben, mint a paraméterként átvett!)
Lista másolása megfordítva
Írj függvényt, amely lemásol egy listát, de úgy, hogy a másolat az eredeti fordítottja legyen! Ötlet: ehhez használható a gyakorlati óráról származó lista megfordítása ötlet.
Nincs benne ismétlés
Írj függvényt, amely úgy módosít egy paraméterként kapott listát, hogy abban ne legyen kétszer egymás után ugyanaz az elem! Pl. ha a bemeneti lista 1,1,5,7,4,4,1,5,5,5,6, a megváltozott lista tartalma legyen 1,5,7,4,1,5,6. (Figyelj arra, hogy ehhez csak egymás melletti elemeket kell vizsgálni. Egymástól távol szerepelhet többször is ugyanaz a szám.)
A függvény megírása előtt gondold át, fog-e módosulni itt a lista eleje mutató!
Mindegyik elem csak egyszer
Írj függvényt, amely úgy módosít egy paraméterként kapott listát, hogy abban minden elem csak egyszer szerepeljen! Térjen vissza a függvény az esetleg megváltozott lista eleje pointerrel! (Pl. ha a bemeneti lista 1,5,7,4,4,1,5,6, a megváltozott lista tartalma legyen 1,5,7,4,6).
Mindegyik elem csak egyszer – új listával
Írj függvényt, amely létrehoz egy listát olyan módon, hogy az a paraméterként kapott lista minden elemét csak egyszer tartalmazza. (Vagyis a feladat ugyanaz, mint az előbb, csak nem módosítani kell a listát, hanem létrehozni egy újat.)
Lista közepe
Adott egy láncolt lista, amelyről tudjuk, hogy páratlan számú eleme van. Meg kell keresni a középsőt, és adni rá egy pointert. De úgy, hogy csak egyetlen ciklust használunk! (Tehát ha megszámoljuk, mekkora – első ciklus, és utána újra az elejéről elindulva megkeressük a középsőt – második ciklus, az nem jó.)
Beszúrás az ötödik helyre
Írj függvényt, amely egy listába beszúr egy elemet úgy, hogy az az ötödik legyen! (A számozás 1-től indul.) Ha a lista rövidebb, akkor kerüljön a végére az új elem. A függvénynek paraméterei legyenek a lista elejére mutató pointer és a beszúrandó adat. Visszatérési értéke legyen a lista elejét mutató pointer.
Definiáld az egyszeresen láncolt lista elemét úgy, hogy az max. 50 karakter hosszúságú neveket tároljon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj rövid főprogramot, amelyben definiálsz egy listát. Feltételezve, hogy a lista fel van töltve, szúrd be az 5. helyre a Mézga Géza nevet!
Ötödik elem törlése
Írj függvényt, amely egy lista ötödik elemét törli! (A számozás 1-től indul.) Ha nincs ötödik elem, akkor ne történjen semmi. A függvénynek egy paramétere legyen csak, az a lista elejére mutató pointer.
Definiáld az egyszeresen láncolt lista adatszerkezetét úgy, hogy max. 30 karakter hosszúságú szavakat tároljon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj rövid főprogramot, amelyben definiálsz egy listát. Feltételezve, hogy a lista fel van töltve, töröld ki a függvénnyel az 5. elemet!
Párosak törlése
Írj függvényt, amely paraméterként vesz át egy számokból álló listát, és törli abból a páros számokat! Ha a lista eredeti tartalma 2,3,4,5,6, akkor a módosított lista 3,5 kell legyen.
Definiáld az egyszeresen láncolt lista adatszerkezetét úgy, hogy az egész számokat tartalmazzon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj programrészt, amely meghívja egy listára a függvényt!
Beszúrás adott helyekre
Írj függvényt, amely paraméterként vesz át egy számokból álló listát, és minden páros szám elé beszúr egy listaelemet, amely annak ellentettjét tartalmazza! Például ha az eredeti lista 2,3,4,5, akkor a módosított -2,2,3,-4,4,5 legyen.
Definiáld az egyszeresen láncolt lista adatszerkezetét úgy, hogy az egész számokat tartalmazzon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj programrészt, amely létrehoz két listaelemet, és meghívja a keletkező listára a függvényt.
Elejéről a végére
Írj függvényt, amely egy lista legelső elemét a lista végére helyezi át! (Például az 1,2,3,4,5 listából így 2,3,4,5,1 lesz.) Ha kettőnél kevesebb elem van, akkor ne csináljon semmit.
Definiáld az egyszeresen láncolt lista adatszerkezetét úgy, hogy egész számokat tartalmazzon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj programrészt, amely létrehoz két listaelemet, és a függvénnyel áthelyezi az első elemet a lista végére!
Végéről az elejére
Írj függvényt, amely egy lista utolsó elemét a lista elejére helyezi át! (Például az 1,2,3,4,5 listából így 5,1,2,3,4 lesz.) Ha kettőnél kevesebb elem van, akkor ne csináljon semmit.
Definiáld az egyszeresen láncolt lista adatszerkezetét úgy, hogy az valós számokat tartalmazzon! Készíts rajzot, amely a listakezelést mutatja számozott lépésekkel! Írj programrészt, amely létrehoz két listaelemet, és meghívja a keletkező listára a függvényt.
Fordított listák
Definiálj egy irányban láncolt lista elemeinek tárolására alkalmas adatstruktúrát, a lista valós típusú adattaggal rendelkezik! Írj függvényt, amely paraméterként kapja két, ilyen elemekből felépülő lista címét! A függvény tegye át a két lista elemeit fordított sorrendben egy harmadik listába, és ennek a listának a kezdőcímét adja vissza! (Ne foglalj memóriát, hanem az eredeti listaelemek pointereinek átállításával oldd meg a feladatot!) Például ha a két bemenő lista elemei: {1.0, 3.0, 5.0} és {2.0, 4.0, 6.0}, akkor a kimenő lista {6.0, 4.0, 2.0, 5.0, 3.0, 1.0} legyen!
Páratlanok duplázása
Definiálj két irányban láncolt lista elemeinek tárolására alkalmas adatstruktúrát, a lista pozitív egész számokat tárol! Írj függvényt, amely paraméterként kapja egy ilyen elemekből felépülő, mindkét végén strázsával lezárt lista címét! A függvény duplázzon meg minden olyan listaelemet, amely páratlan számot tartalmaz, vagyis hozzon létre és fűzzön be minden ilyen listaelem elé vagy mögé egy új listaelemet, melybe a páratlan értéket átmásolja!
Rendezett beszúrás
Hozz létre típust, mely alkalmas egészek láncolt listában való tárolására! Írj függvényt, amely átvesz egy NULL-terminált, növekvően rendezett listát a fenti típusból, és egy új számot. A számot úgy szúrja a listába, hogy annak rendezettsége megmaradjon. A működés áttekintéséhez készíts ábrát! Egy másik függvénnyel gondoskodj a lista felszabadításáról is. Az elkészült függvények alkalmazását rövid programrészlettel szemléltesd; a listát feltöltöttnek tekintheted.
Listák összefűzése
Hozz létre típust, mely alkalmas tetszőleges méretű szavak láncolt listában való tárolására! (A szavak helyét dinamikusan kell kezelni!) Írj függvényt, amely átvesz két NULL-terminált listát a fenti típusból, és az első lista végéhez fűzi a másodikat. A függvény az új lista kezdőcímével térjen vissza; feltételezhetjük, hogy az átvett eredeti listákat és kezdőcímeiket a hívás helyén már nem használjuk tovább. A függvény akkor is helyesen működjön, ha bármelyik lista üres! A működés áttekintéséhez készíts ábrát! Egy másik függvénnyel gondoskodj a lista felszabadításáról is. Az elkészült függvények alkalmazását rövid programrészlettel szemléltesd; a listákat feltöltöttnek tekintheted.
Beszúrás véletlenszerű helyre
Hozz létre típust, mely alkalmas valós számok láncolt listában való tárolására! Írj függvényt, amely átvesz egy NULL-terminált listát a fenti típusból, és egy új számot. A számot véletlenszerűen kiválasztott helyre szúrja a listába, tehát az a végére és az elejére is kerülhet! A működés áttekintéséhez készíts ábrát! Az elkészült függvény alkalmazását rövid programrészlettel szemléltesd; a listát feltöltöttnek tekintheted.
Hány különböző?
Adott az alábbi struktúrájú, egész számokat tároló láncolt lista:
struct ListaElem {
int ertek;
struct ListaElem *kov;
};Készíts programot, mely megszámolja, hogy a listában hány különböző érték van! Az eredeti listát ne változtasd meg!
A lista fájlba írása
Definiáljunk legfeljebb 50 betűs szavak tárolására alkalmas, egyszeresen láncolt listát!
Írjunk függvényt, amely egy paraméterként kapott listát egy szintén paraméterként kapott nevű szövegfájlba ír! Legyen minden sorban egy szó!
Írjunk függvényt, amely egy fájlnevet kap paraméterként, visszatérési értéke pedig a fájlból beolvasott szavakat tartalmazó lista!
Figyeljünk arra, hogy a fájlba kiírt szavak sorrendje visszaolvasva ne forduljon meg!
Névsor összeállítása
Készíts programot, amely beolvassa az egy megadott szövegfájlban soraiban található neveket, és névsort állít össze belőlük. A nevek maximum 100 karakteresek, viszont tetszőlegesen sok lehet belőlük.
Szélsőérték keresése
Egy csapat névsorát az alábbi láncolt listában tároljuk:
struct NevLista {
char nev[100];
unsigned int eletkor;
struct NevLista *next;
};Készíts programot, mely a csapat leghosszabb nevű tagjának az életkorát képes megmondani! (Feltesszük, hogy csak egy leghosszabb nevű létezik.)
Lista rendezése szélsőérték keresésével
Írj függvényt, amely egy paraméterül kapott, egész számokból álló listát rendez növekvő sorrendbe, szélsőértékkereséses módszerrel!
Lista rendezése buborékrendezéssel
Írj függvényt, amely egy paraméterül kapott, egész számokból álló listát rendez növekvő sorrendbe, buborék módszerrel!
Futóverseny
Adott egy futóverseny résztvevőinek listája:
struct Versenyzo {
char *nev;
time_t ind, erk;
struct Versenyzo *next;
};Az ind adat az indulási időpontját, az erk az érkezését tárolja egész számként, UnixTime formátumban (1970. jan. 1. 0:00 óta eltelt másodpercek száma). Készíts programot, mely meghatározza, hogy melyik futó kapja az első, második és harmadik díjat!
Duplán láncolt lista másolása
Írj függvényt, amely lemásol egy duplán láncolt listát!
Duplán láncolt lista megfordítása
Írj függvényt, amely megfordít egy duplán láncolt listát! Vajon elég ehhez csak megcserélni a kezdő- és a végstrázsát? Rajzold le!
Duplán láncolt listák összefűzése
Írj függvényt, amely egy paraméterként kapott, duplán láncolt, mindkét végén strázsás listához hozzáfűz egy másikat! (Az első lista ezáltal hosszabb lesz, a második pedig megszűnik létezni. Figyelj arra, hogy a második lista strázsáit ilyenkor fel kell szabadítani!)
Könyvek
Definiálj C-ben egy duplán láncolt, mindkét végén strázsás listát, amelyik könyek adatait képes tárolni – szerző (max. 30 betű), cím (max. 50 betű) és terjedelem (pozitív egész szám) formájában. Írj egy függvényt, amelyik megadja, hogy a paraméterként kapott szerző hány oldalnyi könyvet írt összesen.
Fésűs lista
Dolgozd át úgy az előző „szerzők, könyvek” programot, hogy fésűs listát alkalmazzon! A fő listában a szerzők legyenek, amely szerzőkhöz további listákat, a könyvek listáit rendeljük hozzá.
Keresés a raktárban
Egy duplán láncolt, mindkét végén strázsás lista termékeket tárol, név (30 karakter), cikkszám (20 karakter), és raktárkészlet (darab) formájában. Definiáld a lista struktúrát! Írj egy függvényt, amelyik egy adott cikkszámú elemről megmondja, hogy mennyi áll rendelkezésre a raktárban. Egy cikkszám csak egyszer szerepel. Ha nincs olyan, akkor 0.
Duplán láncolt lista – különféle műveletek
Az alábbi struktúrával megadott, két irányban láncolt, mindkét végén strázsával lezárt láncolt listát egy több szerző által közösen készített C nyelvű program kezeli.
- Első strázsa: prev=NULL, erről megismerhető
- Végstrázsa: next=NULL, erről megismerhető
typedef struct ListaElem {
char ident[50+1];
struct ListaElem *prev, *next;
} ListaElem;A feladat elkészíteni a lista kezeléséhez szükséges alábbi függvényeket:
- Törlő függvény, mely két pointert kap: a lista kezdő- (strázsa-) elemének címét, valamint a törlendő elem címét. Nem biztos, hogy a törlendő elem a megadott listában található. Feladat: megkeresni a listában a megadott elemet. Ha benne van, kifűzni a listából és felszabadítani az általa lefoglalt memóriát.
- Beszúró függvényt, mely két pointert kap: a lista kezdő- (strázsa-) elemének címét, valamint a beszúrandó elem címét. Az új elemet az ident mező szerint ABC sorba rendezett listába ident szerint rendezetten kell beszúrnia! A beszúrandó elemet a program más részén már lefoglalták, most tehát a pointerek megfelelő beállítása a feladat.
Negatívak törlése
Hozz létre típust, mely alkalmas egészek kétszeresen láncolt listában való tárolására! Írj függvényt, amely átvesz egy mindkét végén strázsával lezárt listát a fenti típusból, és kitörli a negatív értékű elemeket. A működés áttekintéséhez készíts ábrát! Egy másik függvénnyel gondoskodj a lista felszabadításáról is. Az elkészült függvények alkalmazását rövid programrészlettel szemléltesd; a listát feltöltöttnek tekintheted.
Duplán láncolt lista másolása
Definiálj két irányban láncolt lista elemeinek tárolására alkalmas adatstruktúrát,
a lista 20 elemű int tömb adattaggal rendelkezik! Írj függvényt, amely paraméterként
kapja egy ilyen elemekből felépülő lista címét! A függvény adja vissza a lista másolatát
(a másolt lista kezdőelemének címét)! (Vagyis hozzon létre egy másik listát, amely ugyanazokat
az adatokat tartalmazza ugyanolyan sorrendben, mint a paraméterként átvett!)
Beszúrás az ötödik elem után
Definiálj C-ben egy egyszeresen láncolt listát, amelyik egész számokat tárol. Írj egy függvényt, amelyik egy paraméterként kapott lista ötödik eleme után beszúr egy ugyancsak paraméterként kapott számot. Ha rövidebb, akkor az elejére kerüljön az új szám.
Készíts teljes programot, amellyel a függvény működése kipróbálható!
Tizedik elem törlése
Definiálj C-ben egyszeresen láncolt listát, amelyik maximum 45 betűs szavakat tárol. Írj egy függvényt, amelyik egy paraméterként kapott lista tizedik elemét törli; ha a lista rövidebb ennél, akkor ne csináljon semmit.
Készíts teljes programot, amellyel a függvény működése kipróbálható!
Lista átláncolása (megoldás hosszú magyarázattal)
Adott a következő definíció:
typedef struct elem {
int adat;
struct elem *kov;
} Elem;A fenti elemekből egyszeresen láncolt, NULL-terminált láncolt listát építünk. Írj olyan függvényt, amely átvesz egy listát a fenti típusból, a lista első elemét kiveszi, és a lista végére fűzi; az így kapott lista kezdőcímét adja vissza. Pl. start→A→B→C→NULL lista helyett az ujstart→B→C→A→NULL listát kapjuk. A lista teljes tartalmáról nem készíthet másolatot a memóriában.
Készíts teljes programot, amellyel a függvény működése kipróbálható!
Melyik szó hányszor
Írj programot, amelyik végigolvas egy szövegfájlt, és kiírja ABC szerint rendezve a benne szereplő összes szót, illetve melléjük, hogy melyik hányszor szerepelt.
Kereszthivatkozások
Írj programot, amely kereszthivatkozás listát készít egy adott szövegfájlról; vagyis megadja az összes benne szereplő szót, és minden szó mellé azoknak a soroknak a számát, amelyekben az illető szó megtalálható!
Gráf listában
Adott egy gráf, amelyet láncolt listákban tárolunk. A láncolt lista egy eleme tartalmaz egy jelzőbitet, egy mutatót az ő szomszédjait felsoroló láncolt listára, illetve a következő elem mutatóját:
struct graf {
bool jelzobit;
struct szomszed *szom;
struct graf *next;
};A jelzőbitet a program szabadon használhatja. A szomszédos elemek mutatóit tartalmazó láncolt lista szerkezete az alábbi:
struct szomszed {
struct graf *el;
struct szomszed *next;
};Határozza meg a program, hogy az így leírt gráf összefüggő-e!
Keress hurkot a gráfban, és írja ki a programod, hogy van-e benne!
Határidőnapló listában
Írj programot, amely határidőnaplót kezel! A program tárolja események adatait időponttal és fontossággal! A programnak tetszőlegesen sok eseményt tudnia kell tárolni; az események száma futás közben változhat. Az adatszerkezet gyakori méretváltozása kizárja a tömbbel történő praktikus megvalósítást, ezért válassz láncolt listát a megvalósításhoz! Feladatok:
- Programrészt írni, amelyik a lista elejére beszúr egy új eseményt.
- Programrészt írni, amelyik a lista végére fűz egy új eseményt.
- Összes eseményt kilistázó programrész.
- A listát felszabadító programrész.
Listakezelő függvények
Írd meg függvényekként az előző feladat programrészeit!
Listák és rekurzió
Egy láncolt lista egy első elemből, és egy abból kiinduló láncolt listából áll. Ezen gondolat alapján írjunk függvényeket, amelyek:
- Kiírják az egyszeresen láncolt listában tárolt adatokat.
- Kiírják az egyszeresen láncolt lista adatait visszafelé.
- Felszabadítják a listát.
Mikor érdemes használni a rekurziót a listáknál? Mikor nem?
Lista rendezése új lista építésével
Írj programot, amely duplán láncolt, mindkét végén strázsás listát épít könyvek címeiből! Írj függvényt, amely egy paraméterként kapott listát rendez a mű címe szerinti ábécé sorrendbe!
Lista rendezésére kétféle megoldás létezik: első, hogy a lista elemei megmaradnak, és a bennük lévő adatokat cseréljük ki (mint a tömböknél); a második, sokkal hatékonyabb megoldás pedig az, hogy az átláncolásukkal rendezzük a listát. Ilyenkor ugyanis nincsen szükség adatok cserélgetésére, hanem csak a pointerek módosulnak. A feladat ezért az utóbbi megvalósítása.
Tipp
- Segédfüggvény készítése, amely paraméterként kap egy rendezett, strázsákkal lezárt listát, valamint egy listaelem címét, és a listaelemet a megfelelő helyre befűzi a listába. (Memóriafoglalás tehát nem történik, csak a pointerek állítgatása.)
- A rendezőfüggvény emelje ki a rendezetlen listából a két strázsa közötti elemeket egy strázsa nélküli listába, a két strázsa pedig mutasson egymásra (azaz üres lista jön létre, ez lesz a rendezett lista).
- Egy ciklusban vegye le a rendezetlen lista első elemét, és hívja meg a segédfüggvényt, amely ezt az elemet beszúrja a rendezett listába! A ciklus addig menjen, amíg van elem a rendezetlen listában!
Lista rendezése quicksort algoritmussal
Írj függvényt, amely egy paraméterül kapott, egész számokból álló, duplán láncolt listát rendez gyorsrendezéssel!