class Node:
def __init__(self, cargo=None, next=None):
self.__cargo = cargo
self.__next = next
def value(self):
return self.__cargo
def next(self):
return self.__next
def set_next(self, node):
self.__next = node
def __str__(self):
return str(self.value())
def print_list(self):
"""
Prints the cargo of this node and then recursively of each node connected to this one.
@pre: self is a node (possibly connected to a next node).
@post: Has printed a space-separated list of the form "a b c ... ",
where "a" is the string-representation of this node,
"b" is the string-representation of my next node, and so on.
A space is printed after each printed value.
"""
print(self, end=" ") # print my head
tail = self.__next # go to my next node
if tail is not None : # as long as the end of the list has not been reached
tail.print_list() # recursively print remainder of the list
def print_list_avec_virgule(self):
print(self, end=", ") # print my head
tail = self.__next # go to my next node
if tail.next() is not None : # as long as the end of the list has not been reached
tail.print_list_avec_virgule() # recursively print remainder of the list
else:
# case tail is the end <-> tail.next() is None
print(tail, end=" ") # last elem does not need a virgule
class LinkedList :
def __init__(self):
self.__length = 0
self.__head = None
def size(self):
return self.__length
def first(self):
return self.__head
def add(self, cargo):
node = Node(cargo,self.__head)
self.__head = node
self.__length += 1
def print(self):
"""
Prints the contents of this linked list and its nodes.
@pre: self is a (possibly empty) LinkedList
@post: Has printed a space-separated list of the form "[ a b c ... ]",
where "a", "b", "c", ... are the string representation of each
of the linked list's nodes.
A space is printed after and before the opening and closing bracket,
as well as between any two elements.
An empty linked is printed as "[ ]"
"""
print("[", end=" ")
if self.__head is not None:
self.__head.print_list()
print("]")
""" Solution attendue: récursive """
def print_avec_virgule(self):
print("[", end=" ")
if self.__head is not None:
self.__head.print_list_avec_virgule()
print("]")
""" Autre solution """
def print_avec_virgule2(self):
print("[", end=" ")
tmp = self.first()
if tmp is None:
print("]")
return
# Le dernier elem n'a pas de virgule
while tmp.next() is not None:
print(tmp.value(), end=", ")
tmp = tmp.next()
print(tmp.value(), end=" ]\n")
""" Autre solution """
def print_avec_virgule3(self):
tmp = self.first()
if tmp is None:
s = "[ ]"
else:
s = "[ "
while tmp.next() is not None:
s += str(tmp.value()) + ", "
tmp = tmp.next()
# Le dernier elem n'a pas de virgule
s += tmp.value() + "]\n"
print(s)
""" TO DO """
def print_avec_separateur(self,sep):
print("[", end=" ")
tmp = self.first()
if tmp is None:
print("]")
return
# Le dernier elem n'a pas de virgule
while tmp.next() is not None:
print(tmp.value(), end=sep)
tmp = tmp.next()
print(tmp.value(), end=" ]\n")
lst = LinkedList()
lst.add("pomme")
lst.add("ananas")
lst.add("prune")
lst.add("beer")
print("Sol 1 - Avec récursion")
lst.print_avec_virgule()
print("Sol 2 - Sans récursion")
lst.print_avec_virgule2()
print("Sol 3 - Généralisé")
lst.print_avec_separateur(" - ")
print("Sol 4 ?")
print(lst) # Comment changer ça ?
Sol 1 - Avec récursion
[ beer, prune, ananas, pomme ]
Sol 2 - Sans récursion
[ beer, prune, ananas, pomme ]
Sol 3 - Généralisé
[ beer - prune - ananas - pomme ]
Sol 4 ?
<__main__.LinkedList object at 0x7f671560ff50>
class LinkedList :
def __init__(self):
"""
Initialises a new linked list object.
@pre: -
@post: A new empty linked list object has been initialised.
It has 0 length, contains no nodes and the head points to None.
"""
self.__length = 0
self.__head = None
def size(self):
"""
Returns the number of nodes contained in this linked list.
@pre: -
@post: Returns the number of nodes (possibly zero) contained in this linked list.
"""
return self.__length
def first(self):
return self.__head
def add(self, cargo):
"""
Adds a new Node with given cargo to the front of this linked list.
@pre: self is a (possibly empty) LinkedList
@post: A new Node object is created with the given cargo.
This new Node is added to the front of the linked list.
The length counter has been incremented.
The head of the list now points to this new node.
"""
node = Node(cargo,self.__head)
self.__head = node
self.__length += 1
# ==== TO DO =====
def insert(self,s):
"""
- @pre s est un string à insérer dans la liste chainée; self est une liste chaînée dont les noeuds contiennent des strings; les noeuds de la liste sont ordonnées en ordre croissant selon les valeurs (strings) qu'ils contiennent.
- @post Un noeud contenant le String s a été inséré dans la liste de façon à ce qu'après l'insertion celle-ci soit toujours en ordre croissant.
"""
# ===> CAS 1: LISTE VIDE
if self.size() == 0:
self.add(s)
# ===> CAS 2: AJOUT EN PREMIER
elif s < self.first().value():
self.add(s)
# ===> CAS 3: PARCOURS
else:
# Ne pas oublier d'incrémenter la taille de la liste
self.__length += 1
# Initialisation du parcours
curr = self.first()
# ===> CAS 3A: AJOUT MILIEU
while (curr.next() is not None):
if s > curr.next().value():
# On insère entre curr et curr.next
new_node = Node(s,curr.next())
curr.set_next(new_node)
return # Necessaire
# suite du parcours
curr = curr.next()
# ===> CAS 3B: AJOUT FIN (on sort du while)
new_node = Node(s,None)
curr.set_next(new_node)
def __str__(self):
tmp = self.first()
if tmp is None:
return "[ ]"
else:
s = "[ "
while tmp is not None:
s += str(tmp.value()) + " "
tmp = tmp.next()
s += "]"
return s
class Node:
def __init__(self, cargo=None, next=None):
"""
Initialises a new Node object.
@pre: -
@post: A new Node object has been initialised.
A node can contain a cargo and a reference to another node.
If none of these are given, a node with empty cargo (None) and no reference (None) is created.
"""
self.__cargo = cargo
self.__next = next
def value(self):
"""
Returns the value of the cargo contained in this node.
@pre: -
@post: Returns the value of the cargo contained in this node, or None if no cargo was put there.
"""
return self.__cargo
def next(self):
return self.__next
def set_next(self, node):
self.__next = node
def __str__(self):
"""
Returns a string representation of the cargo of this node.
@pre: self is possibly empty Node object.
@post: returns a print representation of the cargo contained in this Node.
"""
return str(self.value())
# CASE EMPTY
l1 = LinkedList()
print("Liste:", l1, ", size :", l1.size())
# NON-EMPTY
l2 = LinkedList()
l2.add("abc"), l2.add("def"), l2.add("xyz")
print("Liste:", l2, ", size :", l2.size())
# CASE FRONT
l2.insert("aaa")
# CASE MIDDLE
l2.insert("ghi")
l2.insert("def")
# CASE END
l2.insert("zzz")
print("Liste: ", l2, ", size :", l2.size())
Liste: [ ] , size : 0
Liste: [ xyz def abc ] , size : 3
Liste: [ aaa zzz xyz ghi def def abc ] , size : 7
class CircularLinkedList :
class Node:
def __init__(self,cargo=None,next=None):
""" Initialises a new Node object. """
self.__cargo = cargo
self.__next = next
def __str__(self):
return self.__cargo
def value(self):
""" Returns the value of the cargo contained in this node. """
return self.__cargo
def next(self):
""" Returns the next node to which this node links. """
return self.__next
def set_next(self,node):
""" Sets the next node to which this node links to a new node. """
self.__next = node
def __init__(self):
""" Initialises a new empty circular linked list.
@pre: -
@post: A new circular linked list with no nodes has been initialised.
The first pointer refers to None.
"""
self.__first = None # pointer to the first node
self.__last = None # pointer to the last node
def first(self):
""" Returns the first node of this circular linked list.
@pre: -
@post: Returns a reference to the first node of this circular linked list,
or None if the circular linked list contains no nodes.
"""
return self.__first
def last(self):
""" Returns the last node of this circular linked list.
@pre: -
@post: Returns a reference to the last node of this circular linked list,
or None if the circular linked list contains no nodes.
"""
return self.__last
def add(self, cargo):
""" Adds new Node with given cargo to front of this circular linked list.
@pre: self is a (possibly empty) CircularLinkedList.
@post: A new Node object is created with the given cargo.
This new Node is added to the front of the circular linked list.
The head of the list now points to this new node.
The last node now points to this new node.
"""
node = self.Node(cargo,self.first())
self.__first = node
if self.last() == None : # when this was the first element being added,
self.__last = node # set the last pointer to this new node
self.last().set_next(node)
def __str__(self):
return "First: {}, Last: {}".format(self.first(),self.last())
def remove(self,cargo):
""" Removes a node with given cargo from the circular linked list.
@pre: -
@post: A node with given cargo was removed from the circular linked list.
The removed node, with next pointer set to None, is returned.
In case multiple nodes with this cargo exist, only one is removed.
The list is unchanged if no such node exists or the list is empty.
In that case, None is returned as result.
"""
# == CAS LIMITE 1: liste vide ==
if self.first() is None:
return None
# == CAS LIMITE 2: liste avec 1 seul élément ==
elif self.first() is self.last():
if self.first().value() == cargo:
self.__first = None
self.__last = None
return Node(cargo,None)
# not found
return None
# == CAS LIMITE 3: on veut retirer first() ==
elif self.first().value() == cargo:
self.__first = self.__first.next()
self.__last.set_next(self.first())
return Node(cargo,None)
# == CAS GENERAL: liste avec plusieurs éléments ==
else:
curr = self.first()
while curr.next() is not self.first(): # Autrement dit, tant que curr n'est pas last
if curr.next().value() == cargo:
# === CAS LIMITE 4: dernier élément
if curr.next() is self.last():
self.__last = curr
self.__last.set_next(self.first())
return Node(cargo,None)
# === CAS GENERAL: pas le dernier élém ===
curr.set_next(curr.next().next())
return Node(cargo,None)
curr = curr.next()
return None
def removeAll(self,s):
""" Removes all nodes with given cargo. """
b = self.remove(s)
while b is not None:
b = self.remove(s)
class TourDeRole :
@classmethod
def main(cls):
l = CircularLinkedList()
l.add("Charles")
l.add("Kim")
l.add("Siegfried")
l.add("Sébastien")
l.add("Charles")
l.add("Siegfried")
print(l)
l.remove("Kim")
print(l)
l.remove("Charles")
print(l)
l.remove("Charles")
print(l)
l.removeAll("Siegfried")
print(l)
l.remove("Sébastien")
print(l)
TourDeRole.main()
First: Siegfried, Last: Charles
First: Siegfried, Last: Charles
First: Siegfried, Last: Charles
First: Siegfried, Last: Siegfried
First: Sébastien, Last: Sébastien
First: None, Last: None