3-Data structures
Table of Contents
Data structures......................................................................................................................................3
Algorithms............................................................................................................................................3
Benodigdheden van algorithme.......................................................................................................3
OOP......................................................................................................................................................4
ADT (Abstract Data Type)...................................................................................................................4
Algoritmische efficiëntie......................................................................................................................4
Pseudocode...........................................................................................................................................5
Afspraken.........................................................................................................................................5
Belangrijke functies..............................................................................................................................6
Primitieve operaties tellen....................................................................................................................6
Big O Notation.....................................................................................................................................7
Big Omega.......................................................................................................................................7
Big Theta..........................................................................................................................................7
Basic math............................................................................................................................................7
List-based collections...........................................................................................................................8
Arrays...............................................................................................................................................8
Main methods..............................................................................................................................8
Costs............................................................................................................................................9
Grow a array (insert)...................................................................................................................9
Linked List.....................................................................................................................................10
Main methods............................................................................................................................10
Singly linked list.......................................................................................................................10
Costs.....................................................................................................................................11
Double linked List.....................................................................................................................11
Cost.......................................................................................................................................11
Circulary linked List..................................................................................................................11
Stacks.............................................................................................................................................11
Methodes...................................................................................................................................11
Array-based stacks....................................................................................................................12
Queues...........................................................................................................................................12
Methodes...................................................................................................................................12
Searching Algorithms.........................................................................................................................13
Lineair Search................................................................................................................................13
Binairy Search................................................................................................................................13
Sorting Algorithms.............................................................................................................................14
Insertion Sorting Algorithm...........................................................................................................14
Bubble Sort....................................................................................................................................14
Selection Sort.................................................................................................................................14
Quick Sort......................................................................................................................................15
Cost.......................................................................................................................................15
Merge Sort.....................................................................................................................................15
List & sets...........................................................................................................................................15
MAPS.................................................................................................................................................15
Methodes........................................................................................................................................16
1
, Entry ADT......................................................................................................................................16
Opbouw..........................................................................................................................................16
Costs met list-based map...............................................................................................................16
Hashing...............................................................................................................................................17
Soorten hash codes.........................................................................................................................17
Soorten compression functions......................................................................................................17
Collision handeling........................................................................................................................18
Seperate chaining......................................................................................................................18
Open addressing........................................................................................................................18
Linear probing...........................................................................................................................18
Double hashing.........................................................................................................................18
Cost................................................................................................................................................18
Dictionaries.........................................................................................................................................19
Methodes........................................................................................................................................19
Costs met list-based map...............................................................................................................19
Search table....................................................................................................................................19
Binary search.................................................................................................................................20
Priority Queues...................................................................................................................................20
sorted list........................................................................................................................................20
Unsorted list...................................................................................................................................20
Selection sort..................................................................................................................................20
Insertion sort..................................................................................................................................20
Trees...................................................................................................................................................21
Terminologie..................................................................................................................................21
ADT...............................................................................................................................................21
Methodes........................................................................................................................................21
Soorten verplaatsingen...................................................................................................................21
Binary trees....................................................................................................................................22
Proper Binary Trees.......................................................................................................................22
Vb array.....................................................................................................................................22
binary search.............................................................................................................................22
binary insertion.........................................................................................................................22
binary deletion...........................................................................................................................23
Heap...............................................................................................................................................23
Insertion max Heap (upheap)....................................................................................................23
Deletion max Heap (downheap)...............................................................................................23
Sort............................................................................................................................................23
Graphs.................................................................................................................................................24
terminologie...................................................................................................................................24
Edge types......................................................................................................................................24
graph types.....................................................................................................................................24
Terminologie..................................................................................................................................24
Properties.......................................................................................................................................25
Methods.........................................................................................................................................25
Structure.........................................................................................................................................25
graphs.............................................................................................................................................26
DFS (Depth-First Search) & BFS (Breadth-First Search).............................................................27
Directed Graph...................................................................................................................................28
Dijkstra algoritme..........................................................................................................................28
2
, Data structures
DEF: We gebruiken data structuren om ongeorganiseerde data op te slaan als
georganiseerde data om nadien efficiënt te gebruiken.
Gebruik: In een computer programma waar
de Instructies + Data gebruiken. Hier moet de
data georganiseerd beschikbaar zijn en
raadpleegbaar zijn.
Bij grotere applicaties is efficiëntie de sleutel.
Voorbeeld: Array is een voorbeeld van een data structuur.
• Een array plaatsen we in het RAM op een vaste grootte.
• Gemakkelijk om data op te zoeken
• Slecht om te gebruiken wanneer we de array moeten vergroten of verkleinen.
TIP: Ken je limitaties van geheugenopslag.
Algorithms
DEF: Een oplossing voor een algoritmisch probleem. (optellen van
getallen, gemiddelde, fibonachi, …)
Hier hebben we altijd een input dat lijd naar een output.
We kunnen algoritmes schrijven in code maar ook in pseudcode.
Benodigdheden van algorithme
Juistheid Efficiëntie
Concrete stappen
Zekerheid
Niet dubbelzinnig geschreven
Eindigende aantal stappen
Eindigend
Het moet eindigen
3
Table of Contents
Data structures......................................................................................................................................3
Algorithms............................................................................................................................................3
Benodigdheden van algorithme.......................................................................................................3
OOP......................................................................................................................................................4
ADT (Abstract Data Type)...................................................................................................................4
Algoritmische efficiëntie......................................................................................................................4
Pseudocode...........................................................................................................................................5
Afspraken.........................................................................................................................................5
Belangrijke functies..............................................................................................................................6
Primitieve operaties tellen....................................................................................................................6
Big O Notation.....................................................................................................................................7
Big Omega.......................................................................................................................................7
Big Theta..........................................................................................................................................7
Basic math............................................................................................................................................7
List-based collections...........................................................................................................................8
Arrays...............................................................................................................................................8
Main methods..............................................................................................................................8
Costs............................................................................................................................................9
Grow a array (insert)...................................................................................................................9
Linked List.....................................................................................................................................10
Main methods............................................................................................................................10
Singly linked list.......................................................................................................................10
Costs.....................................................................................................................................11
Double linked List.....................................................................................................................11
Cost.......................................................................................................................................11
Circulary linked List..................................................................................................................11
Stacks.............................................................................................................................................11
Methodes...................................................................................................................................11
Array-based stacks....................................................................................................................12
Queues...........................................................................................................................................12
Methodes...................................................................................................................................12
Searching Algorithms.........................................................................................................................13
Lineair Search................................................................................................................................13
Binairy Search................................................................................................................................13
Sorting Algorithms.............................................................................................................................14
Insertion Sorting Algorithm...........................................................................................................14
Bubble Sort....................................................................................................................................14
Selection Sort.................................................................................................................................14
Quick Sort......................................................................................................................................15
Cost.......................................................................................................................................15
Merge Sort.....................................................................................................................................15
List & sets...........................................................................................................................................15
MAPS.................................................................................................................................................15
Methodes........................................................................................................................................16
1
, Entry ADT......................................................................................................................................16
Opbouw..........................................................................................................................................16
Costs met list-based map...............................................................................................................16
Hashing...............................................................................................................................................17
Soorten hash codes.........................................................................................................................17
Soorten compression functions......................................................................................................17
Collision handeling........................................................................................................................18
Seperate chaining......................................................................................................................18
Open addressing........................................................................................................................18
Linear probing...........................................................................................................................18
Double hashing.........................................................................................................................18
Cost................................................................................................................................................18
Dictionaries.........................................................................................................................................19
Methodes........................................................................................................................................19
Costs met list-based map...............................................................................................................19
Search table....................................................................................................................................19
Binary search.................................................................................................................................20
Priority Queues...................................................................................................................................20
sorted list........................................................................................................................................20
Unsorted list...................................................................................................................................20
Selection sort..................................................................................................................................20
Insertion sort..................................................................................................................................20
Trees...................................................................................................................................................21
Terminologie..................................................................................................................................21
ADT...............................................................................................................................................21
Methodes........................................................................................................................................21
Soorten verplaatsingen...................................................................................................................21
Binary trees....................................................................................................................................22
Proper Binary Trees.......................................................................................................................22
Vb array.....................................................................................................................................22
binary search.............................................................................................................................22
binary insertion.........................................................................................................................22
binary deletion...........................................................................................................................23
Heap...............................................................................................................................................23
Insertion max Heap (upheap)....................................................................................................23
Deletion max Heap (downheap)...............................................................................................23
Sort............................................................................................................................................23
Graphs.................................................................................................................................................24
terminologie...................................................................................................................................24
Edge types......................................................................................................................................24
graph types.....................................................................................................................................24
Terminologie..................................................................................................................................24
Properties.......................................................................................................................................25
Methods.........................................................................................................................................25
Structure.........................................................................................................................................25
graphs.............................................................................................................................................26
DFS (Depth-First Search) & BFS (Breadth-First Search).............................................................27
Directed Graph...................................................................................................................................28
Dijkstra algoritme..........................................................................................................................28
2
, Data structures
DEF: We gebruiken data structuren om ongeorganiseerde data op te slaan als
georganiseerde data om nadien efficiënt te gebruiken.
Gebruik: In een computer programma waar
de Instructies + Data gebruiken. Hier moet de
data georganiseerd beschikbaar zijn en
raadpleegbaar zijn.
Bij grotere applicaties is efficiëntie de sleutel.
Voorbeeld: Array is een voorbeeld van een data structuur.
• Een array plaatsen we in het RAM op een vaste grootte.
• Gemakkelijk om data op te zoeken
• Slecht om te gebruiken wanneer we de array moeten vergroten of verkleinen.
TIP: Ken je limitaties van geheugenopslag.
Algorithms
DEF: Een oplossing voor een algoritmisch probleem. (optellen van
getallen, gemiddelde, fibonachi, …)
Hier hebben we altijd een input dat lijd naar een output.
We kunnen algoritmes schrijven in code maar ook in pseudcode.
Benodigdheden van algorithme
Juistheid Efficiëntie
Concrete stappen
Zekerheid
Niet dubbelzinnig geschreven
Eindigende aantal stappen
Eindigend
Het moet eindigen
3
