Datalogilaboration 4 - Sökning

Binärsökning i ordlista är laborationens tema och uppgiften är att bland fembokstavsorden finna alla ordpar av typen alpin pinal, där första ordet delas i 2+3, kuperas till 3+2 och då ger andra ordet.

Inläsning från fil och linjär sökning

Filen /info/kurser/datalogi_e03/labbar/ordlista.txt innehåller 1862 svenska ord, nämligen alla som består av fem olika bokstäver. Ta en titt på filen för att se hur den är uppbyggd och skriv sedan ett program som läser in filen i vektorn listord. Låt filen heta Kolla.java och börja så här
    class Kolla1 {
        static int N=1862;
En utskrift ska göras när ordlistan är inläst. Programmet ska sedan kolla om ett angivet ord finns i ordlistan enligt följande exempel.
Observera att här ska man undvika använda tecknet < för att läsa in filen utan att man ska använda javas-funktioner för filinläsning.(titta på exempelet Register2 i föreläsning4 eller exemplen i övning5 i olika övningsgrupper)
    java Kolla1 trams
    Ange namn på den fil som ska läsas in: ordlista.txt
    Ordlistan inläst!
    trams finns
Klassen Kolla1 ska, förutom main() innehålla en metod finns() som returnerar true eller false efter en linjär sökning i vektorn. Från main() anropas den så här.
    if (finns(listord, args[0]))
        System.out.println(args[0] + " finns");
Tänk efter vilken typ argumenten har och vilken typ returvärdet har. Provkör programmet med ordet gurka och med ordet banan. Förklara bananresultatet! (Tips: förklaringen finns i den text du har läst.)

Linjär sökning efter alpina pinaler

Utöka filen med en klass Kolla2 som är en kopia av Kolla1. Ta bort sökningen efter args[0] och lägg i stället in en slinga som för varje listord kollar om det ord som bildas när man kastar om bokstäverna som i alpin->pinal finns i ordlistan. Alla alpina pinaler ska skrivas ut.

Körningen visar sej ta ganska lång tid. Medan datorn jobbar kan du själv ägna dej åt att göra sökningen snabbare. Det är labbens avslutande moment.

Binär sökning

Utöka filen med en klass Kolla3 som är en kopia av Kolla1. Du ska ändra metoden finns så att den gör binär sökning i stället. Om du vill kan du ta vettiga delar av den kod Weiss har i boken (leta efter binary search), men några små ändringar måste till. I hans första upplagga blir a[mid].compares(x) till exempel listord[mid].compareTo(ord). I båda upplagorna ska hans return mid ha ett annat returvärde, och hans throw-sats ska bytas ut mot ännu en return-sats. För att se hur sökningen går till ska du efter raden mid = ( low + high ) / 2 stoppa in en utskrift av listord[mid].

Provkör med några olika ord. Hur många sökord blir det som mest? Och hur många blir det som minst?

Binär sökning efter alpina pinaler

Utöka filen med en klass Kolla4 som är en kopia av Kolla2. Kopiera in binärsökningen från Kolla3 men ta bort utskriftsraden. Provkör och uppskatta hur många gånger snabbare binärsökningen är!

Försök till sist få underskrift av en lärare.

Fenomenal prestation av ..................................... intygar.............................. den .................


^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 26 oktober 2003
Tekniskt stöd: <webmaster@nada.kth.se>