C++ liste liée

Question

Je suis en train de faire liste chaînée similaire aussi celui ici:

linked list in C

est d'avoir la « tête », je l'ai appelé d'abord, dans un autre struct. Cependant j'ai trouvé faire ce changement. Il est difficile d'ajouter des valeurs à la structure list_item. J'ai essayé quelques trucs pour voir si ça marche. Il compile, mais quand je cours le code, il va planter. Toute aide serait utile ici. Je sais que la cause du crash est quand je veux pointer le new_node vers la liste liée.

#include <iostream> 

using namespace std; 

struct list_item 
{ 
    int key; 
    int value; 
    list_item *next; 
}; 

struct list 
{ 
    struct list_item *first; 
}; 

int main() 
{ 
    list *head; 
    list *new_node; 

    head = NULL; 
    head->first = NULL; 

    for(int i = 0; i < 10; i++) 
    { 
     //allocate memory for new_node 
     new_node = (list*)malloc(sizeof(list)); 
     new_node->first = (list_item*)malloc(sizeof(list_item)); 
     //adding the values 
     new_node->first->key = i; 
     new_node->first->value = 10 + i; 

     //point new_node to first; 
     new_node->first->next = head->first; 

     //point first to new_node; 
     head->first = new_node->first; 

    } 

    //print 
    list *travel; 
    travel->first = head->first; 

    int i = 0; 
    while(travel != NULL) 
    { 
     cout << travel->first->value << endl; 
     travel->first = travel->first->next; 
    } 

    return 0; 
} 

Answer 1

Vous créez 10 listes, je pense que vous pourriez essayer de faire quelque chose comme ceci:

#include <iostream> 

using namespace std; 

struct list_item 
{ 
    int key; 
    int value; 
    list_item *next; 
}; 

struct list 
{ 
    struct list_item *first; 
}; 

int main() 
{ 
    //Just one head is needed, you can also create this 
    // on the stack just write: 
    //list head; 
    //head.first = NULL; 
    list *head = (list*)malloc(sizeof(list)); 
    list_item *new_node = NULL; 

    head->first = NULL; 

    for(int i = 0; i < 10; i++) 
    { 
     //allocate memory for new_node 
     new_node = (list_item*)malloc(sizeof(list_item)); 
     //adding the values 
     new_node->key = i; 
     new_node->value = 10 + i; 

     //if the list is empty, the element you are inserting 
     //doesn't have a next element 

     new_node->next = head->first; 

     //point first to new_node. This will result in a LIFO 
     //(Last in First out) behaviour. You can see that when you 
     //compile 
     head->first = new_node; 

    } 

    //print the list 
    list_item *travel; 
    travel = head->first; 

    while(travel != NULL) 
    { 
     cout << travel->value << endl; 
     travel = travel->next; 
    } 

    //here it doesn't matter, but in general you should also make 
    //sure to free the elements 
    return 0; 
} 

C'est ce qui se passe. Au début, vous n'avez qu'une tête et aucun élément.

head 
    | 
    | 
    V 
NULL 

Ensuite, vous ajoutez votre premier élément. Assurez-vous que le « new_node-> suivant == NULL »:

head 
    | 
    | 
    V 
node: ------------------> NULL 
key = 0 
value = 10 

Ensuite, vous ajoutez un autre nœud avant, mais votre append premier nœud à son nœud suivant. vous déplacez le pointeur de la tête vers le nouveau nœud

head: 
first 
    | 
    | 
    V 
node: ---------> node: -------------> NULL 
key: 1    key: 0 
value: 11   value: 10 

etc.

Puisque vous utilisez C++, vous pouvez envisager d'utiliser « nouveau » et « supprimer ». Il suffit de remplacer

new_node = (list_item*)malloc(sizeof(list_item)); 

avec

list *head = new list 

Answer 2

La ligne suivante alloue uniquement de la mémoire pour votre structure list. La liste contient uniquement un pointeur, vous devez également allouer de la mémoire pour new_node->first avant d'affecter à l'un de ses membres.

//allocate memory for new_node 
new_node = (list*)malloc(sizeof(list)); 

Answer 3

Je pense que vous voulez faire quelque chose comme:

#include <iostream> 
#include <cstdlib> 

using namespace std; 

typedef struct tag_list_item 
{ 
    int key; 
    int value; 
    struct tag_list_item *next; 
} list_item; 

typedef struct 
{ 
    list_item *head; 
} list; 

int main() 
{ 
    list my_list; 
    list_item *new_node; 
    list_item *previous_node = NULL; 

    my_list.head = NULL; 

    for(int i = 0; i < 10; i++) 
    { 
     //allocate memory for new_node 
     new_node = (list_item*)malloc(sizeof(list_item)); 

     //adding the values 
     new_node->key = i; 
     new_node->value = 10 + i; 

     if(previous_node == NULL) 
     { 
      my_list.head = new_node; 
     } 
     else 
     { 
      previous_node->next = new_node; 
     } 
     previous_node = new_node;  
    } 

    //print 
    list_item *iter = my_list.head; 

    while(iter != NULL) 
    { 
     cout << iter->value << endl; 
     iter = iter->next; 
    } 

    return 0; 
} 

changements de note:

Pour malloc, j'ai ajouté:

#include <cstdlib> 

j'ai changé vos structures de liste à typedefs, a dû déclarer "next" en utilisant le tag puisque le typedef n'est pas complet à ce momentJ'ai changé le nom de votre liste en "my_list" et je l'ai déclaré directement (sans le pointeur). Dans ce cas, vous pouvez simplement demander au compilateur de l'allouer automatiquement sur la pile.

list my_list; 

Je garde un pointeur pour « previous_node » de sorte que vous pouvez attribuer le pointeur « suivant » beaucoup plus facilement. Notez que le premier noeud alloué est pointé par le pointeur "head" dans la structure de la liste. Je crois que c'est le nom traditionnel du pointeur vers le premier élément d'une liste.

if(previous_node == NULL) 
{ 
    my_list.head = new_node; 
} 
else 
{ 
    previous_node->next = new_node; 
} 
previous_node = new_node; 

Answer 4

head = NULL; 
head->first = NULL; 

Il y a la question. Vous ne pouvez pas suivre un pointeur et le définir sur NULL si vous avez défini le pointeur sur NULL.

Ce devrait être

head = malloc(sizeof(list)); 
head->first = NULL; 

Cela devrait corriger votre code.

Espoir qui aide, Billy3

EDIT: Il y a aussi un problème avec votre boucle FOR. Lorsque vous allouez la liste, vous ne devez allouer qu'une seule fois la liste elle-même. Lorsque vous insérez un élément, vous n'attribuez qu'un élément list_item.Vous attribuer un pointeur de liste à un membre qui accepte un pointeur list_item;)

Voir le poste de Gabe pour une démonstration de comportement correct :)

Answer 5

Regardez votre déclaration struct

 
struct list_item 
{ 
    int key; 
    int value; 
    list_item *next; 
}; 

Cela devrait être

 
struct list_item 
{ 
    int key; 
    int value; 
    struct list_item *next; 
}; 

Hope this helps, Meilleures salutations, Tom