• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

mula_russa

[C++] Ajuda: Ordenar uma lista ligada (Resolvido)

11 mensagens neste tópico

Ola Pessoal.

Estou a fazer um programa e necessito de fazer uma função que me ordene uma lista ligada. Preciso ordenar a lista, que e uma lista de pessoas, alfabeticamente pelo nome, que e um mebro privado de pessoa. Será que alguem me pode ajudar a arranjar um resoluçao para isto? É que já tou farto de andar aqui as cabeçadas mas está dificil.

Obrigado

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pá depois de semanas de volta de listas ligadas devido há cadeira Estruturas de Dados embora o tenha feito em Java a lógica é a mesma.

Bom penso que o melhor método é criar uma lista ligada temporária em seguida corres a lista e lês o primeiro carácter do nome e depois tipo todos o que começam com "A" ele mete na lista temporária depois "B" e por ai adiante no final apaga a lista original e copia a lista temporária para o lugar da original.

É uma método um pouco passivo mas funcional.

Espero ter ajudado  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ola Pessoal.

Estou a fazer um programa e necessito de fazer uma função que me ordene uma lista ligada. Preciso ordenar a lista, que e uma lista de pessoas, alfabeticamente pelo nome, que e um mebro privado de pessoa. Será que alguem me pode ajudar a arranjar um resoluçao para isto? É que já tou farto de andar aqui as cabeçadas mas está dificil.

Obrigado

magician, esse método é perfeitamente funcional e simples, logo é o que aconselho ( Keep it simple ;) ). Mas os professores normalmente insistem nas suas soluções retrógradas do século passado pois acham que são mais proveitosas pedagogicamente. Esquecem-se que um bom programador é o que se desenrasca qdo precisa e que escreve código que funcione consistentemente.

A solução que os professores querem é uma em que retires e insiras elementos na lista um a um para teres que actualizar os ponteiros.

Faz assim:

cria uma função que retire um elemento o guarde e actualize os ponteiros

cria outra para inserir um elemento, e actualizar os ponteiros.

Usa um algoritmo de ordenação que recorra a essas duas.

Quicksort por exemplo

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É isso é verdade os profs gostam de complicar e isso ta comprovado ;)

Cada vez que me lembro de ter feito um editor de palavras com listas ligadas :S té me dá arrepios :S

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

os profs não gostam só de complicar... pelos menos os meus querem é algoritmos eficientes, e querem que saibamos por que razão são eficientes (ou não).

assim à primeira vista, o método que o magician sugeriu ia ter complexidade O(n2), quando que existem algoritmos que resolvem o tempo O(n*log n).

no entanto é um pouco complicado aplicar algoritmos de ordenação em listas ligadas, acho que a forma mais simples de resolver o problema passa por copiar a lista ligada para um array, ordenar o array e depois voltar a criar a lista ligada. isto resolve-te o problema sem aumentar a sua complexidade.

para ordenares o array tens as funções do C, qsort, heapsort e mergesort (por exemplo).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

@Rui Carlos

Já agora podias explicar como calculas a complexidade dos algoritmos ?? é que dei isso a ED mas ainda nao consegui perceber e os apontamentos dos profs não explicam ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens vários métodos para fazer isso. e podes faze-lo do mesmo modo que num vector (tens e q ter as variaveis necessarias para guardar os enderecos).

-----------

Se queres ordenar alfabeticamente uma coisa que podes fazer é realmente criar outra lista (ou seja declarar um novo apontador do tipo de nó que tens) mas em vez de copiar os nós para esse apontador moves.

Ficavas com tipo uma lista A (que aponta para o inicio da lista) e uma nova a B (que ainda não aponta para nada, ou melhor aponta para NULL).

Só precisas de dizer que o B aponta para o nó de A que seria alfabeticamente o primeiro e na lista A dizer que o nó antes desse aponta para o nó que esse apontava.

Nesse caso tens sempre adicionar à lista B não pelo primeiro endereço (o de ;) mas sempre pelo último da lista (terás que ter esse apontador noutra varíavel). Senão estarias a metê-los sempre no iníco da lista e ficavas com ela organizada alfabeticamente mas ao contrário. No fim simplesmente dizias que o apontador da lista A (que estará vazia) aponta para o mesmo endereço que B. Aí terias a lista A perfeitamente organizada. Isto dentro de um ciclo até que A aponte para NULL significa que toda a lista foi transferida para B e tás pronto a alterar o valor de A.

192cq9.th.jpg

A imagem mostra mais ao menos o que irá acontecer em memória e e em lógica (lol paint é do melhor)

-----------

Mas a lista secundária só está aí para ajudar a visualizar as coisas. É mais fácil para nós pensarmos na forma de tirar daqui e por ali.

Esse método é igualmente eficaz se em vez de criares uma lista B. Simplesmente criares uma varíavel Inicio do tipo do nó e dizeres que aponta para A. Em seguida percorres a lista desde de Inicio à procura do nó alfabeticamente menor desde Inicio. Assim que o encontres, o valor apontado por Inicio (que será A no primeiro caso) aponta para esse nó e que o nó antes desse aponta para o mesmo que o nó alfabeticamente menor apontava. O nó alfabeticamente menor passa a apontar para o mesmo que Inicio e Inicio passa a apontar para o nó que "moves-te" porque não vais comparar os outros nós outra vez com ele certo? Isto estaria dentro de um while até que o valor apontado por Inicio apontasse para NULL. Isso quereria dizer que o nó por onde ias começar a procurar ia ser o último logo tinhas acabado a ordenação.

3mt2.th.jpg

Neste caso o  2º passo e 3º passo na imagem ficam iguais porque apesar se o código correr todo na mesma o último nome já está na posição que deve.

------------

Outro método seria procurares ao invés da alfabeticamente menor.. procurares pela maior e metê-la sempre no inicio da lista A. Procuravas a partir de uma variável Inicio que seria sempre o primeiro nó que fosse classificado como o maior alfabeticamente. Pois esse seria o que separava lista ordenada do resto da lista por ordenar. Quando esse nó apontasse para NULL (excepto na primeira busca pois podia ser o últim da lista) quer dizer que chegas-te ao fim da lista e está organizada.

------------

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

obrigado a todos pelas vossas ajudas! Esta comunidade é muito porreiraça!

0

Partilhar esta mensagem


Link 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