Pointeur vers pointeur dans la liste liée
Quelqu'un peut-il m'expliquer pourquoi ce code me donne comme résultat la liste vide:
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
Mais si je change la fonction begin () avec le pointeur vers le pointeur, cela me donne la bonne liste?
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
Pouvez-vous aussi m'expliquer pourquoi lorsque je passe dans le principal le nœud head à la fonction begin, je dois le passer comme "& head"? et pas plus comme "tête"
Réponses
Dans le premier programme de cet extrait de code
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
le pointeur headest passé à la fonction beginpar valeur. C'est-à-dire qu'une copie de la valeur du pointeur headdéclaré dans main est créée et attribuée au paramètre avec le même nom de la fonction begin
void begin(node *head);
Ainsi, dans la fonction, c'est le paramètre headqui contient initialement une copie du pointeur d'origine headqui est modifié. Le pointeur d'origine dont headla valeur a été affectée au paramètre n'est pas modifié.
Pour changer la tête du pointeur d'origine déclarée dans main, vous devez la passer à la fonction par référence indirectement via un pointeur vers la tête du pointeur comme cela est fait dans le deuxième programme.
La fonction doit donc être déclarée comme
void begin(node **head);
Et vous devez passer la tête du pointeur indirectement à travers un pointeur vers elle
begin( &head );
Dans ce cas, en déréférençant le pointeur passé, la fonction obtiendra un accès direct à la tête du pointeur d'origine déclarée dans main et pourra la modifier (pas une copie de sa valeur telle qu'elle a lieu dans la première définition de fonction)
new->next = *head;
*head = new;
Pour le rendre plus clair, considérez ce programme démonstratif simple.
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
Sa sortie est
Before calling f t is equal to 0
After calling f t is equal to 0
Comme la fonction f traite une copie de la valeur de l'argument passé, la valeur de la variable tdéclarée dans main n'a pas été modifiée.
Vous devez donc passer la variable d'origine tpar référence via un pointeur comme
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
Maintenant, la sortie du programme est
Before calling f t is equal to 0
After calling f t is equal to 10
Dans ces programmes de démonstration, le nom Test utilisé comme alias pour le type intet en général l'objet ta ce type.
Supposons maintenant que le nom T est un alias pour le type int *.
typedef int * T;
Dans ce cas une déclaration en main comme par exemple
T t = NULL;
signifie que la variable ta le type pointeur int *. C'est cela équivaut à
int * t = NULL;
Donc, pour le passer à une fonction qui doit changer la variable d'origine t, nous devons le passer par référence comme
f( &t );
cela signifie que la fonction correspondante doit avoir le type de paramètre déclaré comme
void f( T *t );
mais comme Tc'est un alias, int *cela signifie que la fonction a un paramètre du type int **.
void f( int * *t );
Parce que headc'est (effectivement) une variable locale, la changer n'a aucun effet en dehors de la fonction, alors que changer *headchange ce qui headpointe vers, et donc le fait.
Si vous vouliez qu'une fonction puisse changer la valeur d'une intvariable (par exemple, x), vous lui passeriez un pointeur vers x, qui aurait le type int*et vous obtiendrez le pointeur xen utilisant &x. La même chose vaut quel que soit le type x.
Un peu de confusion peut provenir de la déclaration
node *head;
au lieu de
node* head;
Vous déclarez head. headest la variable et c'est un pointeur. Ce n'est pas un nœud. Notez également qu'un nœud n'est pas une liste chaînée: une liste chaînée est une collection de nœuds et éventuellement quelque chose d'autre afin d'avoir une implémentation utile. Plus d'informations à ce sujet plus tard à la fin.
Le fait est que vous avez main()déclaré head, juste un fichier node*. Le nœud lui-même n'existe même pas encore. Vous avez déclaré begin()comme
void begin(node *head);
et je pense que vous le verrez plus clairement
void begin(node* parameter);
parameterest node*.
À l'intérieur, begin()vous obtenez une copie du pointeur et la modification du pointeur ne modifiera pas le pointeur d'origine main(). Dans votre cas, il sera main()toujours indiqué NULL.
Ce qui compte, c'est qu'un pointeur est comme n'importe quelle variable: un pointeur a une adresse. Et un contenu. Lorsque vous passez par valeur, comme vous l'avez fait, le pointeur begin()commence par NULL, la valeur qui provient main(). Mais le lien entre eux se termine dans l'appel: la valeur initiale.
Lorsque vous passez un pointeur vers begin(), en utilisant l'opérateur 'adresse de' et en écrivant les &headchoses changent: vous le changerez en utilisant l'opérateur, '*'ce qui signifie que vous changerez l'adresse vers laquelle il pointe, donc il changera main(). Depuis headest node*un pointeur vers celui-ci sera déclaré commenode**
Mais pensez à changer la déclaration de begin()pour une liste chaînée en utilisant:
node* begin(node* node);
La logique est que l'insertion d'un nœud peut changer la tête de la liste, vous renvoyez donc la nouvelle adresse, comme dans
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
est une manière courante d'écrire ceci. Un autre est à utiliser node**.
La façon dont je décris ici, toute opération qui peut changer la tête de la liste doit
- retourner la nouvelle tête
- recevoir et mettre à jour un pointeur vers le pointeur de la tête
Revoyez ce code qui s'insère au début de la liste:
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
retour newvous obtenez headmis à jour. Et vous pouvez écriremain()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
Notez la ligne another = _insert_begin(i, another);et vous voyez comment le pointeur main()est mis à jour.
C'est la sortie
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
En utilisant cette implémentation de display_list(), qui imprime 5 valeurs par ligne:
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
Autre exemple: insertion à la fin
notez que l'insertion à la fin peut également changer la tête, dans le cas où la liste est vide, il faut donc toujours renvoyer l'adresse de la tête
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
Autre utilisation: insérer dans l'ordre croissant
Bien sûr, l'insertion dans l'ordre croissant peut également changer la tête, comme dans
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
Supprimer une liste
Supprimer une liste doit également renvoyer un node*pour invalider le pointeur de tête. C'est habituel. Au fur et à mesure que vous vous habituez à la mécanique, cela garantit qu'un pointeur invalide ne reste pas.
Notez que cette logique est coopérative: vous devez renvoyer le pointeur de tête à chaque appel pouvant changer la tête
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
Un programme en cours
Sortie du programme d'exemple
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
L'exemple de programme C
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
Une structure de liste liée sans doute plus utile
Considérer ce qui suit
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
De cette façon, une liste liée est définie comme un conteneur de nœuds.
- Il a même une option
name. sizeest toujours disponible et à jour- une limite de taille peut être implémentée comme
capacity - insérer à la fin et au début ne vous oblige pas à suivre tous les autres nœuds, car la liste encapsule des pointeurs vers la tête et la queue
- un nœud a des pointeurs vers les nœuds suivants ET précédents afin que certaines données telles que des listes de lecture ou des collections de ce type puissent être itérées plus facilement.
- un programme peut avoir n'importe quel nombre de listes puisque chacune encapsule toutes ces métadonnées.
- une liste peut contenir n'importe quoi puisque les données sont un pointeur vers void,
void* - des fonctions comme empty () ou size () peuvent être implémentées facilement
- toutes les fonctions utilisent un pointeur vers la liste
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
En ce qui concerne:
void begin(node *head){
Changer headseulement change la pile d'appels 'head', ce qui est nécessaire est de changer où 'head' dans la fonction de l'appelant pointe. Pour ce faire, l'appelant doit passer l'adresse de «tête». Le fait que `` tête '' soit en soi un pointeur n'aide pas à clarifier ce qui doit être fait,