Jump to content

eeliminar repeticoes em listas ligadas


suzy
 Share

Recommended Posts

malta

é o seguinte, tenho uam lista ligada simples, e quero eliminar os nomes que se repetem.

ora bem, á medida que vou percorrendo a lista ligada, tenho de comparar de o nome do no inicial com os nomes dos outros nós se for igual elimina, sendo assim em cada iteracção.

é assim o raciocionio??

obrigada

Link to comment
Share on other sites

penso que o que estas a dizer irá ter uma complexidade de O(n^2).

se tiveres hipotese de teres feito uma hashtable, iria iterando a lista e inserindo na hashtable qdo existisse uma colisão e em que o valor fosse igual ao valor da lista retiraria esse valor da lista, depois de iterar toda a lista apagaria a hashtable da memoria e assim com uma complexidade O(n) conseguiria fazer esse processo, ter  uma lista sem repeticoes.

se não interessa a complexidade do algoritmo, penso que sim possas fazer dessa maneira.

boas programacoes

Link to comment
Share on other sites

Outra solução simples seria manipular a forma como inseres na lista, podes inserir já de acordo com o teu problema.

Claro que ias ficar com uma inserção mais cara, mas poupas no resto.

Mas pessoalmente penso que ia para uma hashtable também...

Link to comment
Share on other sites

malta

é o seguinte, tenho uam lista ligada simples, e quero eliminar os nomes que se repetem.

ora bem, á medida que vou percorrendo a lista ligada, tenho de comparar de o nome do no inicial com os nomes dos outros nós se for igual elimina, sendo assim em cada iteracção.

é assim o raciocionio??

obrigada

Acho que estás correcta. Em cada iteração tens 2 apontadores: o primeiro percorre os nós da lista um a um, a partir do 1º nó, e o segundo percorre-os também um a um, mas a partir do nó seguinte ao apontado pelo primeiro apontador. Depois é só compará-los, como disseste.

falk0n e QuickFire: tenho quase a certeza que a ajuda que ela está a pedir é para um trabalho escolar, e que tem que usar unicamente a estrutura indicada 😄

Desaparecido.

Link to comment
Share on other sites

Bem, há 3 dias tinha um projecto para entregar que percorria uma lista toda à procura de duplicados no momento da inserção, e demorava 2 minutos num caso teste que tinha de passar em menos de 10 segundos. No meu caso estava a fazer sort da lista antes de fazer output, e o que fiz foi no momento do output, testar se o valor do elemento da lista actual era igual ao seguinte. Só com esta optimização o código passou a resolver o caso mais lento em 2 segundos. 😄

<3 life

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
 Share

×
×
  • 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.