RE: Ordenação de Lista Ligada

[Alfredo Goldman <gold@ime.usp.br>]

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