bild
Skolan för
elektroteknik
och datavetenskap

Laboration 5 - Atomvikter

Ditt program ska bygga upp en databas över alla grundämnens beteckningar och atomvikter så att det supersnabbt kan söka önskad information. I terminalfönstret ställs frågorna, t ex
    Atombeteckning: Ag
    Atombeteckning: Au
    Atombeteckning: Q
    Atombeteckning: 
och i ett annat fönster skriver programmet ut informationen (dvs atomnamnet och atomvikten) överskådligt och tjusigt! Om atomen inte finns dyker felmeddelandet Okänd atom: Q upp i fönstret istället.

Du ska göra två versioner av programmet. Först löser du det med Pythons inbyggda datastruktur dictionary och sedan genom att själv implementera en hashtabell.


Hashning med Pythons inbyggda dictionary

Datafilen atoms.dat består av rader av typen
    Ag  107.868
I den första varianten av programmet ska du läsa in filen i en dictionary atomlist med atombeteckningen som nyckel och atomvikten som värde, alltså enligt principen
   atomlist["Ag"] = 107.868
Några tips:
  • Kolla med atomlist.has_key() om atomnamnet finns.
  • Databasen har atomvikterna som textsträngar, men float(vikt) gör om dom till tal att räkna med. Detta vill du få rätt till laboration 7 där du ska räkna ut molekylvikter.

Grafiken

För att få till grafiken importerar du klassen molgrafik från filen molgrafik.py och skapar en instans av den: mg=molgrafik(). Dessutom behövs en klass Ruta du kan lägga överst i ditt program:
class Ruta:          
    atom="( )"
    num=1    
    next=None
    down=None

Ditt objekt mg kan visa rutor. (Det ska du använda i laboration 7 också.) Gör ett objekt r av Ruta och sätt instansvariabeln atom till det du vill ska synas i grafikfönstret (atomnamn och -vikt). Använd sedan metoden show så här: mg.show(r)

Om programmet avslutas direkt hinner man inte se grafiken blinka förbi. Se därför till att ha en slinga för inmatning av flera atomer...


Egen hashtabell

I den andra versionen av programmet ska du byta ut Pythons inbyggda dictionary med en egen hashtabell. Här följer ett programskelett du kan utgå från. I detta skelett är det tänkt att krockproblemet ska lösas med kvadratisk probning.

class Node:
    # I varje position i hashtabellen lagras en nod
    key=""
    value=None

class Hashtable:
    size=31
    table=[None]*31
    hashiter = 0 # behövs för hashfunction() och rehash()
    
    def __init__(self,n):
        # En konstruktor. Med hjälp av denna kan man
        # vid instansiering bestämma storleken på tabellen.
        self.size=n
        self.table=[None]*n
        
    def getsize(self):
        return self.size
    
    def has_key(self,key):
        # Finns något lagrat med nyckeln "key"?
        h=self.hashfunction(key)
	p=self.table[h]
        while p!=None and p.key!=key:
            h=self.rehash(h)
            p=self.table[h]
        if p!=None and p.key==key:
            return True
        return False

    def put(self,key,value):
        # Stoppa in "value" med nyckeln "key", dvs skapa en nod 
	# och stoppa in den på rätt plats i "table"
        ---

    def get(self,key):
        # Hämta det som finns lagrat med nyckeln "key"
        # Om det inte finns: kasta ett särfall
        ---
        raise Exception,key+" finns inte"
    
    def hashfunction(self, key):
        # Returnera hashvärdet av key - "startar den kvadratiska probningen"
        ---

    def rehash(self, oldhash):
        # Beräkna nästa plats (efter oldhash) enligt kvadratisk probning
        ---
Hur stor bör hashvektorn vara för att man inte ska få för många krockar? Kom ihåg att det är bäst att använda primtal. Använd detta tal och konstruera ett objekt av klassen Hashtable.
from Hashtable import Hashtable
...
atomtable = Hashtable(17) #...men sjutton är fel
Gör en kopia av första versionen av programmet och använd din Hashtable: hasha in alla atomer i atomtabellen med atomtable.put(...), kolla om de finns där med atomtable.has_key(...) och hämta innehållet med atomtable.get(...).


Lysande genomfört av................................. menar............................ den ...............


Sidansvarig: Magnus Rosell <rosell@csc.kth.se>
Uppdaterad 2006-09-18