Könny? feladatok 1 Költözés: Egy szövegfájlban tételek szerepelnek, amit költözéshez szeretnénk bedobozolni. Minden tételnek van neve és súlya. Olvassuk be a tételeket egy láncolt listába, ahol a sorrend a listában legyen ugyanolyan, mint a fájlban. Majd kérjünk a billenty?zetr?l egy számot, ami az els? doboz teherbírása. Induljunk el a listában, és kezdjük el tölteni a dobozt úgy, hogy ha egy tétel még belefér a dobozba, akkor töröljük ki a listából, és a doboz szabad kapacitását csökkentsük. Ha megtelik a doboz vagy elérjük a lista végét, akkor kérjük a következ? számot, amíg még van elem a listában. Természetesen a dobozba rakott tételeket írjuk ki a képerny?re. Közepes feladatok 2 Sorbanállás: egy postán három ablakhoz állnak sorban. Minden ügyfél bizonyos ideig tartó dolgot akar elintézni (egész számú perc), és nyitás után valahány (egész perc) id?vel érkezik. Egy szövegfájlban van leírva, hogy ki mikor érkezik és mennyi ideig tart majd a teend?je, méghozzá érkezési sorrendben. Modellezd a postán a három sor haladását úgy, hogy a három sor egy-egy láncolt lista legyen, és amikor valaki érkezik, akkor a legrövidebb sorba áll be (egyenl?ség esetén a program tetsz?legesen választhat, nem kell véletlenszer?en). Ha valaki a sor elejére kerül, elkezdi intézni a dolgait. Ha ezzel készen van, elhagyja a postát. A program addig fusson, amíg az utolsó ügyfél is készen nem lesz. A program folyamatosan írja ki ha valaki érkezik vagy távozik és hogy ezt hanyadik percben teszi, és a futás végén a legpechesebb ember adatait, akinek a legtöbbet kellett várnia. (tipp: az, hogy ki mennyit várt, lehet ugyanolyan attribútum mint pl. a neve.) 3 Memóriakezelés: Modellezzünk egy absztrakt gépet és egy program lefutását. A gépünkben van 3-féle méret? memórialap (1, 2, és 3 méretekben), mindegyikb?l N darab. Egy szövegfájl tartalmaz egy programot, amely memóriafoglalás és felszabadítás m?veleteket tartalmaz. A memóriafoglalás két paraméteres: egy változónév és egy méret (1,2,3). A felszabadítás csak változónevet igényel. Egy példa: new a 2 new b 1 delete a delete b A program kezeljen két listát, az egyikben a még szabad lapokat, a másikban a lefoglaltakat, és mozgassa a lapokat a m?veleteknek megfelel?en. Adjon hibaüzenetet, ha a program olyan lapot akar lefoglalni, amib?l nincs több, vagy olyan lapot akar felszabadítani, amit nem foglalt le. Futtatás végén adjon egy listát a felszabadítatlan lapokról. 4 Kett? mélység? könyvtárstruktúra: egy szövegfájl minden sorában két szó szerepel egy / jellel elválasztva. Ez egy kétszint? könyvtárszerkezet összekeverve. A feladat az, hogy a szövegfájl beolvasása után fa alakban írja ki a program az adatokat. program/putty jatek/tetris program/devc adat/orarend adat |-orarend jatek |-tetris program |-devc |-putty Tehát rendezni kell mindkét szinten, a f?könyvtár elemei is ABC sorrendben kövessék egymást, és az egyes könyvtárak tartalma is legyen rendezett. Az adatokat természetesen láncolt listában kell tárolni. Nem kell felkészülni ékezetes karakterekre. (tipp: 'a' < 'b') Nehéz feladatok 5 Összef?z? rendezés: gyors rendez? eljárás, ami már rendezett listák összef?zésén alapul. Az összef?zés lényege, hogy a két listán el?refelé végighaladva mindig azt az elemet tesszük az eredményként létrejöv? lista végére, amelyik kisebb. Ezzel úgy rendezünk, hogy ahogy olvassuk a számokat egy fájlból, azokat kis listákba rakjuk, minden kis listát addig töltünk, amíg monoton számsort olvasunk. Így rövid, akár egy elem?, de egyesével rendezett listákat kapunk. Ezeket mi másban tárolnánk, mint egy nagy, összefogó láncolt listában. Amikor megvannak a kis listák, azokat párosával összef?zzük. Érdemes ezt úgy csinálni, hogy az els? két elemet összef?zni, és a lista végére beszúrni az eredményt. Ha már csak egy lista van az összefogó listában, akkor abban az adatok rendezve vannak. A program olvassa be a szövegfájlban tárolt számokat, és minden összef?zés után írja ki a teljes állapotot, vagyis az összes kis lista tartalmát. 6 Memóriakezelés memóriaolvasással: mint a 3-es feladat, azzal a különbséggel, hogy a memória most már egy nagy bájtsorozat, és nem csak lefoglalni és felszabadítani lehet, hanem az x-edik bájtot olvasni is. A szabad memória N bájt legyen. Amikor memóriát igénylünk, akkor a méretnek megfelel? darabot "kivágunk" a szabad memóriából, és az els? ennyi bájtot a program részére a lefoglalt lapok közé tesszük. Ekkor 0-tól n-1-ig olvashatjuk a memóriát, mert ezeket foglaltuk le. Ha lefoglalunk még, azt is felvesszük a listába, amikor pedig felszabadítunk, akkor a szabad lapok közé visszakerül a lap, de úgy, hogy ha lehet "összeolvasztani" más szabad lapokkal, akkor ezt meg kell tenni. Példa:           foglalt lista   szabad lista           -               [0123456789..] new a 4  [0123]          [456789..] new b 2  [0123][45]      [6789...] read 2 delete a [45]            [0123][6789..] read 4 new c 3  [012][45]       [3][6789...] new d 2  [012][45][67]   [3][89..] delete c [012][67]       [345][89..]   <-összeolvasztás Vagyis mindig az els? annyi bájtot kell adni, amennyit még lehet. Ebben a példában a "c" kevesebb memóriát kért mint az "a", ezért a 3-as memóriacímet másodszorra már nem osztjuk ki. Ilyenkor egy "read 3" hibaüzenetet adjon. Amikor "d"-t lefoglaljuk, mivel a szabad listában az els? nem elég nagy, ezért a második lapból kell "kivágni". A rendszer adjon hibaüzenetet, ha nincs elég nagy lap foglaláshoz, ha read m?veletet hívunk lefoglalatlan területre, és ha felszabadítani akarnánk lefoglalatlan változót. Futtatás végén a felszabadítatlan változókat írja ki.