1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

[C] Problemas em entender apontadores juntamente com "queues"

Discussão em 'Programação' iniciada por Nazgulled, 14 de Dezembro de 2007. (Respostas: 12; Visualizações: 1460)

  1. Nazgulled

    Nazgulled Power Member

    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:
    Código:
    typedef struct sNode {
    	int elem;
    	struct sNode *next;
    } Node;
    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:
    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;
    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.
     
  2. Baderous

    Baderous Banido

    Não fazes um reset à cauda. O que tu fazes é a actualização do apontador para a cauda, para a nova cauda. Não te esqueças que q é não é uma queue mas sim um apontador para queue, ou seja um apontador para uma struct que tem 2 apontadores (head,tail). Quando inseres um novo elemento na queue, adicionas ao fim da queue, logo tens de fazer o q->tail->next=x; para colocares o apontador next do último elemento da queue a apontar para o mesmo local que o x (também ele um apontador). Ou seja, no fim disto, a tua queue já vai estar "feita" mas falta actualizar o apontador para a queue (o tal q). Para isto tens de fazer q->tail=x para que assim ele possa ir actualizando sempre a queue, senão a struct Queue deixaria de fazer sentido (a sua vantagem é teres sempre 2 apontadores: 1 para a head e outro para a tail que vai sendo sempre actualizado).

    Vê se percebes este esquema da operação de inserção na queue:

    [​IMG]
     
  3. Nazgulled

    Nazgulled Power Member

    Era isso que eu queria dizer quando disse "reset".

    Mas como é que ao fazeres q->tail->next = x "também estás a fazer" q->head->next = x?

    O que tu explicaste no teu post é a parte que eu já entendi.
     
  4. Baderous

    Baderous Banido

    Mas nunca fazes isso. O apontador head aponta sempre para o início da queue e só é actualizado quando se remove um elemento da queue ou quando se insere pela primeira vez um elemento na queue vazia. Portanto, se queres saber quais são os elementos presentes na queue, começas a percorrer do início para o fim. Quando fazes a listagem dos elementos, entras pelo apontador head no início da queue e depois, basicamente, é uma operação de listagem dos elementos de uma lista ligada. O apontador head não se altera. Não sei se estou a responder bem à tua dúvida...
     
  5. greatbunzinni

    greatbunzinni Power Member

    Em que ano é que ensinam estruturas de dados aos alunos? Julgava que era algo que seria dado logo no 1º semestre do 1º ano.
     
  6. HecKel

    HecKel The WORM

    Isso não me parece que tenha trazido muito conteúdo útil à questão inicial, pois não? ;)

    E quanto ao ano em que se ensinam estruturas de dados, depende muito de faculdade para faculdade ;)
     
  7. Nazgulled

    Nazgulled Power Member

    @Baderous
    Deves estar a responder, eu é que devo estar parvinho e não entendo nada. No entanto, antes de ler essa tua resposta, como não tive possibilidades de vir à net, tive a tentar fazer mais uns desenhos e acho que cheguei a uma conclusão. Vou apresentar aqui os meus esquemas (acho que dá para entender) para me dizerem se é isto que está a acontecer ou tem algum erro, mas acho que é mais ao menos isto que acontece. Os pontos fulcrais para eu entender isto, estão a vermelho. Basicamente, são os passos do que aconteceu quando temos uma lista vazia e inserimos 2 elementos sendo o '5' o primeiro seguido do '2'.

    [​IMG]

    @greatbunzinni
    Óbvio que isso não tem lógica nenhuma e como o HecKel disse, depende. No 1º ano e no 1º semestre em LEI no Minho nem se quer se aprende C, por isso... Só no segundo semestre e pelo menos comigo, estruturas de dados foi dado numa forma básica, não exploraram muito e o trabalho proposto não necessitou de grandes conhecimentos em estruturas de dados para o fazer.
     
    Última edição: 14 de Dezembro de 2007
  8. slack_guy

    slack_guy Power Member

    Vê lá se estas (1 e 2) explicações sobre filas te ajudam.
     
  9. Baderous

    Baderous Banido

    O teu esquema está todo certo.
    Como podes ver o head só é alterado quando se insere o 5 (passa de NULL para 5), de resto fica sempre a apontar para o 5. O tail é que vai sendo alterado conforme se adicionam elementos à queue.
     
  10. Nazgulled

    Nazgulled Power Member

    O que me tava a falhar era visualizar os apontadores e para aonde apontava e o quê. Mas foi preciso fazer assim um esquema detalhado ao não chegava lá...

    @slack_guy
    Vou ver isso com atenção apesar de já ter chegado lá, sempre deve ajudar a perceber mais qualquer coisa e/ou melhor.

    Thank you all!
     
  11. Tyran

    Tyran Power Member

    Uma coisa divertida é pensares como um comboio lol, se vais metendo carruagens na cauda não altera a cabeça... não podes passar de null porque se não lá se vai a carruagem ao tentares liga-la a uma que não existe... Podes também meter carruagens pelo meio que se ligues bem as mesmas e não apagues nenhuma e por conseguinte todas as outros a ela ligadas.
    Podes eventualmente alterar a cabeça se por exemplo quiseres que o comboio se ligue a um outro...
    Epah isto pelo menos é uma maneira engraçada e pensar, ah quem goste ah quem não goste lol

    cumpzz
     
  12. Baderous

    Baderous Banido

    Mas aqui trata-se de uma queue, ou seja, os elementos removem-se da cabeça da lista e adicionam-se novos elementos na cauda. Se quiseres pensar num exemplo do dia-a-dia pensa antes numa fila do supermercado.
     
  13. Tyran

    Tyran Power Member

    Ups... então nesse caso tens de tirar a carruagem da frente =S não fica mt bem num comboio lol, por isso vai mesmo pa fila, aproveita enquanto tiveres nas compras de natal :P
    Ou pensas num fio de condutor mas é melhor não ficticiar muito :)
    Cumpzz
     

Partilhar esta Página