Skillnad mellan versioner av "TDDC30 - Programmering i Java, datastrukturer och algoritmer"
Admin (Diskussion | bidrag) |
Admin (Diskussion | bidrag) |
||
Rad 23: | Rad 23: | ||
== Listor == | == Listor == | ||
− | <b> Enkellänkad lista </b> | + | <b> Enkellänkad lista </b><br> |
− | <b> Dubbellänkad lista </b> | + | <b> Dubbellänkad lista </b><br> |
− | <b> Cirkulärt dubbellänkad lista </b> | + | <b> Cirkulärt dubbellänkad lista </b><br> |
+ | |||
+ | == Iterator == | ||
= Traversering = | = Traversering = |
Versionen från 29 mars 2016 kl. 01.04
TDDC30 är en grundkurs i programspråket java, datastrukturer och algoritmer. Kursen omfattar 6 högskolepoäng och hålls undervisas både för Industriell ekonomi och för Systemvetenskap på Linköpings universitet. Kursen är en påbyggnadskurs på TDDD11 - Programmering, grundkurs och förutsätter att studenten har grundläggande programmeringskunskaper gällande ett "programmeringstänk".
Kursen går igenom ett antal sorteringsalgoritmer, olika typer av datastrukturer, hur man skriver UML-diagram, hur man använder det grafiska Swingpaketet och allmänt hur man ska tänka för att programmera objektorienterat. Examinationsmomenten innefattar 5 stycken laborationer (0-4) och en tentamen. Tentan består av en teoretisk del och en praktisk programmeringsdel.
Innehåll
Java
Java är ett av världens mest använda programmeringsspråk, just för dess operativsystemsneutralitet. I programspråket ADA som kursen TDDD11 undervisas i så använder man en kompilator som tolkar den källkod som programmeraren skrivit och gör om den till maskinkod som datorn kan köra. I Java så finns det ett mellanlager som kallas för Java Virtual Machine (JVM). JVM gör det möjlig att köra samma javakod på alla operativsystem som har stöd för detta, vilket i stort sett gör språket plattformsoberoende, det går lika bra att köra javakod i en Androidtelefon som på en Mac.
Språket är uppbyggt på klasser som på olika sätt kommunicerar och interagerar med varandra.
UML
Unified Modeling Language (UML) är ett objektorienterat sätt att modelera system som beskriver hur olika klasser hör ihop, vilka attribut (variabler eller konstant) och metoder som varje klass har, vilken access andra har till klassen osv. Man kan även avläsa om en klass ärver eller implementerar en annan klass.
Datastrukturer
Heap
Maxheap Minheap
Binärt sökträd
Kö (Queue)
Stack
Listor
Enkellänkad lista
Dubbellänkad lista
Cirkulärt dubbellänkad lista
Iterator
Traversering
Traversering innebär att man läser av alla noderna i ett träd i en speciell ordning. Det finns 4 olika sätt att traverseringar: Level-traversering, preorder-traversering, inorder-traversering och postorder-traversering.
Levelorder-Traversering
Preorder-Traversering
Inorder-Traversering
Postorder-Traversering
Sorteringsalgoritmer
En sorteringsalgoritm används för att sortera data. Olika algoritmer är olika effektiva beroende på förhållandena där den ska implementeras.
Bubble sort
Bubble sort-algoritmen är en relativt långsam algoritm med en medeltidskomplexitet på O(n2).
Algoritm
Minst till vänster, störst till höger.
1) Börja i någon av ändarna (detta fallet höger)
2) Jämför de två bredvidliggande objekten. Är vänster mindre än höger -> Byt plats
3) Hoppa ett steg till vänster. Upprepa steg 2.
4) När algortimen träffar vänsterkanden, upprepa steg 1. Upprepa detta tills datat är sorterat
Exempel
513426
513426
513246
512346
152346
125346
123546
123456