Topic outline

  • General

    • Hasznos könyvek

    • Kása Zoltán - Algoritmusok és adatszerkezetek (jegyzet)

      https://ms.sapientia.ro/~kasa/adat.htm

    • Pontozás:

      Laborjegy: \( \frac{Parciális1+Parciális2+Házik}{3} \) (legalább 5-ös)

      * A parciálisok részben kell, hogy tükrözzék a háziknál elért eredményt, ellenkező esetben megvonható az átmenő jegy.


      ! PONTOZÁSI ÚTMUTATÓ FRISSÍTÉS !


      Szubjektív okok miatt a laborjegyek nem fogják tartalmazni a házi feladatokra kapható pontszámot. Ennek oka az, hogy sok olyan esettel találkoztam, amikor egyesek 10-est kapnak, mások 5-öst, és nyilvánvaló, hogy a befektetett munka alapján legjobb esetben is fordítva kellene hogy legyen. Ezúton elnézést kérek mindenkitől, aki becsületesen megdolgozott a pontjaiért, kárára nem válik, de az előbbieknek megfelelően nem tudom pontszerűsíteni a feladatokat.

      Laborjegy javítása illetve megszerzése pótszesszióban, a vizsga napján reggel nyolctól.

      Aki pótszesszióban jönne laborvizsgára, azt megkérném, hogy iratkozzon fel a következő oldalon, hogy a segítségek és a szükséges termek számát tudjam megoldani:

      https://forms.gle/GY1vWa2ptrGmzG3K8

      Ha nagyon sokan kell mindkét tárgyból vizsgázzanak, akkor lehet, hogy a szesszió végén kinevezünk még egy napot pót-laborvizsgára.

  • 1. Műveletek tömbökkel

    • Alapvető tömbműveletek feltöltése:

      szükséges függvények (csoporttól függően)

      • Létrehozás - void (int**, int) - calloc, malloc
      • Feltöltés - void (const char *, int**, int*) - állományból
      • Feltöltés - void (int*, int, int, int) - véletlenszámokkal
      • Kiírás  - void (int*, int)
      • Kiírás  - void (const char*, int*, int) - állományba
      • Rendezés - void (int*, int) - tetszőleges algoritmussal
      • Keresés - int (int*, int, int) - pozíciót térít vissza - lineáris/bináris
      • Törlés - void (int*, int*, int) - értéket töröl, csökkenti a tömb hosszát
      • Minimum - int (int*, int)
      • Maximum - int (int*, int)
      • Másolás - void (int*, int, int*, int)


  • 2. Tömb, ami ismeri a méretét

    • IntArray típus, egy tömb, ami ismeri a saját méretét (hasonló a C++ STL vector típusához)

      szükséges függvények és struktúra:

      typedef struct IntArray {
            int size;
            int *elements;
      } IntArray;


      • IntArray* Create(int)
      • void Destroy(IntArray*)
      • int Put(IntArray*, int, int)
      • int Get(IntArray*, int)
      • int Length(IntArray*)
      • void Print(IntArray*)

      Plusz:

      • IntArray* Fesul(IntArray*, IntArray*) - két MÁR rendezett "tömb" összefésülése.
      • minden, az 1D tömbműveleteknél megírt függvény átírása IntArray* típusra (a lehető legegyszerűbben, lehet mellékelni az első labor tömb.h állományát is.

  • 3. Buborékos rendezés, Strassen algoritmusa

    • Buborékos rendezés három változata (a jegyzetből).

      Tesztelés: hány összehasonlítást végez el a három algoritmus külön-külön UGYANAZON 1.000.000 elemű véletlenszámokkal feltöltött tömb rendezése során. Fel lehet használni az 1. laboron megírt tömbökkel foglalkozó modult.


      Strassen algoritmus implementálása (Kása Zoltán honlapjáról), klasszikus mátrixszorzás implementálása, majd a kettő összehasonlítása, hogy hány szorzást hajtottak végre.

  • 4. Polinom AAT

    Polinom AAT implementálása

    szükséges függvények és struktúra:

    typedef struct Polinom {
          int fok;
          int *egyutthatok;

          int size;

    } Polinom;


    • Polinom* Create(int) - nullpolinomot létrehoz, max paraméter tag
    • void Destroy(Polinom*)
    • int PutEgyutthato(Polinom*, int, int) - ellenőrizni kell, hogy belefér-e, fokszámot át kell állítani, ha kell
    • int GetEgyutthato(Polinom*, int) - adott fokszámú tag együtthatójának lekérdezése
    • int NullPolinom(Polinom*) - ellenőrzés
    • void Print(Polinom*) - "szép" kiírás
    • Polinom* Osszead(Polinom*, Polinom*)
    • Polinom* Szoroz(Polinom*, Polinom*)
    • Polinom** Oszt(Polinom*, Polinom*) - tételezzük fel, hogy az első nagyobb, mint a másodi; az eredmény egy Polinom* elemeket tartalmazó kételemű tömb, aminek a 0. eleme a hányados-polinom, az 1. eleme a maradék-polinom.
    • int PolinomErteke(Polinom*, int) - behelyettesítési érték


    PutEgyutthato tesztsorozat (nullpolinomból kiindulva):

    P=Create(10);

    PutEgyutthato(P, 0, 2) -> fokszám: 0

    PutEgyutthato(P, 2, 1) -> fokszám: 2

    PutEgyutthato(P, 4, 1) -> fokszám: 4

    PutEgyutthato(P, 4, 0) -> fokszám: 2

    PutEgyutthato(P, 2, -2) -> fokszám: 2

    PutEgyutthato(P, 0, 0) -> fokszám: 2

    PutEgyutthato(P, 4, 0) -> fokszám: 2

    PutEgyutthato(P, 11, 2) -> fokszám: 2 -> HIBA!

    PutEgyutthato(P, 2, 0) -> fokszám: 0 (nullpolinom)




  • 5. Tömb adatszerkezet

    1. Egér a labirintusban

    Egy bemeneti állományban adott egy labirintus, egy egér pozíciója a labirintusban és a sajt pozíciója a labirintusban. Írjatok játékot, amelyben egy felhasználó el tudja vezetni az egeret a sajthoz. Az irányításhoz a nyilakat, vagy az ASDW billentyűket kell lehessen használni. Az egérnek tilos a pályáról leugrani és a falra mászni!

    Bemenet:

    n m

    n x m-es labirintus-mátrix (0-út, 1-fal)

    Ex Ey (egér koordinátái)

    Sx Sy (sajt koordinátái)


    A program futása során a labirintust tároljátok

    a. 2D tömbben,

    b. 1D tömbben.

    (2 projekt forráskódját kell feltölteni)


    2. Ritka mátrixokra írjátok meg a következő függvényeket:

    • beolvasás,
    • kiírás,
    • összeadás,
    • szorzás.

    A bemenet:

    n m

    n x m-es mátrix


    Írjátok meg 3 és 4 soros ábrázolással egyaránt.

    (2 projekt forráskódját kell feltölteni)

  • 6. Verem, sorok, listák

    1. Verem adatszerkezet

    typedef struct STACK{

        int size;

        char *elements;

        int sp; //stack pointer - veremmutató

    }STACK;


    STACK* Create(int); //létrehoz egy vermet

    void Push(STACK*, char); //betesz a verem tetejére

    char Pop(STACK*); //kiveszi a veremből a legfelső elemet

    char Top(STACK*); //megnézi a verem legfelső elemét

    int isEmpty(STACK*); //ellenőrzi, hogy üres-e a verem

    int isFull(STACK*); //ellenőrzi, hogy tele van-e a verem

    void Destroy(STACK*); //felszabadít

    void Print(STACK*); //kiírja a teljes verem tartalmát (segédfüggvény, nem tartozik az adatszerkezet definíciójához)


    2. Egyszeresen láncolt lista

    typedef struct PELEM{

        int data; //adatmező

        struct PELEM *next; //következő elem címe, ha nincs, akkor 0.

    }PELEM;


    //egy elemre vonatkozó függvények

    PELEM* Create(int); //létrehoz egy elemet

    void Destroy(PELEM*); //felszabadít egy elemet

    //lista

    PELEM* CreateL(); //return NULL;

    void DestroyL(PELEM*); //felszabadítja a teljes listát

    PELEM* insertLast(PELEM*, int); //beszúr a lista utolsó eleme után

    PELEM* insertFirst(PELEM*, int); //beszúr a lista első eleme elé

    PELEM* insertOrdered(PELEM*, int); //beszúr rendezetten egy feltételezhetően már rendezett listába

    void Print(PELEM*); //kiírja a lista adat-mezőit

    PELEM* SortL(PELEM*); //elrendezi a listaelemeket adatmező szerint növekvő sorrendbe

    PELEM* Delete(PELEM*, int); //töröl adott értékű elemet a listából


    3. Várakozási sor implementálása dinamikusan láncolt listával (szabad, sőt kell használni a már megírt függvényeket)

    typedef struct VSOR{

        PELEM* listafej;

        PELEM* listaveg;    ///opcionális

    }

    VSOR* Create(); //létrehoz egy várakozási sort

    void Destroy(VSOR*);   //felszabadít egy várakozási sort

    void Push(VSOR*,int);  //betesz a várakozási sor egyik végére

    int Pop(VSOR*);   //kiveszi a következő elemet

    int Top(VSOR*);   //megnézi, hogy ki a következő elem a sorban

    void Print(VSOR*);   //kiírja a teljes várakozási sor tartalmát

    int isEmpty(VSOR*); //ellenőrzi, hogy üres-e a sor

    int isFull(VSOR*); //ellenőrzi, hogy tele van-e a sor


    4. Elsőbbségi sor implementálása dinamikusan láncolt listával (szabad, sőt kell használni a már megírt függvényeket)

    typedef struct ESOR{

        PELEM* listafej;

    }

    ESOR* Create(); //létrehoz egy elsőbbségi sort

    void Destroy(ESOR*);   //felszabadít egy elsőbbségi sort

    void Push(ESOR*,int);  //betesz az elsőbbségi sor megfelelő pozíciójára

    int Pop(ESOR*);   //kiveszi a következő elemet

    int Top(ESOR*);   //megnézi, hogy ki a következő elem a sorban

    void Print(ESOR*);   //kiírja a teljes elsőbbségi sor tartalmát

    int isEmpty(ESOR*); //ellenőrzi, hogy üres-e a sor

    int isFull(ESOR*); //ellenőrzi, hogy tele van-e a sor


    5. Kétszeresen láncolt lista

    typedef struct PELEM2{

        int data; //adatmező

        struct PELEM2 *prev, *next; //előző és következő elem címe, ha nincs, akkor 0.

    }PELEM2;


    //egy elemre vonatkozó függvények

    PELEM2* Create(int); //létrehoz egy elemet

    void Destroy(PELEM2*); //felszabadít egy elemet

    //lista

    PELEM2* CreateL(); //return NULL;

    void DestroyL(PELEM2*); //felszabadítja a teljes listát

    PELEM2* insertLast(PELEM2*, int); //beszúr a lista utolsó eleme után

    PELEM2* insertFirst(PELEM2*, int); //beszúr a lista első eleme elé

    PELEM2* insertOrdered(PELEM2*, int); //beszúr rendezetten egy feltételezhetően már rendezett listába

    void Print(PELEM2*); //kiírja a lista adat-mezőit

    PELEM2* SortL(PELEM2*); //elrendezi a listaelemeket adatmező szerint növekvő sorrendbe

    PELEM2* Delete(PELEM2*, int); //töröl adott értékű elemet a listából




  • 7. Verem alkalmazása

    1. A már megírt karakterverem felhasználásával értékeljetek ki egy teljesen zárójelezett kifejezést.

    Teljesen zárójelezett: minden operátor és annak a két operandusa zárójelbe van téve.

    Operátorok: +, -, *, /

    Operandusok: egész számok.

    Bemenet:

    a teljesen zárójelezett kifejezés (szóközjelek nélkül)

    Pl.: (((3+2)*(5-1))+(5-(2*3)))



    2. (Plusz egy fél házit ér) Értékeljetek ki egy tetszőleges aritmetikai kifejezést a fordított lengyel forma felhasználásával.

  • 8. Rendezések

    A következő rendezéseket kell megírni, mindegyik rendezés egy egész elemű tömböt kell növekvő sorrendbe rendezzen:

    1. Buborékos rendezés (Bubble sort) - kétszer optimalizált változat

    2. Kiválasztó rendezés (Selection sort)

    3. Beszúró rendezés (Insertion sort)

    4. Shell rendezés - változtatható h értékekkel (m hosszúságú h tömb)

    5. Számláló rendezés (Counting sort) - stabil változat, O(n+k) bonyolultságú (stable counting sort)

    6. Összefésülő rendezés (Merge sort)

    7. Gyorsrendezés (Quicksort)

    8. Kupacrendezés (Heap sort)


    A megoldandó feladat:

    Definiáljunk egy N értéket, mely kezdetben 10. Hozzunk létre egy N méretű, véletlenszámokkal feltöltöt tömböt (A). Készítsünk egy hasonló méretű tömböt, majd másoljuk le az eredeti elemeit az új tömbbe. Ezt rendezzük el az első rendezési módszerrel, majd újramásoljuk, ezután elrendezzük a második módszerrel, újramásoljuk, újra rendezzük stb.

    Megjegyzés: a rendezések megírása közben kövessük a tömbök változását, hogy az algoritmus funkcionálisan megfelel-e a megbeszélteknek (papíron lehet ellenőrizni). A kiírásokat a végső verzióból teljesen ki kell venni!

    Mikor valamennyi rendezés működik, növeljük az N értékét 10.000-1.000.000 közötti értékre és mérjük meg valamennyi rendezés futási idejét a generált tömbre. A kimenetet a következő programváznak megfelelelően kell kiírni:

    [...]

    #include <time.h>

    #define N 50000

    int main() {

    [...]

    clock_t start, stop; ///idomereshez szukseges valtozok


    int *A, *a;

    CreateRandArray(&A,N,1,100); ///sajat tombletrehozo fuggveny: letrehoz, veletlenszamokkal feltolt - 1. labor

    CreateArrayMalloc(&a, N); ///sajat tombletrehozo fuggveny: letrehoz - 1. labor


    ///Ezt a szakaszt kell a 8-szor a rendezesekre megirni


    Masol(A,N, a, N); ///tomb masolasa masik tombbe - 1. labor, ha nem akkor frissen megirva

    start = clock();

    Bubble(a,N);

    stop = clock();

    printf("Bubble sort: %.6f mp.\n", (float)(stop-start)/CLOCKS_PER_SEC);


    ///szakasz vege


    [...]

    }

    • Extra feladatok:

      1. Radix sort - számjegyrendezés

      2. Összefésülő rendezés 3 részre darabolással.

      3. Optimális összefésülése m db egész elemű rendezett tömbnek.

  • 10. Fák

    1. Bináris keresőfa - egy tömböt kell beolvasni, és felépíteni a keresőfát. Az adatszerkezet .h állománya a csatolmányban.

    https://moodle.ms.sapientia.ro/pluginfile.php/2442/course/section/2581/binfa.h?time=1557141151329

    2. Trie adatszerkezet. Adott egy szógyűjtemény, határozzuk meg, hogy egy adott prefixxel hány szó kezdődik.

    3. AVL fa - önkiegyensúlyozó bináris keresőfa, az előző keresőfához hasonlóan (plusz 4 forgatás).



    Plusz feladatok:

    4. (+5 pont, személyes bemutatás) Piros-fekete fa - az előzőhöz hasonlóan.


  • 11. Hasító táblák (hashing tables)

    Írjátok meg annak a hasító táblának a kezelését, amelyik: 

    • egyszeresen hasít
    • szavakat tárol láncolt listákban

    1. Szerkezet

    • Lista:

    typedef struct ELEM{

       char * szo;

       struct ELEM * next;

    }ELEM

    • A hasító tábla tárolótömbje ELEM** típusú.

    2. Szükséges függvények:

    • Beszúrás
    • Törlés
    • Keresés (elemet térítsen vissza)
    • Teljes tábla kiírása
    • Tábla felszabadítása.

    3. A beszúrás legfeljebb 100 hosszú const char * típusú szavakat kap paraméternek, és a konkrét elemfoglalás a szó méretének megfelelően történik.

  • 2019.05.27 - Info 10:00

  • 2019.05.27 - Info 13:00

  • 2019.05.27 - SzT 19:00

  • 2019.05.28 - SzT 15:00

  • 2019.05.28 - Aut 19:00

  • 2019.05.29 - Inf 08:00

  • 2019.05.29 - Inf 10:00

  • 2019.05.29 - Aut 13:00

  • 2019.05.29 - Tk-SzT 15:00

  • 2019.05.29 - SzT 17:00