Ir para o conteúdo
mundo

Partir Lista ligada a meio

Mensagens Recomendadas

mundo

Bom dia, estou com duvidas a resolver um exercicio aqui de exame.

O enunciado é o seguinte:

Defina uma função break_list que parta uma lista ligada em dois segmentos de igual comprimento, devolvendo o endereço da lista correspondente ao segundo. Se a lista inicial tiver comprimento ímpar, o segundo segmento terá a mais um elemento do que o primeiro. Por exemplo, se a lista original tiver

os elementos 1,2,3,4,5,6,7, após a execução da função, a lista passa a ter apenas os valores 1,2,3 e o resultado da função deverá ser a lista com os elementos 4,5,6,7.

A função a definir só terá que produzir resultados válidos para listas de comprimento superior ou igual a 2.

Certifique-se que a solução apresentada executa em tempo linear no tamanho da lista e que não aloca memória adicional.

O codigo que eu tenho, e nao esta a funcionar bem, penso eu, é este:

typedef struct lnode {
int info;
struct lnode *next;
} Lnode, *List;

int comp(List l){
int i;

if(l == NULL) return 0;

while(l->next != NULL){
	i++;
}
return i;
}

List break_list(List l){
List aux, aux2;
int i, j, tam;

tam = comp(l);

if(l == NULL || comp(l) < 2) return;

if(comp(l)%2 != 0){

	for(i=0;i<(tam/2)-1 ; i++){
		aux->info = l->info;
		if(l->next == NULL){
			return NULL;
		}
		aux->next = l->next;
	}

	for(j = (tam/2); j < tam ; j++){
		aux2->info = l->info;
		if(l->next == NULL){
			return NULL;
		}
		aux2->next = l->next;
	}


}
else{

	for(i=0;i<(tam/2) ; i++){
		aux->info = l->info;

		if(l->next == NULL){
			aux->next = NULL;
		}
		aux->next = l->next;
	}

	for(j = (tam/2); j<tam ; j++){
		aux2->info = l->info;

		if(l->next == NULL){
			aux2->next = NULL;
		}
		aux2->next = l->next;
	}

}
return aux2;
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Xiii ... não precisas de nada disso.

Repara que se arranjares dois ponteiros para percorrer a lista em que um percorre devagarinho e outro percorre depressa (de 2 em 2), quando o ponteiro rápido chegar ao fim, o ponteiro lento está a meio :)

Precisas de ter atenção a erros "off by one", mas basicamente é isto.

Editado por pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Mas ao fazer isso, caso seja impar a primeira parte não vai ter mais um que a segunda?

"Precisas de ter atenção a erros "off by one", mas basicamente é isto." É com isto que queres dizer isso?

Se for, tenho que depois passar manualmente o elemento a mais para a segunda parte certo?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Não, não, não. Não passas nada de lado nenhum para outro lado: fica tudo exactamente onde está.

Só precisas de alterar um único link: o link do último elemento da primeira metade da lista.

Por exemplo, para a lista {1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7} vais ao "3->next" e metes a NULL e devolves o valor que lá estava antes.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

nem um nem outro

Lnode * l1 = NULL, * l2 = NULL; // dois iteradores de nós

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

sim é, em termos de significado é o mesmo

no entanto, o que apresentei lesse como dois ponteiros para nós de uma lista e o que apresentaste lesse como duas listas distintas.

o que escrevi era uma dica de como chegares à solução


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Se for asneira peço, mas digam-me se assim está correcto

List break_list(List l){

   Lnode *l1 = NULL, *l2 = NULL;

   for(l1 = l; l1 != NULL; l1 = l1->next){
    for(l2 = l; l2 != NULL; l2 = l2->next + 2){

	    l2->info = l->info;
	    if(l2->next == NULL){
		    l1->next = NULL;
	    }
    }
   }
   return l2;
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Não estou mesmo a conseguir implementar isto.

Deixa-me ver se percebi, a estrategia que o pmg referiu, seria de ter por exemplo, um while em que cada iteraçao incrementa 2, e dentro desse while 1 ciclo for para percorrer o que ira andar mais devagar, assim que o while parar, coloco o ponteiro->next do que anda devagar a apontar para nulo, e retorno o ponteiro rapido?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não

ele nunca referiu um ciclo dentro de um ciclo

o que ele disse foi um ciclo só em que os ponteiros "andam a velocidades diferentes"


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Imagina a lista {1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8};

arranja dois ponteiros (lento e rapido) e mete-os a apontar para o 1

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 2; o rapido aponta para 3)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 3; o rapido aponta para 5)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 4; o rapido aponta para 7)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 5; o rapido aponta para NULL)

Pronto!

O ponteiro lento aponta para o elemento que deve ser o primeiro da metade "nova" da lista (nesta situacao -- tens de verificar se acontece assim em todas as situacoes)

em codigo seria qualquer coisa assim

while (rapido != NULL) {
 lento = lento->next;
 rapido = rapido->next->next;
}

MAS ATENCAO QUE O CODIGO ESTA MUITO INCOMPLETO! Tens que acertar onde comecam os ponteiros lento e rapido, tens que validar o acesso intermedio do ponteiro rapido, ...


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Será isto?

List break_list(List l){

   Lnode *lento = l, *rapido = l;

   while(rapido != NULL){
    lento = lento->next;
    rapido = rapido->next->next;
    if(rapido->next->next == NULL){
	    rapido = lento->next;
	    lento->next = NULL;
    }
   }
   return rapido;
}

Ou ainda está incompleto?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

pelas respostas que estás a apresentar só posso depreender que não estás sequer a testar as hipóteses que apresentas

metes algo parecido com o que foi te explicado e parece nem sequer queres perceber o que está a acontecer

ao perceber, certos erros que aparecem no teu código nem sequer te passavam pela cabeça


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Estou a testar, e a fazer com uma folha ao lado, acho que so falta colocar a info, so nao estou a colocar a main, porque é algo que onde estou a estudar nunca fizemos muito, para testar, supostamente com os meus rascunhos, penso que isso funcionaria

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Vou fazer o desenho com as iterações a ver se percebi, e juntar o codigo, e agradecia que me corrigissem por favor:

List break_list(List l){

   Lnode *lento = l, *rapido = l;

   while(rapido->next != NULL){
    lento = lento->next;
    rapido = rapido->next->next;
    if(rapido->next == NULL){
	    rapido = lento;
	    lento = NULL;
    }
   }
   return rapido;
}

Por exemplo a lista ligada impar: 1->2->3->4->5->6->7

inicializaçao: lento = 1, rapido = 1

1ª iteração: lento = 2, rapido = 3

2ªiteraçao: lento = 3, rapido = 5

3ª iteração: lento = 4, rapido = 7

o rapido passa a ser o local onde esta o lento

coloca o local onde o lento se encontra a nulo

4ª iteraçao: ja nao entra no while

A minha duvida prende-se na 3ª iteraçao, e se o if está correto

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

1º - atribuir NULL ao ponteiro "lento" não altera nada na lista, estás somente a alterar o valor do ponteiro.

2º - o ponteiro "rapido" fica com o valor de lento (4), mas no entanto continuas a não "partir" a lista

3º - agora experimenta com uma lista com um número par de elementos


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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Estou mesmo a nora, eu já percebi que caso a lista seja par, esse algoritmo nao funciona, sera que me podes dar mais um empurranzinho? com o a condiçao no if a ser rapido->next->next, passa a funcionar para listas pares também, não estou a conseguir partir a lista a metade

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Se rapido->next for NULL, nao podes fazer rapido->next->next!

rapido->next->next é o mesmo que (rapido->next)->next que, se for NULL, seria NULL->next.

Editado por pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Mas se rapido->next for NULL já nao entra no ciclo, que situaçao pode isso acontecer?

Eu percebi, que só aquele if ali, isto não vai dar bem, poq o while vai continuar a executar, nao estou a conseguir mesmo fazer a parte de partir a lista

Editado por mundo

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
mundo

Neste momento o código está assim, acham que se encontra algo incorreto?

List break_list(List l, List *parte1, List *parte2) {

Lnode *lento = l, *rapido = l->next;

if (l == NULL || l->next == NULL) {
	*parte1 = l;
	*parte2 = NULL;
} else {
	lento = l;
	rapido = l->next;
	while (rapido != NULL) {
		rapido = rapido->next;

		if (rapido != NULL) {
			lento = lento->next;
			rapido = rapido->next;
		}
	}
	// O lento está antes do meio da lista, entao separa-se em 2 a lista
	*parte1 = l;
	*parte2 = lento->next;
	lento->next = NULL;
}
return *parte2;
}

Edit: enganei me a colar o codigo, esta correto agora penso eu

Editado por mundo

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo
if (rapido == NULL) {  // só entra no if se rapido for igual a NULL
 lento = lento->next;
 rapido = rapido->next; // se rapido é NULL como podes aceder a rapido ->next ?????
}


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.