J'étudie des structures de données et des listes liées, mais je ne comprends pas comment effectuer une copie d'une liste liée. Quelqu'un peut-il expliquer cela, éventuellement utiliser pseudocode ou code C?
3 Réponses :
Comprenez-vous comment ajouter un nouveau noeud à une liste existante? Et comprenez-vous comment traverser (c'est-à-dire itérair) une liste? Copier une liste vient d'effectuer simultanément ces deux opérations (Traverse Lista; pour chaque élément, copiez l'élément et ajoutez-le sous la forme d'un nouveau nœud à la liste).
La logique pour la duplication d'une liste liée est récursive et basée sur les observations suivantes:
Si vous encodez la liste liée en C ++, cela peut être très propre:
La réponse à ce post a été donnée et acceptée - tout bon!
Toutefois, si quelqu'un recherche une approche itérative dans la classe de nœud: strong> p> Voici la mise en œuvre itérative: p> complexité de temps: o (n) strong> p> complexité spatiale: où n = nombre de nœuds dans la liste liée. P> Sa préférence personnelle à utiliser une approche récursive ou itérative, mais je suggérerais de penser à penser À propos de la pile d'appels de fonction lors de l'utilisation de récursif. P> Test de l'unité: strong> p> [Test]
public void CopyLinkedListIterativelyTest()
{
Node head = new Node(1);
head.Next = new Node(2);
head.Next.Next = new Node(3);
head.Next.Next.Next = new Node(4);
head.Next.Next.Next.Next = new Node(5);
var actual = runner.CopyLinkedListIteratively(head);
while (actual != null)
{
Assert.AreEqual(head.Val, actual.Val);
actual = actual.Next;
head = head.Next;
}
}