I am trying to sort a linked list in descending order
Can you please help me, i am trying to sort the linked lists according to the documentation in the add function but i am getting an error which says: f.add('b', 2) File "", line 69, in add AttributeError: 'NoneType' object has no attribute 'next' how can i avoid this? Thankyou.
class Frequency(object):
"""
Stores a letter:frequency pair.
>>> f = Frequency('c', 2)
>>> f.letter
'c'
>>> f.frequency
2
>>> f
{c: 2}
"""
def __init__(self, letter, frequency):
self.letter = letter
self.frequency = frequency
self.next = None
def __repr__(self):
return '{%s: %d}' % (self.letter, self.frequency)
class SortedFrequencyList(object):
"""
Stores a collection of Frequency objects as a sorted linked list.
Items are sorted from the highest frequency to the lowest.
"""
def __init__(self):
self.head = None
def add(self, letter, frequency):
开发者_开发知识库 """
Adds the given `letter`:`frequency` combination as a Frequency object
to the list. If the given `letter` is already in the list, the given
`frequency` is added to its frequency.
>>> f = SortedFrequencyList()
>>> f.add('a', 3)
>>> f
({a: 3})
>>> f.add('b', 2)
>>> f
({a: 3}, {b: 2})
>>> f.add('c', 4)
>>> f
({c: 4}, {a: 3}, {b: 2})
>>> f.add('b', 3)
>>> f
({b: 5}, {c: 4}, {a: 3})
"""
current = self.head
found = False
if self.head is None:
self.head = Frequency(letter, frequency)
else:
prev = None
while current is not None:
if current.letter == letter:
current.frequency = current.frequency + frequency
found = True
prev = current
current = current.next
next1 = current.next
if next1 is None:
current = next1
if current.frequency < next1.frequency:
temp = current
current = next1
next1 = temp
else:
current = next1
next1 = current.next.next
if found is False:
prev.next = Frequency(letter, frequency)
In the lines
current = current.next
next1 = current.next
what happens if current.next == None
?
I don't know if you are doing this as a Python exercise or because you actually need the functionality; if the latter, there is already a built-in class that does this for you. It's collections.Counter
(in Python 2.7 or 3.x); if you're using an earlier version then you can make one yourself by subclassing collections.defaultdict
. It also uses Python dictionaries instead of storing data as key-value pairs.
Example:
>>> from collections import Counter
>>> x = Counter()
>>> x['a'] += 2
>>> x['b'] += 3
>>> x['c'] += 1
>>> x
Counter({'b': 3, 'a': 2, 'c': 1})
You can recover the sorted key-value pair representation of your data with
x.most_common()
精彩评论