Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

PJM

Listas Ligadas BubbleSort

Mensagens Recomendadas

PJM

Pessoal estou a iniciar C e comecei a aprender Listas Ligadas, agora depois de perceber mais ou menos como se cria e apaga listas (ainda não sei remover um certo componente) não sei como é que posso ordenar as listas... Será que me podiam dar uma dica?

O algoritmo do bubblesort é o mais simples e passa por trocar dois a dois, algo do género:

trocou = 1;
for(i=0;i<total-1 && trocou;i++)
{
     trocou = 0;
     for (j=0; j < total - i - 1; j++) 
     {
          if (j[0] > j[1])
          {
             temp = j[0];
             j[0] = j[1]; 
             j[1] = temp;
             trocou = 1;
          }
     }
}

Poderiam dar uma dica?

Cumprimentos,

      PJM

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Eu tenho no meu blog um exemplo com exemplos de funções simples de listas ligadas.

Deixo aqui o link: http://programmingadvt.blogspot.com/2010/04/lista-ligada-exemplo.html

Quanto à ordenação, tens de fazer uma espécie de troca de endereço.

Imagina assim: Se nó actual for maior do que o próximo o nó anterior tem de receber o endereço do próximo nó e o nó actual tem de receber o endereço do nó que está a seguir ao próximo. Agora tenta aplicar isto, se tiveres dúvidas posso dar um exemplo.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PJM

Obrigado pela resposta Localhost.

Eu penso que percebo a teoria, por exemplo:

Inicio (Header)  |    Nó1      |    Nó2

      0                        10              5

O que deveria acontecer é que o Nó anterior (Header) deveria apontar para o Nó2, e o Nó2 a apontar para o no1. No entanto o Nó1 deveria apontar para NULL, será isso?

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

struct products_field {
int price;
struct products_field *next;
} typedef products;

products* Create_List()
{
products *temp = (products*) malloc(sizeof(temp));

if (temp)
{
	temp->price = 0;
	temp->next = NULL;
}

return temp;
}

void AddNode(products *List)
{
products *new = (products*) malloc(sizeof(products));

scanf("%d", &new->price);
new->next = NULL;

for(; List->next; List = List->next);
List->next = new;
}

void PrintNode(products *List)
{
for (; List; List = List->next)	printf("%d\n", List->price);
}

void OrderNode(products *List)
{
products *prev = List, *act = List->next, *temp;
int change = 1;
while (change)
{
	change = 0;
	while (act->next)
	{
		if (prev->price > act->price)
		{
			temp = prev;
			prev = act;
			act = prev;
			change = 1;
		} 
	}
}


}

int main()
{
products *List = Create_List();
int i;

for (i=0;i<4;i++)	AddNode(List);

PrintNode(List->next); //passar header
printf("\n------------\n");
OrderNode(List);
PrintNode(List->next);

return 0;
}

Já tentei fazer isso, funciona tudo menos o OrderNode (é um programa de testes porque quero realmente aprender e não que me façam o trabalho, mas se puderes explicar onde falho ou dar um exemplo agradecia imenso, pois estou mesmo a nora com isto)

Cumprimentos,

    Pedro Magalhães

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
jpedro20

Eu só vi o código assim por alto mas penso que aqui está um erro

if (prev->price >  act->price)
                        {
                                temp = prev;
                                prev = act;
                                act = prev;
                                change = 1;
                        } 

nao devia ser act=temp? É que anteriormente estás a modificar o prev para o valor de act e de seguida o act fica com o mesmo valor.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PJM

Por acaso não, acho que está tudo mal, o problema é que eu não estou a perceber como irei ordenar isto.

Estou a quase 1 semana nisto, que complicação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Como o Nó2 já aponta para NULL então ao fazeres as trocas o Nó1 recebe automaticamente NULL porque recebe o endereço para o qual o Nó2 aponta, que é NULL.

Se noAct > noProx {
  noAnt->prox = noProx;
  noAct->prox = noProx->prox;
  noProx = noAct;
}

Já é um bocado tarde mas acho que é algo como isto. Tenta aplicar.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PJM

Alterei para:

void OrderNode(products *List)
{
products *prev = List, *act = List->next;
int change = 1;
while (change)
{
	change = 0;
	while (act->next)
	{
		if (act->price > prev->price)
		{
			act->next = prev;
			act->next = prev->next;
			prev = act;
			change = 1;
		}
		act = act->next;
		prev = prev->next;
	}
}


}

E continua a não dar.

P.s.-> já consegui ordenar usando um ponteiro de ponteiros e ordenar como se fosse um array, agora queria era mesmo tentar conseguir ordenar a propria lista...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Se tiveres tempo eu sabádo ou assim deixo-te aqui um exemplo com ordenação. Estou sem tempo por hoje e por amanhã.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
..::Myr::..

Boas,

Estou com exactamente o mesmo problema que o PJM. Já tentei vários algoritmos de ordenamento, mas não estou a conseguir. Tenho este código:

void ordena(List head){

    List y, aux, temp, temp2;
    int j, k, n=0, w;

    aux=head->next;

    while(aux){
        n++;
        aux=aux->next;
    }


    for(k=1;k<n;k++){

        temp2=index(head, k);
        y=temp2;

        for(j=k-1;j>=0 && y->EV.P.normal<(index(head, j))->EV.P.normal;j--){
            aux=index(head, j);
            aux->next=aux;
        }

        aux->next=y;
    }
}

Onde a função index serve para calcular o nó em que nos queremos situar, com o seguinte código:

List index(List head, int k){

    int w=0;
    List aux;
    aux=head->next;

    while(w<k){
        w++;
        aux=aux->next;
    }

    return aux;
}

A minha intenção passa por tentar fazer como se faz com um insertion sort para vectores. A função index serve para fazer uma espécie de "lista[k]". Os "->EV.P.normal" são os valores que eu quero comparar.

Ao passar o header da lista a esta função devia ordená-la, mas fica exactamente igual.  :wallbash:

O que será que estou a fazer mal?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PJM

Tu queres ordenar temporariamente a lista, ou queres ordenar a lista original mesmo?

Desculpa a demora e só posso ver o teu problema mais logo ou amanha (tenho entrega até as 23h59m de hoje e estou relativamente atrasado)

Cumps,

    PJM

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
miguel4

boas

Eu ja respondi noutro post que é dificil usar um bublesort em listas porque os elementos não estão seguidos na memória como o vector.

Portanto deixo aqui a mesma resposta que deixei noutro post semelhante:

olha estou um pouco enferujado a trabalhar com listas xD

mas eu fazia antes com um algoritmo desde género apesar de muito lento

    void ordena_lista_preco(Lista lista_eventos){

    Lista aux=lista_eventos;

    int trocas;

    do{

      trocas=0;

      while(aux->proximo!=NULL){

          if( (aux->info) > (aux->proximo->info) ){

            swap(lista_eventos,aux); // troca o nó aux na lista  com o nó seguinte

            trocas++;

          }

          aux=aux->proximo;

      }

      aux=lista_eventos;

    }

    while(trocas!=0);

    }

    void swap(Lista list,Lista x){

      Lista aux=list,auxtroca;

     

      while(aux!=NULL){

          if(aux->proximo==x){

            auxtroca=x->proximo;

            x->proximo=x->proximo->proximo;

            aux->proximo=auxtroca;

            aux->proximo->proximo=x;

            break;

          }

      }

    }

     

desculpa senão funcionar mas sei que pelo menos essa lógica simplifica o problema.

cumps.

PS: não testei o programa


keep it simple!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
miguel4

sim é sem duvida o algoritmo mais rapido para listas apesar da dificil implementação. é um algoritmo de ordenação um pouco complexo mas se o entenderes bem facilita-te em muito o trabalho :)

Nem me tinha lembrado desse. Boa ideia  yyajsayy :D


keep it simple!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PJM

Podes usar bubblesort em listas ligadas de forma simples, arranjas um ponteiro de ponteiros guardando o ponteiro para a lista em questão, passas para esse ponteiro de ponteiros (vector) o endereço de memória de cada nó, depois ordenas o respectivo vector.

No fim ou imprimes o vector ou apontas o header para o primeiro nó, o primeiro nó para o segundo, etc... e quando chegasses ao fim o último elemento iria apontar para NULL.

Cumprimentos,

    PJM

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
miguel4

Olha que isso não é bem verdade.

Existem algoritmos estáveis e instáveis.

Os únicos que tens a certeza que não problemas são os estáveis a não ser que o campo pelo qual ordenas tenha valores únicos, nesses casos podes usar qualquer deles.

Cumps


keep it simple!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
miguel4

O que eu estou a dizer é que para qualquer um funcionar o valor no critério de ordenação não pode ser repetido.

Cumps


keep it simple!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.