Liste, pile e code
Nella lezione del 27/10, abbiamo visto le principali strutture dati basate sul concetto di sequenza:
-
- Implementazione tramite puntatori (linked list)
- Implementazione tramite array
-
- Basate su liste
- Basate su array (in genere code circolari)
In aggiunta a quanto detto, ecco i file python con le implementazioni (corrette ed espanse) delle strutture dati viste a lezione. Inoltre la versione C++ delle liste (sia linkate che basate su array) si trova sulla pagina del libro di testo. Potete inoltre trovare qui un'implementazione delle liste tramite doppio puntatore.
Sequences
Today, we introduced the sequence data structures:
-
- Array
-
- Based on lists
- It is possible to have the same structures based on arrays (as Circular Queues)
Here you can find the files with the python implementation of the data structures. A C++ version can be found on the web page of Shaffer's book. A C implementation of doubly linked lists can be found here.
Simple List Implementation
#!/usr/bin/python class ListItem(object): '''Elemento della lista''' def __init__(self, elem, next=None): self.data=elem self._next=next class List(object): '''ADT Lista''' def __init__(self): self.head=ListItem(None) # testa della lista (elemento dummy) self.tail=self.head # coda della lista self.current=self.head # posizione corrente (coda della partizione sinistra) self.lsize=0 # dimensione della partizione sinistra self.rsize=0 # dimensione della partizione destra def setStart(self): '''Spostamento di current nella posizione di testa''' self.current=self.head self.rsize+=self.lsize self.lsize=0 def setEnd(self): '''Spostamento di current nella posizione di coda''' self.current=self.tail self.lsize+=self.rsize self.rsize=0 def getValue(): if self.rsize==0 : return None else : return self.current._next.data def insert(self,elem): '''Inserimento di un elemento nella testa della partizione destra''' self.current._next=ListItem(elem,self.current._next) # aggiorna tail se self.current==self.tail if self.tail==self.current : self.tail=self.tail._next self.rsize+=1 def delete(self): '''Cancellazione di un elemento alla testa della partizione destra''' if not self.current._next : return None res = self.current._next.data self.current._next=self.current._next._next self.rsize-=1 return res def next(self): '''Spostamento di current nella posizione successiva''' if self.current != self.tail : self.current=self.current._next self.rsize-=1 self.lsize+=1 def prev(self): '''Spostamento di current nella posizione precedente''' if self.current!=self.head: curr=self.head while curr._next != self.current : curr=curr._next self.current=curr self.lsize-=1 self.rsize+=1 def setPos(self,pos): '''Spostamento di current alla posizione pos; self.lsize=pos''' if pos<0 or pos>self.rsize+self.lsize : raise IndexError self.rsize = self.rsize+self.lsize-pos self.lsize = pos self.current=self.head for i in range(pos): self.next() def __str__(self): '''Costruzione della versione stampabile della lista''' res='[' if self.head==None : return res+' ]' if self.head==self.current : res+=' |' curr=self.head._next while curr != None : res+=' '+`curr.data` if curr==self.current : res+=' |' curr=curr._next return res+' ]' # Test -- non viene eseguito quando il modulo viene caricato come libreria if __name__ == '__main__' : def doprint(command) : '''Funzione di aiuto per la stampa formattata; notate l'uso di eval per eseguire codice contenuto in una stringa passata come parametro!''' eval(command) print command, ' '*(20-len(command))+'=>\t', a a = List() doprint('a.insert(1)') doprint('a.insert("pippo")') doprint('a.insert(2.0)') doprint('a.next()') doprint('a.insert("pluto")') doprint('a.setEnd()') doprint('a.delete()') doprint('a.prev()') doprint('a.insert("2")') doprint('a.setStart()') doprint('a.delete()')
