24

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.188

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Vamos usar os conceitos de lista ligada e heurística de união ponderada para criar pseudo-códigos que realizem funções para MAKE-SET, FIND-SET e UNION.

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Relembremos que lista ligada é composta por células que vão apontar para o próximo elemento.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Tendo esse conceito em mente, podemos criar pseudo-comandos nas formas:

pointed first

//aponta para a lista, se já apontado, vai para o primeiro //elemento

pointed next

//aponta para o próximo elemento, se pointed for o último, //retorna 0

pointed last

//se o primeiro elemento estiver apontado, então aponta para //o último elemento

list size

//se o primeiro elemento estiver apontado, então retorna o //tamanho da lista

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Precisamos relembrar o que cada função desejada faz: MAKE-SET - cria uma lista de elementos, útil para criação de lista encadeada; FIND-SET – acha o elemento representativo da lista; UNION – une os elementos de duas listas, ligando os próximos elementos nos anteriores; APPEN – insere um conteúdo no alvo indicado.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Portanto, os pseudo-códigos então assumem as formas:

MAKE-SET(pointed)

1. pointed next=NIL //não está na lista

2. pointed first=pointed

3. pointed last=pointed

4. pointed size=1

FIND-SET(pointed)

1. return pointed first

UNION(pointed)

1. if pointed1 first size > pointed2 first size

2. then APPEND(pointed1 first, pointed2first)

3. else APPEND(pointed2 first, pointed1first)

APPEND(pointed1, pointed2)

//pointed3 será o alvo a ser preenchido, composto pelas //listas pointed1 e pointed2

1. pointed1 last next = pointed2

2. pointed1 size = pointed1 size + pointed2 size

3. pointed3 = pointed2

4. while pointed3 NIL

5. do pointed3 = pointed1

6. pointed3 = pointed3 next

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.