Jump to content
Leudassdf

Estruturas auto-referenciadas

Recommended Posts

Leudassdf

Boas pessoal,

atualmente estou a começar a estudar estruturas e vi isto num tuturial

typedef struct ponto {
double x;
double y;
struct ponto *origem;
} Ponto;

Pelo que consegui perceber isto é uma estrutura auto-referenciada. o que eu nao consegui perceber é o que é que isto significa.

Ou seja, onde diz struct ponto *origem,nao consegui perceber o que faz esta declaraçao.

Alguem me pode explicar?

Cumprimentos

Share this post


Link to post
Share on other sites
pwseo

Se estás a estudar structs então não precisas já do typedef:

struct ponto {
 double x, y;
 struct ponto *origem;
};

A declaração struct ponto *origem significa que a tua struct ponto tem um campo chamado origem que aponta para uma outra struct ponto. Dizemos que há auto-referenciação porque estás a utilizar struct ponto dentro da sua própria definição. Não é nada mais que isso.

É importante compreender o motivo pelo qual origem é um apontador e não uma struct ponto. Quando defines uma struct em C e crias uma variável desse tipo, é alocada memória para todos os campos. Ora, se dentro de uma struct ponto existir uma struct ponto, a alocação de memória será infinita, pois dentro de cada struct ponto haverá sempre mais struct ponto, e o compilador não seria capaz de parar:

struct ponto {
 double x, y;
 struct ponto {
   double x, y;
   struct ponto {
     double x, y;
     struct ponto {
       /* ... buraco sem fim ... */
     };
   };
 };
};

Por esse motivo, dentro de cada struct ponto existe um apontador para struct ponto. Um apontador é apenas um valor numérico, e por isso deixa de haver recursividade na definição.

Isto ajuda-nos a perceber que em C é impossível criar definições recursivas (outras linguagens, como Haskell, permitem-no), mas podemos utilizar auto-referenciação (uma struct que contenha apontadores para structs do mesmo tipo) para emular essa recursividade -- como acontece em muitas estruturas de dados que irás construir, começando com as listas ligadas.

PS.: por que motivo cada ponto definido nesse tutorial precisa de apontar para a origem? São pontos com coordenadas relativas em vez de absolutas?

Share this post


Link to post
Share on other sites
Leudassdf

Sim. As coordenadas são relativas.

No entanto fiquei sem perceber qual a utilidade de fazer struct ponto *origem;

Isto vai ter alguma utilidade no programa?

Share this post


Link to post
Share on other sites
pwseo

Utilizas struct ponto *origem porque se as coordenadas são relativas, tens que saber em relação a que ponto o são. Por esse motivo, tens que incluir a origem em cada ponto, e isso é feito criando um apontador para o ponto da origem dentro de cada ponto.

Diz-me: o que compreendes de apontadores?

Share this post


Link to post
Share on other sites
Leudassdf

Utilizas struct ponto *origem porque se as coordenadas são relativas, tens que saber em relação a que ponto o são. Por esse motivo, tens que incluir a origem em cada ponto, e isso é feito criando um apontador para o ponto da origem dentro de cada ponto.

Diz-me: o que compreendes de apontadores?

Não sei muito. So agora é qie começei a ver...

No entanto sei que os apontadores servem p.ex para passar valores por referencia e não por valor. Isto permite-nos ir ao endereço onde se encontra guardado o valor declarado a uma variável e alterá-lo ou consultá-lo.

Ou seja por aquilo que percebo um apontador aponta para um determinado endereço de memoria.

Share this post


Link to post
Share on other sites
pwseo

Tentar estudar self-referencing structs sem compreender apontadores é como resolver equações de segundo grau sem saber as operações matemáticas comuns: não são difíceis, mas exigem que se saibam algumas coisas de base.

Vou explicar-te o assunto de outra forma: cada struct ponto não pode conter dentro de si uma struct ponto, porque o compilador nunca seria capaz de parar essa definição infinita. Por esse motivo, em vez de cada ponto ter dentro de si o ponto origem tem um apontador para esse ponto. Como um apontador é apenas um endereço, a definição deixa de ser "infinita". Desta forma, tu podes pegar num ponto qualquer e facilmente saber qual a origem à qual ele se refere: basta seguir o endereço que armazenaste em origem.

PS.: pratica os teus conhecimentos em apontadores; sem isso, tudo o resto fica complicado.

Share this post


Link to post
Share on other sites
Leudassdf

Tentar estudar self-referencing structs sem compreender apontadores é como resolver equações de segundo grau sem saber as operações matemáticas comuns: não são difíceis, mas exigem que se saibam algumas coisas de base.

Vou explicar-te o assunto de outra forma: cada struct ponto não pode conter dentro de si uma struct ponto, porque o compilador nunca seria capaz de parar essa definição infinita. Por esse motivo, em vez de cada ponto ter dentro de si o ponto origem tem um apontador para esse ponto. Como um apontador é apenas um endereço, a definição deixa de ser "infinita". Desta forma, tu podes pegar num ponto qualquer e facilmente saber qual a origem à qual ele se refere: basta seguir o endereço que armazenaste em origem.

PS.: pratica os teus conhecimentos em apontadores; sem isso, tudo o resto fica complicado.

Claro que irei treinar. No entanto eu com o apontador origem consigo fazer alguma coisa?

Podes dar-me um exemplo?

Share this post


Link to post
Share on other sites
pwseo

Consegues saber as coordenadas x e y do ponto de origem, podes trocar o ponto de origem por outro ponto qualquer, entre outras coisas. Não sou eu que posso dar-te respostas sobre isso; o tutorial que estás a seguir é que deveria explicar por que motivo utiliza um apontador para a origem :)

Share this post


Link to post
Share on other sites
HappyHippyHippo

acho que o maior problema é pensares no exercício em questão em vez no que realmente o método foi usado.

como já foi dito, o ponteiro é usado para se poder definir uma referência de memória para um tipo de dados estruturado X dentro desse mesmo tipo de dados.

o caso mais comum (porque a razão do seu uso é mais do que evidente) é em listas ligadas (uma lista de nós, em que cada nó guarda um valor e aponta para a posição de memória para o nó seguinte).

pensa no que tens quando usas arrays:

int array[10];

isto não é mais do declarar um bloco de memória que ocupa o espaço de 10 inteiros contíguos. no entanto existe o problema que ficas inicialmente limitado a 10 elementos, sendo o processo de redimensionamento dessa memória algo que pode ser pesado computacionalmente.

uma estrutura usada para colmatar esse problema são listas ligada que só ocupam a memória necessária sendo fácil inserir e retirar elementos sem problemas de limite (tirando o limite máximo de memória).

no caso mais simples, terás o tipo de dados estruturados No, que formará a seguinte estrutura:

+----+  +----+  +----+
| No ---> No ---> No --->
| Val|  | Val|  | Val|
+----+  +----+  +----+

como vês, está implícito que na declaração do tipo de dados estruturado tens de ter a referência para o nó seguinte e o inteiro que irá guardar o valor do nó.

o problema é que não podes fazer o seguinte:

struct No {
 struct No no; // <---
 int val;
};

a razão já foi explicada acima pelo @pwseo, isto seria um ciclo infinito, e a razão pela qual o compilador não permite tal coisa.

é por isso que é usado um ponteiro, porque um ponteiro é uma referência a uma posição de memória e como tal não é mais do que um número.

struct No {
 struct No * no; // <--- ponteiro
 int val;
};

----------

o caso to teu exercício, o que está a acontecer é o mesmo. tens um ponto num referencial Xr,Yr que se encontra definido pela estrutura struct ponto, só que para definir esse ponto nesse referencial, necessitas de saber qual o ponto de origem desse referencial.

imagina um ponto dentro de uma janela do teu ecrã:

+--- ecrã ----------------------------------------------------------------+
|                                                                         |
|       +--- janela ----------------+                                     |
|       |                           |                                     |
|       |        * Ponto            |                                     |
|       |                           |                                     |
|       |                           |                                     |
|       +---------------------------+                                     |
|                                                                         |
|                                                                         |
+-------------------------------------------------------------------------+

se tiveres guardada a posição do ponto numa estrutura como a usada no teu código, terás:

struct ponto OrigemEcra = {0.0, 0.0, NULL};
struct ponto OrigemJanela = {10.0, 10.0, &OrigemEcra};

struct ponto PontoRefJanela = {10.0, 10.0, &OrigemJanela};
struct ponto PontoRefEcra = {PontoRefJanela.x + PontoRefJanela.origem->x,
                            PontoRefJanela.y + PontoRefJanela.origem->y,
                            &OrigemEcra};

os dois pontos (PontoRefJanela, PontoRefEcra) estão referenciar o mesmo pixel do ecrã ...


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.