Moment 4, ADT och datastrukturer

Översikt

Implementation och analyser av vanliga datastrukturer.

Mål

Du skall skapa en egen implementation av följande datastrukturer:

-Dynamisk stack

-Dynamisk kö

-Prioritetskö

-Länkad lista

-Dynamisk array (vector)

Du skall analysera beteendet för varje av dessa strukturer och beskriva dess prestanda/ komplexitet i O()-notation. Du skall känna till komplexiteten hos en optimal implementation.

Minnesanteckningar

I litteraturen:

Kapitel Elementary Data structures.

Kapitel Abstract data types.

Kapitel Priority queues and Heapsort.