Comment créer dynamiquement de nouveaux nœuds dans les listes chaînées en C++

Quelqu'un pourrait-il me dire si c'est l'idée de base de listes liées? Quels sont les avantages et les inconvénients de cette méthode et quelles sont les meilleures pratiques lors de la mise en œuvre de listes chaînées en C++? Im nouveau à des structures de données, de sorte que c'est ma première approche. Si il ya une meilleure façon de faire la même chose, s'il vous plaît laissez-moi savoir. En outre, comment voulez-vous créer les nœuds de manière dynamique, sans codage en dur elle? Merci. 

#include <iostream>
#include <string>

using namespace std;
struct node {
    int x;
    node *next;
};

int main()
{

    node *head;
    node *traverser;


    node *n = new node;                 //Create first node
    node *t = new node;                 //create second node

    head =n;                            //set head  node as the first node in out list.
    traverser = head;                   //we will first begin at the head node.

    n->x = 12;                          //set date  of first node.
    n->next = t;                        //Create a link to the next node

    t->x = 35;                          //define date  of second node.

    t->next = 0;                        //set pointer to null if this is the last node in the list.


    if ( traverser != 0 ) {                 //Makes sure there is a place to start
        while ( traverser->next != 0 ) {
            cout<< traverser->x;            //print out first data member
            traverser = traverser->next;    //move to next node
            cout<< traverser->x;            //print out second data member

        }
    }
    traverser->next = new node;  //Creates a node at the end of the list
    traverser = traverser->next; //Points to that node
    traverser->next = 0;         //Prevents it from going any further
    traverser->x = 42;
}
  • Depuis liés liste des opérations sont délicates à obtenir le droit, vous seriez beaucoup mieux, en les définissant comme réutilisable méthodes au sein de votre liste liée de classe, plutôt que d'essayer de faire les bonnes choses à faire manuellement à chaque fois que vous les utilisez. De cette façon, vous n'avez qu'à obtenir le fonctionnement correct une fois, plutôt que de dizaines/centaines de fois 🙂
  • La façon dont vous avez l'impression de la liste semble étrange. Pourquoi ne pas faire while (traverser->next) { cout << traverser->x; traverser = traverser->next; }?
  • A voté pour les fermer comme trop large. Cette demande d'un tutoriel ou d'un livre.
InformationsquelleAutor chancify | 2015-01-02
  1. 0

    Je préfère faire une liste chaînée de classe. Ceci élimine le besoin d'appeler le "nouveau" plus d'une fois. Une belle mise en œuvre avec des exemples peuvent être trouvés ici.

    • Je préfère utiliser std::list que de faire ma propre liste de classe. Le std::list classe fonctionne et a beaucoup, beaucoup d'heures de tests derrière elle.
    • Évidemment STL est le chemin à parcourir, mais si l'OP est en train d'essayer d'apprendre comment il fonctionne, c'est la façon de le faire.
    InformationsquelleAutor erip
  2. 0

    Vous sont en fait déjà de faire de l'allocation dynamique. Donc, vous ne savez pas ce que vous demandez. Mais si vous voulez définir des fonctions à ajouter de nouveaux nœuds à votre liste liée (ou supprimer un nœud, etc.), cela peut être une solution probable:

    L'emplacement des nœuds obtenir insérés ou supprimés dépend du type de structure de données. Dans une file d'attente, de nouveaux nœuds sont ajoutés à la fin; au sommet, dans le cas d'une pile. Une fonction qui ajoute un nœud vers le haut, en simulant la PILE opération push:

    void pushNode(node **head, int Value) {  
  node *newNode = new node;  
  newNode->x = Value;  
  newNode->next = *head;  
  *head = newNode;  
}

    Il serait appelé comme pushNode(&head, 15) où le "chef" serait défini comme node *head = NULL. La racine head doit d'abord être réglé sur NULL. Après cette opération head le nœud nouvellement ajouté (en haut de la pile).

    L'approche est très similaire pour les autres données-structures (viz. les files d'attente) et fonctionne très bien. Mais comme vous êtes à l'aide de C++, je vous propose de définir une classe pour votre liste liée et de définir ces fonctions en tant que méthodes. De cette façon, il sera plus commode et moins sujette aux erreurs.

    Même mieux utiliser std::list. C'est le standard chose, tellement portable et robuste qu'une implémentation personnalisée.

    InformationsquelleAutor B.Shankar
  3. 0

    pour le tutoriel, vous pouvez travailler sur cet exemple:

    #include <iostream>

using namespace std;

struct myList
{
    int info;
    myList* next;
};

int main()
{
    //Creation part
    myList *start, *ptr;
    char ch = 'y';
    int number;
    start = new myList;
    ptr = start;
    while (ptr != NULL)
    {
        cout << "Enter no. ";
        cin >> ptr->info;
        cout << "Continue (y/n)? ";
        cin >> ch;
        if (ch == 'y')
        {
            ptr->next = new myList;
            ptr = ptr->next;
        }
        else
        {
            ptr->next = NULL;
            ptr = NULL;
        }
    }

    //Traversal part begins
    cout << "Let's start the list traversal!\n\n";
    ptr = start;
    while (ptr!=NULL)
    {
        cout << ptr->info << '\n';
        ptr = ptr->next;
    }
}

    Il alloue de la mémoire dynamiquement pour autant d'éléments que vous souhaitez ajouter.

    InformationsquelleAutor technusm1