Listas encadeadas

[Brown.]

Quero implementar a função de ordenação SelectionSort no contexto

de vetores dinâmicos. Deve funcionar para listas encadeadas.

A entrada/saıda do programa deve ser feita por arquivo.

Segue meu codigo com vetores dinâmicos,

como ficaria para listas encadeadas?

#include <stdio.h> 
#include <stdlib.h> 


void SelectionSort(int a[], int array_size); 
int Leitura_Dinamica_Arquivo_Inteiros(char *nome_arquivo, int *numeros[], int *tamanho); 


int main(int argc, char *argv[]) 
  { 
      //FILE *arquivo; 
    int *numero; 
    int j, lidos = 10; 

    if(argc < 2) 
      { 
        printf("\nErro: Digite o nome do arquivo !!!\n\n"); 
        exit(1); 
    } 


    if (Leitura_Dinamica_Arquivo_Inteiros(argv[1], &numero, &lidos)) //se memoria alocada? 
    { 
        printf("\n\nQuantidade de numeros lidos: %d\n", lidos); 
        printf("Os numeros são:\n"); 
        for(j=0; j<lidos; j++)  
        {  
            printf("numero[%d] = %d\n", j, numero[j]); 
        } 
         
        printf("\nOs numeros ordenados:\n"); 
        SelectionSort(numero, lidos); 
        for(j=0; j<lidos; j++)  
        {  
            printf("numero[%d] = %d\n", j, numero[j]); 
        } 
    } 
        free(numero); 
     
    return(0); 
     
  } 

int Leitura_Dinamica_Arquivo_Inteiros(char *nome_arquivo, int *numeros[], int *tamanho) 
{ 
    FILE *arquivo; 
    int lidos = 0; 
     
    if((arquivo = fopen(nome_arquivo,"r")) == NULL) 
    { 
        printf("Erro ao abrir arquivo!!!\n\n"); 
        exit(1); 
    } 
    fscanf(arquivo, "%d", tamanho); 
    int *ptr = (int *) malloc((*tamanho) * sizeof(int)); 
    if(ptr == NULL) return 0; //memoria não alocada 
    lidos = 0; 
    while (fscanf(arquivo, "%d", &ptr[lidos]) == 1) 
    {  
        lidos++; 
    } 
    fclose(arquivo); 
    *numeros = ptr; 

    return 1; 
} 


void SelectionSort(int a[], int array_size) 
{ 
     int i; 
     for (i = 0; i < array_size - 1; ++i) 
     { 
          int j, min, temp; 
          min = i; 
          for (j = i+1; j < array_size; ++j) 
          { 
               if (a[j] < a[min]) 
                    min = j; 
          } 

          temp = a[i]; 
          a[i] = a[min]; 
          a[min] = temp; 
     } 
}

[p4t0X]

Opa, boa noite!

Bom, uma lista simplesmente encadeada seria algo +- assim:

struct elemento_lista{
    int valor;
    struct elemento_lista*proximo;//Ponteiro para o próximo elemento
};

Basicamente, você guarda sempre uma referência do inicio da lista. Quando for adicionar um elemento, guardar a referência do novo elemento adicionado no "proximo" do ultimo elemento. Para percorrer, é só verificar o proximo de todos os elementos da lista.

//Criação da lista
elemento_lista *lista = NULL;

//Adicionar o primeiro elemento
lista = (elemento_lista *) malloc( sizeof( elemento_lista ) );
lista->proximo = NULL;
lista->valor = 5;

//Adicionar o N-simo elemento
elemento_lista *aux = lista;//Aponta a variavel auxiliar para o inicio da lista
while( aux != NULL ){//Percorre a lista até o ultimo elemento (proximo = NULL)
    aux = aux->proximo;//Avança um elemento na lista
}
//Final do loop, aux é o "proximo" do ultimo elemento, (NULL)
aux = (elemento_lista *)malloc( sizeof( elemento_lista ) );
aux->proximo = NULL;
aux->valor = 6;

PS: não compilei o código :s, qualquer coisa é só falar!

[Brown.]

O conceito eu entendi. Não estou conseguindo enxergar como vou implementar em cima do meu codigo citado.

Editado Abril 12, 2010 por Brown.

[p4t0X]

Boa tarde!

Bom, se o conceito você intendeu, é só você fazer isso:

Primeiro sugiro que você crie as funções para a manipulação da lista-ligada (no seu caso, somente a função para adicionar basta);

Depois você usa o método atual para adicionar elementos, só que na lista;

Depois você adapta o selectionSort para funcionar com a lista;

Se tiver qualquer dúvida/problema posta aí!

[Brown.]

O que a função SelectionSort faz. Eu poderia fazer aritmetica de polinomios com lista encadeadas dentro dessa função, para resolver meu problema?

[p4t0X]

SelectionSort é um método de ordenação, veja: http://pt.wikipedia.org/wiki/Selection_sort

Não seria aritmética de ponteiros?!

Acho que até tem como fazer, mais sei lá :o

[Brown.]

Eu confundi...

O que estou tentando fazer é a função Selection Sort com lista encadeada em C.

O restante do algoritmo está pronto, que é trabalhar com arquivos

[p4t0X]

Humm, e qual exatamente a dúvida?!

[Brown.]

Estou trabalhando com chave e post.

Fiz algumas funções...

#define CHAVE(L) ((L)->conteudo)
#define POST(L)  ((L)->posterior)

typedef enum (ERROR, OK) status;
typedef enum (FALSE=0, TRUE=1) bool;
typedef int dado;
typedef struct celula celula, *lista;
struct celula
{
       dado conteudo;
       lista posterior;
};
int leitura_arquivo_inteiros(char *nome_arquivo, lista *p_L, int *tamanho)
status alocar_celula(lista *p_L, dado chave);
status iniciar_lista(lista *p_L);
bool lista_vazia(lista L);
status inserir_inicio_lista(lista *p_L, dado chave);
status print_lista(lista L);
status inserir_final_lista(lista *p_L, dado chave);

status inserir_inicio_lista(lista *p_L, dado chave)
{
    lista L;
    if (alocar_celula(&L, chave) == ERROR) return ERROR;
    POST(L) = *p_L;
    *p_L = L;
    return OK;  
}
status print_lista(lista L){
    lista p;
    if(lista_vazia(L)){
        printf("Lista vazia\n");
        return ERROR;
    }
    else{
        for(p = L; p != NULL; p= POST(p)){
            printf(" %i ",CHAVE(p));
        }
        printf("\n");
        return OK;
    }
}

e outras funções declaradas acima...

Não sei o que poderia usar para fazer o que SelectionSort faz

Acho que seria uma função só

Editado Maio 3, 2010 por Brown.