Verkette Listen
- __blackjack__
- User
- Beiträge: 13111
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
Was __deets__ gesagt hat.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
- __blackjack__
- User
- Beiträge: 13111
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@d_rose: Damit wird man *so* auch nicht arbeiten, ich denke in diesem letzten Teil von Aufgabe a) ging es einfach darum diesen Zusammenhang und die Verkettung und das durchgreifen können über die einzelnen Objekte zu erkennen. Für die Vergleichsmethode in b) muss man dass dann dynamischer/allgemeiner lösen. Und für das Anhängen in c) auch. Ich würde übrigens eventuell erst c) empfehlen, weil das ein kleines bisschen simpler umzusetzen ist als b). Denn da muss man sich erst einmal nur mit *einer* Liste beschäftigen, während beim Vergleich ja *zwei* beteiligt sind.
Meine nicht-repräsentative Python-Lösung erweitert um den Durchgriff auf das dritte Element und schon im Vorgriff auf den Vergleich das `next`-Attribut vom Vergleich per `attrs`-genrierten Vergleichsmethoden zwischen `LinkedList`-Objekten ausgeschlossen:
Meine nicht-repräsentative Python-Lösung erweitert um den Durchgriff auf das dritte Element und schon im Vorgriff auf den Vergleich das `next`-Attribut vom Vergleich per `attrs`-genrierten Vergleichsmethoden zwischen `LinkedList`-Objekten ausgeschlossen:
Code: Alles auswählen
#!/usr/bin/env python3
from attr import attrib, attrs
@attrs
class LinkedList:
value = attrib()
next = attrib(default=None, cmp=False)
def main():
list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
print('list_a', list_a)
print('list_a third value', list_a.next.next.value)
if __name__ == '__main__':
main()
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
@__blackjack__:
Ich sehe da noch ein wenig Verbesserungspotential.
Meine Lösung in Haskell:
Code: Alles auswählen
In [1]: from attr import attrib, attrs
In [2]: @attrs
...: class LinkedList:
...: value = attrib()
...: next = attrib(default=None, cmp=False)
...:
In [3]: LinkedList(5, LinkedList("ab", LinkedList(0.36))) == LinkedList(5, LinkedList("foo"))
Out[3]: True
Meine Lösung in Haskell:
Code: Alles auswählen
data List a = Cons a (List a) | Nil
instance Eq a => Eq (List a) where
Cons a as == Cons b bs = a == b && as == bs
Nil == Nil = True
_ == _ = False
main :: IO ()
main = print $ Cons 42 (Cons 27 Nil) == Cons 42 (Cons 5 Nil) -- ⇒ False
- __blackjack__
- User
- Beiträge: 13111
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@narpfel: Ich weiss jetzt nicht was Du damit sagen willst? ``==`` vegleicht ja nicht die ganze Liste sondern nur einen Knoten. Das halt nur anhand des Wertes und das soll und muss auch so. Das `next` (`nachfolger`) von dem Vergleich ausgenommen ist, braucht man dann in der `equals()`-Methode (`gleich()`) die laut Aufgabenstellung implementiert werden soll. Die habe ich noch nicht gezeigt, weil das ja noch eine offene Aufgabe für d_rose ist. Also man braucht es nicht zwingend, aber es macht den Code einfacher wenn man in der `equals()` einfach ``==`` auf den Knoten verwenden kann ohne prüfen zu müssen ob der Knoten eventuell `None` ist, weil man *da* ja nicht auf das `value`/`eintrag`-Attribut zugreifen kann.
Edit: Obwohl die Lösung ja sowieso nicht so einfach 1:1 übernommen werden kann, also hier ist die `equals()` für die ich die Änderung an den Vergleichen gemacht hatte:
Ohne könnte man die einzelnen Knoten nicht einfach mit ``a == b`` vergleichen, sondern müsste dort explizit `a` und `b` gegen `None` prüfen bevor man deren `value`-Attribute vergleicht.
Edit2: Alternativ, wenn man tatsächlich den ``==``-Operator überschreiben wollte, müsste es so aussehen:
Edit: Obwohl die Lösung ja sowieso nicht so einfach 1:1 übernommen werden kann, also hier ist die `equals()` für die ich die Änderung an den Vergleichen gemacht hatte:
Code: Alles auswählen
from itertools import takewhile, zip_longest
from operator import attrgetter
from attr import attrib, attrs
from more_itertools import iterate
@attrs
class LinkedList:
value = attrib()
next = attrib(default=None, cmp=False)
def __iter__(self):
return takewhile(bool, iterate(attrgetter('next'), self))
def equals(self, other):
return all(a == b for a, b in zip_longest(self, other))
Edit2: Alternativ, wenn man tatsächlich den ``==``-Operator überschreiben wollte, müsste es so aussehen:
Code: Alles auswählen
@attrs
class LinkedList:
value = attrib()
next = attrib(default=None)
def __iter__(self):
return takewhile(bool, iterate(attrgetter('next'), self))
def __eq__(self, other):
return all(
a and b and a.value == b.value for a, b in zip_longest(self, other)
)
def __ne__(self, other):
return not self == other
def __hash__(self):
raise TypeError(f'unhashable type: {self.__class__.__name__!r}')
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
- __blackjack__
- User
- Beiträge: 13111
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
Mal der gesamte Code den ich hier habe, allerdings wie bisher halt auch schon mit zusätzlichen Bibliotheken, damit ich nicht alles selbst implementieren muss:
An dem auskommentierten Codeschnippsel am Ende der `main()`-Funktion sieht man was an dieser Darstellung der verketteten Liste unschön ist, und warum man die Knoten-Objekte in der Regel noch einmal in einer weiteren Klasse kapselt: Man kann nicht so einfach mit einer *leeren* Liste starten, die ja eigentlich als `None` definiert ist durch die Aufgabe, und dann von da ausgehend Elemente anhängen. Man kann das natürlich auch mit dieser einen, der Knoten-Klasse, lösen. Dazu müsste man als Wert einen speziellen Wert einführen, der einen ”leeren” Knoten repräsentiert und auf den entsprechend in den Methoden getestet wird.
Code: Alles auswählen
#!/usr/bin/env python3
from itertools import takewhile, zip_longest
from operator import attrgetter
from attr import attrib, attrs
from more_itertools import iterate, last
@attrs(cmp=False)
class LinkedList:
value = attrib()
next = attrib(default=None)
def __iter__(self):
return takewhile(bool, iterate(attrgetter('next'), self))
def __eq__(self, other):
return all(
a and b and a.value == b.value for a, b in zip_longest(self, other)
)
def __ne__(self, other):
return not self == other
def __hash__(self):
raise TypeError(f'unhashable type: {self.__class__.__name__!r}')
def append(self, value):
last(self).next = LinkedList(value)
def main():
list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
print('list_a', list_a)
print('list_a third value', list_a.next.next.value)
list_b = LinkedList(1, LinkedList(2))
print('list_b', list_b)
list_c = LinkedList(1, LinkedList(2, LinkedList(3)))
print('list_c', list_c)
print('list_b equals list_c', list_b == list_c)
print('append 3 to list_b')
list_b.append(3)
print('list_b', list_b)
print('list_b equals list_c', list_b == list_c)
# list_d = LinkedList()
# print('list_d', list_d)
# list_d.append(42)
# list_d.append(23)
# print('list_d', list_d)
if __name__ == '__main__':
main()
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
- __blackjack__
- User
- Beiträge: 13111
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
Eigentlich möchte man ja über die Werte iterieren und nicht über die Knoten, damit sich das ein bisschen mehr wie normale Listen verhält. Aus dem gleichen Grund gibt's jetzt noch eine `__getitem__()`-Methode, damit man an das dritte Element auch über ``list_a[2]`` heran kommt.
Code: Alles auswählen
#!/usr/bin/env python3
from itertools import takewhile, zip_longest
from operator import attrgetter
from attr import attrib, attrs
from more_itertools import iterate, last, nth
@attrs(cmp=False)
class LinkedList:
value = attrib()
next = attrib(default=None)
def __iter__(self):
return map(attrgetter('value'), self._iter_nodes())
def __getitem__(self, index):
node = nth(self._iter_nodes(), index)
if not node:
raise IndexError(f'index {index!r} out of range')
return node.value
def __eq__(self, other):
return all(
a and b and a.value == b.value
for a, b in zip_longest(self._iter_nodes(), other._iter_nodes())
)
def __ne__(self, other):
return not self == other
def __hash__(self):
raise TypeError(f'unhashable type: {self.__class__.__name__!r}')
def _iter_nodes(self):
return takewhile(bool, iterate(attrgetter('next'), self))
def append(self, value):
last(self._iter_nodes()).next = LinkedList(value)
def main():
list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
print('list_a', list_a)
print('list_a third value', list_a.next.next.value)
print('list_a[2]', list_a[2])
list_b = LinkedList(1, LinkedList(2))
print('list_b', list_b)
list_c = LinkedList(1, LinkedList(2, LinkedList(3)))
print('list_c', list_c)
print('list_b equals list_c', list_b == list_c)
print('append 3 to list_b')
list_b.append(3)
print('list_b', list_b)
print('list_b equals list_c', list_b == list_c)
# list_d = LinkedList()
# print('list_d', list_d)
# list_d.append(42)
# list_d.append(23)
# print('list_d', list_d)
if __name__ == '__main__':
main()
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman