Je suis actuellement en train de suivre un cours d'introduction à l'informatique en ligne et je viens d'apprendre le concept de liste chaînée. Bien que je comprenne le concept de listes liées, je ne sais toujours pas comment gérer les listes liées.
En tant que tel, je cherche de l'aide pour résoudre le problème suivant, ce qui sera d'une aide significative pour ma compréhension des listes liées:
Ecrire une fonction (pas dans la définition de classe LinkedList) qui donne un lien list, changera cette liste liée pour filtrer les nombres impairs. Immédiatement après le retour de la fonction, la liste chaînée n'aura que des nombres pairs.
Je ne sais pas comment accéder aux nœuds de la liste et vérifier s'ils sont impairs ou pairs et les supprimer ou les conserver en conséquence.
Je m'excuse si cela semble être une question triviale, mais j'apprécierais toute aide qui pourrait m'aider à apprendre.
Le code de la liste chaînée et des classes de nœuds (tel que fourni par le cours en ligne):
class Node:
def __init__(self, data=None, next_node=None):
self.data = data
self.next = next_node
def __str__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.length = 0
self.head = None
def print_list(self):
node = self.head
while node is not None:
print(node, end=' ')
node = node.next
print('')
def add_at_head(self, node):
node.next = self.head
self.head = node
self.length += 1
def remove_node_after(self, node):
if node.next is not None:
temp = node.next
node.next = node.next.next
temp.next = None
self.length -= 1
def remove_first_node(self):
if self.head is None:
return
temp = self.head
self.head = self.head.next
temp.next = None
self.length -= 1
def print_backward(self):
def print_nodes_backward(node):
if node.next is not None:
print_nodes_backward(node.next)
if node is not None:
print(node, end=' ')
if self.head is not None:
print_nodes_backward(self.head)
print('')
3 Réponses :
Disons que vous avez une liste chaînée simple et simple qui ressemble à ceci:
>>> lst = LinkedList() >>> lst.add(2) >>> lst.add(5) >>> lst.add(6) >>> lst.add(3) >>> lst.add(7) >>> lst.add(8) >>> lst.add(10) >>> lst.add(1) >>> lst.add(4) >>> print(lst) [2, 5, 6, 3, 7, 8, 10, 1, 4] >>> lst.remove_odds() >>> print(lst) [2, 6, 8, 10, 4]
En d'autres termes, la LinkedList contient une seule tête , qui est un ListNode . Chaque élément de la liste liée est contenu dans un ListNode , et chaque ListNode pointe vers l'élément suivant dans la liste.
Comme vous pouvez le voir, pour ajouter un élément à la liste, soit nous créons un nœud en tête si la liste est vide (ie self.head is None ), soit nous traversons jusqu'à la fin de la liste en sautant continuellement à l'élément .next pour chaque ListNode , en commençant par le head . Nous utilisons également ce paradigme pour imprimer une représentation sous forme de chaîne de notre liste.
Donc, pour supprimer n'importe quel nœud de la liste liée, nous pouvons simplement changer le nœud qui le référence, de sorte que le nœud que nous voulons supprimer est ignoré. À ce stade, il disparaîtra.
Pour supprimer tous les nœuds de liste contenant des données impaires, nous pourrions faire quelque chose comme ceci:
def remove_odds(self):
# special case: head node
# remove odd head elements by simply setting head to the next element after
while (self.head is not None) and (self.head.data % 2 == 1):
self.head = self.head.next
# regular case: the rest of the nodes
current_node = self.head
while (current_node is not None) and (current_node.next is not None):
# if the next node's data is odd, then
if current_node.next.data % 2 == 1:
# skip that node by pointing this node's .next to the next node's .next
current_node.next = current_node.next.next
# otherwise, move forwards in the list
else:
current_node = current_node.next
Preuve de concept :
class LinkedList:
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
def __init__(self):
self.head = None
def add(self, data):
if self.head is None:
self.head = LinkedList.ListNode(data)
else:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = LinkedList.ListNode(data)
def __str__(self):
ret = "["
current_node = self.head
while current_node is not None:
ret = ret + str(current_node.data)
if current_node.next is not None:
ret = ret + ", "
current_node = current_node.next
ret = ret + "]"
return ret
Merci pour cela, c'est ce que j'ai fait en premier, mais ce que l'exercice du cours en ligne recherche une fonction qui n'est pas dans la classe LinkedList (je ne suis pas sûr que ce soit l'expression correcte).
Je laisserai les informations sur la façon d'adapter ces informations comme un exercice pour vous. L'algorithme est ce qui est important - ce qui est certain, c'est que la structure de liste liée avec laquelle vous essayez d'interagir doit avoir des nœuds définis avec un champ .data et .next . Regardez la documentation et la description du projet qui vous ont été données et essayez de comprendre ce que c'est, puis adaptez cette solution pour l'utiliser.
Merci. Je crois que je l'ai compris.
Copié à partir du commentaire: L'idée est de parcourir la liste tête-bêche tout en se souvenant du nœud précédent ; lorsque vous trouvez un nœud d'ordures, appliquez remove_node_after au nœud mémorisé, ou déplacez la tête vers le nœud actuel si nous n'avons pas encore eu le temps de nous souvenir de quoi que ce soit.
Le code serait quelque chose comme ceci (non testé):
class LinkedList:
# ...
def delete_if(self, pred):
prev = None
curr = self.head
while curr:
if pred(curr.data):
if prev:
self.remove_node_after(prev)
else:
self.head = curr
prev = curr
curr = curr.next
llist.delete_if(lambda x: x % 2 == 1) # delete if odd
Merci pour cela, c'est ce que j'ai fait en premier, mais ce que l'exercice du cours en ligne recherche une fonction qui n'est pas dans la classe LinkedList (je ne suis pas sûr que ce soit l'expression correcte).
Il n'est pas nécessaire que ce soit une méthode (une fonction à l'intérieur d'une classe). La même fonction fonctionne même si elle n'est pas placée dans une classe, appelée delete_if (llist, lambda x: x% 2 == 1) (bien que vous souhaitiez peut-être renommer self à autre chose, comme llist , donc ce n'est pas déroutant pour les humains).
Je crois que je l'ai compris. Merci!
# Mahmoud AL-Mokdad
# this course on Udemy By SEfactoru rightðŸ˜
# use my code 😉
def filter_even(ll):
first_node = ll.head
while (first_node is not None) and (first_node.data % 2 != 0):
ll.remove_first_node()
first_node = ll.head
node = first_node
while node is not None and node.next is not None:
if node.next.data % 2 != 0:
ll.remove_node_after(node)
else:
node = node.next
Il n'est pas vraiment possible de répondre à cela sans savoir comment vous représentez vos listes chaînées. Vous devriez publier une partie de votre code indiquant où vous rencontrez des problèmes.
@MarkMeyer Le problème est que je ne sais pas comment procéder pour créer la fonction requise. Je sais que je dois vérifier si les éléments sont pairs ou impairs et supprimer les probabilités. Je sais comment faire cela avec des listes, mais pas des listes liées.
L'idée est de parcourir la liste tête-bêche tout en se souvenant du nœud précédent ; lorsque vous trouvez un nœud d'ordures, appliquez
remove_node_afterau nœud mémorisé, ou déplacez la tête vers le nœud actuel si nous n'avons pas encore eu le temps de nous souvenir de quoi que ce soit.@Amadan c'est exactement ce que j'essaie de faire, mon problème est que je ne sais pas comment parcourir la liste chaînée. Généralement, pour les listes / tableaux, j'utilise des boucles while / for, mais cela ne fonctionne pas pour les listes liées. Si je peux seulement comprendre comment faire cela, je suis sûr que je peux le résoudre.
J'aurais aimé que les
cours en lignene suggèrent pas de ne pas documenter correctement votre code, en fournissant docstrings au minimum.