Module EVMINX4: Algoritmen en Datastructuren (ALDAT)

© Harry Broeders.

Deze pagina was bestemd voor studenten van de Haagse Hogeschool - Academie voor Technology, Innovation & Society Delft groep ECV. Op deze pagina vind je het bij de module ALDAT gebruikte studiemateriaal. Meer recente informatie over het gebruik van algoritmen en datastructuren in in C++ vind je hier.

Beschikbaar materiaal:

• Studiewijzer (inclusief gedetailleerde planning).
• Dictaat ALDAT Druk dit dictaat dubbelzijdig af en bind het in!
• Lambda_Expressions_and_Closures Deze handout wordt tijdens week 6 uitgedeeld.
• Sheets per week.
  1. Inleiding (overzicht ALDAT), overzicht datastructuren.
  2. Toepassingen en implementaties van een stack.
  3. Standard Template Library: overzicht, sequentiële containers, container adapters en associatieve containers.
  4. Standard Template Library: iteratoren, algoritmen en functie objecten.
  5. Toepassingen van dynamische datastructuren: game- tree, min-max algoritme en alfa-beta pruning.
  6. Toepassing: galgje. C++0x lambda functies.
• Introductie in het gebruik van Microsoft Visual C++ 2010 Express Edition (gratis thuis te gebruiken).
• Voorbeeldprogramma's uit mijn dictaat :
  • Balance.cpp (pagina 9) met de benodigde header files: stacklist.h en stack.h.
    Dit programma controleert of de haakjes in de invoer netjes gebalanceerd zijn. Dit is een eenvoudige toepassing van de stack datastructuur.
  • Postfix.cpp (pagina 11) met de benodigde header files: stacklist.h en stack.h.
    Deze postfix (RPN) calculator maakt gebruik van een stack.
  • stackarray.cpp (pagina 14) met de benodigde header files: stackarray.h en stack.h.
    Dit programma test de stack die geïmplementeerd is met behulp van een array (in de include file stackarray.h).
  • stacklist.cpp (pagina 16) met de benodigde header files: stacklist.hen stack.h.
    Dit programma test de stack die geïmplementeerd is met behulp van een gelinkte lijst (in de include file stacklist.h).
  • stack.cpp (pagina 16) met de benodigde header files: stackarray.h, stacklist.hen stack.h.
    Dit programma laat zien hoe je dynamisch (tijdens run-time) kunt kiezen voor een bepaalde implementatie van de stack. Dit is mogelijk door het gebruik van een Abstract Base Class en is een voorbeeld van het gebruik van polymorfisme.
  • stdvector.cpp (pagina 18), stdbalanced.cpp (pagina 19), set.cpp (pagina 20), multiset.cpp (pagina 20) en stdcntwords.cpp (pagina 21).
    Deze programma's laten zien hoe je de standaard datastructuren: vector, stack, set, multiset en map gebruikt.
  • streamitr.cpp (pagina 22).
    Dit programma maakt gebruik van stream iteratoren.
  • find.cpp (pagina 22), find_if.cpp (pagina 23), for_each.cpp (pagina 24), transform.cpp (pagina 25) en remove.cpp (pagina 25).
    Deze programma's laten zien hoe je de standaard algoritmen: find, find_if, for_each, transform en remove gebruikt.
  • mem_func.cpp (pagina 26)
    De standaard functie mem_fun die de koppeling vormt tussen generiek programmeren en object georienteerd programmeren wordt in dit programma gedemonstreerd.
  • galgje0.cpp, galgje1.cpp, galgje2.cpp, galgje3.cpp en galgje4.cpp.
    Vijf verschillende manieren om galgje te spelen.
• Nog meer voorbeeldprogramma's :
  • generiekPrint3.cpp Een functie waarmee de inhoud van een generieke container geprint kan worden. Deze functie maakt gebruik van indexering en is daardoor niet erg generiek (alleen te gebruiken met vector en deque).
  • generiekPrint2.cpp Een functie waarmee de inhoud van een generieke container geprint kan worden. Deze functie maakt gebruik van een iterator en is daardoor wel generiek.
  • generiekPrint1.cpp Een functie waarmee de inhoud van een generieke container geprint kan worden. Deze functie maakt gebruik van twee iterator en is daardoor wel generiek. Deze versie is veel eenvoudiger dan generiekPrint2.cpp.
• Informatie voor week 5 over Boter, Kaas en Eieren.
• Informatie voor week 6: Het gebruik van auto in C++0x maakt het definiëren van iterator types veel eenvoudiger. Zie http://en.wikipedia.org/wiki/C%2B%2B0x#Type_inference
  Een aantal van de bovenstaande programma's kunnen vereenvoudigd worden m.b.v. auto: stdvector_auto.cpp set_auto.cpp multiset_auto.cpp stdcntwords_auto.cpp find_auto.cpp
• Informatie voor week 6: Het gebruik van functor's wordt sterk vereenvoudigd door het gebruik van de C++0x lambda functies.
• Practicumopdrachten:
  • Opdracht 1: Een "homemade" gelinke lijst.
  • Opdracht 2: Algoritme runtime analyse.
  • Opdracht 3: Exceptions.
  • Opdracht 4: Opsporen van fraude.
  • Opdracht 5: Eindopdracht ALDAT.
• Hoe nu verder? Meer leren over C++.
• Andere interessante sites betreffende ALDAT.