On 17/04/15 19:11, niyanax...@gmail.com wrote:
Hello I need guidance trying to solve my assignment.
> I am completely lost when using maps with linked lists.
> I understand linked lists though.
Unfortunately we do not. Linked lists aren't really
a native Python type and maps are a native type - the
dictionary. So implementing the equivalent of a
native type using a non-native type is kind of a
bizarre situation.
Without knowing how your linked list is built we can't
tell you anything about how to build a map(dictionary)
from it.
implement the Map ADT using a singly linked list:
• Map(): Creates a new empty map.
• length(): Returns the number of key/value pairs in the map.
• contains(key): Returns a Boolean indicating if the given key is in the map.
• setitem(key, value): Adds a new key/value pair to the map if the key is not
in the map. If the key is in the map, the new value replaces the original value
associated with the key.
• getitem(key): Returns the value associated with the given key, which must
exist.
• clear(): Clears or empties the map by removing all key/value pairs.
• keys(): Returns a list containing the keys stored in the map.
• values(): Returns a list containing the values stored in the map.
• toString(): Returns a string representation of the map in the following
format: {k1:v1, k2:v2, ..., kN:vN}
• min(): Returns the minimum key in the map. The map can not be empty.
• max(): Returns the maximum key in the map. The map can not be empty.
• copy(): Creates and returns a new map that is a duplicate copy of this map.
That's a pretty hefty API for an assignment of this type!
My Code (so far):
I assume that your Node is in a separate file called LinkedList.py?
class Node:
def __init__( self, item, next = None ) :
self.item = item
self.next = next
def getItem( self ) :
return self.item
def getNext( self ) :
return self.next
def setItem( self, item ) :
self.item = item
def setNext( self, next ) :
self.next = next
That all seems fairly normal.
class Map:
def __init__( self, contents = []) :
self.first = LinkedList.Node(None, None)
self.last = self.first
self.numItems = 0
for e in contents:
self.append(e)
Where does append() come from? Its not a method of Map.
def __len__( self ) :
count = 0
while self != None:
count +=1
self = self.next
return count
Notice you were asked to provide a length() method so
presumably your __len__() operator should just call
self.length(). And if you update self.numItems
correctly isn't length() just returning self.numItems?
def contains() :
pass
def __setitem__( self, index, value ) :
if index >= 0 and index < self.numItems:
cursor = self.first.getNext()
for i in range( index ):
cursor = cursor.getNext()
return cursor.getItem()
you seem to have the setItem and getItem actions reversed?
def __getitem__( self, index, value ) :
if index >= 0 and index < self.numItems:
cursor = self.first.getNext()
for i in range( index ):
cursor = cursor.getNext()
cursor.setItem( value )
return
I suggest you go and have a think about how you will store the key/value
pairs needed for a map in your list. Then think about
how you find a node by key. Then think about how to get the
value or set a new value on that node.
<rant>
I hate when teachers ask students to do stupid stuff like this.
It encourages so many bad practices it's positively dangerous!
If they must have them reinvent the wheel at least let them
use the native Python list to do it!
</rant>
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
