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

PCaseiro

"Bubble Sort" em listas ligadas

Mensagens Recomendadas

PCaseiro

Boa noite malta! Basicamente este exercício pede para implementar uma função do género "bubble sort" com listas simplesmente ligadas. O programa corre bem (mostra a lista corretamente ordenada) mas no final a consola crasha :/

Alguma sugestão?

#define ITEM_TYPE int
typedef struct lnode* List;



typedef struct lnode{
ITEM_TYPE info;
List next;
}List_node;

void ordenalista(List lista){

int contador = 0, i;
/* lista é uma lista recebida */

List head = lista; /* termos sempre disponível o início da lista*/
List actual = NULL; /*lista vazia, ou nó */
List temp = NULL;

if(head == NULL || head->next == NULL){ /* caso de lista vazia ou so com 1 elemento*/
 printf("A lista esta vazia ou tem apenas um elemento");
 return 0;
}


while(head != NULL){ /* contar quantos elementos tem a lista*/
 contador++;
 head = head->next;
 printf("%d \n", contador);
}


for(i=0; i<contador; i++){ /* percorrer todos os elementos da lista*/

 while(head->next != NULL){ /* enquanto não chegarmos ao final da lista*/
	 if(head->info > head->next->info){ /* se o valor do atual for maior que o valor do seguinte*/
		 temp = head->next;
		 head->next = head->next->next; /* não precisamos de usar actual->data, apenas precisamos de mudar os ponteiros*/
		 temp->next = head;
	 }
 }
}
}


void ex213(){

int numero;
List lista;
lista = cria_lista();

while((scanf("%d",&numero)) == 1){ /* lê da esquerda para a direita. SCANF DÁ 1 SE INSERIR INTEIRO, 0 CASO CONTRÁRIO */
 insere_listadesordenado(lista, numero);
}

ordenalista(lista);
imprime_lista(lista);

}

Editado por apocsantos
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

existem vaários problemas, mas vou somente abordar o que referes

o teu processo de troca:

// trocar head com head->next

//      +------+     +------+
// ---->| head |---->| next |---->
//      +------+     +------+

temp = head->next;
//                     temp
//                      |
//                      V
//      +------+     +------+
// ---->| head |---->| next |---->
//      +------+     +------+

head->next = head->next->next;
//                     temp
//                      |
//                      V
//      +------+     +------+
// ---->| head |-+   | next |--+->
//      +------+ |   +------+  |
//               +-------------+

temp->next = head;
//                     temp
//          +------------|----+
//          V            V    |
//      +------+     +------+ |
// ---->| head |-+   | next |-+   +->
//      +------+ |   +------+     |
//               +----------------+

por outras palavras : nem sei como podes dizer algo como:

O programa corre bem (mostra a lista corretamente ordenada)


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

Na minha cabeça o que pensei foi se head->info > head->next->info vou ter que trocar estes dois nós logo, no temp coloco head->next porque vou igualar head->next ao nó seguinte ou seja head->next->next. Mas agora que vejo esta ultima parte do temp->next = head não faz muito sentido. E só disse que corria bem porque apresenta bem o resultado, embora crashe no final.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não estou a dizer que o teu processo está completamente errado.

eu dou-te uma dica:

- a troca dos elementos L(i) e L(i + 1) é feita no ponto L(i - 1)

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

Então e se fizer head->next->next (que é o seguinte a head->next e que é menor que este) = temp? Imprimiu bem mas crashou again. Não estou a ver como o L(i-1) pode servir, se bem que ele serve para "ligar" ao L(i)

Editado por PCaseiro

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Então e se fizer head->next->next (que é o seguinte a head->next e que é menor que este) = temp? Imprimiu bem mas crashou again.

e que código tens agora ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

e que código tens agora ?

tenho o mesmo código inicial mas mudei o temp->next = head para head->next->next = temp;

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

#define ITEM_TYPE int
typedef struct lnode* List;

typedef struct lnode{
ITEM_TYPE info;
List next;
}List_node;
void ordenalista(List lista){
int contador = 0, i;
/* lista é uma lista recebida */
List head = lista; /* termos sempre disponível o início da lista*/
List actual = NULL; /*lista vazia, ou nó */
List temp = NULL;
if(head == NULL || head->next == NULL){ /* caso de lista vazia ou so com 1 elemento*/
	 printf("A lista esta vazia ou tem apenas um elemento");
	 return 0;
}

while(head != NULL){ /* contar quantos elementos tem a lista*/
	 contador++;
	 head = head->next;
	 printf("%d \n", contador);
}

for(i=0; i<contador; i++){ /* percorrer todos os elementos da lista*/
	 while(head->next != NULL){ /* enquanto não chegarmos ao final da lista*/
			 if(head->info > head->next->info){ /* se o valor do atual for maior que o valor do seguinte*/
					 temp = head->next;
					 head->next = head->next->next; /* não precisamos de usar actual->data, apenas precisamos de mudar os ponteiros*/
					 head->next->next = temp;
			 }
	 }
}
}

void ex213(){
int numero;
List lista;
lista = cria_lista();
while((scanf("%d",&numero)) == 1){ /* lê da esquerda para a direita. SCANF DÁ 1 SE INSERIR INTEIRO, 0 CASO CONTRÁRIO */
	 insere_listadesordenado(lista, numero);
}
ordenalista(lista);
imprime_lista(lista);
}

Editado por apocsantos
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

essa alteração não tem sentido nenhum ...

Estou a fazer 1 nó à frente a mais não estou? devia estar a fazer com o atual que é head com o seguinte que é head->next?

Eu compreendo se tiver b a c (a<b<c) e quiser trocar a e b faço:

temp == b;

b == a;

a == temp

mas com nós esta-me a dar uns nós na cabeça :s

Editado por PCaseiro

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

isto é o que tens agora:

// trocar head com head->next

//      +------+     +------+
// ---->| head |---->| next |---->
//      +------+     +------+

temp = head->next;
//                     temp
//                      |
//                      V
//      +------+     +------+
// ---->| head |---->| next |---->
//      +------+     +------+

head->next = head->next->next;
//                     temp
//                      |
//                      V
//      +------+     +------+
// ---->| head |-+   | next |--+->
//      +------+ |   +------+  |
//               +-------------+

head->next->next = temp;
//                     temp
//                       +----+---------------+
//                       V    |               |
//      +------+     +------+ |      +------+ |
// ---->| head |-+   | next |-+   +->| next |-+
//      +------+ |   +------+     |  +------+
//               +----------------+

achas isso correcto ?

se não estás a perceber como resolver, faz um desenho. tudo fica mais claro


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

isto é o que tens agora:

// trocar head com head->next

//	  +------+	 +------+
// ---->| head |---->| next |---->
//	  +------+	 +------+

temp = head->next;
//					 temp
//					  |
//					  V
//	  +------+	 +------+
// ---->| head |---->| next |---->
//	  +------+	 +------+

head->next = head->next->next;
//					 temp
//					  |
//					  V
//	  +------+	 +------+
// ---->| head |-+   | next |--+->
//	  +------+ |   +------+  |
//			   +-------------+

head->next->next = temp;
//					 temp
//					   +----+---------------+
//					   V	|			   |
//	  +------+	 +------+ |	  +------+ |
// ---->| head |-+   | next |-+   +->| next |-+
//	  +------+ |   +------+	 |  +------+
//			   +----------------+

achas isso correcto ?

se não estás a perceber como resolver, faz um desenho. tudo fica mais claro

Vou fazer isso e vou começar de raiz, não me parece que esta versão vá dar a lado algum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

O que me está a fazer confusão é que o meu stor disse para usarmos esta estrutura:

typedef struct lnode* List;

typedef struct lnode{
ITEM_TYPE info;
List next;
}List_node;

enquanto que o mais usual que vejo é:

struct node
{
int data;
struct node *next;
};

qual é a relação entre estas duas estruturas? fazer List lista é o mesmo que structnode *start = NULL?

Editado por apocsantos
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

o teu "stor" tem um mau hábito de poluir o código com tipos desnecessários e/ou com má descrição.

no que toca às duas declarações, não praticamente a mesma coisa, só que a segunda é mais limpa.

a terceira pergunta não faz sentido, como é que uma instanciação simples pode ser igual a uma instanciação com inicialização ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

o teu "stor" tem um mau hábito de poluir o código com tipos desnecessários e/ou com má descrição.

no que toca às duas declarações, não praticamente a mesma coisa, só que a segunda é mais limpa.

a terceira pergunta não faz sentido, como é que uma instanciação simples pode ser igual a uma instanciação com inicialização ?

Mas eu ao fazer List lista; estou a criar um nó certo?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
PCaseiro

Sorry double post mas penso que finalmente entendi!

Se fizer:

void bubbleSort(struct node *start)
{
int swapped, i;
struct node *ptr1;
struct node *lptr = NULL;

if (ptr1 == NULL)
 return;

com a estrutura mais simples e concisa ele associa ptr1 à lista que passamos pelo que pode logo verificar se está vazia ou não.

Se usar a estrutura que tenho usado tenho de fazer:

void bubbleSort(List lista)
{
int swapped, i;
List ptr1;
List ptrlist = NULL;
ptr1 = lista;

if (ptr1 == NULL)
 return;

Ou estou, outra vez :confused: , enganado?

Editado por apocsantos
geshi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

como disse, fundamentalmente, são a mesma coisa, por isso para verificar se é vazia, basta:

struct node* bubbleSort1(struct node* list) {
 if (!list)     // o mesmo que "list == NULL"
   return NULL;

 // ...
}

List bubbleSort2(List list) {
 if (!list)     // o mesmo que "list == NULL"
   return NULL;

 // ...
}


IRC : sim, é algo que ainda existe >> #p@p

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.