Hello Ni'Yana, and welcome!
On Fri, Apr 17, 2015 at 06:11:00PM +0000, 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. May someone work with me?
We will not do your homework, but perhaps we can guide you.
Thank you for showing your code. It looks like you have already made a
lot of progress.
Unfortunately, the one thing you did not tell us is what part of the
assignment you are having problems with! It looks like you have done
most of the work correctly so far, so what part is giving you trouble?
A few comments on your code below:
> 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
Your Node class looks straightforward, but it doesn't match the
requirements. The requirement for the Map is that it must have key:value
pairs. But your Node doesn't have two data fields, it only has one! So
you cannot give the Node both a key and a value.
Your Node class needs to start like this:
class Node:
def __init__(self, key, value, next=None):
self.key = key
self.value = value
self.next = next
That will help get the Map class right. See my comments below.
> class Map:
> def __init__( self, contents = []) :
> self.first = LinkedList.Node(None, None)
First problem: you have added code which is not part of the
specifications. The assignment says that calling Map() returns a new
empty map. It says nothing about Map([1, 2, 3]). Get rid of the
"contents" argument, it is not required. Once you get rid of that, the
"for e in contents" loop is not required. Get rid of it!
Second problem: LinkedList is not defined anywhere. What is it?
The easiest way for this to work is to put the None class and the Map
class in the same file, and then you can just say:
self.first = Node(None, None)
without worrying about the name of the file. Java has a rule that each
class, no matter how tiny, must go in its own file, but Python does not
have such a rule. Related classes may go in the same file.
Third problem: your assignment to self.first is wrong! That gives
the Map a single item, not zero items!
An empty linked list will be represented here by just None alone.
self.first = None
You then traverse the linked list like this:
node = self.first
while node is not None:
print("key = %s, value = %s" % (node.key, node.value))
node = node.next
which will print all the keys and values in the map.
To add a new node to the end, you do this:
node = self.first
# The empty Map case is special.
if node is None:
self.first = Node("the key", "some value")
else:
while node.next is not None:
node = node.next
# Now we are at the end of the linked list.
# Add a new node.
node.next = Node("the key", "some value")
> self.last = self.first
> self.numItems = 0
> for e in contents:
> self.append(e)
>
> def __len__( self ) :
> count = 0
> while self != None:
> count +=1
> self = self.next
> return count
I don't think that this will do what your assignment asks.
The first problem is that your assignment says that your Map must have a
method called `length` which returns the number of items. Your Map class
has no method called `length`, instead it uses the Python special
__len__ method.
I think you need to change the name of this __len__ method to length. It
is still be buggy (have you tested it?) but at least it will do what the
assignment says.
Let us think about how to implement this length method. It is actually
very easy! Your Map class already has a counter which tell you how many
items are in the map, and it is initialised with:
self.numItems = 0
so length is easy:
def length(self):
return self.numItems
Now all you need to do is make sure that every time you add a node to
the Map, add 1 to numItems, and every time you delete a node, you
subtract 1.
> def contains() :
> pass
I assume this is just a stub which is not finished yet.
The contains method just needs to walk the linked list and look for the
key. I showed you code above that walks the linked list printing keys
and values. Instead of printing, you compare the node's key to the key
you are looking for, and if they are equal, return True:
while node is not None:
if node.key == key:
return True
If you reach the end of the linked list without finding the key, you
have to return False.
Both your __setitem__ and __getitem__ methods also ignore what the
assignment says. The assignment wants methods called `setitem` and
`getitem`, not the special Python double-underscore methods. So you need
to change their names, then test them.
Also, they fail to do what the assignment says. Read the requirements:
getitem(key): Returns the value associated with the given key, which
must exist.
Does your __getitem__ method take a key as argument? No it does not, it
takes an index!
getitem needs to take a single argument, the key. It then walks the
linked list (as I showed you above), comparing the node's key to the
wanted key. If they are equal, you then return node.value. If they are
not equal, go on to the next node.
If you run out of nodes before finding the key, that is an error.
setitem needs to take two arguments, a key and a value. You then walk
the linked list (again!) and compare the node's key to the wanted key.
If they are equal, you set the node's value to the new value:
node.value = value
and return.
If you run out of nodes, you add a new node at the end.
Remember what I said about incrementing the counter!
By this time, you should see a pattern. Nearly all these methods
demonstrate the same sort of procedure: you walk the linked list,
looking at each node in turn:
node = self.first
while node is not None:
do_something_with(node)
--
Steve
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
