Jump to content

Partir Lista ligada a meio


mundo

Recommended Posts

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

  • Replies 43
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

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!

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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

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

Link to comment
Share on other sites

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
Link to comment
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
×
×
  • 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.