Jump to content
mundo

Partir Lista ligada a meio

Recommended Posts

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

Share this post


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

Edited by 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!

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
HappyHippyHippo

nem um nem outro

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

Edited by HappyHippyHippo

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

Share this post


Link to post
Share on other sites
mundo

nem um nem outro

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

isso não é equivalente a ter?

List l1 = NULL, l2 = NULL;

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
HappyHippyHippo

nop ... está errado

volta a ler o primeiro post do @pmg porque estás muito longe do pretendido


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Edited by 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!

Share this post


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

Edited by mundo

Share this post


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

Edited by mundo

Share this post


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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

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.