Laboration 3 - OrdträdLaborationens tema är binära sökträd och första uppgiften är att bygga upp ett sökträd från en fil med svenska ord och spotta ut dubbletter. Nästa uppgift är att kolla orden i en engelsk text mot det svenska sökträdet. Finns det några skenbart svenska ord ska dom skrivas ut, dock endast första förekomsten av varje svenskt ord. För att veta vilka ord man redan hittat sparar man förstås dom i ett annat sökträd.Ett sökträd med ordlistaI filenbintree.py ska du skriva en class bintree: med
tre anrop, nämligen följande (som kan tänkas stå i huvudprogrammet
lab3.py ).
from bintree import bintree # Övrigt i filen förblir dolt svenska=bintree() svenska.put("gurka") - - - if svenska.exists("gurka"): - - - svenska.write() # Skriver alla ord i bokstavsordningNär trädobjektets put("gurka") anropas skickar trädet sin
rotpekare och det nya ordet till en rekursiv funktion putta
som ser till att en ny nod skapas på rätt ställe. Analogt gör de
övriga anropen, alltså så här.
class bintree: root=None def put(self,newvalue): self.root=putta(self.root,newvalue) def exists(self,value): return finns(self.root,value) def write(self): skriv(self.root) printHär är klassen slut men sedan kommer definitionerna av putta, finns och skriv .
Trädet ska bara lagra en upplaga av varje objekt som läggs
in, så försöker man stoppa in en dublett händer ingenting.
Det finns förstås också en
I svenskfil=open("word3.txt","r") # Öppnar filen för läsning (r) for rad in svenskfil.readlines(): ord=rad[0:3] # Ett trebokstavsord per rad if svenska.exists(ord): print ord, else: svenska.put(ord) # in i sökträdet printOm du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap. Två binära sökträd med ordlistorNär du nu har ett sökträd med alla svenska trebokstavsord kan du blixtsnabbt kolla om ett givet ord finns med. Du ska nu läsa filen engelska.txt ord för ord och putta in orden i ett annat sökträd. Nu vill du inte ha dubbletterna utskrivna, så kolla förstif engelska.exists(...) . Om ordet redan fanns gör du ingenting, men om det är nytt ska
du också kolla om det råkar finnas som svenskt ord. I så fall ska det
skrivas ut på skärmen.
Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap! När du mottagit det kan du försöka få underskrift av en lärare. Frivilliga extrauppgifterSöt tös: Undersök vilka trebokstavsord som blir andra ord baklänges. Varje ordpar ska bara skrivas ut en gång och symmetriska ord inte alls.Alpin pinal: Undersök vilka fembokstavsord som blir ett annat ord när dom två första bokstäverna flyttas sist. Du kan använda ordlistan word5.txt. Genialt programmerat av ..................................... anser.............................. den ................. |