equivalent of pascal's poitners in python
Brian Quinlan
brian at sweetapp.com
Sun Apr 1 06:44:27 EDT 2001
# I'm not sure that I am the right person to help you with your object
# point since I wouldn't use objects in this case. BTW, are you trying
# to use method overloading?
example = \
"""
For Huffman coding you create a binary tree which
stores individual characters at the leaf nodes, and
an integer (for frequency) at both leaf and internal nodes.
I am new to Python, too, so this code may
not be quite right. Maybe it will be enough for
someone else to fix up.
class HuffmanNode():
def __init__(self, ch, freq):
self.ch=ch
self.freq=freq
self.left=None
self.right=None
def __init__(self, node1, node2):
self.ch=None
self.freq = node1.freq + node2.freq
self.left=node1
self.right=node2
The point is, like java, there is no such thing as a pointer
because any number of variables can represent the same
object, just as if they were pointers to the same object.
Perhaps someone else could also sketch out the
tree-building proceedure:
1) create a node for each character in the source text
with it's frequency of occurrence, and store in a collection
2) remove the 2 least-frequent nodes from the collection,
and join them with a new common parent.
3) put the new parent node back in the collection
4) repeat steps 2,3 until all nodes form a single tree
I think this could be done in very few lines of code,
but as I said, I just started looking python, too.
"""
def prettyTree( tree, depth = 0 ):
# Too lazy to import types, which would lead to MUCH nicer style
if type( tree[1] ) in [type( () ),type( 5 )]:
print ' ' * depth + str( tree[1] )
elif type( tree[1] ):
prettyTree( tree[1], depth + 1 )
if type( tree[0] ) == type( () ):
print ' ' * depth + str( tree[0] )
else:
prettyTree( tree[0], depth + 1 )
d = {}
for i in example:
d[i] = d.get( i, 0 ) + 1
freqs = d.items( )
freqs.sort( lambda x,y: cmp( x[1], y[1] ) )
while len( freqs ) > 2:
freqs = [[freqs[0:2],freqs[0][1] + freqs[1][1]]] + freqs[2:]
# I should be shot for not using a bubble sort here.
freqs.sort( lambda x,y: cmp( x[1], y[1] ) )
prettyTree( freqs )
More information about the Python-list
mailing list