Listas encadeadas

[Brown. 1]

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;
     }
}

[_Isis_ 202]

E qual a dificuldade? você sabe o que é uma lista encadeada?

[Brown. 1]

Só a função Selection Sort com lista encadeada. Alguém?

[_Isis_ 202]

Abstraia.

Se você sabe como o selection sort funciona p/ um array de inteiros, você sabe como ele funciona p/ uma lista ligada. Sempre existe o conceito de chave de ordenação. Isso não vai mudar.

Se você sabe que um elemento da lista ligada aponta p/ o próximo, você sabe que precisa "refazer" as ligações da lista durante a ordenação.

 

É só adaptar o algoritmo. Se você usa struct pra representar os elementos da lista, a chave de ordenação vai ser acessada com '.'. Se é string, a comparação vai ser com strcmp.