मैं गुडरिक एट अल द्वारा डेटा संरचनाओं और एल्गोरिदम के माध्यम से काम कर रहा हूं, और मुझे यह समझने में परेशानी हो रही है कि नीचे दिए गए कोड में त्रुटि क्यों है। विशेष रूप से, यह एक क्रमबद्ध प्राथमिकता कतार का कार्यान्वयन है। नीचे दिए गए कोड में चार वर्ग होते हैं: एक डबल लिंक्ड पोजिशनल लिस्ट के लिए बेस क्लास, पोजिशनल लिस्ट, प्राथमिकता कतार के लिए बेस क्लास, और एक अनसुलझा प्राथमिकता कतार। कक्षा परिभाषाओं के अंत में मैं एक क्रमबद्ध प्राथमिकता कतार बनाता हूं, इसमें तीन कुंजी/मान जोड़ता हूं, और फिर न्यूनतम खोजने का प्रयास करता हूं। हालांकि, एक त्रुटि होती है जो कहती है कि "_find_min" विधि को कॉल करने पर "UnsortedPriorityQueue में कोई विशेषता नहीं है 'is_empty'"। लेकिन "is_empty" को इसकी बेस क्लास से विरासत में क्यों नहीं मिला है?

class _DoublyLinkedBase:
    
    class _Node:
        __slots__ = '_element', '_prev', '_next'

        def __init__(self, _element, _prev, _next):
            self._element = _element
            self._prev = _prev
            self._next = _next

    def __init__(self):
        self._header = self._Node(None, None, None)
        self._trailer = self._Node(None, None, None)
        self._header._next = self._trailer
        self._trailer._prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):
        newest = self._Node(e, predecessor, successor)
        predecessor._next = newest
        successor._prev = newest
        self._size += 1
        return newest

    def _delete_node(self, node):
        predecessor = node._prev
        successor = node._next
        predecessor._next = successor
        successor._prev = predecessor
        self._size -= 1
        element = node._element
        node._prev = node._next = node._element = None #Depreciate node
        return element
        
        
        
        
class PositionalList(_DoublyLinkedBase):

    class Position:

        def __init__(self, container, node):
            self._container = container
            self._node = node

        def element(self):
            return self._node._element

        def __eq__(self, other):
            return type(other) is type(self) and other._node is self._node

        def __ne__(self, other):
            return not(self == other)

    def _validate(self, p):
        if not isinstance(p, self.Position):
            raise TypeError( 'p must be proper Position type' )
        if p._container is not self:
            raise ValueError( 'p does not belong to this container' )
        if p._node._next is None: # convention for deprecated nodes
            raise ValueError( 'p is no longer valid' )
        return p._node

    def _make_position(self, node):
        if node is self._header or node is self._trailer:
            return None
        else:
            return self.Position(self, node)

    def first(self):
        return self._make_position(self._header._next)

    def last(self):
        return self._make_position(self._trailer._prev)

    def before(self, p):
        node = self._validate(p)
        return self._make_position(node._prev)

    def after(self, p):
        node = self._validate(p)
        return self._make_position(node._next)

    def __iter__(self):
        cursor = self.first()
        while cursor is not None:
            yield cursor.element()
            cursor = self.after(cursor)

    def _insert_between(self, e, predecessor, successor):
        node = super()._insert_between(e, predecessor, successor)
        return self._make_position(node)

    def add_first(self, e):
        return self._insert_between(e, self._header, self._header._next)

    def add_last(self, e):
        return self._insert_between(e, self._trailer._prev, self._trailer)

    def add_before(self, p, e):
        original = self._validate(p)
        return self._insert_between(e, original._prev, original)

    def add_after(self, p, e):
        original = self._validate(p)
        return self._insert_between(e, original, original._next)

    def delete(self, p):
        original = self._validate(p)
        return self._delete_node(orignal)

    def replace(self, p, e):
        original = self._validate(p)
        old_value = original._element
        original._element = e
        return old_value
        
class PriorityQueueBase:
    class _Item:
        __slots__ = '_key', '_value'
        def __init__(self, k, v):
            self._key = k
            self._value = v
        def __lt__(self, other):
            return self._key < other._key #Compare items based on keys
        def is_empty(self):
            return len(self) == 0
        
class UnsortedPriorityQueue(PriorityQueueBase):
    #_data is a positional list
    def _find_min(self): #Nonpublic utility, means it shouldn't be accessed->
        if self.is_empty():                           #-> outside of the class
            raise Exception('Priority Queue is empty.')
        small = self._data.first() #This is a positional list
        walk = self._data.after(small)
        while walk is not None:
            if walk.element() < small.element():
                small = walk
            walk = self._data.after(walk)
        return small
    def __init__(self):
        self._data = PositionalList()
    def __len__(self):
        return len(self._data)
    def add(self, key, value):
        #PositionalList elements are _Items.
        self._data.add_last(self._Item(key, value))
    def min(self):
        p = self._find_min()
        item = p.element()
        #PositionalList elements are _Items.
        return (item._key, item._value)
    def remove_min(self):
        p = self._find_min()
        item = self._data.delete(p)
q = UnsortedPriorityQueue()
q.add(1, 'a')
q.add(2, 'b')
q.add(3, 'c')
q.min()
0
Oliver G 14 सितंबर 2020, 17:29

1 उत्तर

सबसे बढ़िया उत्तर

ऐसा इसलिए है क्योंकि यह उस वर्ग के लिए परिभाषित नहीं है। is_empty को आंतरिक वर्ग _Item के लिए परिभाषित किया गया है, PriorityQueueBase के लिए नहीं।

संपादित करें: मैंने आपके कोड पर एक और छुरा लिया और मुझे लगता है कि यह सिर्फ एक इंडेंटेशन मुद्दा है। यदि आप is_empty विधि को ठीक से डी-इंडेंट करते हैं तो समस्या का समाधान होना चाहिए।

2
Exelian 14 सितंबर 2020, 17:41