Lista de discussão de MAC 2301
[Prévia por Data][Próxima por Data]
[Prévia por Assunto][Próxima por Assunto]
[Índice por Data][Índice por Assunto]
[Envie uma nova mensagem para a lista]
[Responda esta mensagem]
RE: Ordenação de Lista Ligada
- Subject: RE: Ordenação de Lista Ligada
- From: Alfredo Goldman <gold@ime.usp.br>
- Date: Thu, 11 Apr 2002 11:57:39 -0300
Olá Pessoal,
Novamente tomei a liberdade de responder um e-mail de um aluno
para toda a lista (dificilmente a dúvida é só dele).
> Professor,
>
> 1- Uma dúvida conceitual... considere a estrutura
> abaixo:
>
> typedef struct no1{
> TipoInfo info;
> struct no1 *prox;
> } No, *apontNo;
>
1) Explicando: os nomes No e apontNo se referem a estrutura
recem criada, no caso No é uma variável do tipo da estrutura
e apontNo é um apontador para a estrutura.
> Se eu substituísse a palavra "No" pela palavra
> "apontNo" daria na mesma? Isto é... a estrutura
> ficaria:
>
> typedef struct no1{
> TipoInfo info;
> struct no1 *prox;
> } apontNo, *apontNo;
>
Ops: Erro de compilação, você teria duas variáveis com o mesmo
nome, sendo uma um apontador.
> Ou seja, a função da minha estrutura (ou a estrutura
> em si) é alterada?
Não.
> Bem... o motivo da pergunta, é que eu notei que no
> programa principal da "lição de casa", existe a
> seguinte declaração de variável:
>
> apontNo p; //início da lista
Isto significa que p é um apontador para No
> Antigamente, quando a estrutura eram simples (sem
> ponteiros para complicar a vida), como a que está a
> seguir:
>
> typedef struct no1{
> TipoInfo info;
> int dado;
> } No;
>
> Usávamos no programa principal a seguinte declaração:
>
> No variável; //Variável do tipo estrutura
>
Antigamente nós tinhamos estruturas fixas, e não havia necessidade de se usar
apontadores.
> Pergunta1: Para a primeira estrutura mostrada, o quê
> sigifica apontNo (sem estrela) e *apontNo declarados
> no programa principal?
Ver resp 1)
> Pergunta2: O quê significa declarar uma variável do
> tipo "No" no programa principal, considerando a
> primeira estrutura mostrada (a que possui ponteiros).
>
Significa ter uma variável com espaço para guardar os seus dados:
Um trecho que pode ajudar.
int a; // variável inteira, posso guardar um inteiro nela
int *b; // apontador para variáveis inteiras
a = 5; // OK
*b = 5; // erro pois eu não reservei o espaço para guardar um inteiro
// e b pode conter um endereço qualquer da memória
b = (int *) malloc (sizeof(int));
// ou b = &a; // b recebe o endereço de a
*b = 1; // OK
> 2- Não estou conseguindo visualizar como ordenar a
> lista ligada. Devo fazer usando Insertion Sort? Bubble
> Sort? Quick Sort? Afinal, qual método de ordenação é o
> melhor? Porquê? E por onde posso começar o raciocínio
> de ordenação usando os ponteiros da lista ligada? Eu
> começo a simular o algorítmo na mão, mas não consigo
> implementá-lo...
>
Os algoritmos de ordenação que você citou foram apresentados para vetores, no
caso de listas ligadas eles devem ser adaptados. A idéia no caso é pensar em
um algoritmo que ordene uma lista (eventualmente criando outra lista).
> 3- Porque o nome na estrutura ("no1", como no exemplo)
> não influencia no programa e sim os nomes "No" e/ou
> "*apontNo"? Aliás, "No" e/ou "*apontNo" são nomes,
> variáveis ou declarações?
>
O no1 (na verdade struct no1) é usado para dizer que o campo prox é
um ponteiro para estruturas do tipo struct no 1. Durante o
programa seriam equivalentes:
struct no1 var1; No1 var;
assim como
struct no1 *apont1; No *apont1; apontNo apont;
> Dê-nos uma luz, por favor!
>
Espero ter ajudado.
Alfredo