Datastrukturer & Algoritmer, Datalogi C

Henning Christiansen 23/10-2001

Opgaver til forelÊsningen 22/10-2002

Opgave 1 og 2 er afleveringsopgave for Datalogi C. Afleveringsfristen er 1. oktober men aftal evt. en senere frist med Lars, da opgaven er annonceret lidt sent.

Opgave 1

Afsnit 17.2 i bogen beskriver en class LinkedList. Udvide klassen med toString- og equals-metoder; equals skal svare til at to lister indeholder de samme (equals) elementer i den samme rÊkkef¯lge. Udvid yderligere klassen med en compareTo-metode, som er baseret p f¯lgende principper, som kaldes en leksikalsk ordning.

≠ hvis to lister indeholder de samme elementer i samme rÊkkef¯lge (som equals ovenfor) betragtes de som vÊrende ens.

≠ hvis liste1πs f¯rste element kommer f¯r liste2πs f¯rste element, s siger vi, at liste1 kommer f¯r liste2.

≠ hvis liste1 og liste2 indeholder de samme elementer i samme rÊkkef¯lge op til og med position n, s gÊlder f¯lgende:

o hvis liste1 ikke har noget n+1πte element, s kommer list1 f¯r liste2

o ellers, hvis liste1πs (n+1)πte element kommer f¯r liste2πs (n+1)πte, s kommer liste1 f¯r liste2.

Grunden til, vi kalder denne ordning leksikalsk, er at den svarer til sortering af n¯gleordene i en ordbog eller et leksikon ã hvis alts hvert ord betragtes som en liste af bogstaver. F.eks. ≥a≤ kommer f¯r ≥ab≤, som kommer f¯r ≥abc≤, som kommer f¯r ≥abe≤. ImplementÈr og aftest l¯sningen.

Opgave 2

I bogens afsnit 17.4 beskrives en klasse SortedLinkedList. Skriv en metode

public SortedLinkedList merge(SortedLinkedList L1,SortedLinkedList L2)

som tager to sorterede lister L1 og L2 og producerer en ny sorteret liste bestÂende af elementerne fra L1 og L2. ImplementÈr og aftest l¯sningen.

Opgave 3 (LÊs og forst opgaveformuleringen; det at l¯se den er kun for sÊrligt interesserede)

Benyt den version af quicksort som blev brugt ved forelÊsningen 8. oktober (se kursets www-side). Opgaven handler om at hÂndoptimere koden ved at erstatte rekursion med en stak implementeret ved et array ã og hvor man ikke skal benytte nogen af Javas medf¯lgende klasser men skrive stakmanipulationen direkte i koden (s som at lÊgge ting ind i arrayet og tÊlle staktoppen op og ned). S i stedet for at have en rekursiv metode

quicksort( Comparable [ ] a, int low, int high )

placeres al koden inde i en ikke rekursiv

quicksortNonRecursive( Comparable [ ] a )

som (i optimeringens ¯jemed) ogs indeholder koden fra ≥partition≤.

For at undg at pakke ting ind i objekter, benytter vi to stakke, en for ≥low≤ og en for high≤:

int [] lowStack = new int [100]; int [] highStack = new int [100];

stackTop = 0; lowStack[0]=0; highStack[0]= a.length ≠ 1;

Stakken initialiseres alts s den indeholder data svarende til det f¯rste kald af den oprindelige rekursive metode.

Strategien en nu at quicksortNonRecursive benytter en l¯kke, der indeholder f¯lgende:

1. Der tages et par af low og high af stakkene og der foretages ≥partition≤

(med mindre forskellen mellem de to er under tÊrsklen, s vi beder

insertionSort om at g¯re arbejdet; indsÊt ogs kopi af indmaden fra insertionSort i quicksortNonRecursive for at vÊre sikker p at spare metodekald)

2. Der hvor den oprindelige quicksort siger

quicksort( a, low, newPosForOldMiddleElt - 1 );

quicksort( a, newPosForOldMiddleElt + 1, high );

smider vi i stedet de to gange argument-par p stakkene.

Benyt de tidsmÂlingsvÊrkt¯jer som blev beskrevet ved en tidligere opgave til at afg¯re hvor meget hurtigere (om noget?) den ikke-rekursive er sammenlignet med den oprindelige rekursive.