Please enable JavaScript.
Coggle requires JavaScript to display documents.
TDA416 - Datastrukturer och Algoritmer (Javas datastrukturer (ListIterator…
TDA416 - Datastrukturer och Algoritmer
OOP
ADT
Abstract Data Type
Encapsulated data together with its methods
Throwable
Error
Exception
Runtime Exception
Checked Exception Classes
If you don't declare packages, all your classes belong to the same package (
the default package
)
Javas datastrukturer
<<Iterable>>
<<Collection>>
<<List>>
AbstractList
(
AbstractCollection
)
AbstractSequentialList
(
AbstractCollection
)
LinkedList
(<<Deque>>)
Vector
(<<RandomAccess>>)
Stack
ArrayList
(<<RandomAccess>>)
<<Queue>>
<<Deque>>
AbstractCollection
<<Set>>
AbstractSet
(
AbstractCollection
)
<<SortedSet>>
<<NavigableSet>>
capacity vs. size
System
.
arraycopy
(Object src, int srcPos, Object dest, int destPos, int length)
throw new
ArrayIndexOutOfBoundsException
(index)
ListIterator
har både previous() och next(), även add(E obj) och set(E obj)
index mellan 0 (före första elementet) och size (efter sista elementet)
(s. 122)
Komplexitet
T(n) is O(f(n)) if there exist
constants c>0 and n0≥0 so that for all n≥n0,
we have
T(n) ≤ cf(n)
Testning
Black-box testing
Baseras på föremålets gränssnitt och funktionella krav
Ex. för en metod:
Variera input-parametrarna över sina tillåtna värden
och jämför resultatet med egna beräkningar.
Även otillåtna värden testas för att se att exceptions kastas
White-box testing
Målet är att testa så många vägar genom föremålet som möjligt
Ex. Branch coverage
Säkerställer att varje val i programmets förgreningar (if/switch/loopar) testas
Driver: ~lokal main()-metod i en klass
TÄNK PÅ
Heap
Partiellt ordnad
Varje nod är
större eller lika med
sina barn (i max-heap)
kallas också
POV-träd
(partiellt ordnat vänsterbalanserat)
Ostabila
sorteringsalgoritmer
(De som swappar okontrollerat)
Quicksort
Heapsort
Selection sort
modCount
för att hålla reda på om listan ändrats för en iterator
final void
checkForComodification
():
ConcurrentModificationException
NoSuchElementException