Versionen från 11 april 2016 kl. 00.17

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.

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.

Klass

En klass är som en mall man använder för att skapa ett objekt i Java. I klassen skriver man instruktioner om hur just den klassen/objektet fungerar. Instruktionerna består av importering av paket, attribut och metoder. Se följande exempel:

package test;

// Detta är en kommentar. Kommentarer i Java skrivs med två stycken slash följt av en text
import java.grafisktpaket.* // Stjärnan (*) betyder att vi importerar precis alla klasser i paketet grafisktpaket.
import java.util.ArrayList; // Här hämtar vi enbart klassen "ArrayList". Det är viktigt att inte hämta onödiga klasser som inte används.

public class skrivText() { // Klassen heter skrivText och är public (dvs synlig för alla).
        System.out.println("Hello World!"); // Här skrivs "Hello World!" ut i konsolen.
}

För att skapa ett objekt så instansierar man en klass, detta görs i koden man vill skapa objektet. I nedanstående exempel instansierar vi klassen ArrayList. Detta sker i två steg:

1. Skapa en referens som ska peka på ett objekt skapat kring en specifik klass.
2. Instansiera och peka referensen på själva objektet.

ArrayList<String> list; // Steg 1: Här skapar referensen "list" till ett ArrayList-objekt.
list = new ArrayList<String>(); // Steg 2. Här skapas själva ArrayList-objektet som referensen "list" pekar på.

Detta kan även göras genom att skriva ihop de två stegen:

ArrayList<String> list = new ArrayList<String>();

UML

UML-diagram

Ett UML-schema beskriver relationen mellan klasser

Unified Modeling Language (UML) är ett objektorienterat sätt att modelera system som beskriver hur olika klasser hör ihop. Ett klassdiagram (som du ser till höger) är en beskrivning över en klass, vad klassen heter, vilka attribut/variabler klassen har och dess metoder. Det beskriver också vilken access varje attribut och metod har genom ett "prefix" som skrivs innan attributet/metoden. Det beskriver dessutom vilket indata varje metod har, samt om metoden returnerar något data.

Ett fullt UML-schema beskriver vilka relationer klasserna har till varandra. Vi kommer senare att gå igenom att klasser kan både ärva och implementera andra klasser. Detta är någonting som ett UML-schema visar. Schemat beskriver även om en klass använder, äger eller "har" en annan klass.

I följande exempel är klassen "Animal" en superklass till subklasserna "Cat" och "Dog", det vill säga att Cat och Dog ärver från Animal. När en klass ärver från en annan klass så kan man via subklassen (Cat & Dog) använda alla metoder som superklassen (Animal) har. Dessutom finns det möjlighet att överskriva (Override) metoder i supeklassen. T.ex har superklassen Animal en klass som heter "Eat". Dock så vill vi specificera exakt vad just Cat och Dog ska äta, så vi skriver en ny Eat-metod i både Cat och Dog. Kallar vi nu på metoder Eat med ett Cat- eller Dogobjekt så kommer deras egna metoder att köras och inte superklassen Animals Eat-metod. Väljer man däremot att inte skriva en ny Eat-metod i sin subklass så kommer huvudklassens metod att köras.

Datastrukturer

Träd

En trädstruktur bygger på en rotnod som är "grunden" i trädet. Det är i roten som all avsökning börjar och det är även i roten som man tar bort objekt ur trädet. Varje nod innehåller det datat man vill lagra, det kan till exempel vara siffror, filmtitlar, personnummer osv. Noden har sedan en referens i sig som pekar på dess barn.
Ett träd har följande uppdelning:

Träd

• Rot: Grundnoden
  
• Förälder: Förälder till noden under sig
  
• Barn: Barn till noden över sig
  
• Syskon: Två noder som har samma förälder
  
• Gren: Ett träd kan ha flera grenar. Varje gren har en toppnod och en egen trädstruktur
  
• Löv: Nod som inte har några barn
  

Heap

En heap bygger på en fullstädig trädstruktur där varje nod högst kan ha 2 stycken barn. Det finns två typer av heapar: Maxheap och Minheap.

Maxheap

Minheap

Maxheap

• Roten har det största värdet i heapen
• Varje barn har ett mindre värde än sin förälder
• Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är större än den nya roten. Finner man ett barn som är större, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är större än noden. Är båda barnen större, byt med den största.
• Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är större än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.

Minheap

• Roten har det minsta värdet i heapen
• Varje barn har ett större värde än sin förälder
• Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är mindre än den nya roten. Finner man ett barn som är mindre, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är mindre än noden. Är båda barnen mindre, byt med den minsta.
• Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är mindre än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.

Binärt sökträd

Binärt sökträd

Ett binärt sökträd består även det av en trädstruktur, dock inte nödvändigtvis ett fullständig träd. Ett binärt sökträd har följande egenskaper:

• Varje nod har ett värde
• Nodens vänstra barn och alla andra noder i det vänstra benet ska ha ett mindre värde än noden själv
• Nodens högra barn och alla andra noder i det högra benet ska ha ett större värde än noden själv

Kö (Queue)

Stack

Listor

Enkellänkad lista
Dubbellänkad lista
Cirkulärt dubbellänkad lista

Iterator

Traversering

Preorder traversering
E C A B D H F G

Inorder traversering
A B C D E F G H

Postorder traversering
B A D C G F H E

Traversering innebär att man läser av (och skriver ut) 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. Ett enkelt sett att tänka vid pre- in- och postorder är att varje nod är en cirkel med tre stycken kontaktpunkter: Vänster, botten och höger. Beroende på vilken typ av traversering man är ute efter väljer man att fokusera på en av de tre kontaktpunkterna. Varje traversering börjar sedan på rotnodens vänstra sida. Följ därefter ytterkanten runt hela trädet tills du är tillbaka vid startläget. Varje gång du stöter på den kontaktpunkten som korresponderar med den traverseringen du gör så skriver du ut värdet i noden.

Levelorder-Traversering
Vid Levelorder-traversering läser man av noderna och dess värde, från vänster till höger och nivå för nivå.
E, C, H, A, D, F, B, G

Preorder-Traversering
Vid preorder-traversering fokuserar du på vänster kontaktpunkt, det vill säga varje gång du stöter på vänster kontaktpunkt så skriver du ut den.
E, C, A, B, D, H, F, G

Inorder-Traversering
Vid inorder-traversering fokuserar du på kontaktpunkten som är under noden. Någonting annat att lägga märke till är att värderna är sorterade från minst till högst.
A, B, C, D, E, F, G, H

Postorder-Traversering
Vid postorder-traversering fokuserar du på höger kontaktpunkt.
B, A, D, C, G, F, H, E

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

Sammanfattningar

Fil:Sammanfattning-TDDC30.pdf