• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

PTutor

Apontadores e Listas não consigo aprender!

17 mensagens neste tópico

Eu normalmente consigo aprender tudo e não tenho problemas em aprender nada. Enquanto os meus colegas estavam a aprender a fazer programinhas para somar 2 números eu já conseguia um Paint  :)

O que não precebo são os ponteiros e as listas... não há maneira de isso me caber na cabeça... vejam este código:

Program Listas;
Uses Crt;
Type
  prec = ^fred;
  lista = prec;
  fred = record
          info: integer;
          lig:  prec;
        End;

Var
  L, p,q,r: lista;
  N,i: 0..10;

Begin
  ClrScr;
  write('De o numero de elementos da lista [1..10]:');
  readln(N);

  L := nil;
  new(p);
  p^.info := 1;
  L := p;
  For i := 2 to N do
    Begin
      new(p^.lig);
      p := p^.lig;
      p^.info := i*i;
    End;
  p^.lig := nil;

  writeln('*** Impressao de sua lista ***');
  p := L;
  While (p <> nil) do
    Begin
      write(' - ',p^.info);
      p := p^.lig;
    End;
  writeln;
  writeln('*** Fim ***');
  readln;
End.

Eu só sei que primeiro é pedido ao utilizador que introduza um número de 1 a 10 e em seguida mostra os quadrados dos números de 1 ao numero introduzido.

Tou no segundo ano de programação e a minha professora põe-nos um exercicio retirado de uma universidade... ela diz que não encontrou nenhuma outra maneira de nos ensinar.  :thumbdown: Colocou-nos um programa gigante, encheu-o de erros e disse "corrijam-no", como é que é suposto corrigir uma coisa que não precebo  :rant_01:

Aqui tá o programa que ela nos colocou:

http://www.icmc.sc.usp.br/~sce182/ldinimp.html

Agora imaginem isso cheio de erros, dado a alguém que nunca viu uma lista na vida. Sim, foi assim que a professora nos explicou.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Essa página até tem uns desenhos castiços, parecidos com aqueles que eu faço quando preciso de lidar com apontadores :)

Para começar precisas de entender o que é um apontador; as listas (implementadas com apontadores) são apenas uma aplicação dos apontadores. Já tens alguma ideia do que é um apontador? Consegues explicar-nos por palavras tuas?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se souberes programar em C/C++ ficam aqui estes links com código muito bem comentado sobre o tema, eu próprio aprendi listas sozinho só de olhar para este código.

Listas simples

Listas duplamente ligadas

De Pascal eu já soube mas infelizmente não te posso ajudar até porque eu nunca cheguei a ir tão longe no Pascal apesar de futuramente pretender trabalhar com Pascal/Delphi mas arranjo-te aqui uns links o assunto

http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node27.html

http://www.di.ufpb.br/liliane/aulas/listas.html

http://student.dei.uc.pt/~marcelo/pascal.html

http://www.unicamp.br/~hans/mc102/pascal/algoritmo/_ligadaNormal.html

Em teoria deve entender as listas como uma espécie de Lego onde um ligasse ao próximo e assim sucessivamente até chegar ao fim (NULL) isto em Listas simples. Nas listas simples um elemento so esta ligado ao próximo como se ve na figura em baixo:

img62.png

Nas lista duplas um elemento esta ligado ao anterior e ao próximo.

listadupla.gif

Umas das desvantagens da listas é que para encontrar um elemento temos que fazer um autentico brute force, porem podemos sempre arranjar uma maneira mais eficaz como por exemplo ordenar os elementos com o Insertion_Sort e depois colocar elementos "bandeira" guardados em variáveis para o efeito

Ex:

temos 600 elementos e queremos optimizar uma busca e queremos encontrar o elemento com o valor 78 Nota: cada ---------- equivale a 100 elementos

1----------23----------45----------80----------102----------563----------798

Se usarmos uma lista simples vamos começar do 45 até ao 78 que da 78-45+1= 34 verificações de elementos ate encontrar

Mas se usarmos uma lista duplamente ligada vamos começar do 80 até ao 78 que da 80-78+1= 3 de elementos ate encontrar

Ou seja numa lista simples so podemos andar para frente

Numa lista duplamente ligada so podemos andar para trás

Atenção: para implementar este método teria que ser criado um array de ponteiros de propósito para guardar estes valores intermediários.

Desvantagens

    * A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida;

    * Para acessar o elemento na posição n da lista, deve-se percorrer os n - 1 anteriores. (se for por brute force total)

Vantagens

    * A inserção ou a retirada de um elemento na lista não implica na mudança de lugar de outros elementos;

    * Não é necessário saber, anteriormente, o número máximo de elementos que uma lista pode ter, o que implica em não desperdiçar espaço na Memória Principal (Memória RAM) do computador.

Se tiveres alguma duvida é só dizeres, infelizmente não posso ajudar em código por já não programar em pascal ja há algum tempo mas com os links que te dei devem conseguir...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda não dei Listas e comecei à duas aulas a dar Ponteiros.

Já sei que as Listas têm a haver com os records e isso, mas como ainda não dei não te posso ajudar.

Já os ponteiros são coisas que só fazem sentido em programas enormes, porque senão não faz diferença. Os ponteiros segundo sei são uma forma de poupar memória.

A sintaxe para o uso de um ponteiro é o seguinte:

Declaração da variável: variavel:^tipo (Ex: idade:^integer)

Criação do ponteiro: variavel:=nil;

                                  new(variavel);

Por exemplo:

idade:=nil;

new(idade);

Limpar memoria: dispose(variavel);

Por exemplo: dispose(idade);

Agora um exemplo:

Program ponteiro;
   var idade:^integer;
Begin
   idade:=nil;
   new(idade);
   writeln('Idade: ');
   read(idade^);
   writeln('');
   writeln('Idade: ', idade^);
   dispose(idade);
End.

Sinceramente... Não te preocupes muito com isso, pois também ainda não percebi a lógica disso...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A utilização de ponteiros não é apenas para poupar memória, em C é-te extremamente útil para passares listas de um scope para outro p.e.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, a minha Professora falou que em outras linguagens era importante, ou se dava mais utilidade...

Mas, no caso dos Pascal, penso que não tem utilidade algum, penso que seja mesmo só para nos adaptarmos para as próximas linguagens.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas, nos programas que fazemos nas aulas (programas pequenos) não se nota o efeito.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Assim que começares a fazer alguma coisa "a sério" vais notar :). Mas basta pensares em como implementarias uma lista com e sem ponteiros.

Já sei que as Listas têm a haver com os records e isso, mas como ainda não dei não te posso ajudar.

Uma lista é um conjunto com um número variável de elementos; já um array é um conjunto com um número fixo de elementos. Há outras propriedades mas para já podemos ficar assim.

A sintaxe para o uso de um ponteiro é o seguinte:

Declaração da variável: variavel:^tipo (Ex: idade:^integer)

Criação do ponteiro: variavel:=nil;

                                  new(variavel);

Já não mexo em Pascal há muito tempo, pelo que peço já desculpa e o favor de me corrigirem se tiver algum erro na exposição seguinte.

Ao declarares uma variável do tipo ponteiro já estás a criar um ponteiro, só que ele ainda não aponta para nada. Um ponteiro é simplesmente um endereço de memória. Uma variável do tipo ponteiro (para "algo"; normalmente dizemos apenas "ponteiro") é uma variável que guarda um endereço de memória. É por isso que os ponteiros, isto é, as variáveis do tipo ponteiro, têm todos o mesmo tamanho; apenas guardam um endereço. Vocês têm noção do que é a memória de um computador, certo? A memória tem um certo tamanho, que dá para guardar X bytes. Cada um destes X bytes está localizado num ponto da memória, e a forma como identificamos esse ponto é através do seu endereço.

Ninguém vai perceber ponteiros a sério se não tiver uma noção sólida do que é e como funciona a memória de um computador.

Quando declaramos uma variável, estamos a reservar uma área, um pedaço da memória para guardar dados (o valor da variável). Esse pedaço de memória consiste num conjunto contínuo de bytes. Ora, cada um destes bytes tem um endereço, pois todos os bytes da memória têm um endereço. Variáveis muito simples, como as do tipo byte em Pascal (já tou super esquecido de Pascal, se bem me lembro este tipo existe) ocupam apenas 1 byte na memória, e logo o endereço de memória da variável é o endereço de memória desse byte. Quando uma variável é de um tipo que ocupa mais do que 1 byte, como por exemplo do tipo String que ocupa vários, dizemos que o endereço de memória dessa variável é o endereço de memória do 1º byte do conjunto; depois já sabemos que os restantes estão nos endereços seguintes.

Segundo esta lógica, as próprias variáveis do tipo ponteiro têm também um endereço, pois o compilador também teve que reservar um espaço para elas. Esse espaço guarda um endereço.

Quando não queremos guardar nenhum endereço em particular num ponteiro, atribuímos-lhe o valor nil, que é o mesmo que dizer "não aponta para nada", ou "não guarda nenhum endereço". Podemos usar esta informação também como uma "marca"; no caso das listas esta marca o final da lista, caso contrário teriamos que ter uma outra variável a dizer onde termina a lista. Mas isto já é um tópico mais avançado.

Quando queremos criar uma variável do tipo integer, já sabemos que a declaramos como

int : integer;

A variável int tem um endereço de memória. Vocês não o vêm, não lidam com ele, mas ele existe, e podem até obtê-lo, assim: @int. O operador @ dá-vos o endereço de uma variável. Podem fazer wrinteln disto, o que vos dará um número; esse número é o endereço de memória da variável, ou melhor dizendo, do 1º byte da variável, ao qual chamamos apenas "endereço da variável".

Vocês podem escrever no ecran o endereço de todas as variáveis do vosso programa e vão ver que nunca encontrarão 2 endereços iguais. E porquê? Porque cada variável tem o seu espaço de memória próprio, que foi reservado apenas para ela, e este espaço tem que ser exclusivo caso contrário estariamos a "misturar" o valor das variáveis. Era uma grande salganhada.

Agora declaramos uma variável do tipo ponteiro para integer:

pint : ^integer;

O simbolo ^ indica que a variável que queremos declarar não é do tipo base indicado (integer) mas sim do tipo ponteiro (para esse tipo base). Esta variável apenas pode guardar endereços de memória. Quando a criamos nunca sabemos que valor tem, pois pode depender do "lixo" que já está na memória que foi reservada para guardar o seu valor. Daí que é boa politica começar por inicializar uma variável com um valor conhecido, qualquer que seja o tipo da variável, pois os ponteiros não são os únicos sujeitos a esta situação. No caso de um inteiro pode ser 0, no de uma string pode ser '' e no de um ponteiro é nil.

int := 0;

pint := nil;

Agora que temos uma variável que é um ponteiro para integer, podemos pô-lo a apontar para qualquer outra variável que seja um integer:

pint := @int;

Temos que usar o operador @ porque queremos o endereço da variável int; caso contrário estariamos a referir-nos ao valor da variável int (e teriamos um erro do compilador, porque a variável pint só pode guardar endereços).

Agora que temos um ponteiro para um integer (a forma usual de dizermos que temos uma variável do tipo ponteiro para integer que está a apontar para uma variável do tipo integer), podemos manipular o valor da variável para onde o ponteiro aponta:

pint^ := 1;

Esta instrução é equivalente a

int := 1;

Ao sufixarmos o ponteiro com o simbolo ^ estamos a dizer ao computador que nos queremos referir não à própria variável pint mas sim à variável para a qual pint aponta, que neste caso é int uma vez que anteriormente colocámos pint a apontar para ela. Confuso? Não, é apenas uma questão de hábito, que até se ganha depressa. Se escreverem int para o ecran vão ver que de facto ela agora é 1 e não 0 como a colocámos inicialmente.

Em Pascal, quando usam a passagem de argumentos por referência (quando usam a palavra var antes do nome da variável), o que acontece na verdade é que é passado para a subrotina um ponteiro para a variável dada como argumento e não o valor da variável. Só que isso fica escondido para nos facilitar a vida. "Referência" é na prática uma designação muito usual para um "ponteiro", ainda que conceptualmente seja um pouco diferente.

Deixo-vos um exercício: escrever uma rotina para trocar 2 inteiros mas usando ponteiros em vez da passagem por referência (var).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigado a toda a gente especialmente ao Electron++ pela grande explicação. Já tou a perceber melhor as listas, só de olhar para a primeira imagem isso já entrou  :)

Ainda tenho algumas duvidas mas isso vem com o estudo, vou olhar melhor para esses links  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

@ Njay obrigado a sua explicação está muito boa. Eu já tinha uma ideia de como a memória funcionava pois estava a aprender Assembly por mim proprio, mas a sua explicação veio reforça-la, é muito esclarecedora.  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deixo-vos um exercício: escrever uma rotina para trocar 2 inteiros mas usando ponteiros em vez da passagem por referência (var)

Program Exercicio;
Uses Crt;

Var n1,n2:Integer;

Procedure TrocarNumeros(vn1:Integer;vn2:Integer);
  Var Aux:Integer;
  Begin

  Aux:=n2;
  n2:=n1;
  n1:=Aux;

  End;

Begin
Clrscr;

  Writeln('Introduza o valor para a primeira variavel (n1)');
  Readln(n1);
  Writeln('Introduza o valor para a segunda variavel (n2)');
  Readln(n2);

  TrocarNumeros(n1,n2);

  Writeln('O valor da primeira variavel e: ',n1);
  Writeln('O valor da segunda variavel e: ',n2);

Readln;
End.

Agora falta trocar algumas variaveis por ponteiros  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

PTutor esse metodo obriga-te a criar uma variavel pah

usem antes este:

numero1=5

numero2=8

numero1=numero1+numero2                5+8=13

numero2=numero1-numero2                13-8=5

numero1=numero1-numero2                13-5=8

simplificando a coisa:

a=5

b=8

a=a+b

b=a-b

a=a-b

simples e tb funciona para numeros negativos, numeros reais.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Wawawiwa, a minha stora nunca me tinha ensinado dessa maneira, e confesso que nunca tinha pensado dessa maneira  :hmm:

É sempre bom saber  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O meu stor tb não mas eu cismei com ele em como conseguia trocar o valor de duas variáveis sem recorrer a variáveis externa e consegui :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora