CP Python - TUTEUR - S13: Linked Lists

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 ?

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())

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()