Estrutura de Dados - Alocação Estática

8/16/2019 Estrutura de Dados - Alocação Estática

1/57

Estruturade Dados


2/57

Introdução● O que são estruturas de dados?

● Em Ciência da computação, uma estrutura de dados é ummodo particular de armazenamento e organização de dadosem um computador de modo que possam ser usados de modo

eficiente – Benef cios?

● Organização da informação● !el"ora o desempen"o● #roporciona o reuso de c$digo● #roporciona interopera%ilidade● Diminui custos


3/57


4/57


5/57

O%&eti'os (erais● Introduzir conceitos referentes ) utilização de

estruturas de dados em pro%lemas en'ol'idosna programação, familiarizando os alunos comas principais estruturas de dados, e suascorrespondentes a%straç*es+

● inal da aula o aluno poder- pro&etar eimplementar di'ersas estruturas de dados,con"ecendo suas 'antagens e des'antagens+


6/57

O%ser'ação● .esta aula são apresentadas algumas

estruturas de dados, com ênfase naquelas quesão utilizadas no decorrer da aula+ /ssim,

algumas estruturas de import0ncia para outrostipos de aplicaç*es como a representação de-r'ores, grafos e matrizes esparsas,fundamental para a -rea de computação

cient fica 11 não estão descritas aqui+


7/57

#rincipais tipos de estruturas de dados

● 2ista● ila● #il"a● 3r'ores● (rafos●

4a%ela 5as"ing● Etc+


8/57

/plicaç*es● Estruturas de dados são muito utilizadas em

aplicaç*es de n 'el mais %ai6o, tais como7 – Implementação de estruturas de %anco de dados –

Compiladores e interpretadores – Editores de te6to – 8ernel de sistemas operacionais – 9edes de computadores – I/ – Etc+


9/57


10/57

Definição● :ma estrutura do tipo 2ista é uma sequência

de elementos do mesmo tipo+● ;eus elementos possuem estrutura interna

a%stra da, ou se&a, sua comple6idade éa%stra da e não afeta o seu funcionamento+


11/57


12/57

Definição● Em uma 2ista podemos realizar as seguintes operaç*es %-sica7

● Criação da 2istaA● Inserção de um elementoA● E6clusão de um elementoA● /cesso a um elementoA● Destruição da listaA● Etc+

● Essas operaç*es dependem do tipo de alocação de mem$riausada

–

Est-ticaA – Din0mica


13/57

/locação Est-tica● O espaço de mem$ria é alocado no momento da

compilação● E6ige a definição do n mero m-6imo de elementos da

2ista● /cesso sequencial7 elementos consecuti'os na

mem$ria


14/57

/locação Din0mica● Espaço de mem$ria é alocado em tempo de e6ecução● / 2ista cresce ) medida que no'os elementos são

armazenados, e diminui ) medida que elementos sãoremo'idos

● /cesso encadeado7 cada elemento pode estar em uma -readistinta da mem$ria+ #ara acessar um elemento, é precisotodos os seus antecessores na 2ista+


15/57

2ista ;equencial 2inear Est-tica● um tipo de 2ista onde o sucessor de um

elemento ocupa a posição f sica seguinte domesmo


16/57

Fantagens do uso de /rra s● /cesso r-pido e direto aos elementos < ndice@● 4empo constante para acessar um elemento● acilidade em modificar informaç*es


17/57

Des'antagens do uso de /rra s● Definição pre'ia do taman"o do arra● Dificuldade para inserir e remo'er um elemento

entre outros dois7 é necess-rios deslocar os

elementos


18/57

Guando utilizar essa 2ista?● 2istas pequenas● Inserção remoção apenas no final da 2ista● 4aman"o m-6imo %em definido● / %usca é a operação mais frequente


19/57

Implementação de 2ista – Criar uma lista – Destruir uma lista

● /lgumas informaç*es %-sica so%re 2ista7● 4aman"o?● Est- c"eia?● Est- 'azia?


20/57

Inserção na 2ista● E6istem H tipos de inserção7

● In cio● !eio● final


21/57

Inserção na 2ista● 4am%ém e6iste o caso onde a inserção é feita

em uma lista que est- 'azia+● Cuidado7 não se pode inserir numa lista 'azia


22/57

Inserção no final da 2ista● !ais f-cil


23/57

Inserção no in cio● .ecessita de deslocamento+


24/57

Inserção de forma Ordenada● 4al'ez se&a necess-rio deslocar os elementos+


25/57

9emoção na 2ista● E6istem H tipos de remoção7

● In cio● !eio● inal


26/57

9emoção no In cio● Desloca todos os elementos posteriores+


27/57

9emoção em qualquer lugar● 4al'ez desloque os elementos


28/57

9emoção no inal● !as facil+


29/57

Importante● Os H tipos de remoção tra%al"am &untos+ / remoção

sempre remo'e um elemento espec fico da lista, oqual pode estar no in cio, no meio ou no final da lista

● Cuidado7 não se pode remo'er de uma lista 'azia


30/57

Consulta na 2ista● E6istem maneiras de consultar um elemento

de uma lista7● #ela posição


31/57

ila


32/57

Definição● :ma estrutura do tipo ila é uma sequencia de elementos

do mesmo tipo, como as listas+● ;eus elementos possuem estrutura interna a%stra da, ou

se&a, sua comple6idade é a%stra da e não afeta o seu

funcionamento+


33/57

Definição● :ma ila é um tipo especial de 2ista● Inserç*es e e6clus*es de elementos ocorrem

nas e6tremidades da lista+● /plicaç*es7

● Controle de flu6oA● 9ecursos compartil"ados


34/57

Definição● Em uma ila podemos realizar as seguintes operaç*es %-sica7

● Criação da filaA● Inserção de um elemento no finalA● 9emoção de um elemento no in cioA● /cesso a um elemento no in cioA●

Destruição da filaA● Etc+

● Essas operaç*es dependem do tipo de alocação de mem$riausada – Est-ticaA – Din0mica


35/57

/locação Est-tica● O espaço de mem$ria é alocado no

momento da compilação● E6ige a definição do n mero m-6imo de

elementos da ila● /cesso sequencial7 elementos

consecuti'os na mem$ria


36/57

/locação Din0mica● Espaço de mem$ria é alocado em tempo de

e6ecução● / ila cresce ) medida que no'os elementos são

armazenados, e diminui ) medida queelementos são remo'idos● /cesso encadeado7 cada elemento pode estar

em uma -rea distinta da mem$ria+ #ara acessarum elemento, é preciso todos os seusantecessores na ila+


37/57

ila Est-tica● 4ipo de ila onde o sucessor de um elemento

ocupa a posição f sica seguinte do mesmo


38/57

Implementação de ila – Criar uma fila – Destruir uma fila

● /lgumas informaç*es %-sica so%re fila7●

4aman"o?● Est- c"eia?● Est- 'azia?


39/57

Inserção na ila● Em uma ila a inserção é sempre no final● 4am%ém e6iste o caso onde a inserção é feita

em uma fila que est- 'azia● Cuidado7 não se pode inserir numa fila c"eia


40/57

Inserção na ila

ã l


41/57

9emoção na ila● Em uma ila a remoção é sempre no in cio● Cuidado7 não se pode remo'er de uma fila

'azia

9 ã il


42/57

9emoção na ila

C l il


43/57

Consulta na ila● Em uma ila a consulta se d- apenas ao

elemento que est- no in cio+

C l il


44/57

Consulta na ila


45/57

#il"a

D fi i ã


46/57

Definição● :ma estrutura do tipo #il"a é uma sequencia deelementos do mesmo tipo, como as listas e filas+● ;eus elementos possuem estrutura interna a%stra da, ou

se&a, sua comple6idade é a%stra da e não afeta o seu

funcionamento+

D fi i ã


47/57

Definição● :ma #il"a é um tipo especial de 2ista● Inserç*es e e6clus*es de elementos ocorrem

apenas no in cio da lista+● /plicaç*es7

● /nalise de uma e6pressão matem-ticaA● /'aliação de e6pressão p$s1fi6aA● Con'erter uma e6pressão in1fi6a para p$s1fi6aA● Con'erter um n mero decimal para %in-rio● Etc+

Definição


48/57

Definição● Em uma #il"a podemos realizar as seguintes operaç*es%-sica7

● Criação da pil"aA● Inserção de um elemento no in cioA● E6clusão de um elemento do in cioA● /cesso a um elemento do in cioA● Destruição da filaA

● Essas operaç*es dependem do tipo de alocação demem$ria usada

– Est-ticaA – Din0mica

/locação Est tica


49/57

/locação Est-tica● O espaço de mem$ria é alocado no

momento da compilação● E6ige a definição do n mero m-6imo de

elementos da #il"a● /cesso sequencial7 elementos

consecuti'os na mem$ria

/locação Din0mica


50/57

/locação Din0mica●

Espaço de mem$ria é alocado em tempo dee6ecução● / #il"a cresce ) medida que no'os elementos

são armazenados, e diminui ) medida queelementos são remo'idos

● /cesso encadeado7 cada elemento pode estarem uma -rea distinta da mem$ria+ #ara acessar

um elemento, é preciso todos os seusantecessores na ila+

Implementação de #il"a


51/57

Implementação de #il a

– Criar uma pil"a – Destruir uma pil"a

● /lgumas informaç*es %-sica so%re pil"a7●

4aman"o?● Est- c"eia?● Est- 'azia?

Inserção na #il"a


52/57

Inserção na #il a● Em uma #il"a a inserção é sempre no seu in cio● 4am%ém e6iste o caso onde a inserção é feita em uma

pil"a que est- 'azia+● Cuidado7 não se pode inserir em uma pil"a c"eia

9emoção na #il"a


53/57

9emoção na #il a● Em uma #il"a a remoção é sempre no seuinicio+● Cuidado7 não se pode remo'er de uma pil"a

'azia+

Consulta na #il"a


54/57

Consulta na #il a● Em uma #il"a a consulta se d- apenas aoelemento que est- no seu in cio+


55/57


56/57

9eferência Bi%liogr-fica


57/57

9eferência Bi%liogr fica●

Cormen, 4"omas 5+ et+ al+ /lgoritmos7 4eoria e #r-tica+ EditoraCampus, +● Ji'iani, .i'io+ #ro&eto de /lgoritmos+ Editora .o'a ronteira, K+● ;edgeLicM, 9o%ert+ /lgorit"ms in CNN+ /ddison esle , +● !an%er, :di+ Introduction to /lgorit"ms7 / Creati'e /pproac"+ /ddison

esle , PQRQ+● ;edgeLicM, 9o%ert+ and la&olet, #"ilippe+ /n Introduction to t"e

/nal sis of /lgorit"ms+ /ddison esle , PQQS+● "ttps7 programacaodescomplicada+Lordpress+com indice estrutura1de1

dados● "ttp7 pt+slides"are+net fa%riciolopessanc"ez estrutura1de1dados1

conceitos1fundamentais

Documents

Estrutura de Dados - Alocação Estática