Datastructuren en algoritmen

Datastructuren en algoritmen Doelstelling Datastructures + algorithms = programs Boek van Niklaus Wirth: bedenker Pascal en Modula Datastructuur: structuur om informatie op te slaan Algoritme: voorschrift om berekening uit te voeren Goede kennis van belangrijke datastructuren en algoritmen is nodig om zelf goede programma’s te kunnen schrijven Helpt bij het herkennen van de juiste datastructuur en het juiste algoritme om je probleem op te lossen.

Data Structuren en Algoritmen - week 1

oktober 2014

1

Datastructuren en algoritmen Onderwerpen Overzicht belangrijke datastructuren en algoritmen - Datastructuren: arrays, lijsten, bomen, expressies, etc - Algoritmen: sorteren, herkennen, datastructuur gerelateerd Overzicht belangrijkste Object-georienteerde technieken zoals: -

klassen en objecten inheritance en toepassingen polymorfisme dynamische binding gebruik van de standaard bibliotheek Java


oktober 2014

2

Toepassingen -

tekenprogramma chatapplicatie: client server programma toepassingen in C2

Werkwijze Leren door te doen, dus accent op de opdrachten. Studie materiaal Boek(en) sheets Toetsing opdrachten


oktober 2014

3

Object-georiënteerd programmeren Objectgeoriënteerd programmeren is gebaseerd op data en operaties op deze data. • Het gedrag van een object is volledig beschreven door de operaties die op het object van toepassing zijn (abstractie). • Kennis van de implementatiedetails van een object zijn niet nodig om een object te kunnen begrijpen/gebruiken (inkapseling). • Je kunt klassen gebruiken om nieuwe klassen vanaf te leiden (overerving/inheritance)


oktober 2014

4

Voordelen van het gebruik van klassen • Klassen zijn goede bouwblokken: Je kunt klassen eenvoudig samenstellen tot grotere systemen. • Een (goede) klasse kan in isolement begrepen worden (dus zonder kennis te nemen van andere klassen). Een klasse is dus een afgerond geheel. • De implementatie van een klasse kan gewijzigd worden zonder gevolgen voor de gebruiker van de klasse, zolang de interface van de klasse niet gewijzigd wordt. • Klassen vormen vaak een directe afspiegeling van entiteiten uit het probleemdomein.


oktober 2014

5

Klassen en Objecten Object Geintegreerde eenheid van: • data (opgeslagen in toestandsvariabelen) • methoden/operaties (functies werkend op de data)

Eigenschappen van Objecten • Ze kunnen dynamisch gecreëerd worden • Hun interne toestand kan veranderen • Ze bieden hun data bescherming


oktober 2014

6

Object-georienteerd programma Alleen maar objecten, die door boodschappen te sturen (aanroepen operaties) informatie uitwisselen.

Het ene object stuurt een boodschap naar het andere object dooreen methode van dat andere object aan te roepen.


oktober 2014

7

Object-georienteerd programma Nodig: een variabele met een referentie naar dat andere object

v1 = v2.n2(p);


oktober 2014

8

Klassen Ieder object is een instantie van een bepaalde klasse. Objecten uit dezelfde klasse hebben dezelfde: - namen en typen van velden - operaties die aangeroepen kunnen worden Een klasse dient als blauwdruk om nieuwe objecten te creëren.


oktober 2014

9

Voorbeeld: Een grafisch tekenprogramma

Verschillende voorwerpen waarop dezelfde operaties moeten worden gedaan: Figuren: cirkels, lijnen, rechthoeken, driehoeken Operaties: • transleren • vervormen (resizen) • tekenen in verschillende kleuren en dikten • groeperen van figuren (je kunt nu operaties op een groep uitvoeren)


oktober 2014

10

Objecten en klassen Eisen aan een objectgeoriënteerde programmeertaal 1

Niet (meer) gebruikte objecten moeten automatisch opgeruimd worden (automatic garbage collection).

2

Ieder niet standaard type komt overeen met een klasse en vice versa (integer, boolean etc. zijn standaard typen).

3

Inheritance: Een klasse mag gedefinieerd worden als een uitbreiding of een beperking van een andere klasse.

4

Polymorfisme en dynamische typering/binding: Het moet mogelijk zijn vanuit een programma verwijzingen (variabelen) te hebben die bij objecten van verschillende klassen kunnen behoren en waarbij de uitvoering van een operatie afhangt van de klasse waartoe het object behoort.

5

Multiple Inheritance: Het moet mogelijk zijn een klasse te laten erven van meer dan één klasse en ook meerdere keren van één klasse.


oktober 2014

11

Objecten en klassen Hoe zit het met Java en C++ mbt deze eisen? Java voldoet aan alle eisen behalve aan 5. Er zijn in Java echter andere mechanismen die multiple inheritance heel dicht benaderen. C++ is geen pure objectgeoriënteerde taal en heeft ook geen automatic garbage collection. C++ heeft echter wel multiple inheritance. Dus C++ voldoet aan: 3, 4 en 5. Verder heeft C++ de mogelijkheid van operatoroverlading. Het is mogelijk de optelling (+) en vermenigvuldiging (*) te herdefiniëren voor bv. matrices. Dit leidt tot zeer elegante programma’s. C++ heeft zeer veel features, die de taal zeer krachtig maken, maar aan de andere kant leiden tot het makkelijk maken van programmeerfouten. C++ was in jaren 80 en 90 heel populair maar is een moeilijke taal om mee te werken. Java is tegenwoordig populairder.


oktober 2014

12

Wat is Java? Java programma’s worden gecompileerd naar zgn. bytecode. Bytecode is een machineonafhankelijk tussenformaat. Voor ieder platform waar je je Java programma wil draaien moet er een zgn. bytecode-interpreter zijn. Dit wordt ook wel een Java virtuele machine (JVM) genoemd. De bytecode-interpreter voert nu de bytecodeopdrachten uit. Alle moderne internetbrowsers zoals: Chrome, FireFox en Explorer hebben een ingebouwde bytecode-intepreter (Java plugin). Het is dus mogelijk vanuit deze browsers Javaprogramma’s (applets) te draaien. Java applets worden steeds minder gebruikt. JavaScript is tegenwoordig de taal om client-side processing te doen. Veel bytecodeinterpreters bevatten tegenwoordig een justin-time(JIT) compiler. Dit betekent dat de bytecode tijdens het interpreteren wordt doorvertaald naar machinecode. Hierdoor wordt de efficiëntie flink verhoogd!


oktober 2014

13

Klassen in Java: Persoonklasse

class Persoon { private String naam; private int leeftijd; public Persoon(String n, int l) leeftijd = l; naam = n; }

{

public String toString() { return (naam + "\n" + leeftijd); } public void setLeeftijd(int l) leeftijd = l; }

{

}


oktober 2014

14

Klassen in Java: Gebruik van de klasse Persoon

class Main { static public void main (String args[]) Persoon p = new Persoon("Piet",25); System.out.println(p. toString()); p.setLeeftijd(26); System.out.println(p. toString()); } }

{

Opgave Pas nu de methode setLeeftijd zo aan dat alleen een hogere leeftijd geaccepteerd wordt.


oktober 2014

15

Klassen in Java: Persoon Frame – demo in Netbeans

De klasse persoon hoeft hiervoor niet te worden aangepast. We maken nu in Netbeans bovenstaande applicatie.


oktober 2014

16

Klassen en typering Iedere klasse correspondeert met een type. Het belang van typering? • Typering dwingt objecten slechts element te zijn van één klasse => objecten van verschillende klassen kunnen niet verwisseld worden (of alleen onder speciale condities) • Typering biedt de mogelijkheid om al tijdens vertalen een gedeelte van de correctheid van het programma te controleren • Vooral voor grote systemen is (sterke) typering een absolute voorwaarde om tot de realisatie van correcte systemen te komen


oktober 2014

17

Klassen en Typering We onderscheiden: ongetypeerde, zwak en sterk getypeerde talen. Java, Amanda, Clean, Haskell en ook bv. C++ zijn sterk getypeerd. => iedere variabele of parameter heeft één type. Objecten van verschillend type mogen niet verwisseld worden (behoudens type conversie). Er is volledige typecontrole tijdens vertalen. Zwak getypeerde taal: wel typen, maar geen garantie voor correcte foutmeldingen als entiteiten in foute context worden gebruikt. Deel van de typecontrole wordt uitgesteld tot ‘uitvoering van het programma (dynamische typering). Voorbeeld: PHP, JavaScript


oktober 2014

18

Klassen en Typering Voordelen van een sterk getypeerde taal • zonder typecontrole kan systeem op mysterieuze wijze vastlopen • vroege detectie van typefouten bespaart veel tijd in edit compile - debug cyclus • typering is vorm van documentatie • veel compilers genereren efficiëntere code door sterke typering In Java moet het type van iedere functie, variabele of parameter van te voren worden aangegeven in de declaratie ervan.


oktober 2014

19

Gedrag van objecten Enige manier om een object te benaderen is het sturen van boodschappen naar dat object. Reactie op boodschap: • toestand wijzigen • zelf boodschappen naar andere objecten sturen. • resultaat teruggeven Samen noemen we dit het gedrag van een object. We onderscheiden verschillende soorten operaties • modifier: verandert toestand een object • selector: laat toestand ongewijzigd, maar geeft informatie terug • constructor: creëert een object • destructor: vernietigt een object (gaat in Java automatisch)


oktober 2014

20

Relaties tussen objecten 1 2

Gebruiks- (using) relaties Bevat-(containing, aggregatie) relaties

Gebruiksrelaties • Object wordt gebruikt door ander object (maakt er geen deel van uit) Soorten objecten in gebruiksrelaties: • Actor: maakt gebruik van diensten andere objecten, maar wordt zelf nauwelijks gebruikt • Server: Verleent diensten aan andere objecten en gebruikt zelf geen andere objecten • Agent: maakt gebruik van diensten van andere objecten en wordt zelf regelmatig gebruikt door andere objecten Bevat-relaties Containing relatie: object opgebouwd uit andere objecten (maken er deel van uit). Bevatte object alleen zichtbaar voor bevattende object.


oktober 2014

21

Overzicht Java

import

: importeren van andere klassen vgl. uses

void

: letterlijk leeg

{

: begin resp. eind van een syntactisch blok vergl. begin .. end

;

A:

}

: afsluiter van een statement

een assignment levert een waarde op: x = y = 0; betekent: y = 0; x = y;

B:

verschil tussen = (toekenning) en == (vergelijking) if (x == 1) a = b;


oktober 2014

22

C:

werking van ++ (ophoging) en -- (verlaging) hangen af van plaatsing if (++ x == 1) ... if (x ++ == 1) ...

/* eerst ophogen */ /* eerst vergelijken */

void main { ... } int char string while (conditie) statement; if (conditie) statement; for (statement; conditie; statement) statement; for (elem : var) return ...;


oktober 2014

23

Datastructuren Een klasse kan gebruikt worden voor het realiseren van een zgn. datastructuur. Het werken met datastructuren maakt programmeren veel overzichtelijker waardoor programma’s beter onderhoudbaar worden. Voorbeeld de Stack Een stack (stapel) wordt gebruikt om gegevens in op te slaan. De volgende operaties zijn van toepassing op een stack: Push: Pop: Top: IsEmpty:

Voeg waarde toe aan bovenkant stack Verwijder bovenste element stack Geef waarde bovenste element stack Is de stack leeg?

Een stapel kan gebruikt worden om een zgn. postfixexpressie te evalueren.


oktober 2014

24

Abstracte Datastructuren Infix en PostFix Infix 2+3 6 * (8 - 9) (5 + 2) * (6 + 7) Postfix 23+ 689-* 52+67+* Bij postfix geen haken nodig! PostFix expressie kan eenvoudig door computer verwerkt worden mbv. een stack : 23+ 2

3 2

+ 3 2

5

Oefening Evalueer 6 8 9 - * en 5 2 + 6 7 + * Infix naar postfix kan ook mbv een stack • Werk infix af van links naar rechts • Kopieer getal steeds direct naar resultaat • Plaats operatie op hulp stack, maar verwijder eerst alle operatoren die er al op staan met hogere prio en zet deze in resultaat. Een ( telt als operatie met lage prio • Bij ) verwijder alle operaties tot je de ( tegen komt • Op eind plaats alle over gebleven operaties terug


oktober 2014

25

1. Abstracte Datastructuren Implementatie Stack (van Integers) class StackInt { public StackInt() { elems=new int[100]; top=-1; } public void push(int i) top++; elems[top]=i; }

{

public int pop() { return elems[top--]; } private int[] elems; private int top; }


oktober 2014

26

Opgave Voeg een functie isEmpty aan Stack die true teruggeeft als de stack leeg is en anders false. Implementeer een grafische postfix calculator mbv een stack. Gebruik hiervoor de HP35 als voorbeeld: http://www.hpmuseum.org/simulate/hp35sim/hp35sim.htm


oktober 2014

27

Datastructuren en algoritmen

Recommend Documents