Lógica de Programação - Listas

8/17/2019 Lógica de Programação - Listas

1/30

Lógica de ProgramaçãoAplicações Práticas do Uso de Vetores

Prof. Vinícius Breda


2/30

Vetor como Lista

● Os vetores possuem muitas aplicações,dentre elas a de servir como uma lista paraarmazenar dados.

● Nesta aula será estudado como utilizar umvetor como uma lista de dados, sendocapaz de organizar o vetor e pesquisaralgum dado no mesmo.


3/30

Utilizando um Vetor como Lista

magine um programa que deva fazer a leitura de !"n#meros e em seguida apresentá$los na mesmaordem em que foram informados.

%eriamos o seguinte algorítmo&' ( )efiniar a varíavel do tipo inteiro para controlar

a mal*a de repetiç+o! ( )efiniar o vetor Numero do tipo inteiro para os

!" n#meros- ( niciar o programa fazendo a leitura dos !"

n#meros e armazená$los no vetor Numero ( /presentar ap0s a leitura os !" n#meros.


4/30


Diagrama de BlocosInício

I = 0, I < 20,I = I + 1

Numeros[I]

I = 0, I < 20,I = I + 1

Numeros[I]

Fim


5/30


PseudocódigoAlgoritmos 1istaInícioar inteiro , Numeros2!"3

para 4 ", 5 !", 4 6' !aça leia7Numero238!im"para

para 4 ", 5 !", 4 6' !aça escrea7Numero238!im"para

#im


6/30

$lassi!icação dos %lementos de

um Vetor 9eria :astante #til se o programa, antes de apresentaros n#meros, efetuasse o processamento deordenaç+o crescente, facilitando assim a localizaç+o

de algum n#mero, quando for efetuada umapesquisa visual.

;


7/30


um Vetor Para fazer a ordenaç+o do vetor, acrescentaremosmais um passo ao algoritmo anterior.

%eriamos o seguinte algorítmo&' ( )efiniar a varíavel do tipo inteiro para controlar a

mal*a de repetiç+o! ( )efiniar o vetor Numero do tipo inteiro para os !"

n#meros

- ( niciar o programa fazendo a leitura dos !"n#meros e armazená$los no vetor Numero

& ' $olocar em ordem crescente os elementos doetor(

> ( /presentar ap0s a leitura os !" n#merosordenados.


8/30


um Vetor Para fazer a ordenaç+o do vetor, acrescentaremosmais um passo ao algoritmo anterior.

%eriamos o seguinte algorítmo&' ( )efiniar a varíavel do tipo inteiro para controlar a

mal*a de repetiç+o! ( )efiniar o vetor Numero do tipo inteiro para os !"

n#meros

- ( niciar o programa fazendo a leitura dos !"n#meros e armazená$los no vetor Numero

& ' $olocar em ordem crescente os elementos doetor(

> ( /presentar ap0s a leitura os !" n#merosordenados.


9/30


um Vetor /gora falta definir como o quarto passo, ou se?a, aordenaç+o do vetor será feita. Para isso consideraremoso seguinte algoritmo&

' ( @omparar n#mero da primeira posiç+o do vetor comtodos os outros

! ( Auando o n#mero comparado for maior, trocar am:osde posiç+o

- ( /p0s comparar o n#mero na primeira posiç+o comtodos os outros, comparar o n#mero da segundaposiç+o com os de posiç+o maior

( Auando o n#mero comparado for maior, trocar am:osde posiç+o

> ( @ontinuar o processo, comparando o n#mero naterceira posiç+o, quarta, etc, at= que todos ten*am sidocomparados.


10/30

%)emplo de *rdenação

$rescente)ado o seguinte vetor de cinco posições&

N2"3 4

N2'3 4 CN2!3 4 DN2-3 4 >N23 4 -

Podemos ordená$lo em ordem crescente seguindoos passos do algoritmo anterior, gerando oseguinte resultado a cada passo&


11/30

%)emplo de *rdenação

$rescente

Passo 5 N[0] = 3N[1] = 9

N[2] = 8

N[3] = 7 N[4] = 5

Passo 1

N[0] = 8

N[1] = 9

N[2] = 7 N[3] = 5

N[4] = 3

Passo 2

N[0] = 8

N[1] = 9

N[2] = 7

N[3] = 5

N[4] = 3

Passo 3

N[0] = 7

N[1] = 9

N[2] = 8N[3] = 5

N[4] = 3

Passo 4

N[0] = 5

N[1] = 9

N[2] = 8 N[3] = 7

N[4] = 3

Passo N[0] = 3N[1] = 8

N[2] = 9N[3] = 7

N[4] = 5

Passo 7 N[0] = 3N[1] = 7

N[2] = 9 N[3] = 8N[4] = 5

Passo 8 N[0] = 3 N[1] = 5

N[2] = 9

N[3] = 8

N[4] = 7


12/30

%)emplo de *rdenação$rescente

Passo 9

N[0] = 3 N[1] = 5

N[2] = 8

N[3] = 9

N[4] = 7

Passo 10

N[0] = 3 N[1] = 5

N[2] = 7N[3] = 9

N[4] = 8

!esu"#a$o

N[0] = 3 N[1] = 5

N[2] = 7 N[3] = 8

N[4] = 9


13/30

$lassi!icação dos %lementos deum Vetor ' *rdenação $rescente

/ seguir = mostrado o diagrama de :locos e opseudoc0digo do completo do programa capaz deler !" n#meros, ordená$los em ordem crescente

7utilizando o m=todo visto8 e mostrá$los para ousuário.

/ primeira e a #ltima parte do diagrama de :locos ?áfoi estuda no início dessa aula. 9+o as partes que

fazem a leitura e e


14/30


Início

I = 0, I < 20,I = I + 1

Numeros[I]

I = 0, I < 20,I = I + 1

Numeros[I]

Fim

I = 0, I < 19,I = I + 1

% = I+1, % < 20,% = % + 1

Numero[I]&

Numero[%]

' = Numero[I] Numero[I] = Numero[%]

Numero[%] = '

(


15/30


O primeiro a ser o:servado = a utilizaç+o de umasegunda variável para controlar o índicesu:sequente no processo de ordenaç+o, no caso a

variável +.O:serve que no primeiro loop para a variável I =iniciada em ", e no segundo loop para a variável + = iniciada em I,-. sso implica na seguintesequEncia& .uando I !or + será

" ',!,-,,>,F,D,...,'

' !,-,,>,F,D,...,'

! -,,>,F,D,...,'

- ,>,F,D,...,'

... G,'

'C '


16/30


O:serve que somente quando a variável + atinge ovalor ' = que este looping se encerra, retornandoao looping da variável I, acrescentando mais um

em I at= que I atin?a o seu limite e am:os osloopings se?am encerrados.Auando a variável I for ", a variável + será ' e contará

at= '. /o final deste ciclo, a variável I =acrescentada de mais ' tornando$se ' assim sendo

a variável + passa a ser !. Auando a variável + voltar a ser ', a variável I passa a ser ! e a variável+ passa a ser -. ;ste ciclo irá ser e


17/30


Outro ponto a ser o:servado = o fato da utilizaç+o do algoritmode troca, que utiliza a instruç+o se Numero23 / Numero2H3então. /p0s a verificaç+o desta condiç+o, sendo o primeiron#mero maior que o segundo, efetua$se ent+o a sua troca

com o algoritmo&

I 4 Numero23Numero23 4 Numero2H3Numero2H3 4 I

@onsidere o vetor Numero23 com valor '> e o vetor Numero2H3com valor '". /o final Numero23 deverá estar com '" eNumero2H3 deverá estar com '>. Para conseguir este efeito,= necessária a utilizaç+o de uma variável de apoio, que foi

c*amada de 0.


18/30


I 4 Numero23Numero23 4 Numero2H3Numero2H3 4 I

Para que o vetor Numero23 fique livre para rece:er o valor dovetor Numero2H3, 0 deverá rece:er o valor de Numero23. /ssim sendo, 0 passa a ser '>. Neste momento pode$seimplicar o valor de Numero2H3 em Numero23. )esta forma ovetor Numero23 passa a possuir o valor '". ;m seguida o

vetor Numero2H3 rece:e o valor que está em 0. /o final desteprocesso, ter$se$á Numero23 com '" e Numero2H3 com '>.


19/30


Algoritmos 1istaJcrescenteInício

// declaração das variáveisar inteiro , H, Numeros2!"3

// rotina de entrada de dadospara 4 ", 5 !", 4 6' !aça

leia7Numero238!im"para


20/30


// rotina de processamento de ordenação crescente

para 4 ", 5 ', 4 6' !aça para H 4 6', H5!", H 4 H6' !aça se 1 Numero23 K Numero2H3 2 então I 4 Numero23 Numero23 4 Numero2H3 Numero2H3 4 I

!im"se !im"para!im"para


21/30


// rotina de saída com dados ordenadospara 4 ", 5 !", 4 6' !aça escrea7Numero238!im"para

#im


22/30

$lassi!icação dos %lementos deum Vetor ' *rdenação Al!a34tica

/gora que ?á sa:emos como ordenar um vetor num=rico,vamos adaptar nosso c0digo para um vetor do tipocadeiaL

Mazer um c0digo capaz de ler o nome de !" pessoas,organizar os nomes em ordem alfa:=tica e e


23/30

54todos de Pes6uisa em um Vetor

Auando se tra:al*a com vetores, eles poder+o ser muitograndes, dificultando localizar um determinadoelemento de forma rápida. magine um vetor possuindo""" elementos, como nome de pessoas. esmoestando em ordem alfa:=tica, seria demorado ee


24/30

54todo de Pes6uisa 7e6uencial

;ste = o m=todo mais simples, e consistem em efetuar a:usca da informaç+o dese?ada a apartir do primeiroelemento sequencialmente at= o #ltimo. 1ocalizando ainformaç+o no camin*o, ela = apresentada.

;ste m=todo de pesquisa = lento, por=m eficiente noscasos em que uma matriz encontra$se com seuselementos desordenados.


25/30

54todo de Pes6uisa Binária

;m m=dia, este m=todo de pesquisa = mais rápido que om=todo sequencial, por=m e


26/30


@omo e


27/30


Pelo processo de pesquisa :inária, devemos dividir a listapela metade. 9endo assim, D di ! 4 -. O:serve que oque nos interessa = somente o valor inteiro doquociente. 1ogo a lista fica dividida em duas, comosegue&

8ndice 9omes

" /ndr=' @arlos

! Mrederico

8ndice 9omes

- Rolias

9ílvia

> 9ílvio

F Qaldir

Primeira Par#e )e*un$a Par#e


28/30


;stando a lista dividida em duas partes, deverá serverificado se a informaç+o Qaldir está na primeira ouna segunda parte. )etecta$se que Qaldir está nasegunda parte. )esta forma despreza$se a primeiraparte e divide$se em duas partes novamente a segundaparte. @omo s+o elementos divididos por !, resultamduas ta:elas com dois elementos&

8ndice 9omes

- Rolias

9ílvia

8ndice 9omes

> 9ílvio

F Qaldir

Primeira Par#e)e*un$a Par#e


29/30


/p0s esta segunda divis+o, verifica$se em qual das partesQaldir está situado. @omo está na segunda parte,despreza$se a primeira e divide$se a segunda partenovamente por dois, so:rando um elemento em cadaparte.

/p0s a terceira divis+o, Qaldir = encontrado na segundaparte da lista. 9e for pesquisado um elemento que n+oe 9ílvio

8ndice 9omes

F Qaldir

Primeira Par#e )e*un$a Par#e


30/30

%)ercícios para a Aula

)esenvolver o diagrama de :locos e pseudoc0digo paraas pesquisas sequencial e :inária, aplicadas a uma listacom !" nomes.

Documents

Lógica de Programação - Listas