Exe08 - Aplicar um algoritmo de ordenação em lista encadeada de inteiros

[waldeyr]

Samuel, não é isso que o exercício pede.

[gustavohgarcez]

Gustavo Henrique Garcez Andrade

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define TAMANHO 10

// Lista Encadeada de Inteiros
//----------------------------

// Define o tipo No contendo
typedef struct Item {
    int dado;
    struct Item *prox;
} No;

//Define o primeiro No da lista
No* ponteiroInicio = NULL;

// Funcao que define a lista como vazia.
void criarLista() {
    ponteiroInicio = NULL;
}

//Funcao que adiciona dados
void adicionarDado(int dado) {
    No* ponteiroNo;
    ponteiroNo = (No *) malloc(sizeof (ponteiroNo));
    if (ponteiroNo == NULL) {
        printf("Erro de memoria. Voce esta programando o Windows?\n");
    }

    ponteiroNo->dado = dado;
    ponteiroNo->prox = NULL;
    if (ponteiroInicio == NULL)
        ponteiroInicio = ponteiroNo;
    else {
        ponteiroNo->prox = ponteiroInicio;
        ponteiroInicio = ponteiroNo;
    }
}

//Funcao que imprime a lista
void imprimirLista() {
    printf("--------------------------------\n");
    No* ponteiroNo;
    if (ponteiroInicio == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    ponteiroNo = ponteiroInicio;
    while (ponteiroNo != NULL) {
        printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox);
        ponteiroNo = ponteiroNo->prox;
    }
    printf("--------------------------------\n");
}

//Funcao que busca dados na lista
void buscarDado(int dado){
    No* ponteiroNo;
    if (ponteiroInicio == NULL){
        printf("Lista Vazia\n");
        return;
    }
    ponteiroNo = ponteiroInicio;
    while (ponteiroNo != NULL){
        if (ponteiroNo->dado == dado){
            printf("[%d(%p)]\n", ponteiroNo->dado, ponteiroNo);
        }
        ponteiroNo = ponteiroNo->prox;
    }

}

//Algoritmo de Ordenação
//----------------------

void bubble(){
    int comp = 0, troca = 0; 
    No* ponteiroNo;
    if (ponteiroInicio == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    //Ordena vetor pelo metodo da bolha
    for (int i = 0; i < TAMANHO; i++) {
        ponteiroNo = ponteiroInicio;
        while (ponteiroNo->prox != NULL) {
            int atual = ponteiroNo->dado;
            int proximo = ponteiroNo->prox->dado;
            comp++;
            if (atual > proximo) {
                ponteiroNo->dado = proximo;
                ponteiroNo->prox->dado = atual;
                troca = troca + 1;
            }
            ponteiroNo = ponteiroNo->prox;
        }           
    }

    printf("\n");

    //Mostra valores do vetor ordenado   
    imprimirLista();

    printf("\nComparações: %d", comp);
    printf("\nTrocas: %d", troca);
    printf("\n");
}

void main() {
    criarLista();

    //Definindo valores aleatórios
    srand(time(NULL)); //Cria uma semente para numeros aleatorios
    for (int i = 0; i < TAMANHO; i++) {
        adicionarDado(rand() % 10); //Atribui um inteiro aleatorio entre 0 e 9
    }

    //Imprimindo a Lista Encadeada com valores aleatórios
    printf("-- Lista encadeada de inteiros com valores aleatórios --\n");
    imprimirLista();

    //Ordenando e Imprimindo a Lista Encadeada com Bubble
    printf("\n-- Lista encadeada de inteiros ordenado com Bubble --\n");
    bubble();
}

[arthurjf]

Aluno: Arthur José Fernandes

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define TAMANHO 10

// Define o tipo No com struct

typedef struct No {
    int dado;
    struct No *prox;
} No;

//Variavel global com o no mais recente da lista
No* ponteiroFinal = NULL;

//Funcao que adiciona dados

void adicionarDado(int dado) {
    No* ponteiroNo;
    ponteiroNo = (No *) malloc(sizeof (ponteiroNo));
    ponteiroNo->dado = dado;
    ponteiroNo->prox = NULL;
    if (ponteiroFinal == NULL)
        ponteiroFinal = ponteiroNo;
    else {
        ponteiroNo->prox = ponteiroFinal;
        ponteiroFinal = ponteiroNo;
    }
}

//Funcao que imprime a lista

void imprimirLista() {
    No* ponteiroNo;
    if (ponteiroFinal == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    ponteiroNo = ponteiroFinal;
    while (ponteiroNo != NULL) {
        printf("%d\t", ponteiroNo->dado);
        ponteiroNo = ponteiroNo->prox;
    }
    printf("\n\n");
}

void bubbleSort() {
    No* ponteiroNo;
    if (ponteiroFinal == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    for (int i = 0; i < TAMANHO + 1; i++) {
        ponteiroNo = ponteiroFinal;
        No* ponteiroAnterior = NULL;
        int trocou = 0;
        while (ponteiroNo != NULL) {
            No* ponteiroProx = ponteiroNo->prox;
            if (ponteiroProx != NULL && (ponteiroNo->dado > ponteiroProx->dado)) {
                ponteiroNo->prox = ponteiroProx->prox;
                ponteiroProx->prox = ponteiroNo;
                if (trocou == 0)
                    trocou = 1;
                if (ponteiroAnterior != NULL)
                    ponteiroAnterior->prox = ponteiroProx;
                if (ponteiroNo == ponteiroFinal) {
                    ponteiroFinal = ponteiroProx;
                }
            } else if (ponteiroNo->prox == NULL && trocou == 0) {
                return;
            }
            ponteiroAnterior = ponteiroNo;
            ponteiroNo = ponteiroNo->prox;
        }
    }
}

void main() {
    printf("\n");
    // Insere na lista os numeros de 1 a 4
    srand(time(NULL)); //Cria uma semente para numeros aleatorios
    for (int i = 1; i <= TAMANHO; i++) {
        adicionarDado(rand() % 90);
    }
    imprimirLista();
    printf("Ordenando pelo Bubble Sort...\n\n");
    bubbleSort();
    imprimirLista();
}

[Vanderson11]

Vanderson leite campos

include

include

include

define TAMANHO 5

No *ponteiroFinal = NULL;

typedef struct No{ int dado; struct No *prox; }No;

void adicionar(int dado){ No *ponteiroNo;

ponteiroNo = (No *) malloc(sizeof (ponteiroNo));
ponteiroNo->dado = dado;
ponteiroNo->prox = NULL;

if(ponteiroFinal == NULL)
    ponteiroFinal = ponteiroNo;
else{
    ponteiroNo->prox = ponteiroFinal;
    ponteiroFinal = ponteiroNo;
}

}

void imprimir(){ No *no;

if(ponteiroFinal == NULL){
    printf("Lista vazia.\n");
    return;
}

no = ponteiroFinal;

while(no != NULL){
    formato(no);
    no = no->prox;
}
printf("\n");

}

void formato(No *no){ printf("%d\n",no->dado,no,no->prox); }

void ordenarB(){ No anter, atual; int aux = 0; if(ponteiroFinal == NULL){ printf("Lista vazia.\n"); return; }else{ for(int i = 0; i<TAMANHO-1 ; i++){ anter = ponteiroFinal; atual = ponteiroFinal->prox;

        for(int j=0; j<TAMANHO-1; j++){
            if(anter->dado > atual->dado){
                aux = anter->dado;
                anter->dado = atual->dado;
                atual->dado = aux;
            }
            atual = atual->prox;
            anter = anter->prox;
        }
    }
}

}

void main(){ for(int i=0; i<TAMANHO;i++){ adicionar(rand()); } imprimir(); ordenarB(); imprimir();

}

[LarissaJacobina]

Larissa Jacobina

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TAMANHO 4

// Lista Encadeada de Inteiros
//----------------------------

// Define o tipo No contendo
typedef struct No {
    int dado;
    struct No *prox;
} No;

//Define o primeiro No da lista
No* cabeca = NULL;

// Funcao que define a lista como vazia.
void criarLista() {
    cabeca = NULL;
}

//Funcao que adiciona dados
void adicionarDado(int dado) {
    No* ponteiroNo;
    ponteiroNo = (No *) malloc(sizeof (ponteiroNo));
    if (ponteiroNo == NULL) {
        printf("Lista vazia.\n");
    }

    ponteiroNo->dado = dado;
    ponteiroNo->prox = NULL;
    if (cabeca == NULL)
        cabeca = ponteiroNo;
    else {
        ponteiroNo->prox = cabeca;
        cabeca = ponteiroNo;
    }
}

//Funcao que imprime a lista
void imprimirLista() {
    printf("--------------------------------\n");
    No* ponteiroNo;
    if (cabeca == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    ponteiroNo = cabeca;
    while (ponteiroNo != NULL) {
        if (ponteiroNo->prox !=NULL){
            printFormat01(ponteiroNo);
        }else{
            printFormat02(ponteiroNo);
        }
        ponteiroNo = ponteiroNo->prox;
    }
}

void printFormat01(No* ponteiroNo){
    printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox);
    printf("                  |\n");
    printf("                  V\n");
    printf("      -------------\n");
    printf("      |\n");
    printf("      V\n");
}
void printFormat02(No* ponteiroNo){
    printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox);
    printf("                  |\n");
    printf("                  V\n");
    printf("                 NULL\n");
}

//Funcao que busca dados na lista
void buscarDado(int dado){
    No* ponteiroNo;
    if (cabeca == NULL){
        printf("Lista Vazia\n");
        return;
    }
    ponteiroNo = cabeca;
    while (ponteiroNo != NULL){
        if (ponteiroNo->dado == dado){
            printf("[%d(%p)]\n", ponteiroNo->dado, ponteiroNo);
        }
        ponteiroNo = ponteiroNo->prox;
    }

}

void removerDado(int dado) {
    No *ponteiroNo, *ponteiroAnterior;
    if (cabeca == NULL) {// lista vazia
        return; 
    } else { // lista NAO vazia
        ponteiroNo = cabeca;
        ponteiroAnterior = cabeca;
        while (ponteiroNo != NULL) {
            if (ponteiroNo->dado == dado){
                if (ponteiroNo == cabeca){// removendo o primeiro
                    cabeca = cabeca->prox;
                    free(ponteiroNo);// libera memoria
                    return;
                } 
                else{ // removendo do meio
                    ponteiroAnterior->prox = ponteiroNo->prox;//refaz links
                    free(ponteiroNo);// libera memoria
                    return;
                }
            } 
            else{ // continua procurando na lista
                ponteiroAnterior = ponteiroNo;
                ponteiroNo = ponteiroNo->prox;
            }
        }
        return;
    }
}

//Algoritmo de Ordenação
//----------------------

void bubble(){
    int comp = 0, troca = 0; 
    No* ponteiroNo;
    if (cabeca == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    //Ordena vetor pelo metodo da bolha
    for (int i = 0; i < TAMANHO; i++) {
        ponteiroNo = cabeca;
        while (ponteiroNo->prox != NULL) {
            int atual = ponteiroNo->dado;
            int proximo = ponteiroNo->prox->dado;
            comp++;
            if (atual > proximo) {
                ponteiroNo->dado = proximo;
                ponteiroNo->prox->dado = atual;
                troca = troca + 1;
            }
            ponteiroNo = ponteiroNo->prox;
        }           
    }

    printf("\n");

    //Mostra valores do vetor ordenado   
    imprimirLista();

    printf("\nComparações: %d", comp);
    printf("\nTrocas: %d", troca);
    printf("\n");
}

void main() {
    criarLista();

    //Definindo valores aleatórios
    srand(time(NULL)); //Cria uma semente para numeros aleatorios
    for (int i = 0; i < TAMANHO; i++) {
        adicionarDado(rand() % 10); //Atribui um inteiro aleatorio entre 0 e 9
    }

    //Imprimindo a Lista Encadeada com valores aleatórios
    printf("\n Lista encadeada com valores aleatórios\n");
        imprimirLista();

    //Ordenando e Imprimindo a Lista Encadeada com Bubble
    printf("\n Lista encadeada com valores ordenados\n");
    bubble();
        //removendo um dado da lista encadeada
        removerDado(2);
        printf("--------------\n");
        imprimirLista();
}

[Tainara-Ataides]

Tainara Moura De Ataídes

include

include

include

define TAMANHO 4

// Define o tipo No contendo typedef struct No{ int dado; struct No *prox; } No;

//Define o ultimo No da lista No* ponteiroFinal = NULL;

//Funcao que adiciona dados void adicionarDado(int dado) { No ponteiroNo; ponteiroNo = (No ) malloc(sizeof (ponteiroNo)); ponteiroNo->dado = dado; ponteiroNo->prox = NULL; if (ponteiroFinal == NULL) ponteiroFinal = ponteiroNo; else { ponteiroNo->prox = ponteiroFinal; ponteiroFinal = ponteiroNo; } }

//Funcao que imprime a lista void imprimirLista() { No* ponteiroNo; if (ponteiroFinal == NULL) { printf("Lista vazia.\n"); return; } ponteiroNo = ponteiroFinal; while (ponteiroNo != NULL) { if (ponteiroNo->prox !=NULL){ printFormat01(ponteiroNo); }else{ printFormat02(ponteiroNo); } ponteiroNo = ponteiroNo->prox; }

}

void buscarDado(int dado){ No* ponteiroNo; for (int i =0; i <TAMANHO; i++){ printf("%d\t", dado [i]); } for(int i = 1; i <TAMANHO; i++){ for(int j =0; j <TAMANHO-1; j++){ if (dado [j] > dado [j + 1]){ No = dado[j]; dado [j] = dado [j + 1]; dado[j+1] = No; } } } if (ponteiroFinal == NULL) { printf("Lista vazia.\n"); return; } ponteiroNo = ponteiroFinal; while (ponteiroNo != NULL) { if (ponteiroNo->dado == dado) printf("[%d(%p)]\n", ponteiroNo->dado, ponteiroNo); ponteiroNo = ponteiroNo->prox; } }

void removerDado(int dado) { No ponteiroNo, ponteiroAnterior; if (ponteiroFinal == NULL) {// lista vazia return; } else { // lista NAO vazia ponteiroNo = ponteiroFinal; ponteiroAnterior = ponteiroFinal; while (ponteiroNo != NULL) { if (ponteiroNo->dado == dado){ if (ponteiroNo == ponteiroFinal){// removendo o primeiro ponteiroFinal = ponteiroFinal->prox; free(ponteiroNo);// libera memoria return; } else{ // removendo do meio ponteiroAnterior->prox = ponteiroNo->prox;//refaz links free(ponteiroNo);// libera memoria return; } } else{ // continua procurando na lista ponteiroAnterior = ponteiroNo; ponteiroNo = ponteiroNo->prox; } } return; } }

void main() { // Insere na lista os numeros de 1 a 3 for (int i = 1; i <= 4; i++) adicionarDado(i); imprimirLista(); removerDado(2); printf("--------------\n"); imprimirLista(); buscarDado(3); }

[Samuel-Amaro]

/*Aluno: Samuel Amaro do Nascimento*/

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

// Define o tipo No contendo
typedef struct No{
    int dado;
    struct No *prox;
} No;

void printFormat01(No* ponteiroNo);
void printFormat02(No* ponteiroNo);

//Define o ultimo No da lista
No* ponteiroFinal = NULL;
//Funcao que adiciona dados cria um primeiro no e aloca um novo no sempre que e criado
void adicionarDado(int dado) {
    No* ponteiroNo;
    ponteiroNo = (No *) malloc(sizeof (ponteiroNo));
    ponteiroNo->dado = dado;
    ponteiroNo->prox = NULL;
    if (ponteiroFinal == NULL){
        ponteiroFinal = ponteiroNo;
    }else {
        ponteiroNo->prox = ponteiroFinal;
        ponteiroFinal = ponteiroNo;
    }

}

//Funcao que imprime a lista
void imprimirLista() {
    No* ponteiroNo;
    if (ponteiroFinal == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    ponteiroNo = ponteiroFinal;
    while (ponteiroNo != NULL) {
        if (ponteiroNo->prox !=NULL){
            printFormat01(ponteiroNo);
        }else{
            printFormat02(ponteiroNo);
        }
        ponteiroNo = ponteiroNo->prox;
    }

}

void printFormat01(No* ponteiroNo){
    printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox);
    printf("                  |\n");
    printf("                  V\n");
    printf("      -------------\n");
    printf("      |\n");
    printf("      V\n");
}
void printFormat02(No* ponteiroNo){
    printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox);
    printf("                  |\n");
    printf("                  V\n");
    printf("                 NULL\n");
}

void buscarDado(int dado){
    No* ponteiroNo;
    if (ponteiroFinal == NULL) {
        printf("Lista vazia.\n");
        return;
    }
    ponteiroNo = ponteiroFinal;
    while (ponteiroNo != NULL) {
        if (ponteiroNo->dado == dado)
            printf("[%d(%p)]\n", ponteiroNo->dado, ponteiroNo);
        ponteiroNo = ponteiroNo->prox;
    }
}

//função que remove um no implemetando pelo professor mendes
void removerDado(int dado) {
    No *ponteiroNo, *ponteiroAnterior;
    if (ponteiroFinal == NULL) {
        return;
    } else { // lista NAO vazia
        ponteiroNo = ponteiroFinal;
        ponteiroAnterior = ponteiroFinal;
        while (ponteiroNo != NULL) {
            if (ponteiroNo->dado == dado){
                if (ponteiroNo == ponteiroFinal){
                    ponteiroFinal = ponteiroFinal->prox;
                    free(ponteiroNo);
                    return;
            }
            else{
                    ponteiroAnterior->prox = ponteiroNo->prox;
                    free(ponteiroNo);
                    return;
                }
            }
            else{
                ponteiroAnterior = ponteiroNo;
                ponteiroNo = ponteiroNo->prox;
            }

        }
        return;
    }
}

//função que ordenada  a lista pelo metodo da bolha
void ordenaLista();
void ordenaLista()
{
 No *percorreLista;
 percorreLista = ponteiroFinal;
 No *percorreListaAux;
 percorreListaAux = ponteiroFinal;
 if(percorreLista == NULL) {
    printf("Não tem como ordenar uma Lista Vazia!\n");
 }
 else {
        //vai ordenar pelo metodo da bolha
        while(percorreLista->prox != NULL) {
             while(percorreListaAux->prox != NULL) {
                   No *aux1 = ponteiroFinal;
                   while(aux1->prox != NULL) {
                        No *proximo = aux1->prox;
                        if(aux1->dado > proximo->dado) {
                           int aux = aux1->dado;
                           aux1->dado = proximo->dado;
                           proximo->dado = aux;
                         }
                         //int i = 0;
                         //printf("i do i = %d\n",i);
                         aux1 = aux1->prox;
                   }
              //int i = 0;
              //printf("i = %d\n",i);
              percorreListaAux = percorreListaAux->prox;
             }
             //int e = 0;
             //printf("e = %d\n",e);
             percorreLista = percorreLista->prox;
        }

 }
}

void main() {
 srand(time(NULL)); //para gerar numeros Aleatorios
 for(int i = 0; i < 20; i += 1)
     adicionarDado(rand() % 100); //cria novos nos com dados aleatorios
 imprimirLista();
 ordenaLista();
 imprimirLista();
}

[Judy-Ellen]

Judy Ellen Vera Martins

include

include

include

define TAMANHO 5

// Definir o tipo No contendo typedef struct No { int dado; struct No *prox; } No;

//Definir o primeiro No da lista No* topo = NULL;

// Definir a lista como vazia. void criarLista() { topo = NULL; } //Adicionar dados void adicionarDado(int dado) { No ponteiroNo; ponteiroNo = (No ) malloc(sizeof (ponteiroNo)); if (ponteiroNo == NULL) { printf("Lista vazia.\n"); } ponteiroNo->dado = dado; ponteiroNo->prox = NULL; if (topo == NULL) topo = ponteiroNo; else { ponteiroNo->prox = topo; topo = ponteiroNo; } } //Imprimir a lista void imprimirLista() { No ponteiroNo; if (topo == NULL) { printf("Lista vazia.\n"); return; } ponteiroNo = topo; while (ponteiroNo != NULL) { if (ponteiroNo->prox !=NULL){ printFormat01(ponteiroNo); }else{ printFormat02(ponteiroNo); } ponteiroNo = ponteiroNo->prox; } } void printFormat01(No ponteiroNo){ printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox); printf(" |\n"); printf(" V\n"); printf(" -------------\n"); printf(" |\n"); printf(" V\n"); } void printFormat02(No ponteiroNo){ printf("[%d(%p)|%p]\n", ponteiroNo->dado, ponteiroNo, ponteiroNo->prox); printf(" |\n"); printf(" V\n"); printf(" NULL\n"); } //Buscar dados na lista void buscarDado(int dado){ No ponteiroNo; if (topo == NULL){ printf("Lista Vazia\n"); return; } ponteiroNo = topo; while (ponteiroNo != NULL){ if (ponteiroNo->dado == dado){ printf("[%d(%p)]\n", ponteiroNo->dado, ponteiroNo); } ponteiroNo = ponteiroNo->prox; } } //Remover dados void removerDado(int dado) { No ponteiroNo, ponteiroAnterior; if (topo == NULL) {// lista vazia return; } else { // lista NAO vazia ponteiroNo = topo; ponteiroAnterior = topo; while (ponteiroNo != NULL) { if (ponteiroNo->dado == dado){ if (ponteiroNo == topo){// remover o primeiro topo = topo->prox; free(ponteiroNo);// liberar memoria return; } else{ // remover do meio ponteiroAnterior->prox = ponteiroNo->prox;//refaz links free(ponteiroNo);// liberar memoria return; } } else{ // continuar procurando na lista ponteiroAnterior = ponteiroNo; ponteiroNo = ponteiroNo->prox; } } return; } } void bubble(){ int comp = 0, troca = 0; No* ponteiroNo; if (topo == NULL) { printf("Lista vazia.\n"); return; } //Ordenar o vetor pelo metodo bolha for (int i = 0; i < TAMANHO; i++) { ponteiroNo = topo; while (ponteiroNo->prox != NULL) { int atual = ponteiroNo->dado; int proximo = ponteiroNo->prox->dado; comp++; if (atual > proximo) { ponteiroNo->dado = proximo; ponteiroNo->prox->dado = atual; troca = troca + 1; } ponteiroNo = ponteiroNo->prox; }
} printf("\n");
//Mostra valores do vetor ordenado
imprimirLista();
printf("\nComparações: %d", comp); printf("\nTrocas: %d\n", troca); } void main() { criarLista(); //Definindo valores aleatórios srand(time(NULL)); //Criar uma semente para os números aleatorios for (int i = 0; i < TAMANHO; i++) { adicionarDado(rand() % 10); //Atribuir um nùmero inteiro e aleatorio entre 0 e 9 } //Imprimindir a Lista Encadeada com valores aleatórios printf("Lista encadeada com valores aleatórios\n"); imprimirLista(); //Ordenandar e Imprimindir a Lista Encadeada com Bubble printf("Lista encadeada com valores ordenados\n"); bubble(); //remover um dado da lista encadeada removerDado(2); imprimirLista(); }