"Bubble Sort" em listas ligadas

PCaseiro · April 18, 2015 at 07:29 PM

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

}

Edited April 18, 2015 at 08:20 PM by apocsantos
geshi

HappyHippyHippo · April 18, 2015 at 07:46 PM

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)

PCaseiro · April 18, 2015 at 08:08 PM

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.

HappyHippyHippo · April 18, 2015 at 08:21 PM

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)

Edited April 18, 2015 at 08:25 PM by HappyHippyHippo

PCaseiro · April 18, 2015 at 08:25 PM

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)

Edited April 18, 2015 at 08:26 PM by PCaseiro

HappyHippyHippo · April 18, 2015 at 08:26 PM

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 ?

PCaseiro · April 18, 2015 at 08:27 PM

e que código tens agora ?

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

HappyHippyHippo · April 18, 2015 at 08:28 PM

e que código tens agora ?

PCaseiro · April 18, 2015 at 08:31 PM

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

Edited April 18, 2015 at 11:11 PM by apocsantos
geshi

HappyHippyHippo · April 18, 2015 at 08:33 PM

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

PCaseiro · April 18, 2015 at 08:35 PM

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

Edited April 18, 2015 at 08:39 PM by PCaseiro

HappyHippyHippo · April 18, 2015 at 08:42 PM

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

PCaseiro · April 18, 2015 at 08:44 PM

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.

PCaseiro · April 18, 2015 at 09:00 PM

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?

Edited April 18, 2015 at 11:11 PM by apocsantos
geshi

HappyHippyHippo · April 18, 2015 at 09:25 PM

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 ?

PCaseiro · April 18, 2015 at 09:30 PM

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?

PCaseiro · April 18, 2015 at 09:43 PM

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 😕 , enganado?

Edited April 18, 2015 at 11:12 PM by apocsantos
geshi

HappyHippyHippo · April 18, 2015 at 09:49 PM

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;

 // ...
}

"Bubble Sort" em listas ligadas

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Important Information