O ano passado na universidade aprendi listas ligadas na sua forma mais básica, coisa que nunca tinha ouvido falar em C (também, no secundário não se aprende muito). A estrutura de uma simples lista ligada era assim:
Eu entendo este código e sei usar as listas ligadas desta forma. Sei adicionar elementos, remove-los e fazer uma listagem de todos os elementos. Este ano, numa cadeira diferente, foi-nos apresentado as "queues", coisa muita parecida com as listas ligadas mas com uma pequena diferença. Agora íamos ter um apontador para a cabeça da lista e outro para a cauda da lista. Ou seja, para além da estrutura acima apresentada íamos usar uma outra:
Seguidamente apresento o resto código que inclui o main(), função que inicializa uma "queue", função que permite inserir elementos na "queue" e função que lista todos os elementos da "queue":
Executando este código e como os elementos inseridos na "queue" são inteiros aleatórios, o seguinte output é apenas um exemplo do resultado obtido:
Até aqui tudo bem, mas agora é que começa a minha dúvida. Olhando para a função listQueue(), é criado um apontador temporário (temporário porque está criado dentro da função e será automaticamente destruido assim que a função terminar) ao qual é atribuido o apontador 'q->head'. Desta forma, percorremos o apontador temporário até o próximo valor ser NULL, quando for NULL, é porque chegamos ao fim da "queue".
Olhando agora para a função insertQueue(), mais propriamente para o seguinte código que é onde realmente aparecem as minhas dúvidas:
Vejamos, se a cauda da "queue" for nula (está vazia, estamos a inserir o 1º elemento), então atribuimos o elemento criado (x) à cabeça da "queue", seguidamente, atribuimos o mesmo elemento à cauda. Numa próxima inserção a "queue" já não vai estar vazia, logo, vamos atribuir o elemento criado ao próximo elemento da cauda da "queue" e seguidamente atribuimos o mesmo elemento à própria cauda e assim sucessivamente porque daqui para frente a "queue" nunca mais será nula.
Eu não entendo como é que isto funciona. Quando a "queue" não é nula, estamos sempre a dizer que os novos elementos são atribuidos ao próximo elemento da cauda e seguidamente fazemos um tipo de "reset" à cauda" atribuindo-lhe o próprio elemento, o que iria definir o 'q->tail->next' como NULL. Depois, na função de listagem da "queue" percorremos o 'q->head' até ser nulo. Não entendo como é que ao percorrer o 'q->head' conseguimos apresentar todos os elementos inseridos quando na nossa função de inserção, apenas "trabalhamos" com o 'q->head" uma única vez, quando a lista está vazia/nula, definindo assim o primeiro elemento da lista. E eu não consigo visualizar de onde aparecem os restos dos elementos devido à insercção do resto dos elementos em 'q->tail->next' e depois ao "reset" de 'q->tail'.
Bem, eu sei que isto são tudo apontadores e tal, mas é mesmo isso que eu estou a falhar em ver. Não estou a conseguir visualizar como é que ao fazermos 'q->tail->next = x;' depois vai ser possível fazer "q->head = q->head->next;" (usando o apontador temporário obviamente) e imprimir o próximo elemento na "queue".
Será que alguém me consegue explicar como funcionam estes apontadores como se eu fosse mesmo burro? Já tentei pegar em papel e lápis e fazer uns esboços de memória a apontar para ali e tal, mas não estou a conseguir, não estou a conseguir visualizar como é que isto está a funcionar.
P.S: Desculpem o testamento, mas eu gosto de explicar as coisas ao pormenor para evitar que haja mal entendidos e também porque isto é um problema que me está a dar a volta a cabeça e eu gostava de perceber como funciona. E a melhor forma para isso é apresentar o maior número de dados possível sobre o problema.
Código:
typedef struct sNode {
int elem;
struct sNode *next;
} Node;
Código:
typedef struct {
Node *head;
Node *tail;
} Queue;
Seguidamente apresento o resto código que inclui o main(), função que inicializa uma "queue", função que permite inserir elementos na "queue" e função que lista todos os elementos da "queue":
Código:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
void insertQueue(Queue *q, int elem) {
if(!q) return;
Node *x = (Node*)malloc(sizeof(Node));
if(!x) return;
x->elem = elem;
x->next = NULL;
if(q->tail) q->tail->next = x;
else q->head = x;
q->tail = x;
}
Queue* initQueue() {
Queue *x = (Queue*)malloc(sizeof(Queue));
if(!x) return NULL;
x->head = NULL;
x->tail = NULL;
return x;
}
void listQueue(const Queue *q) {
if(!q) return;
if(!q->head) return;
printf("\n");
Node *ptr = q->head;
do {
printf("%d", ptr->elem);
ptr = ptr->next;
if(ptr) printf(" -> ");
} while(ptr);
}
int main(void) {
int i, num;
Queue *q;
srand((unsigned int)time(NULL));
q = initQueue();
printf("RANDOM: ");
for(i = 0; i < MAX; i++) {
num = rand() % 100 + 1;
printf("%d ", num);
insertQueue(q, num);
}
printf("\n");
listQueue(q);
return 0;
}
Executando este código e como os elementos inseridos na "queue" são inteiros aleatórios, o seguinte output é apenas um exemplo do resultado obtido:
Código:
RANDOM: 58 18 11 92 50 91 43 64 46 83
58 -> 18 -> 11 -> 92 -> 50 -> 91 -> 43 -> 64 -> 46 -> 83
Até aqui tudo bem, mas agora é que começa a minha dúvida. Olhando para a função listQueue(), é criado um apontador temporário (temporário porque está criado dentro da função e será automaticamente destruido assim que a função terminar) ao qual é atribuido o apontador 'q->head'. Desta forma, percorremos o apontador temporário até o próximo valor ser NULL, quando for NULL, é porque chegamos ao fim da "queue".
Olhando agora para a função insertQueue(), mais propriamente para o seguinte código que é onde realmente aparecem as minhas dúvidas:
Código:
if(q->tail) q->tail->next = x;
else q->head = x;
q->tail = x;
Eu não entendo como é que isto funciona. Quando a "queue" não é nula, estamos sempre a dizer que os novos elementos são atribuidos ao próximo elemento da cauda e seguidamente fazemos um tipo de "reset" à cauda" atribuindo-lhe o próprio elemento, o que iria definir o 'q->tail->next' como NULL. Depois, na função de listagem da "queue" percorremos o 'q->head' até ser nulo. Não entendo como é que ao percorrer o 'q->head' conseguimos apresentar todos os elementos inseridos quando na nossa função de inserção, apenas "trabalhamos" com o 'q->head" uma única vez, quando a lista está vazia/nula, definindo assim o primeiro elemento da lista. E eu não consigo visualizar de onde aparecem os restos dos elementos devido à insercção do resto dos elementos em 'q->tail->next' e depois ao "reset" de 'q->tail'.
Bem, eu sei que isto são tudo apontadores e tal, mas é mesmo isso que eu estou a falhar em ver. Não estou a conseguir visualizar como é que ao fazermos 'q->tail->next = x;' depois vai ser possível fazer "q->head = q->head->next;" (usando o apontador temporário obviamente) e imprimir o próximo elemento na "queue".
Será que alguém me consegue explicar como funcionam estes apontadores como se eu fosse mesmo burro? Já tentei pegar em papel e lápis e fazer uns esboços de memória a apontar para ali e tal, mas não estou a conseguir, não estou a conseguir visualizar como é que isto está a funcionar.
P.S: Desculpem o testamento, mas eu gosto de explicar as coisas ao pormenor para evitar que haja mal entendidos e também porque isto é um problema que me está a dar a volta a cabeça e eu gostava de perceber como funciona. E a melhor forma para isso é apresentar o maior número de dados possível sobre o problema.