Hi,
I'm reading "How to think like a computer scientist in python". So far,
it's been smooth sailing, but the final exercise in chapter 19 really
has me stumped. Is it just me, or did this book get very difficult, very
quickly? It says:
"As an exercise, write an implementation of the Priority Queue ADT using a
linked list. You should keep the list sorted so that removal is a constant
time operation. Compare the performance of this implementation with the
Python list implementation."
Here is the code so far:
import sys
class Node:
def __init__(self, cargo=None, next=None, prev=None):
self.cargo = cargo
self.next = next
self.prev = prev
def __str__(self):
return str(self.cargo)
def printBackward(self):
if self.next != None:
tail = self.next
tail.printBackward()
print self.cargo
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def printBackward(self):
print "["
if self.head != None:
self.head.printBackward()
print "]"
def addFirst(self, cargo):
node = Node(cargo)
node.next = self.head
self.head = node
self.length = self.length + 1
def printList(node):
sys.stdout.write("[")
while node:
sys.stdout.write(str(node.cargo))
if node.next != None:
sys.stdout.write(", ")
else:
sys.stdout.write("]")
node = node.next
print
def printBackward(list):
if list == None:
return
head = list
tail = list.next
printBackward(tail)
print head,
def removeSecond(list):
if list == None: return
if list.next == None: return
first = list
second = list.next
first.next = second.next
second.next = None
return second
def printBackwardNicely(list):
print "[",
if list != None:
head = list
tail = list.next
printBackward(tail)
print head,
print "]"
class Queue:
def __init__(self):
self.length = 0
self.head = None
def isEmpty(self):
return (self.length == 0)
def insert(self, cargo):
node = Node(cargo)
node.next = None
if self.head == None:
self.head = node
else:
last = self.head
while last.next: last = last.next
last.next = node
self.length = self.length + 1
def remove(self):
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length - 1
return cargo
class ImprovedQueue:
def __init__(self):
self.length = 0
self.head = None
self.last = None
def isEmpty(self):
return (self.length == 0)
def insert(self, cargo):
node = Node(cargo)
node.next = None
if self.length == 0:
self.head = self.last = node
else:
last = self.last
last.next = node
self.last = node
self.length = self.length + 1
def remove(self):
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length - 1
if self.length == 0:
self.last = None
return cargo
class PriorityQueue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def insert(self, item):
self.items.append(item)
def remove(self):
maxi = 0
for i in range(1,len(self.items)):
if self.items[i] > self.items[maxi]:
maxi = i
item = self.items[maxi]
self.items[maxi:maxi+1] = []
return item
class Golfer:
def __init__(self, name, score):
self.name = name
self.score = score
def __str__(self):
return "%-16s: %d" % (self.name, self.score)
def __cmp__(self, other):
if self.score < other.score: return 1
if self.score > other.score: return -1
return 0
I figured I'd copy ImprovedQueue and tamper with the insert method
so as to traverse the linked list, checking if the cargo of the next node
was smaller than the one I was inserting, and if so, to set the current
node's next to the new node, and the new node's next to the node with the
lesser value, but I just can't get this to work outside of my head. I'd
appreciate any pointers anyone might give me to figure this out.
--
http://mail.python.org/mailman/listinfo/python-list
