Puntero al puntero en la lista vinculada
¿Alguien puede explicarme por qué este código me da como resultado la lista vacía?
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;
}
Pero si cambio la función begin () con el puntero a puntero, ¿me da la lista correcta?
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;
}
¿Puede también explicarme por qué cuando paso en el main el nodo principal a la función begin, tengo que pasarlo como "& head"? y no mas como "cabeza"
Respuestas
En el primer programa de este fragmento de código
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
el puntero headse pasa a la función beginpor valor. Es decir, headse crea una copia del valor del puntero declarado en main y se asigna al parámetro con el mismo nombre de la función begin
void begin(node *head);
Entonces, dentro de la función, es el parámetro headque contiene inicialmente una copia del puntero original headque se cambia. El puntero original headcuyo valor se asignó al parámetro no se modificará.
Para cambiar la cabeza del puntero original declarada en main hay que pasarla a la función por referencia indirectamente a través de un puntero a la cabeza del puntero como se hace en el segundo programa.
Entonces la función debe declararse como
void begin(node **head);
Y tienes que pasar la cabeza del puntero indirectamente a través de un puntero.
begin( &head );
En este caso, al eliminar la referencia al puntero pasado, la función obtendrá un acceso directo al cabezal del puntero original declarado en main y podrá cambiarlo (no una copia de su valor, ya que tiene lugar en la primera definición de función)
new->next = *head;
*head = new;
Para hacerlo más claro, considere este sencillo programa demostrativo.
#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;
}
Su salida es
Before calling f t is equal to 0
After calling f t is equal to 0
Como la función f trata con una copia del valor del argumento pasado, el valor de la variable tdeclarada en main no se modificó.
Por lo tanto, debe pasar la variable original tpor referencia a través de un puntero como
#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;
}
Ahora la salida del programa es
Before calling f t is equal to 0
After calling f t is equal to 10
En estos programas demostrativos, el nombre Tse usa como un alias para el tipo inty, en general, el objeto ttiene este tipo.
Supongamos ahora que el nombre T es un alias para el tipo int *.
typedef int * T;
En este caso una declaración en main como por ejemplo
T t = NULL;
significa que la variable ttiene el tipo de puntero int *. Eso es equivalente a
int * t = NULL;
Entonces, para pasarlo a una función que debe cambiar la variable original t, necesitamos pasarlo por referencia como
f( &t );
eso significa que la función correspondiente tendrá el tipo de parámetro declarado como
void f( T *t );
pero como Tes un alias para, int *por lo tanto, significa que la función tiene un parámetro del tipo int **.
void f( int * *t );
Porque heades (efectivamente) una variable local, por lo que cambiarla no tiene ningún efecto fuera de la función, mientras que cambiar *headcambia lo que headapunta y, por lo tanto, lo hace.
Si quisiera que una función pueda cambiar el valor en una intvariable (digamos, x), le pasaría un puntero a x, que tendría el tipo int*y obtendría el puntero xusando &x. Lo mismo se aplica sin importar el tipo x.
Un poco de confusión puede provenir de declarar
node *head;
en vez de
node* head;
Estás declarando head. heades la variable y es un puntero. No es un nodo. Tenga en cuenta también que un nodo no es una lista vinculada: una lista vinculada es una colección de nodos y posiblemente algo más para tener una implementación útil. Más sobre esto más adelante al final.
El hecho es que ha main()declarado head, solo un node*. El nodo en sí ni siquiera existe todavía. Declaraste begin()como
void begin(node *head);
y creo que lo verás más claramente como
void begin(node* parameter);
parameteres node*.
En begin()su interior , obtiene una copia del puntero y cambiar el puntero no cambiará el puntero original en main(). En su caso, main()siempre apuntará a NULL.
Lo que importa es que un puntero es como cualquier variable: un puntero tiene una dirección. Y un contenido. Cuando pasa por valor, tal como lo hizo, el puntero en begin()comienza con NULLel VALOR del que proviene main(). Pero el vínculo entre ellos termina en la llamada: el valor inicial.
Cuando pasa un puntero a begin(), usando el operador 'dirección de' y escribiendo, las &headcosas cambian: lo cambiará usando el operador, '*'lo que significa que cambiará la dirección a la que apunta, por lo que cambiará main(). Dado que heades node*un puntero, se declarará comonode**
Pero considere cambiar la declaración de begin()para una lista vinculada usando:
node* begin(node* node);
La lógica es que la inserción de un nodo puede cambiar el encabezado de la lista, por lo que devuelve la nueva dirección, como en
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
es una forma común de escribir esto. Otro es usar node**.
De la manera que estoy describiendo aquí, cualquier operación que pueda cambiar el encabezado de la lista debe
- devuelve la nueva cabeza
- recibir y actualizar un puntero al puntero de la cabeza
Vea nuevamente este código que inserta al principio de la lista:
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;
}
regresando newse headactualiza. Y puedes escribir enmain()
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);
Tenga en cuenta la línea another = _insert_begin(i, another);y verá cómo main()se actualiza el puntero .
Esta es la salida
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
Usando esta implementación de display_list(), imprime 5 valores por línea:
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;
};
Otro ejemplo: insertar al final
tenga en cuenta que insertar al final también puede cambiar el encabezado, en el caso de que la lista esté vacía, por lo que aún necesitamos devolver la dirección del encabezado
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;
}
Otro uso: insertar en orden ascendente
Claro, insertar en orden ascendente también puede cambiar la cabeza, como en
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()
Eliminar una lista
Eliminar una lista también debe devolver un node*para invalidar el puntero principal. Es habitual. A medida que se acostumbre a la mecánica, esto asegurará que no quede un puntero inválido.
Tenga en cuenta que esta lógica es cooperativa: debe asignar el puntero de cabeza hacia atrás en cada llamada que pueda cambiar la cabeza
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 programa en ejecución
Salida del programa de ejemplo
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
El programa de ejemplo en 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;
};
Una estructura de lista vinculada posiblemente más útil
Considera lo siguiente
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 esta forma, una lista enlazada se define como un contenedor de nodos.
- Tiene incluso un opcional
name. sizeestá siempre disponible y actualizado- se puede implementar un límite de tamaño como
capacity - insertar al final y al principio no requiere que siga todos los demás nodos, ya que la lista encapsula punteros tanto a la cabeza como a la cola
- un nodo tiene punteros a los nodos siguientes Y anteriores, por lo que algunos datos, como listas de reproducción o colecciones como esa, se pueden iterar más fácilmente.
- un programa puede tener cualquier número de listas, ya que cada una encapsula todos estos metadatos.
- una lista puede contener cualquier cosa, ya que los datos son un puntero para anular,
void* - funciones como vacío () o tamaño () se pueden implementar fácilmente
- todas las funciones usan un puntero a la lista
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
respecto a:
void begin(node *head){
Cambiar headsolo cambia la pila de llamadas 'head', lo que se necesita es cambiar a dónde apunta 'head' en la función de la persona que llama. PARA hacer eso, la persona que llama debe pasar la dirección de 'cabeza'. El hecho de que 'cabeza' sea, en sí mismo, un puntero no ayuda con la claridad de lo que se debe hacer,