Ponteiro para ponteiro na lista ligada
Alguém pode me explicar porque esse código me dá como resultado a lista vazia:
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;
}
Mas se eu mudar a função begin () com o ponteiro para ponteiro, ele me dá a lista certa?
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;
}
Você também pode me explicar por que quando eu passo no principal o nó principal para a função begin eu tenho que passá-lo como "& cabeça"? e não mais como "cabeça"
Respostas
No primeiro programa neste snippet de código
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
o ponteiro headé passado para a função beginpor valor. Essa é uma cópia do valor do ponteiro headdeclarado em main é criada e é atribuída ao parâmetro com o mesmo nome da função begin
void begin(node *head);
Portanto, dentro da função, é o parâmetro headque mantém inicialmente uma cópia do ponteiro original headque é alterado. O ponteiro original headcujo valor foi atribuído ao parâmetro não está sendo alterado.
Para alterar a cabeça do ponteiro original declarada em main, você deve passá-la para a função por referência indiretamente por meio de um ponteiro para a cabeça do ponteiro, como é feito no segundo programa.
Portanto, a função deve ser declarada como
void begin(node **head);
E você tem que passar a cabeça do ponteiro indiretamente por meio de um ponteiro para ele
begin( &head );
Neste caso, desreferenciando o ponteiro passado, a função obterá um acesso direto ao cabeçalho original do ponteiro declarado em main e pode alterá-lo (não uma cópia de seu valor, pois ocorre na primeira definição de função)
new->next = *head;
*head = new;
Para tornar mais claro, considere este programa demonstrativo simples.
#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;
}
Sua saída é
Before calling f t is equal to 0
After calling f t is equal to 0
Como a função f trata de uma cópia do valor do argumento passado, o valor da variável tdeclarada em main não foi alterado.
Então você precisa passar a variável original tpor referência por meio de um ponteiro 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;
}
Agora a saída do programa é
Before calling f t is equal to 0
After calling f t is equal to 10
Nesses programas demonstrativos, o nome Té usado como um apelido para o tipo inte, principalmente, o objeto ttem esse tipo.
Vamos agora assumir que o nome T é um apelido para o tipo int *.
typedef int * T;
Neste caso, uma declaração principal como por exemplo
T t = NULL;
significa que a variável ttem o tipo de ponteiro int *. Isso é equivalente a
int * t = NULL;
Portanto, para passá-lo para uma função que deve alterar a variável original t, precisamos passá-lo por referência, como
f( &t );
isso significa que a função correspondente deve ter o tipo de parâmetro declarado como
void f( T *t );
mas como Té um alias para, int *portanto, significa que a função tem um parâmetro do tipo int **.
void f( int * *t );
Como headé (efetivamente) uma variável local, alterá-la não tem efeito fora da função, ao passo que alterar o *headque headaponta para, e assim o faz.
Se você quiser que uma função seja capaz de alterar o valor em uma intvariável (digamos, x), você passaria a ela um ponteiro para x, que teria o tipo int*e você obteria o ponteiro xusando &x. O mesmo é válido independentemente do tipo x.
Um pouco de confusão pode surgir ao declarar
node *head;
ao invés de
node* head;
Você está declarando head. headé a variável e é um ponteiro. Não é um nó. Observe também que um nó não é uma lista vinculada: uma lista vinculada é uma coleção de nós e possivelmente outra coisa para ter uma implementação útil. Mais sobre isso no final.
O fato é que você main()declarou head, apenas um node*. O nó em si ainda nem existe. Você declarou begin()como
void begin(node *head);
e acho que você vai ver mais claramente como
void begin(node* parameter);
parameteré node*.
Dentro, begin()você obtém uma cópia do ponteiro e alterar o ponteiro não alterará o ponteiro original main(). No seu caso, ele main()apontará para sempre NULL.
O que importa é que um ponteiro é como qualquer variável: um ponteiro tem um endereço. E um conteúdo. Quando você passa por valor, assim como você fez, o ponteiro begin()começa com NULLo VALOR de onde veio main(). Mas o vínculo entre eles termina na ligação: o valor inicial.
Quando você passa um ponteiro para begin(), usando o operador 'endereço de' e escrevendo &headcoisas mudam: você vai mudá-lo usando o operador, '*'o que significa que você vai mudar o endereço para o qual ele aponta, então ele mudará main(). Uma vez que headé node*um ponteiro para ele será declarado comonode**
Mas considere alterar a declaração de begin()para uma lista vinculada usando:
node* begin(node* node);
A lógica é que inserir um nó pode mudar o cabeçalho da lista, então você retorna o novo endereço, como em
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
é uma maneira comum de escrever isso. Outra é usar node**.
Da maneira que estou descrevendo aqui, qualquer operação que pode mudar o cabeçalho da lista deve
- devolva a nova cabeça
- receber e atualizar um ponteiro para o ponteiro da cabeça
Veja novamente este código que insere no início da 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;
}
voltando newvocê se headatualiza. E você pode escrever emmain()
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);
Observe a linha another = _insert_begin(i, another);e você verá como o ponteiro main()é atualizado.
Esta é a saída
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
Usando esta implementação de display_list(), que imprime 5 valores por linha:
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;
};
Outro exemplo: inserir no final
note que inserir no final também pode alterar o cabeçalho, caso a lista esteja vazia, então ainda precisamos retornar o endereço do cabeçalho
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;
}
Outro uso: inserir em ordem crescente
Claro, inserir em ordem crescente também pode alterar o cabeçote, como em
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()
Excluindo uma lista
Excluir uma lista também deve retornar um node*para invalidade do ponteiro de cabeça. É normal. Conforme você se acostuma com a mecânica disso, isso garante que um ponteiro inválido não permaneça por perto.
Observe que esta lógica é cooperativa: você deve atribuir o ponteiro de cabeça de volta a cada chamada que pode mudar a cabeça
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;
};
Um programa em execução
Saída do programa de exemplo
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
O programa C de exemplo
#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;
};
Uma estrutura de lista vinculada indiscutivelmente mais útil
Considere o seguinte
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;
Dessa forma, uma lista vinculada é definida como um contêiner de nós.
- Tem até um opcional
name. sizeestá sempre disponível e atualizado- um limite de tamanho pode ser implementado como
capacity - inserir no final e no início não exige que você siga todos os outros nós, uma vez que a lista encapsula ponteiros para o início e o fim
- um nó tem ponteiros para os próximos E os nós anteriores, de modo que alguns dados, como listas de reprodução ou coleções como essa, podem ser iterados mais facilmente.
- um programa pode ter qualquer número de listas, já que cada uma encapsula todos esses metadados.
- uma lista pode conter qualquer coisa, pois os dados são um ponteiro para o vazio,
void* - funções como empty () ou size () podem ser implementadas facilmente
- todas as funções usam um ponteiro para a lista
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
a respeito de:
void begin(node *head){
Mudar headapenas muda a pilha de chamadas 'cabeça', o que é necessário é mudar para onde 'cabeça' na função do chamador aponta. PARA fazer isso, o chamador deve passar o endereço de 'cabeça'. O fato de a 'cabeça' ser, por si só, um indicador não ajuda na clareza do que precisa ser feito,