Liste, pile e code

Nella lezione del 27/10, abbiamo visto le principali strutture dati basate sul concetto di sequenza:

• Liste
  • Implementazione tramite puntatori (linked list)
  • Implementazione tramite array
• Pile
• Code
  • Basate su liste
  • Basate su array (in genere code circolari)
• Dizionari

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.

Today, we introduced the sequence data structures:

• List
  • Linked list
  • Array
• Stack
• Queue
  • Based on lists
  • It is possible to have the same structures based on arrays (as Circular Queues)
• Dictionary

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()')