Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

PJM

Listas Ligadas BubbleSort

Recommended Posts

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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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...

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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?

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other sites
yyajsayy

Podes fazer qualquer tipo de algoritmo, o problema é que se tiveres uma lista com demasiados "nodos" estás meio-dia para o fazer .. mas tudo funciona


"If it don't work the first time, rename it to version 1.0."

http://seguranca-informatica.pt

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.