Grundlæggende Programmering (GP) Efterår 2005 Forelæsning 12 Slides ligger på nettet. Du er velkommen til at printe dem nu. Vi begynder 9.15. www.itu.dk/courses/GP/E2005 Martin Lillholm
Grundlæggende Programmering (GP) Efterår 2005 Forelæsning 12 Slides ligger på nettet. Du er velkommen til at printe dem nu. Vi begynder 9.15. www.itu.dk/courses/GP/E2005 Martin Lillholm
Spørgetime
Spørgetime mandag den 2. januar 9-12 – lokale annonceres
Eksamen er onsdag den 4. januar 9-13
Mail gerne spørgsmål på forhånd
Vejledende løsninger til obligatoriske opgaver på hjemmesiden efter sidste afleveringsfrist (den 12. december)
Gamle eksamenssæt og vejledende løsninger på hjemmesiden efter sidste afleveringsfrist (den 12. december)
Sidste gang
Undtagelser (exceptions)
Rekursion – spørgsmål og udvalgte emner
Denne gang
Tilbagelænet gennemgang af:
Abstrakte datatyper
Dynamiske strukturer
Stakke og køer
Træer og grafer
Collections
Evaluering
Prøveeksamen
Abstrakte datatyper
Opbevarer data på en struktureret måde
En samling data (interne)
Et antal operationer (eksterne, grænseflade), der kan udføres på data
Indsæt
Fjern
Find
...
Eksempler: Liste, stak, kø, træ og graf
Klasser/objekter kan netop give denne abstraktion. Hvorfor ?
Implementation vs. abstraktion
Eksempel fra tidligere: arrayList Hvordan er arrayList implementeret ?
Liste – abstrakt
En lineær samling af data – en liste – hmm en rekursiv definition
Typiske operationer:
Indsæt på vilkårlig plads
Fjern på vilkårlig plads
Opdater på vilkårlig plads
Indhold på vilkårlig plads
…
Kø (queue) – abstrakt
Typisk en liste, men med restriktioner på hvordan vi indsætter og tager ud
First-in, first-out (FIFO)
Typiske operationer
enqueue indsæt element bagest i kø
dequeue fjern element fra køens start
empty er køen tom?
Tavlegennemgang
Hvad kan man bruge en kø til ?
Stak (stack) – abstrakt
Typisk en liste, men med restriktioner på hvordan vi indsætter og tager ud
Last-in, first-out (LIFO)
Typiske operationer:
push
pop
peek
empty
Tavlegennemgang
Hvad kan man bruge en stak til ... kaldstak, rekursion og stak
Decode.java L&L side 623 i BlueJ
Implementation
Hvordan ser den abstrakte datatyper ud inden i ?
Kan have mange forskellige implementationer
Stadig med samme grænseflade
Typisk baseret på
Tabeller – (nogen gange 2,3, … dimensionelle)
Hægtede type
…
Dynamiske strukturer
En tabel er ikke dynamisk
En arrayList dynamisk, men benytter faktisk (statiske) tabeller.
Person person1 = new Person(”Martin Lillholm”, 192);
En ”rigtig” dynamisk (enkelthægtet) liste kunne se således ud:
class Node {
int info; // Blot et eksempel på data
Node next; // Husk at objektvariable er referencer
}
Tavlegennemgang
info kan have en vilkårlig type og altså godt være en klassetype - afhænger af, hvad vi vil gemme.
Enkelthægtet liste (linked list)
Tavlegennemgang af
Indsættelse
Sletning
Køretid, sammenlignet med en almindelig (statisk) tabel
MagazineRack.java L&L side 615 i BlueJ
Dobbelthægtet liste (doubly linked list)
class Node {
int info; // Blot et eksempel på data
Node next, prev; // Husk at objektvariable er referencer
}
Tavlegennemgang
Hvorfor nu det?
Mange andre muligheder ...
Listeheader med front og rear referencer
Kombinationer af de ovennævnte
Det virker besværligt det her ... ArrayList er meget nemmere ... helt rigtigt, men bag kulisserne sker noget lignende (ADT!)
Dynamiske strukturer med statiske byggeklodser
L&L side 387 Tunes.java side 387 i BlueJ
ArrayList
Træ (tree) ikke lineær struktur
Rodknude (root)
Interne knuder (internal nodes)
Bladknuder (leaf nodes)
Tavlegennemgang ... datalogiske træer vokser nedad ...
Hvor mange børn kan en knude have ?
Tavlegennemgang:
Binære søgetræer
Sortering ved hjælp af binære træer
Implementation ? Rekusiv definition …
Graf (graph) ikke lineær struktur
Knuder (nodes)
Kanter (edges)
Tavlegennemgang
Ikke orienteret graf, orienteret graf, kantvægte, DAG, ...
Eksempler på brug – uformel tavlegennemgang
Korteste vej
Korteste vej og internettet
Alle korteste veje - Krak
Onkel rejsende Mac – Travelling Sales Person
Ressourceplacering
Java Collections API & Generics
ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap ...
Masser af standardmetoder ...
Generics
LinkedList myStringList = new LinkedList();
LinkedList myPersonList = new LinkedList();
ArrayList myPersonList = new ArrayList();
ArrayList myObjectList = new ArrayList();
Hvordan skriver man generics – OOP
Mere om API’et ?
By popular demand …
Hvordan laver man et stand-alone Java program ?
Det er faktisk ikke så så ligetil som man skulle tro…
Normalt kræves en JVM
Applet
Genvej eller ikon
Native compiler
BulletTrain
Excelsior JET
…
Comments