Estrut Dados Material

2010

Mariela Inés Cortés

Estrutura de Dados

Copyright © 2010. Todos os direitos reservados desta edição à SECRETARIA DE EDUCAÇÃO A DISTÂNCIA (SEAD/UECE). Nenhuma parte deste material poderá ser reproduzida, transmitida e gravada, por qualquer meio eletrônico, por fotocópia e outros, sem a prévia autorização, por escrito, dos autores.

EXPEDIENTE Design instrucionalAntonio Germano Magalhães JuniorIgor Lima RodriguesPedro Luiz Furquim Jeangros

Projeto gráficoRafael Straus Timbó VasconcelosMarcos Paulo Rodrigues Nobre

Coordenador EditorialRafael Straus Timbó Vasconcelos

DiagramaçãoMarcus Lafaiete da Silva MeloFrancisco José da Silva Saraiva

IlustraçãoMarcos Paulo Rodrigues Nobre

CapaEmilson Pamplona Rodrigues de Castro

PRESIDENTE DA REPÚBLICALuiz Inácio Lula da Silva

MINISTRO DA EDUCAÇÃOFernando Haddad

SECRETÁRIO DE EDUCAÇÃO A DISTÂNCIACarlos Eduardo Bielschowsky

DIRETOR DO DEPARTAMENTO DE POLÍTICAS EM EDUCAÇÃO A DISTÂNCIA – DPEADHélio Chaves Filho

SISTEMA UNIVERSIDADE ABERTA DO BRASILCelso Costa

GOVERNADOR DO ESTADO DO CEARÁCid Ferreira Gomes

REITOR DA UNIVERSIDADE ESTADUAL DO CEARÁFrancisco de Assis Moura Araripe

VICE-REITORAntônio de Oliveira Gomes Neto

PRÓ-REITORA DE GRADUAÇÃOJosefa Lineuda da Costa Murta

COORDENADOR DA SECRETARIA DE EDUCAÇÃO A DISTÂNCIAAntonio Germano Magalhães Junior

COORDENADOR GERAL UAB/UECEFrancisco Fábio Castelo Branco

COORDENADORA ADJUNTA UAB/UECEJosete de Oliveira Castelo Branco Sales

COORDENADOR DA LICENCIATURA EM INFORMÁTICAJoaquim Celestino Junior

COORDENADOR DE TUTORIA E DOCÊNCIA DA LICENCIATURA EM INFORMÁTICAJorge Luís de Castro e Silva

SumárioApresentação ....................................................................................................................... 7

Unidade 1Introdução à Complexidade de Algoritmos ........................................................................... 9

Capítulo 1 - Introdução ...................................................................................................... 11O que é análise de algoritmos? ............................................................................................. 12

Capítulo 2 - Medidas de Complexidade ............................................................................. 14Comparação entre algoritmos ..............................................................................................15

Unidade 2Representação dos Dados ..................................................................................................... 23

Capítulo 1 - Modelagem Conceitual ................................................................................... 25Tipo de dados .......................................................................................................................25Tipo abstratos de dados ........................................................................................................28Critérios para a escolha da estrutura de dados adequada ....................................................31

Unidade 3Listas .................................................................................................................................... 35

Capítulo 1 - Listas ............................................................................................................... 37Introdução .............................................................................................................................37Defi nição do TAD Lista ...........................................................................................................37

Implementação do TAD Lista usando alocação estáti ca ............................................................... 38Implementação do TAD Lista usando alocação dinâmica ............................................................. 43Variações sobre o TAD Lista ........................................................................................................... 49

Capítulo 2 - Pilhas .............................................................................................................. 51Implementações do TAD Pilha usando vetores .....................................................................52Implementação do TAD Pilha usando ponteiros ...................................................................54

Capítulo 3 - Filas ................................................................................................................. 57Implementação do TAD Fila usando vetores .........................................................................57Implementação do TAD Fila usando ponteiros .....................................................................60

Unidade 4Árvores ................................................................................................................................ 65

Capítulo 1 - Árvores ........................................................................................................... 67Árvore binária ......................................................................................................................68

Capítulo 2 - Árvore binária de busca .................................................................................. 71Defi nição do TAD Árvore Binária de Busca ...........................................................................71Implementação do TAD Árvore Binária de Busca .................................................................72

Ordens de percurso em árvores binárias ...................................................................................... 77Relação entre o número de nós de uma árvore binária e sua altura ........................................................................................................................ 79

Capítulo 3 - Árvores AVL ..................................................................................................... 81

Unidade 5Busca avançada ................................................................................................................... 89

Capítulo 1 - Tabela de dispersão ........................................................................................ 91A função de dispersão ...........................................................................................................92Estratégias para resolução de colisões ..................................................................................94

Encadeamento .............................................................................................................................. 94Técnicas de sondagem ................................................................................................................... 95

Capítulo 2 - Busca digital .................................................................................................... 97Árvore digital.........................................................................................................................98

Capítulo 3 - Estruturas autoajustáveis................................................................................ 100Listas autoajustáveis .............................................................................................................100

O constante aumento da complexidade dos sistemas e suas demandas computa-cionais relacionadas a tempo e espaço, impõem o desafío de projetar soluções algorítmi-cascadavezmaiseficientes.Nestecontexto,asestruturasdedadoseseusalgoritmostêm um papel fundamental uma vez que constituem os blocos construtores utilizados naresoluçãodosmaisdiversosproblemasemtodasasareasdacomputação.

O objetivo do presente livro é apresentar de forma clara e amigável diferentes estruturas de dados e seus algoritmos de manipulação, analisando a estratégia mais eficienteparaasuaimplementação,emtermosdecomplexidade.Estaanáliseenvolvea utilização de técnicas de projeto associadas a técnicas de programação, as quais são adequadasàscaracteristicasdaaplicaçãoespecífica.

Olivroestáorganizadoemcincounidades.Asprimeirasfornecemasbasesne-cessárias para a análise e o projeto de uma boa solução algorítmica incluindo concei-tosbásicossobrecomplexidade,tiposeestruturasdedados.AUnidade3apresentaoconceito central de Listas, a partir do qual duas importantes e amplamente utilizadas estruturassãoderivadas:PilhaseFilas.

AUnidade4apresentaaestruturadeÁrvore,suaconceituação,implementaçãoealgoritmosdemanipulaçãobásicos.Maisespecificamente,nestaunidadesãoexplo-radasasÁrvoresBináriasdeBuscaanalizandosuascaracterísticaseasimplicaçõesemrelaçãoàeficiência.Nestecontexto,afundamentaçãoefuncionamentodasárvoresbalanceadas(AVL)sãoapresentados.Finalmente,naUnidade5sãodescritasastécni-casavançadasdepesquisaaplicadassobreestruturasdedadosespecíficas,taiscomotabelasdedispersão,buscadigitaleestruturasautoajustáveis.

O conteúdo apresentado destina-se principalmente para professores e alunos de graduaçãoemCiênciasdaComputaçãoouáreasafins,fornecendoumembassamentoteórico e uma clara noção das estratégias a serem seguidas na implementação dos algoritmosparaamanipulaçãoeficientedasestruturasdedadosmaisamplamenteutilizadas.

A autora

Unidade

Objetivos:

• Nestaunidadeéintroduzidooconceitodecomplexidadedealgoritmos.Esteconceito é central na Ciência da Computação, uma vez que possibilita avaliar e comparar soluções algorítmicas, fornecendo os insumos necessários para determinar qual é o algoritmo mais adequado para resolver determinada classe deproblemas.

1Introdução à Complexidade

de Algoritmos

11ESTRUTURA DE DADOS

Capítulo 1Introdução

Um algoritmo determina um conjunto de regras não ambíguas asquaisespecificam,paracadaentrada,umaseqüênciafinitadeoperações,gerandocomoresultadoumasaída.Oalgoritmorepresentaumasoluçãopara um problema se, para cada entrada, gera uma resposta correta, sem-prequedispordetempoememóriasuficientes.

Um algoritmo pode ser implementado através de diferentesprogra-mas.Ouseja,diferentesimplementaçõespodemserpropostasapartirdeumúnicoalgoritmo.Estasituaçãonoscolocanadificuldadedeescolherqualéamelhorsoluçãoparaoproblemaespecífico.Assimsendo,apenasresolveroproblemaparecenãosersuficienteumavezquediferentessolu-ções podem ser idealizadas a partir de algoritmos, para a resolução de um únicoproblema.Neste contexto, se tornanecessárioummecanismoquepermita determinar se uma solução é melhor do que uma outra, de forma a fornecer uma ferramenta de apoio à desição em relação à qualidade das soluçõespropostas.

De forma geral, a qualidade de um programa depende do ponto de vis-ta.Porumlado,o usuário determina a qualidade de um programa através de critérios, tais como:

• Facilidade de uso e entendibilidade da interface do programa levan-doemcontadiferentesníveisdeexperiência.

• Compatibilidade do programa com outros programas ou versões de programas, de forma a facilitar a troca de informação com outros sistemasexistentes.

• Desempenho, em relação à velocidade de execução e tempo de res-posta.

• Quantidade de memória utilizada pelo programa durante a sua exe-cução,aspectoquepodesetornarumfatorlimitante.

Os últimos dois itens estão diretamente ligados à quantidade de dados aseremprocessados,ouseja,aotamanhodaentrada.

Por outro lado, critérios que podem ser determinantes desde o ponto de vista da organização desenvolvedora incluem:

• Portabilidadedocódigoentrediferentesplataformas.• Documentaçãoepadronizaçãodocódigo.• Facilidadedeevoluçãoemanutenção.• Reusabilidade do código, permitindo que porções de um programa

sejam reaproveitadas para desenvolver outros produtos, aumentan-doaprodutividade.

Programa codificaumal-goritmo para ser executa-do no computador resol-vendoumproblema.É fundamental que o pro-grama produza a solução com dispêndio de tempo e memória: Importância de ProjetoeAnalisedeAlgo-ritmos.

12 ESTRUTURA DE DADOS

Acorretaavaliaçãodestescritérioséinfluenciadapordiversosfatores,tais como: características do hardware, sistema operacional, linguagens e compiladores, plataforma, etc. Estes fatores são considerados acidentaisumavezquenãoestãodiretamenterelacionadosàqualidadedasolução.Emcontrapartida,osfatoresessenciaissãoinerentesàsoluçãoedetermi-nantesparaasuaqualidade.Otempogastoeoespaçofísiconamemóriasão considerados fatores essenciais. Consequentemente é preciso de ummétodo formal para medir o tempo e a memória requeridos pelo algoritmo, independentemente das características de plataforma de hardware e sof-twaresendoutilizadas.

O que é análise de algoritmos?AanálisedealgoritmoséocoraçãodaCiênciadaComputaçãoetem

por objetivo estabelecer medidas de desempenho dos algoritmos, com vis-tasàgeraçãodealgoritmoscadavezmaiseficientes.Adicionalmentefor-nece fundamentos para a escolha do melhor algoritmo para a resolução de umproblemaespecífico,combasenasuacomplexidade computacional.

O tempo de execução e o espaço de memória alocado são os dois fatores principais que determinam a complexidade computacional de umaalgoritmo.

• Complexidadetemporalconsistenonúmero(aproximado)deinstru-çõesexecutadas.

• Complexidadeespacialconsistenaquantidadedememóriautilizada.De forma geral, tanto a complexidade temporal quanto a espacial po-

dem ser descritas por funções que têm como parâmetro principal o tama-nhodaentradasendoprocessada.Comoexemplostemosque:

• Ordenar100.000 elementos levamais tempoqueordenar10 ele-mentos.

• Aaberturadeumeditordetextoslevamaistempoeconsumemaismemória quando é aberto com um arquivo grande do que com um arquivopequeno.

Além do tamanho da entrada, as características apresentadas naorganizaçãodosdados, tambémpodem influenciarna eficiência deumalgoritmoemrelaçãoaumaoutrasolução.Por exemplo, odesempenhodeumalgoritmoespecíficoparaordenarumconjuntoondeosdadosseencontram parcialmente ordenados pode ser muito diferente se utilizado para ordenar um conjunto de dados totalmente desordenados, conside-randoconjuntosdeigualtamanho.Logoéimportanteestabelecerdequeformaotamanhoecaracterísticasdaentradapodeminfluenciarnocom-portamentodoalgoritmo.

Emalgunscasos,seoalgoritmonãoérecursivo, não contem itera-ções e não usa algoritmos com essas características, o número de passos necessários pode ser independente do tamanho da entrada, e consequen-tementeacomplexidadetemporaléconstante.

Umexemplodealgoritmocomestascaracterísticaséoalgoritmoqueimprime“HELLOWORD”,quepossuicomplexidadeconstante.

A principal característicade um algoritmo recursivo é a ocorrência de chama-dasaelepróprio.Para avaliar a complexi-dade de um algoritmo re-cursivo é preciso analisar quantas vezes a função vai ser chamada, e quan-tas operações acarretam cadachamada.


#include <stdio.h>

main()

for(;;)

Printf (Hello Word!\n”);

Considerando que é impossível fazer uma predição exata do tempo e memória a serem utilizados a estratégia consiste em estabelecer uma apro-ximação, com base em conceitos e modelos matemáticos.

1. Descreva com suas palavras a relação entre os conceitos de algoritmo e programa.

2.Determine emquais casos e de que formaas especificações a seguirpodemdependerdotamanhoouorganizaçãodosdadosdaentrada.Jus-tifiqueasuaresposta.

a.Procuraromaiorelementoemumasequência.

b.Modificaroconteúdodeumavariável.

c. Imprimiroconteúdodeumasequênciadeelementos.

d.Apartirdosdadosdeumapessoa:nome,datadenascimento,sexo,determinarseapessoaémaiorde18anos.


Capítulo 2Medidas de Complexidade

De forma geral, a complexidade de um algoritmo é determinada pela quantidade de trabalho requerido sobre um determinado tamanho da en-trada.Otrabalhodependediretamentedonúmerodeoperações básicas efetuadas.

Considere o problema de estabelecer se um determinado elemento pertenceaumconjuntode100elementos.Asoluçãomaissimplesparaeste problema envolve uma pesquisa sequencial onde o elemento procu-radoécomparadoacadaumdoselementospertencentesaoconjunto.Onúmero de comparações realizadas irá depender dos diversos cenários possíveis.Aprincipiopodemosanalizarduassituações:oelementoéen-contrado na primeira comparação realizada ou, o elemento não existe no conjunto.Noprimeirocasoseriaprecisosomenteumacomparação,en-quanto que no último caso todo o conjunto precisaria ser checado, envol-vendo,portanto100comparações.

Apartirdassituaçõesapresentadaspodemosconcluirqueacomple-xidade de um algoritmo pode ser estabelecida utilizando uma estratégia pessimista ou máxima, ou otimistaoumínima.Noprimeirocaso,oalgo-ritmo é analisado levando em conta o cenário mais adverso, o que normal-menteiráresultarnomaiortempodeexecução.Estecritérionormalmenteé o mais utilizado uma vez que estabelece uma cota ou limite superior no temporequerido.Emoposiçãoaestaabordagem,acomplexidadeotimis-ta ou mínima é obtida quando o problema é analisado levando em conta umcenárioidealdemandando,portanto,menostempodeexecução.Podeainda ser considerado um caso médio ou esperado, correspondente à mé-dia dos tempos de execução de todas as entradas de tamanho n.Estasestratégias podem ser utilizadas tanto para estabelecer a complexidade espacialquantotemporaldosalgoritmos.

Aanáliseparaocálculodestasmedidaspodeserrealizadaempiri-camente, isto é, com base na experiência e na observação prática, exclusi-vamente,semsebasearemnenhumateoria.Noentanto,amediçãoobtidapodeserinfluenciadaporfatoresacidentaisreferentesàplataformaespe-cífica,comoporexemplo,acapacidadedeprocessamentodocomputadorsendoutilizado.Consequentemente,aexecuçãodeumalgoritmoemumdeterminado computador pode ter um desempenho diferente à medição resultante a partir da execução do mesmo algoritmo em um outro compu-tadorcomcaracterísticasdiferentes.Estaspossíveisdivergênciastornamaabordagembaseadanamediçãoempíricapoucoconfiável.


1. Determine o caso otimista e o caso pessimista a partir das seguintes especificações:

a.Encontraromaiorelementodeumvetor(desordenado)deinteiros.

b.Encontraromaiorelementodeumvetorordenadodeformadecres-centedeinteiros.

c. Removerumdadoelementodeumvetordeinteiros.

d.Idemanteriorconsiderandoumvetorordenadoemformacrescente.

2. Considere o problema de encontrar o maior elemento de um vetor de inteiros.O algoritmo a seguir apresentauma solução simples para oproblema.

int Max (A Vetor)

int i, Temp;

Temp = A[0];

for (i := 1; i < n; i++)

if (Temp < A[i]) Temp := A[i];

return (Temp);

a.DetermineonúmerodecomparaçõesrealizadasentreoselementosdeA,considerandoqueAcontemnelementos.

b.Descrevaquaissãoassituaçõesquerepresentamomelhorcaso,opiorcasoeocasomédioparaoalgoritmo.

Comparação entre algoritmosComo dito anteriormente, para um dado problema podem existir di-

versosalgoritmospossíveis.Cabeaoprogramadoranalisaraspossibilida-des e escolher o algoritmo mais adequado utilizando como critério básico a suacomplexidade.

Umaabordagemamplamenteadotadaparaanalizaracomplexidadede algoritmos é baseada na análise encima das operações fundamentais que compõem o algoritmo, a partir das quais é derivada uma função custo modelando o comportamento que o algoritmo irá a adotar de acordo com os dadosdeentradafornecidos.Emparticular,quandoconsideradasentradassuficientementepequenas,ocustoéreduzido,mesmonocasodealgorit-mosineficientes.Jáparatamanhosdeentradasuficientementegrandes,aescolhaporumdeterminadoalgoritmopodeserumproblemacrítico.Logo,a análise de algoritmos é interessante para valores grandes da entrada, ou seja,nocasodealgoritmosquemanipulamgrandesquantidadesdedados.


O estudo da complexidade consiste em determinar a ordem de magni-tude do número de operações fundamentais realizadas pelo algoritmo, des-critasapartirdadefiniçãodafunção custo.Apartirdesseestudoépossívelrealizar a comparação do comportamento assintótico através da análise dos gráfi coscorrespondentes.

Acomparaçãoentrefunçõescombasenocritériodecomportamento assintótico consiste no estudo do crescimento de funções para valores gran-des de n,nonossocaso,referenteaotamanhodaentrada.Apartirdessaanálise, as funções sãoclassificadasemordens, ondecadaordemagru-pafunçõesdecrescimentosemelhante.Oalgoritmoassintoticamente mais efi cienteéomelhorparatodasasentradas.Nestecontexto,umafunçãoéconsiderada uma cota assintótica superior ou domina assintoticamente ou-tra,quandocrescemaisrapidamentedoqueoutra:graficamente,ográficodaprimeirafunçãoficaporcimadasegundaapartirdecertopontom.Nocaso geral, nem sempre é possível determinar se f (n)<g(n).

Sejam f e g as duas funções de custo que queremos comparar:1. Se f é sempre inferior a g,ouseja,ográficodefficasempreporbai-

xodográficodeg, então a escolha para o algoritmo correspondente a féóbvia.

1. Se f às vezes é inferior a g,evice-versa,eosgráficosdef e g se inter-ceptamemumnúmeroinfinitodepontos.Nestecaso,consideramosqueháempate,eafunçãocustonãoajudaaescolherumalgoritmo.

2. Se f às vezes é g inferior a g,evice-versa,eosgráficosdef e g se cortamemumnúmerofinitodepontos.Portanto,apartirdecertovalor de n, f é sempre superior a g,ouésempreinferior.Nestecaso,consideramos melhor aquele algoritmo que é inferior ao outro para grandes valores de n.

Asfunçõesmaiscomumenteencontradasemanálisedeprogramas,considerando n como tamanho da entrada, são:

f(n) = k Constantef(n) = k . n Linearf(n) = n . log n Logarítmicaf(n) = k . n2 Quadráticaf(n) = k . n3 Cúbicaf(n) = nk Polinomialf(n) = k . en ExponencialAfiguraaseguirrepresentaaordemdecrescimentodasfunçõesmais

comumenteutilizadasnarepresentaçãodacomplexidadedosalgoritmos.Comparativamente podemos concluir que, na medida em que o tamanho

Comportamento observa-do de f(n) quando n tende ainfinito.


da entrada n aumenta, a função linear n cresce mais rapidamente do que a função log(n), que por sua vez cresce mais lentamente do que a função quadrática n2,eassimpordiante.

Sempre é possível determinar a taxa de crescimento relativo de duas funções f(n) e g(n) calculando Lim f(n) / g(n)

x→∞Apartirdestecálculoexistemosseguintesvalorespossíveis:• 0, então g(n) é limite superior para = f(n) • c, então f(n) e g(n) tem complexidades equivalentes• infinito,entãof(n) é limite superior para g(n)Nocasodefunçõesoscilantes,comoocasodesen(n) ou cos(n), nenhu-

maafirmaçãopodeserfeita.

1.ConsidereosalgoritmosAeBcomcomplexidades:

CA(n) = 1000 × n2

CB(n) = 0, 1 × n3

Determine a partir de qual valor de n, CB domina assintoticamente CA?

2.ParaumdeterminadoproblemaP,temosalgoritmosA,B,C,eDcomasseguintescomplexidades.

CA(n) = 100 × n × log n

CB(n) = 1000 × n

CC(n) = 4 × n2

CD(n) = 10 − 5 × en

Classificarosalgoritmosdomelhoratéopior,emtermosdecomplexi-dade, sempre considerando valores grandes da variável n (tamanho da entrada).Justifique.


Anotaçãoutilizadaparadenotaradominaçãoassintóticafoiintrodu-zida por Knuthem1968.Deacordocomestanotação,aexpressãog(n) = O(f(n)) expressa que f(n) domina assintóticamente g(n).Aexpressãopodeserlida da seguinte forma: g(n) é da ordem no máximo de f(n).Asdefiniçõesaseguir formalizam a notação de Knuth.

AnotaçãomaiscomumenteusadaparamediralgoritmoséO,umavezque determina um limite superior da complexidade:

Definição.AfunçãocustoC(n) é O(F(n)) se existem constantes positivas c e m tais que:

C(n)≤c.F(n), quando n≥m

Adefiniçãoacimaafirmaqueexistealgumpontom a partir do qual c . F(n) é sempre pelo menos tão grande quanto C(n).Assim,seosfatoresconstantes são ignorados, F(n) é pelo menos tão grande quanto C(n).

Como exemplo, seja g(n) = (n + 1)2.Logo,g(n) é O(n2), quando m = 1 e c = 4, uma vez que (n + 1)2≤4n2paran≥1.

Emoutraspalavras,quantodizemosqueC(n) = O(F(n)) estamos ga-rantindo que a função C(n) não cresce mais rápido do que F(n).Assim,F(n) é um limite superior para C(n).

De forma geral, os termos de menor peso e os fatores podem sempre ser eliminados uma vez que para valores grandes da variaveis, estes com-ponentessetornamdespresiveis.AssimO(4n3 + 10n2) e O(n3) são sinôni-mos,masosegundotermoémaispreciso.

Se um algoritmo é O(1)significaqueonúmerodeoperaçõesfunda-mentaisexecutadasélimitadoporumaconstante.

Intuitivamente, se g(n) = 2 n2, então g(n) = O(n4), g(n) = O(n3) e g(n) = O(n2).Todasasrespostassãotecnicamentecorretas,masamenoréame-lhorresposta.

Outras defi nições formais

• Limite inferior: ΩAnotaçãoΩéusadaparaespecificarolimiteinferiordacomplexi-dadedeumalgoritmo.

• Complexidade exata: ӨAnotaçãoӨéusadaparaespecificarexatamenteacomplexidadedeumalgoritmo.

• Limite superior estrito: oEnfimanotaçãooéusadaparaespecificarqueacomplexidadedeumalgoritmoeinferiorestritamenteacertafunção.

1.Suponhag(n)=nef(n)=n2,demostrequaldasseguintesafirmaçõeséverdadeira:

a. f(n)=O(g(n))

b.g(n)=O(f(n))

Donald Ervin Knuth, na-cido em Milwaukee, em10deJaneirode1938,éum cientista computacio-nal de renome e professor emérito da UniversidadedeStanford.ÉoautordolivroTheArtofComputerProgramming, uma das principais referências da Ciência da Computação.É considerado o criador do campo de Análise deAlgoritmosefezdiversaseimportantes contribuições a vários ramos da teoria da computação


2.Determineaordemmáximaparaasseguintesfunçõesejustifiqueasuaresposta detalhando os valores de c e n adequados.

a.g(n)=3n3 + 2n2 + n

b.h(n)=n2 + n + 1

Operações com a notação O

AlgumasoperaçõesquepodemserrealizadascomanotaçãoOsãoapresentadas a seguir:

f(n) = O(f(n))c . O(f(n)) = O(f(n)), onde c é uma constanteO(f(n)) + O(f(n)) = O(f(n))O(O(f(n))) = O(f(n))O(f(n)) + O(g(n)) = O(max (f(n), g(n)))O(f(n)) . O(g(n)) =O(f(n) . g(n))f(n ). O(g(n)) = O(f(n) . g(n))

Estasoperações foramdemostradasmatematicamentena literaturaetemaplicaçãodiretaparaocálculodotempodeexecuçãode(trechosde)programas.Porexemplo,aregradasoma,O(f(n)) + O(g(n)) pode ser utili-zada para calcular o tempo de execução de uma sequência de trechos ou sentençasdeprogramas.Aplicandoessaregra,somenteseráconsideradootrecho que tiver atribuído o custo máximo dentre os trechos ou sentenças consideradosnosumatório.

Aplicandoaabordagemdedividir para conquistar, a complexidade de um algoritmo pode ser determinada a partir da complexidade das suas par-tes.Deformageral,aanálisedacomplexidadeéfeitaemformaparticularpara cada algoritmo, mas existem conceitos gerais que só dependem das estruturas algorítmicas ou comandos de controle utilizados no algoritmo:

1)Sequênciaouconjunçãoéumtipodecomandoque,nofluxológicodo programa, é executado e o controle passa para o próximo co-mandonasequência.

• Aanálisedacomplexidadenestecasoenvolveaaplicaçãodaregra da soma para a notação O com base na complexidade dos comandos.

2)Seleçãooudisjunçãoéumtipodecomandoque,nofluxodeexe-cução permite que desvios possam ser feitos a partir do resultado da avaliação de uma condição, executando um bloco de comandos eoutrosnão.

• Aanálisesempreéfeitaconsiderandoopiorcaso.Consequen-temente, na avaliação da complexidade é considerado o desvio que envolve a execução do bloco de comandos mais custoso, a partirdaavaliaçãodacondição.Adicionalmente,aavaliaçãoda condição consome tempo constante

3)Repetiçãoéumtipodecomandoque,nofluxodeexecuçãodopro-grama, permite que um bloco de comandos seja repetido enquanto umacondiçãoésatisfeita.

• Alémdachecagemdacondição(O(1)), o custo de um comando de repetição envolve o custo do bloco envolvido, multiplicado pelonúmerodevezesqueseráexecutado,nopiorcaso.Vale


ressaltar que pode existir aninhamento de comandos de repe-tição.Nestecasoaanáliseéfeitadedentroparafora.Olaçopodeserdefinido(for)ouindefinido(while).

4)Umcomandodeatribuiçãopossibilitaqueumvalorpossaseratri-buídoaumavariável.

• Umcomandodeatribuiçãoconsometempoconstante.

Por exemplo, dado um vetor v de números inteiros de tamanho n, re-tornaromaiorelementodestevetor.

1: int Maximo (int v[], int n)2: int i: n;3: int max;4:

5: if n = 0 error (“ Vetor vazio ”)

6: else 7: max = v[0];

8: for (i = 1; i < n; i++) 9: if v[i] > max then max = v[i];10:

11: return max;12:

O número ndeelementosdovetorrepresentaotamanhodaentrada.Oprogramacontémumcomandodeiteração(8)quecontémumcomandodedesiçãoque,porsuavez,contémapenasumcomandodeatribuição(9).O comando de atribuição requer tempo constante O(1) para ser executado, assimcomoaavaliaçãodocomandodedesição.Considerandoopiorcaso,ocomandodeatribuiçãosempreseráexecutado.

O tempo para incrementar o índice do laço e avaliar sua condição de terminação também é O(1), e o tempo combinado para executar uma vez o laçocompostopelaslinhas(8)e(9)éO(max(1, 1)) = O(1), conforme a regra de soma para a notação O, e considerando que o número de iterações do laço é n - 1,entãootempogastonolaço(8)éO((n - 1) x 1) = O(n - 1), conforme a regra do produto para a notação O.

O algoritmo é estruturado com base em um comando de desição, cuja condição é checada em tempo constante, da mesma forma que a edição da mensagem de erro (O(1)).Poroutro lado,utilizandoaregradasomanova-mente,temosqueaexecuçãodaslinhas(7),(8)e(9)consomeO(max(1, n - 1)) = O(n - 1).Nopiorcasotemosqueaexecuçãodobloco(5)consomeO(n - 1).Finalmente,ocomando(11)éexecutadoemtempoO(1).Aplicandonovamentearegradasomaentre(5)e(11)temosqueO(max(n – 1, 1)) = O(n - 1).Portantoa complexidade temporal do algoritmo Maximoélinear.

Simplificandoaanálise,aquantidadedetrabalhodoalgoritmopodeserdeterminadapelaquantidadedeexecuçõesdaoperaçãofundamental.Noentanto, pode existir mais de uma operação fundamental com pesos diferen-tes.Nestecaso,aregradesomaparaanotaçãoOpodeseraplicada.


ConsidereoalgoritmobuscaBinariadescritoaseguir:

int buscaBinaria (int array[], int chave, int n)

int inf = 0; //Limite inferior

int sup = n - 1; //Limite superior

int meio;

while (inf <= sup)

meio = (inf + sup) / 2;

if (chave == array[meio])

return meio;

else if (chave < array[meio])

sup = meio - 1;

else inf = meio + 1;

return -1; // não encontrado

1. Descreva o funcionamento do algoritmo buscaBinaria. Qual situaçãorepresenta o pior caso? e o melhor?

2. Considerando a execução do algoritmo buscaBinaria em um vetor com 15elementos,quantas repetições (númerodepassos) sãonecessáriospara o algoritmo detectar que uma determinada chave de busca não se encontranovetor.

3. Determine a complexidade temporal do algoritmo buscaBinaria anali-sandopasso-a-passoacomplexidadedecadacomando.

Nestaunidadefoiapresentadoumestudointrodutóriosobreosfun-damentos da teoria sobre complexidade de algoritmos.Esta teoria é defundamental importância uma vez que possibilita determinar a melhor solução para um determinado tipo de problema, assim como também ela-borarprojetosdealgoritmoscadavezmaiseficientes.


CORMENT.H.,LEISERSONC.E.,RIVESTR.L.,STEINC.(2001).Intro-duction to Algorithms.McGraw-HilleTheMitPress.

KNUTHD.E.(1968).The Art of Computer Programming,Vol.1:Funda-mentalAlgorithms.Addison-Wesley.

KNUTHD.E. (1971). Mathematical Analysis of Algorithms.ProcedingsIFIPCongress71,vol.1,NorthHolland,135-143.

WIRTHN.(1986).Algorithms and Data Strutures.Prentice-Hall.

ZIVIANIN.(2005).ProjetodeAlgoritmoscomimplementaçõesemPas-cal e C,2da.Edição.Thomson.

Unidade

Objetivos:

• Nestaunidade édescrito oprocessodeabstração seguidoparaamodelagemedesenvolvimento de uma solução computacional a partir de um problema do mundo real.Nestecontexto,osconceitosdetiposdedados,estruturasetiposabstratossão introduzidos, ressaltando sua importância para a adequada modelagem, manipulaçãoerepresentaçãonamemóriadocomputador.

Representação dos Dados

2


Capítulo 1Modelagem Conceitual

Para que um problema do mundo real possa ser resolvido compu-tacionalmente é necessário utilizar métodos e técnicas que possibilitem a modelagem adequada do problema, de forma que possa ser interpretado e processadopelocomputadorparagerarumasolução.

Os modelos são utilizados para representar o mundo real de forma simplificada,comoobjetivodefacilitarogerenciamentodacomplexidade.Ummodelorefleteosaspectosconsideradosimportantesparaodesenvolvi-mento da aplicação, deixando em um segundo plano, os aspectos que não sãorelevantes.

Amodelagemdesituaçõesdomundorealéalcançadaatravésdeumprocesso de abstração, a partir do qual, somente as propriedades relevantes paraaaplicaçãosãoconsideradasnomodelo.

O processo de abstração envolve a observação das entidades presentes no domínio do problema para a correspondente representação no domínio computacional.

Nonívelmaisbaixodeabstração,arepresentaçãodosdadosanívelde máquina acontece de acordo a padrões de bits e bytes dememória.No entanto, as linguagensdeprogramaçãomodernaspossibilitamqueoprogramador possa trabalhar com objetos relativamente complexos em um nível mais alto de abstração, tornando transparente ao desenvolvedor a ma-nipulaçãodosdadosaoníveldasuarepresentaçãointernanocomputador.Estafacilidadeéalcançadaatravésdautilizaçãodeumavariedadedetipos de dados.

Tipo de dados O tipo de dados associado a uma variável, numa linguagem de progra-

mação,defineoconjuntodevaloresqueavariávelpodeassumir.Istoé,adeclaraçãodavariávelcomosendodeumtipoespecíficodetermina:

1.Aquantidadedebitsquedevemserreservadosnamemória.

2. Como o dado representado por esse padrão de bits deve ser inter-pretado(p.e.,umacadeiade bits pode ser interpretada como sendo uminteirooureal).

Bitsignificadígitobinário,do ingles BInary digiT.Umbit é a menor unidade de informação que pode ser armazenada ou transmiti-da.Umbit pode assumirsomente 2 valores: 0 ou 1, verdadeirooufalso.O conjunto de 8 bits é de-nominadodeByte.

O sistema operacional (SO) é um programa ouconjunto de programas responsável por gerenciar todos os recursos do sis-tema, tais como: coman-dos do usuário, arquivos, memória,etc.


Os tipos têm geralmente associações com valores na memória ou va-riáveis.Consequentemente,tiposdedadospodemservistoscomométodospara interpretar o conteúdo da memória do computador, o que pode variar conformeosistemaoperacionalealinguagemdeimplementação.

Nasuamaioria,as linguagensdeprogramaçãoexigemqueumco-mandodeclarativoquedefineumavariávelespecifiquetambémotipodedadosassociadoàvariável.Estas linguagenssãochamadasde fortemen-te tipadas.Emcontrapartida,aslinguagensfracamente tipadas permitem queadefiniçãodotipocorrespondenteaumavariávelpossaserdetermina-dadinamicamente,emtempodeexecução.

Ostiposdedadospodemserclassificadosemdoisgrupos:primitivos ou básicos e compostosouestruturados.

Os tipos de dados primitivos são fornecidos pela linguagem de progra-maçãocomoumblocodeconstruçãobásico.Dependendodaimplementa-ção da linguagem, os tipos primitivos podem ou não possuir correpondên-cia direta com objetos na memória.Exemplosdetiposprimitivoscomunssão: inteiro, real, caractere, booleano,dentreoutros.

Alémdeestabelecerumesquemapredeterminadodearmazenamento,adefiniçãodeumtipodedadosprimitivoestabelecetambémumconjuntodeoperaçõespredefinidassobreaqueletipo.Consequentemente,adefiniçãode uma variável como instância de um desses tipos determina o conjun-todeoperaçõesquepodemserrealizadasutilizandoessasvariáveis.Porexemplo,aoconsiderarvariáveisdotipoprimitivointeiro(int),asoperaçõespermitidas se traduzem nos operadores aritméticos válidos para os valores dessetipo,nocaso:soma(+),subtração(-),multiplicação(*),divisãointeira(DIV)erestodadivisãointeira(MOD).Estasoperaçõessãoimplementadasde forma nativa por qualquer linguagem de programação, e seu desenvolvi-mentoficatransparenteaousuário.

Dada a complexidade das entidades do domínio do problema a serem modeladas e representadas no universo computacional, o fosso semântico (gapsemântico)envolvendoadescriçãodealtoníveldeumaentidade(do-míniodoproblema),eadescriçãodebaixonível(domíniodasolução)podeserinconciliável.Nestecontexto,apossibilidadededefinirtiposdedadosque possibilitem a representação destas entidades de forma mais próxima da realidade facilita o processo de abstração, assim como contribui para a reduçãodofossosemânticoentreambososdomínios.

Oprogramadorpodedefinirtipos de dados próprios que mais corres-pondam às necessidades de suas aplicações.Linguagensdeprogramaçãoatuaispermitemaosprogramadoresdefinirtiposdedadosadicionais, uti-lizandoostiposprimitivoseasestruturascomoblocosconstrutivos.Porexemplo,paradefiniravariávelEmpregado com esta estrutura heterogênea em C seria:

struct char Nome[9] int Idadefloat Qualifi cação

Empregado

Noentanto,seaestruturaformuitofrequente,oprogramapodeficarvolumosoedifícildeserlido.Ométodomaisadequadoconsisteemdescre-

Amemóriaéodispositivoque permite a um compu-tador armazenar dados de forma temporária ou per-manente.

O fosso semântico repre-senta a diferença entre uma descrição de alto ní-vel e outra de baixo nível relativa a uma mesma en-tidade.


ver a estrutura de dados correspondente uma única vez, associando-a a um nomedescritivo,eutilizaressenometodasasvezesquefornecessário.

typedef struct char Nome[9] int Idadefloat Qualificação TipoEmpregado

EstadeclaraçãodefineumnovotipodenominadoTipoEmpregado que pode ser usado para declarar variáveis da mesma forma como um tipo pri-mitivo.

TipoEmpregado Empregado

Apartirdestadefiniçãoépossívelgerarascorrespondentesvariáveisinstância,asquaisirãoassumirvaloresnosatributos,dependendodotipo.Por exemplo, valores válidos para uma variável do tipo Empregado podem ser:

Nome: João Soares

Idade: 25 anos

Qualificação: 8.58

Umtipodefinidopelousuárioéessencialmenteummodelo usado para construir instâncias de um dado tipo, que descreve todas as características que todas as instâncias deste tipo devem assumir mas não constitui, ele próprio,umaocorrênciarealdestetipo.

Aforma conceitual dos dados é materializada pela estrutura de dados utilizadanaimplementaçãodotipo.Umaestruturadedadoséumaformaparticular de se implementar um tipo, e é construída dos tipos primitivos e/ou compostos de uma linguagem de programação, e por este motivo são chamados de tipos compostosouestruturados.

Umtipocompostoenvolveumconjuntodecamposemembrosorga-nizados de forma coerente, onde o tamanho total da estrutura corresponde àsomadostamanhosdoscamposconstituintes.Exemplosdetiposestru-turadossão:registros,vetores,matrizes,arquivos,árvores,dentreoutros.

Aescolhaporumaestruturadedadosédeterminantenaqualidadeeesforço requeridoparaodesenvolvimentodasolução.Asestruturasdedados e algoritmos são escolhidos com base em critérios diversos, tais como desempenho, restrições de plataforma de hardware e software, capacidade doequipamento,volumededados,etc.Asestruturasdedadosdividem-seemhomogêneaseheterogêneos.Asestruturashomogêneassãoconjuntosdedadosformadosporcomponentesdomesmotipodedado(p.e.,vetores,matrizes,pilhas,listas,etc.).Emcontrapartida,asestruturasheterogêne-as são conjuntos de dados formados por componentes pertencentes a tipos dedadosdiferentes(p.e.,registros).Aescolhadeumaestruturadedadosapropriada pode tornar um problema complicado em uma solução bastante trivial.

Diferentementedoqueacontecenadefiniçãodetiposdedadosbási-cos, onde um conjunto de operações de manipulação é fornecido, no caso dostiposestruturadosdefinidospelousuárioapenasnovosesquemasdearmazenamentosãodefinidos.Istosignificaque,aprincipio,nãosãoforne-cidosmeiosparadefinirasoperaçõesaseremexecutadassobreinstâncias


de tais estruturas.Consequentemente, algoritmosdemanipulaçãopreci-sam ser desenvolvidos de forma a possibilitar a correta utilização e acesso àsnovasestruturasdefinidas.

1.Definaosconceitosdetipodedadobásicoetipodedadodefinidopelousuário.

2. Cite como exemplos tipos de dados básicos que você conhece e detalhe suascaracterísticaseasoperaçõespermitidassobreessestipos.

3.Definaumtipodedadoestruturadoquedescrevadeformaadequadaecompleta as seguintes informações:

a.Livro

b.Círculo

c. Filme

d.Pessoa

e. Aluno

f. Itemdeestoque

g. Contabancaria

Tipo abstratos de dados Um tipo de dado defi nido pelo usuário,incrementadocomadefiniçãoe

implementação das operações necessárias para a sua manipulação, consti-tuiumTipoAbstratodeDados(TAD),conceitocentralnocontextodoPara-digma Orientado a Objetos.AutilizaçãodeTADspermitequelinguagensde programação de propósito geral sejam personalizadas para um domínio de aplicaçãomais específico. Uma vez definidos, podem ser empregadoscomo primitivas da linguagem, e possibilitam o desenvolvimento de compo-nentesdesoftwarereusáveiseextensíveis.

TADsestendemanoçãodetipodedado(estruturadedados+ope-rações)combasenautilizaçãodetécnicasdeocultamentodainformaçãoreferente à estrutura de dados utilizada e à implementação das operações definidas.Esteobjetivoéalcançadoatravésdeumaclaraseparaçãoentreinterfaceeimplementação.

Naabordagemorientadaaobjetos(OO),oprocessodeabstraçãoutili-zado para chegar a uma modelagem computacional de entidades do mundo realébaseadonaanálisedassuasfuncionalidades.Destaforma,osobje-tos são categorizados com base na estrutura e no comportamento comum através da implementação de classes.UmaclassedefineumTADapartirdetrêscomponentes:definiçãodainterfacepública,definiçãodaestruturade dados, e a implementação da interface com base na estrutura de dados escolhida.Ainterfaceépública,umavezquepossibilitaoacessoaosda-dos da classe, enquanto que a implementação é privada, ou seja, oculta ao

O paradigma orientado a objetos envolve um con-junto de técnicas, méto-dos e ferramentas para análise, projeto e imple-mentação de sistemas de software baseado na composição e interação de componentes de software denominadosdeobjetos.

Umainterfacelistaosser-viços fornecidos por um componente, restringindo o acesso de entidades ex-ternasaoobjeto.A interface lista todos osmétodos e argumentos que o objeto entende e é capazderealizar.Defineainterfacedeaces-so à estrutura sem fazer qualquer referência à im-plementação utilizada, e possibilita uma clara se-paração entre implemen-taçãoeespecificação.


usuáriodaclasse.AseguiréapresentadaumailustraçãoquedescreveaorganizaçãodeumTAD.

A interface do TAD é independente da repre-sentação escolhidapara a sua implementação. Istosignificaqueamesmainterfacepodeserimplemen-tadautilizandodiferentesestruturasdedados.Ain-terface propicia uma forma de encapsulamento pro-tegendoainformaçãoprivadadeacessosindevidos.Adicionalmente,estemecanismofacilitaarealizaçãode mudanças, uma vez que estas acontecem de for-ma transparente ao resto do programa, sempre que a interfacesejamantida.Estamodelagemfacilitaodesenvolvimento, extensibilidade e propicia o reuso de software. A seguir é apresentado como exemplo a definiçãodo tipoabstratoRetângulo.Umretângulopodeserdefinidopelasualarguraealtura.Aespecificaçãodotiporetângulopodeserdefinidacomo:

typedef struct

fl oat altura, largura;

TipoRetangulo

Apartirdestasinformaçõesépossívelcalcularsuaáreaeperímetro.Portanto, além do construtor do tipo e das operações de consulta sobre as informações do retângulo, as operações de cálculo de área e perímetro são requeridas.

Desta forma, a interface do tipo abstrato retângulo inclui as seguintes operaçõesdemanipulação.

// construtorRetangulo (float a, float l); // atribui um valor à altura void InitAltura (float a);

// retorna o valor da altura float Altura (void) ; // atribui um valor à largura void InitLargura (float l); // retorna o valor da largura float Largura (void); // calcula o valor do perímetro float Perimetro (void);

// calcula o valor da área float Area (void) const;

Uma classe representaum conjunto de objetos comcaracterísticasafins.Umaclassedefineocom-portamento dos objetos através de seus métodos, e o estado através de seus atributos. Exemplo declasse: animais, vegetais, minerais.

O construtor é um méto-do distinguido que tem como função principal a de instanciar o objeto cor-retamente, para seu uso posterior.


Finalmente, todos os métodos da interface são implementados na lin-guagemdeprogramação.Exemplosdaimplementaçãodealgunsdosméto-dosdainterfacesãoapresentadosaseguir.

Retangulo::Retangulo (float a, float l) altura = a; largura = b;

float Retangulo::Altura (void) return altura;

float Retangulo::Perimetro (void) return 2 * (altura + largura);

Linguagensorientadasaobjetos(OO)forneceminúmerosmecanismosparadarapoioàconceituaçãoenvolvidanadefiniçãoeimplementaçãodeTADs.Dentreestesmecanismostemos:

• Encapsulamentoatravésdequalificadores (private, public e protected).

• Herança• Polimorfismo• Sobrescritadeoperações.

O projeto de um tipo abstrato é uma tarefa difícil, pois este deve ser ideado de forma a possibilitar a sua utilização por parte de terceiros, favo-recendo o reuso e agilizando o processo de desenvolvimento de software.Aatividade de projeto envolve a escolha de operações adequadas, delinean-do seu comportamento consistentemente, de forma que estas possam ser combinadas para realizar funções mais complexas, a partir de operações simples.

Nointuitodeaumentaroreusodasoperações,estasdevemserdefini-das de forma coesa, e ter um comportamento coerente, com um propósito es-pecíficoeevitandoconsiderardiversoscasosespeciaisemummesmocódigo.

OconjuntodeoperaçõesqueintegramainterfacedoTADdeveofere-cer todas as operações necessárias para que os usuários possam manipu-laraestruturaadequadamente.Umbomtesteconsisteemchecarsetodasaspropriedadesdoobjetodeumdeterminadotipopodemseracessadas.

Deformageral,ostiposabstratosdedados(TADs)sãocaracterizadosatravésdesuasoperações.Noentanto,nocódigo,umaclassequeimple-menta um tipo abstrato possui uma representação: a estrutura de dados propriamenteditaquesuportataisoperações.Arepresentaçãoenvolveumacoleçãodecamposcadaumdosquaiséassociadoaumtipodedados.

Emuma representação recursiva, um campo pode ser vinculado aoutrotipoabstratoouumaclasse.

A escolha pela representação mais adequada ao problema envolveuma análise aprofundada, uma vez que cada representação possível possui diferentesvantagensedesvantagens.

Acoesãoédefinidacomoa medida de proximidade no relacionamento entre todas as responsabilida-des, os dados e os méto-dos de uma classe. Sim-plificando, coesão podeser traduzida como a me-dida que indica se uma classe ou operação tem umafunçãobemdefinidano sistema. Em geral, aalta coesão é considera-da uma propriedade al-tamente positiva por que facilitaoreuso.

A fase de projeto produzuma descrição computa-cional do que o software deve fazer, e deve ser co-erente com as especifica-ções geradas na análise, de acordo com os recursos tecnológicosexistentes.


1.DefinaosconceitosdeTipoAbstratodeDadosedeClasse.Estabeleçaorelacionamentoquevinculaambosconceitos.

2.Defina TADs para os tipos de dados estruturados para as entidadeslistadasaseguirespecificandodetalhadamenteainterfacecompleta.Ainterface deve incluir todas as operações necessárias para a correta ma-nipulaçãodotipo,dentreelasosmétodosdeinicialização,modificação,econsulta.a.Livrob.Círculoc. Filmed.Pessoae. Alunof. Itemdeestoqueg. Contabancária

3. Implemente duas das interfaces propostas no exercício anterior utili-zando a linguagem de programação da sua escolha ou pseudo-código próximodalinguagem.

Critérios para a escolha da estrutura de dados adequada

Comoditoanteriormente,ainterfacedoTADindependedaimplemen-tação e, portanto, diferentes estruturas de dados podem ser utilizadas como esquema de armazenamento na memóriaparaseusatributos.Apartirdoesquemautilizadoosdadospodemserarmazenadoserecuperados.

Aformaemqueaalocaçãodememóriaacontece,podeserumfatordeterminanteparaaescolhadeumadeterminadaestruturadedados.

Uso da memória

Informalmente, podemos dizer que existem três maneiras de reservar-mos espaço de memória para o armazenamento de informações:

• Usodevariáveisglobais(eestáticas).Oespaçoreservadoparaumavariávelglobalexisteenquantooprogramaestiversendoexecutado.

• Usodevariáveislocais.Nestecasooespaçoficareservadoapenasenquanto a função que declarou a variável está sendo executada, sendo liberado para outros usos quando a execução da função ter-mina. Por estemotivo, a função que chamanão pode fazer refe-rênciaaoespaçolocaldafunçãochamada.Asvariáveisglobaisoulocais podem ser simples ou vetores, sendo que no caso dos vetores, é preciso informar o número máximo de elementos ou tamanho do vetor.Apartirdotamanhoinformado,ocompiladorreservaoespa-çocorrespondente.

Amemóriaéodispositivoque permite a um compu-tador guardar dados de forma temporária ou per-manente.


• Requisiçõesaosistemaemtempodeexecução.Esteespaçoalocadodinamicamente permanece reservado até que explicitamente seja liberadopeloprograma.Umavezqueoespaçoéliberadoficadispo-nívelparaoutrosusos.Seoespaçoalocadonãoforliberadoexplici-tamente pelo programa, este será automaticamente liberado quando asuaexecuçãoterminar.Aseguiréilustradaesquematicamenteaalocaçãodamemóriapelosistemaoperacional.

Quando requisitamos ao sistema operacional para executar um de-terminado programa, o código em linguagem de máquina do progra-madevesercarregadonamemória.O sistema operacional reserva tam-bém o espaço necessário para ar-mazenarmos as variáveis globais (e estáticas) utilizadas ao longo doprograma.Orestantedamemóriaéutilizado pelas variáveis locais e pe-las variáveis alocadas dinamica-mente enquanto o programa está executando.Cada vez que uma determinada fun-ção é chamada, o sistema reserva o espaço necessário para as variáveis locais da função. Este espaço per-tence à pilha de execução e, quando a função termina, é desempilhado e

liberado.Apartedamemórianãoocupadapelapilhadeexecuçãopodeserrequisitadadinamicamente.Seaolongodediversaschamadasafunção,apilha cresce atingindo o espaço disponível existente, dizemos que ela “estou-rou”eoprogramaéabortadocomerro.Similarmente,seoespaçodememó-ria livre for menor que o espaço requisitado dinamicamente, a alocação não é feita e o programa pode prever um tratamento de erro adequado (por exem-plo,podemosimprimiramensagem“Memóriainsuficiente”einterromperaexecuçãodoprograma).

Como mencionado anteriormente, a alocação de memória pode acon-teceremtempodecompilação(estática)ouemtempodeexecução(dinâmi-ca).Nocasodaalocaçãodememóriaemformaestática,oespaçodestinadoparaoarmazenamentodosdadospossuiumtamanhofixo,quenãopodesermodificadoaolongodaexecuçãodoprograma.Adicionalmente,aaloca-çãodememóriaaconteceemespaçoscontíguos,istoé,umdoladodooutro.Exemplosdealocaçãoestáticadememóriasãovariáveisglobaisevetores.Nocasodovetor,apartirdecertoendereçoεquearmazenaoprimeiroele-mento a1 do vetor, os elementos subsequentes podem ser acessados direta-mente incrementando em k o endereço inicial do vetor, onde k é o tamanho dememóriaocupadoporcadaelementodovetor.


Emcontrapartida, no casode alocaçãodinâmica, amemória é ge-renciada sob demanda, ou seja, os espaços de memória são alocados e de-salocadosdependendodanecessidade,duranteaexecuçãodoprograma.Consequentemente, a alocação não acontece necessariamente de forma contígua(ousequencial),podendo,osdados,ficaremesparsosnamemóriadocomputador.Apartirdestaconfiguraçãoondeosdadossãoarmazena-dos de forma não sequencial, o acesso é alcançado através de variáveis do tipo ponteiro,indicandooendereçodememóriacorrespondente.Aseguiré ilustrada esquematicamente a distribuição dos elementos integrantes de umacadeiaaolongodamemória.Naprimeiracolunaéindicadooendereçocorrespondenteaoconteúdo.Acolunaponteiro indica o endereço do próxi-moelementonacadeia.Notequeosegundoelementonãoocupaoendereçoconsecutivo ao a1.

Endereço Conteúdo Ponteiro Observação

L=3FFB a1 1D34 Primeiro elemento acessado a partir de L

1D34 a2 BD2F

BD2F a3 AC13

1500 an-2 16F7

16F7 an-1 5D4A

5D4A an nullÚltimo elemento da cadeia. O endereço null indica que o elemento não tem sucessor.

Apartirdascaracterísticasdecadaumadasabordagensparaaalo-caçãodosdados,vantagensedesvantagenspodemserestabelecidas.

Alocaçãoestática:• Vantagem:Possibilitaacessodiretoaolocaldamemória,umavez

que os dados se encontram armazenados de forma contígua ou se-quencial. Consequentemente, em alguns casos, as operações debusca podem ter custo constante O(1).

• Desvantagem:Éprecisodeterminaremtempodecodificação,quan-toespaçoénecessário.Estaestimativapodeserdifícildeseresta-belecida,eestásujeitaaflutuaçõesaolongodaexecução.Conse-quentementeoespaçopode resultar insuficienteoupode tersidosobreestimado.Poroutro lado,aalocaçãosequencialnamemóriaprejudica as operações de inserção e remoção, uma vez que a se-quencialidadedosdadosprecisaserpreservada.Comisso,nopiorcaso, o custo destas operações pode ser de O(n) por conta dos deslo-camentos necessários para abrir ou fechar espaços para inserção e remoção,respectivamente.

Alocaçãodinâmica:• Vantagem:nãoénecessáriofixarotamanhodaestruturaapriori,

uma vez que a alocação de memória é feita sob demanda em tempo deexecução.Comissoéevitadoodesperdíciodeespaço,eoriscodeficarsemespaçoéreduzido.Consequentemente,nãoexisteres-triçãoencimadonúmerodeinserçõeseremoções.Adicionalmente,estas operações não requerem de nenhum esforço adicional uma vez que envolvem somente o ajuste dos ponteiros já que os elemen-tosseencontramesparsosnamemória.

• Desvantagem: o gerenciamento dos dados diretamente da memória pode ser trabalhoso e propenso a erros. Como conseqüência da

O ponteiro ou apontador é um tipo de dado que ar-mazena o endereço de um outrodado.A partir do ponteiro, odado que se encontra no respectivo endereço pode ser acessado e manipu-lado.


não linearidade na alocação dos dados, o acesso a um determina-do elemento i torna necessário o percurso pelos i – 1 elementos an-terioresnasequência.Estapropriedade,quecaracterizaoacessosequencial aos dados, torna a operação de busca por um elemento de custo O(n).

Nestaunidadefoiapresentadooconceitodeabstraçãoeseusníveis,easuaimportâncianoprocessodemodelagem.Tiposdedadosbásicoseestruturadosforamdefinidosnestecontexto,comomeiosderepresentareinterpretarasinformaçõesmanipuladaspelaaplicação.Adicionalmente,oconceito de tipo abstrato é estabelecido como um mecanismo de extensão e customização de linguagens de programação, no intuito de facilitar o de-senvolvimentodesistemas.TADssãocaracterizadosporsuasoperações,as quais são encapsuladas junto à sua estrutura, sendo acessíveis exclu-sivamenteatravésdainterfaceespecificada,garantindoindependênciadaimplementaçãoutilizada.Aindependênciaderepresentaçãotornapossívelalterararepresentaçãodeumtiposemqueseusclientessejamafetados.Finalmente, noções de gerência de memória foram introduzidas, focando nas principais características que influenciam na escolha pela alocaçãoestáticaoudinâmicadamemória.Umaanálisedosfatoresquecontribuemnatomadadedecisãofoiapresentada.

CORMENT.H.,LEISERSONC.E.,RIVESTR.L.,STEINC.(2001).Intro-duction to Algorithms.McGraw-HilleTheMitPress.

TENENBAUMA.M.,LANGSAMY.,AUGENSTEINM.J.(1995).Estruturas de Dados Usando C,MakronBooks/PearsonEducation.

WIRTHN.(1986).Algorithms and Data Structures.Prentice-Hall.


Unidade

Objetivos:

• Existem certas estruturas clássicas que se comportam como padrões uma vezquesãoutilizadasnapráticaemdiversosdomíniosdeaplicação.Nestaunidadeé apresentada a estrutura de dados Lista e o correspondente Tipo Abstrato,detalhando a sua interface e apresentando duas implementações: vetores e ponteiros.Variantesdotipoabstratolistas,naformadePilhaseFilas,deamplautilizaçãoprática,sãodescritas.

Listas

3


Capítulo 1Listas

IntroduçãoUmconjuntodeelementospodeserintuitivamenterepresentadoatra-

vésdeumalistalinear.Listassãoestruturasextremamenteflexíveisquepossibilitam uma ampla manipulação das informações uma vez que inser-çõeseremoçõespodemaconteceremqualquerposição.

Umalistapodeserdefinidacomoumaestruturalinear,finitacujaor-demédadaapartirdainserçãodosseuselementoscomponentes.Aslistassão estruturas compostas, constituídas por dados de forma a preservar a relaçãodeordemlinearentreeles.Cadaelementonalistapodeserumdadoprimitivoouarbitrariamentecomplexo.

Emgeral,umalistasegueaformaa1, a2, a3,...,an, onde n determina o tamanhodalista.Quandon = 0 a lista é chamada nula ou vazia.Paratodalista, exceto a nula, ai + lsegue(ousucede)ai (i<n),eai - 1 precede ai (i>1).Oprimeiro elemento da lista é a1, e o último an.Aposiçãocorrespondenteaoelemento ai na lista é i.

Ascaracterísticasbásicasdaestruturadedadoslistasãoasseguintes:• Homogênea.Todososelementosdalistasãodomesmotipo.• A ordemnos elementos é decorrente da sua estrutura linear, no

entanto os elementos não estão ordenados pelo seu conteúdo, mas pelaposiçãoocupadaapartirdasuainserção.

• Para cada elemento existe anterior e seguinte, exceto o primeiro, que não possui anterior, e o último,quenãopossuiseguinte.

• Épossívelacessareconsultarqualquerelementonalista.• Épossívelinserireremoverelementosemqualquerposição.

Defi nição do TAD ListaComoapresentadonaunidadeanterior,adefiniçãodeumTipoAbs-

tratodeDados (TAD)envolveaespecificaçãoda interfacedeacessoparaamanipulaçãoadequadadaestrutura,apartirdaqualsãodefinidasemdetalhe,asoperaçõespermitidaseosparâmetrosrequeridos.Oconjuntode operações depende fortemente das características de cada aplicação, no entanto,épossíveldefinirumconjuntodeoperaçõesmínimo,necessárioecomumatodasasaplicações.

Uma estrutura é dita delinear uma vez que seus elementos componentes se encontram organizados de forma que todos, a ex-ceção do primeiro e últi-mo, possuem um elemen-to anterior e um posterior, somente.


Interface do TAD Lista

/* Cria uma lista vazia

Lista Criar ()

/*insere numa dada posição na lista.

int Inserir (Lista l, tipo _ base dado, corrente pos)

/* Retorna o elemento de uma dada posição

tipo _ base consultaElemento (Lista l, corrente pos)

/*Remove o elemento de uma determinada posição

int Remover (Lista l, corrente pos)

/* Retorna 1 a lista está vazia, ou 0 em caso contrario.

int Vazia (Lista l)

/* Retorna 1 se a lista está cheia, ou 0 em caso contrario.

int Cheia (Lista l)

/* Retorna a quantidade de elementos na lista.

int Tamanho (Lista l)

/* Retorna o próximo elemento na lista a partir da posição corrente.

corrente proximoElemento (Lista l, corrente pos)

/*Busca por um determinado elemento e retorna sua posição corrente, ou -1 caso não seja encontrado.

corrente Busca (Lista l, tipo _ base dado)

Umavezdefinidaainterface,estapodeserimplementadautilizandoumarepresentaçãodosdadosadequada.Existindomaisdeumaestruturaadequada, a escolha depende principalmente das necessidades e caracterís-ticasdosdadosaseremmanipuladospelaaplicação.

Aseguir,oTipoAbstratoListaéimplementadoutilizandoduasestru-turas de dados comumente utilizadas e adequadas às necessidades, cada umacomvantagensedesvantagensparticulares.

Implementação do TAD Lista usando alocação estática Naimplementaçãodelistaadotandoalocaçãodememóriaestáticaos

elementos componentes são organizados em posições contíguas de memória utilizando arranjosouvetores.

Vantagensedesvantagensdestaestruturaforamdiscutidasnaunida-de3.Emparticular,autilizaçãodevetoressetornaadequadanocasoem


que existe uma clara noção do tamanho da entrada a ser processada, e uma perspectivaqueindicaqueasaplicaçõesqueirãoutilizaroTADnãoestarãoexecutando muitas operações de inserção e remoção que possam vir a alte-rarsignificativamenteotamanhopreestabelecido.Aestruturaçãodalistautilizandoalocaçãoestáticaéapresentadagraficamenteaseguir.Noteque,a partir do endereço correspondente ao primeiro elemento no vetor (pos),econhecendo o tamanho (c)decadacomponentenalista,épossívelcalcularo endereçonamemóriadequalquer elementoarmazenadonovetor. Issogarante o acesso direto aos elemento em O(1).

Aseguir éapresentadaadefiniçãodaestruturadedadose imple-mentaçãodasoperaçõesdefinidasnainterfaceutilizandoalocaçãoestáticadememóriaatravésdadefiniçãodevetores.Considerandoautilizaçãodealocação estática de memória, o tamanho da estrutura de dados precisa ser determinadoemtempodecompilação.

#define tamanho

Umalistaéumtipodedadoqueestruturaelementoscujotipopodeser arbitrariamente complexo, envolvendo inclusive, a utilização de outros TADs.A definição a seguir especifica o tipo base dos elementos da listacomointeiros.

typedef int tipo _ base;

Os elementos da lista são organizados em um vetor, de tamanho pre-definido.Adicionalmente,umatributocontendoaquantidadedeelementosda lista (quant_Elem)éincluídonaestruturanointuitodetornarmaisfácile ágil o acesso aos elementos e possibilitar o controle do crescimento da estrutura.

typedef struct tipo _ base v[tamanho];

int quant _ Elem;

no _ Lista;

A informação relativa à quantidade de elementos existente na lista pode ser útil em diversas situações uma vez que, conhecendo a posição na memória(endereço)doprimeiroelementodalista,épossívelcalcularoen-dereço do último elemento e, consequentemente, da primeira posição dispo-nível.Istoépossívelporcontadapropriedadedearmazenamentocontíguopropiciadapelaestruturadedados.

Anotaçãoutilizadanaim-plementação é próxima à linguagemC.

Na linguagem C, a posi-ção que corresponde ao primeiro elemento do ve-tor corresponde ao índice i = 0. Em outras lingua-gens, como por exemplo Pascal, o primeiro elemen-to no vetor se encontra na posiçãoi=1.


Finalmentealistaédefinidacomoumponteiroàestruturadedadosondeoselementossãoagregados.

typedef no _ Lista *Lista;

Acriaçãodeumalistainicialmentevaziaenvolveadefiniçãodopon-teiro correspondente, apontando a um endereço de memória reservado com tamanho adequado para o armazenamento da estrutura, em particular, o primeironórepresentandoacabeçadalista.Otamanhodalistaéiniciali-zadoemzeroumavezqueinicialmentenãocontemelementos.

Lista Criar () Lista l = (Lista) malloc (sizeof (no _ Lista));

If (l != NULL) l -> quant _ Elem = 0;

return (l);

else printf (“Não existe memória suficiente”); return;

Normalmente,alistaprecisaserpercorridadeformaarealizaralgumtipodeprocessamentosobreosdadosqueacompõem.Consequentementese torna necessário um mecanismo que possibilite checar no momento em quenãosejapossívelprocessarmaisnenhumelemento.OmétodoultimoE-lementoéresponsávelporfazerestachecagem.

int ultimoElemento (Lista l, corrente pos) if (pos + 1 == l -> tamanho) return (1) else return (0);

Aexecuçãodeumaoperaçãoderemoçãorequeraexistenciadenomínimoumelementonalista.OmétodoVazia retorna o valor 1 no caso da listaseencontrarvazia,e0emcasocontrário.

int Vazia (Lista l) if (l -> quant _ Elem == 0) return (1)else return (0);

Outra operação que pode ser de utilidade é a checagem pelo caso em que a estrutura que armazena a lista possa estar cheia, uma vez que esta situação podeinviabilizarainserçãodeumnovoelemento.Estemétodoédefundamen-tal importância, principalmente no caso de utilização de alocação de memória estática onde a tentativa de inserção de um novo elemento pode acarretar o estourodamemória,fazendocomqueoprogramaterminecomerro.


int Cheia (Lista l) if (l -> quant _ Elem == tamanho) return (1)else return (0);

Adicionalmente,opercursoaolongodoselementosdeumalistare-quer de uma operação que possibilite a movimentação ao longo da estrutu-ra,elementoaelemento.AfunçãoproximoElemento retorna o índice no vetor correspondente à posição do próximo elemento, se for o último e não tiver próximo,retorna-1.

corrente proximoElemento (Lista l, corrente pos) pos = pos++;

if (validaPos(pos) return (pos); return (-1);

Aoperaçãodeinserçãoépossivelmenteumadasmaisimportantes,umavezqueéatravésdelaquealistaseráconstruída.Emparticular,otipolista não possui nenhuma restrição em relação à inserção, podendo aconte-ceremqualquerposição.Destaforma,nahoradeinserirumelementonalista, é necessário informar qual a posição correspondente ao novo elemen-to,sejanoinicio,meiooufimdalista.Considerandoqueainserçãonemsempre é possível por conta da limitação de espaço da estrutura de dados utilizada, a função retorna 1 se a inserção foi realizada com sucesso e 0 em caso contrário

int Inserir (Lista l, tipo _ base dado, corrente pos) int i;if (!validaPos(l) || (cheia (l))) return (0);

for (i = tamanho(l) ; i >= pos; i--) l -> v[i] = l -> v[i-1];

l -> v[pos] = dado;

l -> tamanho = (l -> tamanho)++;

return (1);

Dependendo da posição onde o elemento será inserido, o trabalho re-queridopodeserestimadodeformaaestabelecerocustodafunção.Pelofato de se utilizar alocação estática e contígua de memória para o armaze-namento dos elementos da lista, a inserção de um elemento em uma execu-ção requer que o espaço físico na memória seja providenciado em tempo de compilação.Paraissoénecessáriodeslocar(shift)todososelementosneces-sários,desdeaposiçãorequeridaatéofinaldalista.Porexemplo,sealistapossui5elementoseonovoelementoprecisaserinseridonaposição3,osúltimos3elementosprecisarãoserdeslocadosàdireita,paraqueaposição


deinserçãorequeridafiquedisponívelparaonovoelementoaserinserido.Asituaçãoéilustradanafiguraaseguir.

O pior cenário neste caso acontece quando é requerida a inserção na primeira posição da lista, obrigando o deslocamento de todos os elementos dalistaemumaposiçãoàdireita.Netecaso,ocustorequeridoéO(n).

Analogamenteàoperaçãodeinserção,aoperaçãoderemoçãoexcluium elemento em qualquer posição, portanto esta posição precisa ser infor-mada explicitamente.Oalgoritmo é responsável por checar se aposiçãoinformadarepresentaumaposiçãoválidadentrodaestrutura.

int Remover (Lista l, corrente pos) int i;if (vazia(l) || (!validaPos(l)) return (0);

dado = l -> v[pos];

for (i = pos; i <=(tamanho(l))-1; i++) l -> v[i-1] = l -> v[i];

l -> tamanho = (l -> tamanho)--;

return (1);

Realizando uma análise análoga ao caso da inserção, o custo para a remoção é O(n).

Nocasoemquesejanecessárioremoverumelementodeacordocomalgumconteúdoespecífico,oelementoemquestãoprecisaserpreviamentelocalizado através da operação de Busca.Apartirdaposiçãoretornadapelabusca, caso o elemento seja efetivamente encontrado na estrutura, a remo-çãopoderáserefetivamenterealizada.

Abuscaporumdeterminadoelementopodeseroriginadadeduasfor-mas.Naprimeiravariante,abuscapodeserorientadaporumdeterminadoconteúdo, retornando como resultado a sua posição na lista, no caso em que oelementoforefetivamenteencontrado,casocontrárioretorna-1.

corrente Busca (Lista l, tipo _ base dado) int i;for (i = 0; i <= tamanho(l); i++)if (l -> v[i] == dado) return (i);return (-1);


O pior caso possível para esta busca, consiste na situação onde o elementoprocuradonãoseencontrana lista.Nestasituaçãoa listaserápercorrida na totalidade, sem sucesso, passando pelos n elementos que de-terminamseutamanho.Consequentemente,ocustodestaoperaçãonoseupior caso é O(n),ousejalinear.

Nasegundavariante,abuscapodeacontecerapartirdeumadeter-

minadaposiçãonalista,retornandooelementocontidonessaposição.

tipo _ base Consulta (Lista l, corrente pos) return (l -> v[pos-1]);

AcomplexidadedabuscanestecasoéO(1) uma vez que consiste no acesso direto à posição correspondente, demandando para isso tempo cons-tante.

1.ConsiderandoaimplementaçãodoTADutilizandoalocaçãoestáticadememória resolva as questões a seguir:

a) Expliqueporqueocustodaremoçãoemumalistaimplementadauti-lizando alocação estática e contígua de memória é O(n).

b)Implementeaoperaçãoqueretornaaquantidadedeelementosnalis-ta,cujocabeçalhoé:inttamanho(listal).Determineacomplexidadedaoperaçãoimplementada.

c)Implementeométodoauxiliarqueverifiqueseumadeterminadapo-siçãoéválida,istoé,seencontradentrodoslimitesdovetor.Ocabe-çalhodaoperaçãoéintvalidaPos(correntepos).

Implementação do TAD Lista usando alocação dinâmica NaimplementaçãodoTipoAbstratolistaadotandoalocaçãodememó-

ria dinâmica a alocação de memória é gerenciada sob demanda em tempo deexecução.Estacaracterísticadeterminaqueoselementoscomponentessãoorganizadosemposiçõesnão-contíguas,ficandoespalhadosaolongodamemória.Consequentemente,nãoéprecisoestimara priori o tamanho da estrutura uma vez que o espaço é alocado na medida da necessidade, dependendodasoperaçõesdeinserçãoeremoçãorealizadas.

VantagensedesvantagensdestaestruturaforamdiscutidasnaUnida-de3.Emparticular,estaestruturasetornaadequadaquandootamanhodaestruturaédesconhecidoepodevariardeformaimprevisível.Noentan-to, a gerência da memória torna a implementação mais trabalhosa e pro-pensaaerros,podendoacarretaremperdadeinformação.Adicionalmente,oacessoaosdadoséseqüencial,nosentidoqueparaacessaroelementona


posição m, se torna necessário percorrer os m - 1elementosanteriores.Comisso, no pior caso, a busca por um elemento na lista demanda custo O(n).

A seguir é apresentada a definição da estrutura de dados e imple-mentaçãodasoperaçõesdefinidasnainterfaceparaoTADListautilizandoalocaçãodinâmicadememóriaatravésdeponteiros.AnotaçãoutilizadanaimplementaçãoépróximaàlinguagemC.Estaestruturarepresentaumaseqüênciadeelementosencadeadosporponteiros,ouseja,cadaelementodeve conter, além do dado propriamente dito, uma referência para o próximo elementodalista.Graficamente,aestruturadedadosparaaimplementa-ção de listas utilizando ponteiros é a seguinte:

Por exemplo, uma lista com valores de ponteiros a endereços reais tem a seguinte forma:

O espaço total de memória gasto pela estrutura é proporcional ao nú-mero de elementos nela armazenados: para cada novo elemento inserido na estruturaéalocadoumespaçodememóriaparaarmazená-lo.Consequen-temente, não é possível garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, e, portanto não é possível ter acessodiretoaoselementosdalista.Istoimplicaque,parapercorrertodosos elementos da lista, devemos explicitamente seguir o encadeamento dos elementos.Paraisto,éprecisodefiniraestruturadonó,comoumaestrutu-ra auto-referenciada contendo, além do conteúdo de informação, um pontei-roaopróximoelementonasequência.Asdefiniçõesaseguirimplementamaestruturacorrespondente.

typedef struct node *no _ ptr;

struct node tipo _ base elemento;

no _ ptr prox;

;

Finalmentealistaédefinidacomoumponteiroaoprimeironódalis-ta,apartirdoqualasequênciadenóséencadeada.

typedef apontador _ no Lista;

Aimplementaçãodelistascomponteirosrequerumcuidadoespecialuma vez que qualquer erro na manipulação dos ponteiros pode acarretar emperdaparcialoutotaldalistadeelementos.Assimsendo,autilização


de um ponteiro auxiliar para o percurso ao longo da lista pode ser de gran-deutilidade.ComesseobjetivodefinimosumtipoCorrente, a ser utilizado como cópia da lista de forma a possibilitar a sua manipulação com segu-rança.

typedef no _ ptr Corrente;

A funçãoquecria uma lista vazia utilizando alocação dinâmica de memóriaéapresentadaaseguir.Afunçãotemcomovalorderetornoalistavazia inicializada, isto é, o valor de retorno é NULL, pois não existem ele-mentosnalista.

Lista Criar () return (NULL);

O método Inicializar posiciona o índice da posição corrente no inicio da lista.Desta formaoponteiropos aponta para o mesmo local onde se encontraoprimeiroelementoda lista.Estemétodoéútil quandoa listaprecisaserpercorridadesdeoinicio.

corrente Inicializar (Lista L) corrente pos = L; return (pos);

O deslocamento de um elemento para o seguinte na lista é dado pelo percurso ao longo dos ponteiros, onde, a partir do nó atual, a função a se-guirretornaoponteiroondeselocalizaopróximoelementonalista.

corrente proximoElemento (corrente p) return (p -> prox);

Aprocura por um conteúdona lista é realizada através da funçãoBusca.Estafunçãopercorrealistadesdeoinicio,enquantooelementonãoforencontrado.Afunçãoretornaaposiçãodoelementonalistaemcasodesucesso na procura, ou NULLseoelementonãoforencontrado.

corrente Busca (Lista L, tipo _ base x)

corrente p = L;

while ((p != NULL) && (p -> elemento != x))

p = p -> prox;

return p;


O acesso às informações contidas nos nós da lista é realizado através da função Consulta, que retorna o conteúdo de informação armazenado no nóreferenciadopeloponteirocorrente.

tipo _ base Consulta (Lista L, corrente p) if (p != NULL) return (p -> elemento);

Aremoçãodeumelementodalistaenvolveaanálisededuassitua-ções: a remoção do primeiro nó da lista ou de um nó em outra posição qual-quer,semsernoiniciodalista.Aseguir,oprocessoderemoçãoemcadacasoéilustrado.

Nocasodaremoçãodoprimeiroelementodalistaénecessárioqueoponteiroàlistasejaatualizado,indicandoonovoprimeiroelemento.

Nocasoderemoçãodeumelemento,semseroprimeiro,oprocessoconsiste em fazer um by pass sobre esse elemento através do ajuste correto dosponteiros,paraposteriormenteliberaramemóriacorrespondente.Paraefetivar a remoção é preciso o nó anterior ao nó a ser removido, que pode ser obtido a partir da função auxiliar Anterior.

A funçãoRemover apresentada a seguir, remove o elemento corres-pondente a uma determinada posição pos, passadapor parâmetro.Estaposição pode ser resultado de um processo de busca, a partir de um deter-minadoconteúdo.Emambososcasoséprecisoliberaramemóriacorres-pondenteaonóremovido.

Aseguiréapresentadooalgoritmoqueimplementaoprocessodere-moção.

int Remover (Lista l, corrente pos) corrente noAnterior = Anterior (L, pos); if (noAnterior == NULL) l = l -> prox; else

corrente tmp _ cell = pos;

noAnterior -> proximo = pos -> prox;

free (tmp _ cell);

return (1);


A inserção emuma lista pode acontecer em qualquer posição, quepodesernoinicio,nofinalouqualqueroutraposiçãonomeiodalista.Oconteúdo do parâmetro pos representa a posição de inserção requerida para o elemento novo a ser inserido, no caso de inserção na cabeça da lista pos é null.Nestecaso,oponteiroLqueapontavaaoprimeiroelementodalistaapontaagoraparaonovoelementoinserido.

Para qualquer outro valor de pos, o processo de inserção acontece comoilustradoaseguir.Alistaprecisaserpercorridaatéaposiçãodein-serçãorequerida.Nesseponto,onovoelementoseráinseridoatualizandoosponteiroscorrespondentes.

int Inserir (Lista l, tipo _ base dado, corrente pos) int i; Corrente atual = Inicializar (l);

Lista novo = (Lista) malloc(sizeof(struct node)); novo -> elemento = dado;

if (pos == NULL) novo -> prox = l;

l = novo;

else while (atual -> next != NULL) and (atual -> next != pos)

atual = atual -> prox;

novo -> prox = atual -> prox;

atual -> prox = novo;

else return (1);

AfunçãoVazia éutilizadaparaverificarsealistapossuiounãoele-mentos armazenados. A verificação consiste em checar se o ponteiro aoprimeiro elemento é null.


int Vazia (Lista L) if (L == NULL) return (1) else return (0);

AfunçãoultimoElemento éutilizadaparaverificarofinaldalista.Estachecagem consiste em determinar se o próximo elemento que segue ao atual é NULL.

int ultimoElemento (corrente p)

if (p -> prox == NULL) return (1) return (0);

Com exceção de Busca e Anterior todas as operações consomem tempo O(1).Istoporquesomenteumnúmerofixodeinstruçõeséexecutadosemlevaremcontaotamanhodalista.ParaBusca e Anterior o custo é O(n),poisa lista inteira pode precisar ser percorrida se o elemento não se encontra ou foroúltimodalista.

UtilizandooTADListadefinidonestaunidade,implementecomoapli-caçãoumprogramaque,dadasduaslistasAeB,crieumaterceiralistaLintercalandooselementosdasduaslistasAeB.

Lista Intercala (Lista A , Lista B)

Lista L = cria ();

corrente pos _ L = Inicializar (L);

corrente pos _ A = Inicializar (A);

corrente pos _ B = Inicializar (B);

/*Assumimos que A e A tem o mesmo tamanho

while (not ultimoElemento(pos _ A)) &&

(not ultimoElemento (pos _ B))

Inserir (L, Consulta (pos _ A), null);

pos _ A = proximoElemento (pos _ A);

Inserir (L, Consulta (pos _ B), null);

pos _ B = proximoElemento (pos _ B);

return(L);


Considerando a implementação do TADutilizando alocação dinámica dememória resolva as questões a seguir:

1. Implemente a operação que retorna a quantidade de elementos na lista, cujocabeçalhoé: intTamanho(Listal).Determineacomplexidadedaoperaçãoimplementada.

2. Implemente uma rotina para a remoção de uma lista desalocando a me-móriautilizada.OcabeçalhodarotinaévoidRemove_list(ListaL).

3. Implemente a rotina auxiliar chamada anterior usada na remoção, de acordo com o seguinte cabeçalho corrente anterior (Lista L, corrente pos).Esta rotina retornaaposiçãodoelementoanterioraumaoutraposiçãopos.SeoelementonãoforencontradoretornaNULL.

4.UtilizandoasoperaçõesdefinidasnainterfacedoTADListaimplementeum método que dadas duas listas L1 e L2, calcule L1 ∪L2(união)eL1∩L2(interseção).OresultadodasoperaçõesdeveserretornadoemumaterceiralistaL3.

5.UtilizandoasoperaçõesdefinidasnainterfacedoTADListaimplementeum método que dada uma lista retorne uma segunda lista onde os ele-mentospertencentesàprimeiraestejamordenadosemformacrescente.Determineacomplexidadedoseualgoritmo.

6.Escrevaumprogramaque,utilizandooTADLista,façaoseguinte:

a)Criequatrolistas(L1,L2,L3eL4);

b)Insirasequencialmente,nalistaL1,10númerosinteirosobtidosdeformarandômica(entre0e99);

c)IdemparaalistaL2;

d)ConcateneaslistasL1eL2,armazenandooresultadonalistaL3;

e)ArmazenenalistaL4oselementosdalistaL3(naordeminversa);

f)ExibaoconteúdodaslistasL1,L2,L3eL4.

Variações sobre o TAD Lista

Lista ordenada

Uma lista ordenada é uma lista onde seus elementos componentes são organizados de acordo a um critério de ordenação com base em um campo chave. A ordem estabelecida determina que a inserção de um determinado elemento na lista irá a acontecer no lugar correto. A lista pode ser ordenada de forma crescente ou decrescente.


A partir da existência de um critério de ordenação na lista, a função res-ponsável pela busca por um determinado conteúdo na lista pode ser adaptado de forma a tornar a busca mais efi ciente.

Lista circular

A convenção consiste em manter a última célula apontando para a pri-meira. Desta forma, o teste por fi m de lista nunca é satisfeito. Com isso, pre-cisa ser estabelecido um critério de parada de forma a evitar que o percurso na lista não encontre nunca o fi m. Uma forma padrão é estabelecido com base no número de elementos existentes na lista.

Lista duplamente encadeada

Em alguns casos pode ser conveniente o percurso da lista de trás para frente através da adição de um atributo extra na estrutura de dados, contendo um ponteiro para a célula anterior. Esta mudança na estrutura física acarreta um custo extra no espaço requerido e também aumenta o trabalho requerido nas inserções e remoções, uma vez que existem mais ponteiros a serem ajus-tados. Por outro lado simplifi ca a remoção, pois não mais precisamos procurar a célula anterior (O(n)), uma vez que esta pode ser acessada diretamente através do ponteiro correspondente.


Capítulo 2Pilhas

Emgeral, asoperaçõesde inserçãoe remoção realizadassobre lis-tassãocustosas.Nocasodaimplementaçãoutilizandoalocaçãodememó-riaestática,estasoperaçõesacarretamamovimentaçãodoselementos.Nocaso da alocação dinâmica o deslocamento até a posição correta de inserção ou remoção envolve o percurso ao longo do encadeamento pelos elemen-tos.Emambososcasos,ocustodestasoperaçõeséO(n).Estassituaçõesdesfavoráveis podem ser contornadas se os elementos a serem inseridos e removidos se encontram em posições determinadas especialmente, como a primeiraouúltimaposição.

UmaPilha é uma lista com a restrição de que inserções e remoções sãoexecutadasexclusivamenteemumaposição,referenciadacomofimoutopo.

Pilhas são conhecidas como estruturas LIFO do inglês Last In First Outouúltimoqueentraprimeiroquesai.EmumaPilhaoúnicoelementoacessíveléoelementoqueseencontranotopo.Consequentemente,aope-ração de busca ao longo da estrutura, por exemplo, não é uma operação aplicávelparaestaestruturadedados.Graficamente,umapilhapodeserrepresentada da seguinte forma:

O funcionamento de uma pilha pode ser facilmente interpretado a partirdeumaanalogiasimplescomumapilhade livrospesados.Livrossão empilhados, um encima de outro, sendo que o último livro empilhado é oqueficanotopodapilha,e,portantoéoúnicovisívelequepodesercon-sultadosemprecisarmovimentaroutrosexemplares.Porsetratardelivrospesados, o acesso a um livro determinado na pilha, requer que os livros encimadestesejamretirados,umaum,apartirdotopo.Destaforma,oúltimolivroempilhadoseráoprimeiroaserretiradodapilha.Apartirdes-ta descrição, o funcionamento da pilha pode ser modelado de acordo com a seguinteinterface.


InterfacedoTADPilha

/* Cria uma pilha vazia

Pilha Criar ()

/*insere um novo elemento no topo da pilha.

int Push (Pilha p, tipo _ base dado)

/* consulta pelo elemento que se encontra no topo

tipo _ base Top (Pilha p)

/*Remove e retorna o elemento do topo

int Pop (Pilha p)

/* Retorna 1 se não tem mais elementos na pilha, ou 0 em caso contrario.

int Vazia (Pilha p)

/* Retorna 1 se a pilha estiver cheia, e 0 em caso contra-rio.

int Cheia (Pilha p)

/* Retorna a quantidade de elementos na pilha.

int Tamanho (Pilha l)

Pilhas são listas, portanto as abordagens de implementação utiliza-dasparalistassãoválidasparaocasodaimplementaçãodepilhas.Consi-derando que a implementação de pilhas representa uma variação de listas, boapartedaespecificaçãoeimplementaçãodelistaspodeseraproveitada.

Implementações do TAD Pilha usando vetoresLevando em conta as restrições inerentes à própria estrutura de da-

dos e as restrições na manipulação da pilha, a estrutura projetada para a implementaçãode listasémodificada,adicionandomaisumcampodeinformação referente à localização do elemento que se encontra no topo da pilha.Estainformaçãoéindispensávelnaimplementaçãodasoperaçõesdeinserçãoeremoção,deformaapossibilitaroacessodiretoaolocal.Comessa pequena alteração na estrutura de dados as operações passam a de-mandartempoconstante.

O fato de máquinas mo-dernas possuírem opera-ções sobre pilhas como parte do conjunto de ins-truções, faz desta estru-tura uma abstração fun-damental na Ciência da Computação, depois do vetor.


#define tamanho;

struct estrutura _ Pilha int topo;

tipo _ base elementos [tamanho];

;

typedef struct estrutura _ Pilha *Pilha;

EmCumapilhaédefinidacomoumponteiroàestrutura,queépas-sadoporvalorparaasfunçõesqueirãomodificaroconteúdodapilha.

Dada a semelhança com a estrutura de dados utilizada para o caso de listas, o método Criar se mantem essencialmente o mesmo, adicionando somente a sentença de inicialização do campo topoparaaprimeiraposição.

Naescolhapelaextremidadedovetoraserdefinidacomootopo onde a inserção e remoção de elementos estará acontecendo, é importante ana-lisaroscustosdecorrentesdestaescolha.Comodiscutidoanteriormente,apropriedade de alocação contígua de memória traz como desvantagem a ne-cessidadedemovimentaçõesdoselementosaolongodaestruturadedados.Nessecaso,seotopoforescolhidocomoaprimeiraposiçãodovetor,ocustoda inserção e remoção seria de O(n).Emcontrapartida,adefiniçãodetopocomo sendo o último elemento inserido é mais conveniente uma vez que este podeseracessadoemtempoconstanteapartirdotamanhodaestrutura.

Aoperaçãoderemoçãodoelementoqueseencontranotopodapilhaédescritanoalgoritmoaseguir.

tipo _ base Pop (Pilha p)

tipo _ base v;

v = p -> elementos [p -> topo];

(p -> topo)--;

return v;

A remoção de um elemento somente é possível sempre que a pilhacontiverpelomenosumelemento.Nessecasooelementoécopiadoemumavariável auxiliar para seu retorno posterior, decrementando em 1, conse-quentemente,aposiçãodoúltimoelemento.Alógicaseguidaparaaimple-mentação do algoritmo de consulta do topo, Top, é a mesma, com a diferença de que não é preciso alterar a posição do topo uma vez que nenhum elemen-toéremovidodapilha.

Oalgoritmoqueverificaseapilhaseencontravaziaounãoébasea-do na informação contida no campo topo.Considerandoqueotopo indica indiretamente a quantidade de elementos efetivamente contidos na pilha, a checagem pela posição onde este elemento se encontra é utilizado para estabelecerseapilhaestávazia.Nessecasoafunçãoretorna1.


int Vazia (Pilha p) if (p -> topo == 0) return (1)else return (0);

Umaestratégiasimilarpodeserutilizadaparaestabelecerseapilhaseencontra cheia, só que neste caso a posição do elemento no topo precisa ser confrontadacontraotamanhototalreservadoparaaestruturadedados.

ConsiderandoaimplementaçãodoTADutilizandoalocaçãoestáticademe-moria resolva as questões a seguir:

1. Implemente o algoritmo Push, responsável pela inserção de um novo elementonotopodapilha,deacordoàseguinteespecificação:int Push (Pilha p, tipo _ base dado).

2. Implemente o algoritmo que consulta e retorna o conteúdo correspon-dente ao elemento que se encontra no topo, atendendo ao seguinte cabe-çalho: tipo _ base Top (Pilha p).

3.Implementeoalgoritmoqueverificaseapilhaestácheia,atendendoaoseguinte cabeçalho: int cheia (Pilha p), retornando1emcasoafir-mativoe0emoutrocaso.

4.Expliqueporqueémaisconvenienteadefiniçãodotopodapilhanofinalenãonoiniciodaestrutura.

Implementação do TAD Pilha usando ponteirosNocasodaimplementaçãodepilhasutilizandoalocaçãodinâmicade

memória, a desvantagem do acesso sequencial necessário para alcançar qualquerelementodapilhapodesercontornadoeficientemente,umavezque no caso da pilha, as operações acontecem necessariamente a partir de umextremo.Aescolhapeloextremodaestruturaaserconsideradocomotopo irá a determinar o custo envolvido na execução das operações: enquan-to que o acesso ao último elemento da pilha envolve custo O(n), o acesso ao primeiroelementoéconstante.Consequentemente,nocasodaimplemen-taçãodapilhautilizandoponteiros,adefiniçãodotopo como sendo o inicio (cabeçada lista) dapilha émais vantajoso em termosdedesempenho ecomplexidade.

Aestruturadedadosutilizadanaimplementaçãodapilhaéidênticaàqueladefinidanocasodelistas,consequentemente,amaiorpartedasope-rações são coincidentes, tais como Criar e Vazia.


typedef struct node *no _ ptr;

struct no tipo _ base elemento;

no _ ptr prox;

;

typedef no _ ptr Pilha;

ApartirdadecisãodeprojetoparaoTADPilhadeconsiderarotopopara as operações de inserção (push)eremoção (pop)nacabeçada listade elementos, cuidados especiais na implementação de tais operações são requeridosdeformaaevitarperdadeinformação.

AoperaçãoPush, responsável pela inserção de um novo elemento no topodapilha,consistenaalocaçãodememóriaparaonovoelemento.Seaalocação de memória é realizada com sucesso, o novo componente é instan-ciado com a informação correspondente e inserido como primeiro elemento na lista, atualizando consequentemente a cabeça da lista com o endereço do novoelemento.Nocasoemqueainserçãoaconteçacomsucesso o algoritmo retorna1,e0emcasocontrario.

int Push (Pilha p, tipo _ base x) no _ ptr novo = (no _ ptr) malloc (sizeof (struct no)); if (no _ tmp == NULL)

fatal _ error (“Memoria insufi ciente!!”); return (0);

else novo -> elemento = x; novo -> prox = p; p = novo;

return (1);

Considerando a implementação do TADutilizando alocação dinâmica dememoria resolva as questões a seguir:

1. Implemente o algoritmo Pop, responsável pela remoção de um elemento notopodapilha,deacordoàseguinteespecificação:tipo _ base Pop (Pilha p)

As operações de alocaçãoe desalocação de memó-ria, malloc e free, respec-tivamente,sãocaras.Estecusto pode ser reduzido através de um algoritmo que implemente a remo-ção lógica de elementos onde, em lugar de desa-locar a memória, a célula correspondente é mantida em uma pilha auxiliar de forma que quando uma nova célula é requerida, esta pilha é checada pri-meiro, antes de alocar umanovacélula.


2. Implemente o algoritmo que consulta e retorna o conteúdo correspon-dente ao elemento que se encontra no topo, atendendo ao seguinte cabe-çalho: tipo _ base Top (Pilha p).

3. Implementeumaoperaçãoquelibereamemóriaalocadapelapilha.De-termineacomplexidadedoseualgoritmo.

4.Expliqueporqueémaisconvenienteadefiniçãodotopodapilhanoini-cioenãonofimdaestrutura,nocasodeutilizaçãodeponteiros.

5.UtilizandoasoperaçõesdefinidasnainterfacedoTADListaedoTADPilha, elabore um algoritmo que dada uma lista ordenada, inverta a or-demdoselementosnalista,utilizandoparaissoumapilha.Determineacomplexidadedoseualgoritmo.

6.UtilizandoasoperaçõesdefinidasnainterfacedoTADPilhaescrevaumalgoritmoparaordenarpilhas,sendoquenofinaldoprocessamentooselementos da pilha devem estar dispostos em ordem crescente de seus valores.Determinequalaestruturaauxiliarmaisadequadaparasupor-taroprocesso.Determineacomplexidadedoseualgoritmo.

7. UtilizandoasoperaçõesdefinidasnainterfacedoTADPilhaescrevaumalgoritmo que forneça o maior, o menor e a média aritmética dos elemen-tosdeumapilhadadacomoentrada.


Capítulo 3Filas

Assimcomopilhas,filassãolistasquepossuemalgumasrestriçõesespecíficasparaaexecuçãodasoperaçõesdeinserçãoeremoção.Nafila,as inserções são realizadas em um extremo, enquanto, que ao remover no outro.AfilasegueomodeloFIFO,doinglêsFirst In First Out, ou seja, que o primeiroqueentranafilaéoprimeiroemsair.

InterfacedoTADFila

/* Cria uma fila vazia

Fila Criar ()

/*insere um novo elemento no topo da fila.

int Inserir (Fila p, tipo _ base dado)

/* Consulta pelo elemento que se encontra no topo

tipo _ base Top (Fila f)

/*Remove e retorna o elemento do topo

int Remover (Fila f)

/* Retorna 1 se não tem mais elementos na fila, ou 0 em caso contrario.

int Vazia (Fila f)

/* Retorna 1 se a fila estiver cheia, e 0 em caso contrario.

int Cheia (Fila f)

/* Retorna a quantidade de elementos na fila.

int Tamanho (Fila f)

Implementação do TAD Fila usando vetoresConsiderando que a operação de remoção acontece em uma extre-

midade e a inserção na outra, é interessante manter apontadores indican-do ambos extremos da estrutura, de forma que o acesso seja direto (O(n)).Consequentemente,aestruturadedadosfilainclui,alémdovetorqueiráa comportar as informações correspondentes, os índices correspondentes aoinicioefimdafila,eotamanhodafilarelativoaonúmerodeelementoscontidos.Aseguintefiguramostraumafilaemalgumestadointermediário.


De acordo com esta estratégia e depois da remoção de “b” e “a”, e da inserção de “f” e “1”,asituaçãodafilaseriaaseguinte:

Ainserçãodeumelementonafilaincrementaotamanhoeoíndicequeindicaofimdafila,enquantoquenaremoçãodeumelementootama-nhodafilaédecrementadoeoíndicequeindicaoinicioéincrementado.Estaestratégiaevitaamovimentaçãodeelementossemprequeumainser-çãoouremoçãoforrealizada.Comissoocustodeambasoperaçõesficaconstante.

Levandoemcontaasrestriçõesinerentesàmanipulaçãodafila,aes-trutura projetada para a sua implementação utilizando alocação de memó-riaestáticaouvetorprecisasermodificadaemrelaçãoàpilha.Nestecasoé preciso indicar mais um campo de informação referente à localização do elementoqueseencontranoiniciodafila.Estainformaçãoéindispensávelna implementação das operações de inserção e remoção, de forma a possi-bilitaroacessodiretoaolocal.Comessapequenaalteraçãonaestruturadedadosasoperaçõespassamaserexecutadasemtempoconstante.

#define tamanho;

struct estrutura _ Fila int ini; int fim; int quant _ elementos;

tipo _ base elementos [tamanho];

;

typedef struct estrutura _ Fila *Fila;

Noentantoexisteumproblemapotencialumavezqueafilapodeficaraparentemente cheia, no entanto vários elementos podem ter sido removi-dos,podendoexistirnaverdadepoucoselementosnafila(observeafiguraanterior).

A solução para contornar este problema é implementar o chamadoincremento circular encima do vetor, onde sempre que os índices de inicio ou defimchegamnofinaldovetor,estessãoredefinidosnaprimeiraposiçãodovetor.Estaestratégiarequerumcuidadoespecialnahoradopercursosobreaestrutura,umavezqueofimdovetorprecisaserdeterminadologi-


camente(p.e.,pelaquantidadedeelementosnafila),enãomaisfisicamentepelofimdaestrutura.Afiguraaseguirexemplificaofuncionamentodafilautilização o vetor circular, onde o conteúdo “c” foi removido e adicionado o conteúdo “m”.

Acriaçãodeumafilavazia,similarmenteàcriaçãodeumalista,en-volve a alocação de memória para a estrutura de dados respectiva, e a pos-terior inicialização dos campos envolvidos, no caso os índices de inicio e fim,eaquantidadedeelementosqueprecisamserinicializadosem0.

Considerandoainserçãodeelementosacontecendonofimearemo-çãonoinicio,ocódigodasrespectivasoperaçõeséapresentadoaseguir.Nocaso da inserção, e levando em conta que o tamanho da estrutura de dados estática foi estabelecida em tempo de compilação, é importante verificarqueexistaespaçodisponívelparaarmazenarumnovoelemento.Apósestaverificação,onovoelementoéinseridonaprimeiraposiçãolivreindicadapor fim.Apósisso,tantofim quando a quantidade de elementos precisam seratualizados.

void inserir (Fila f, tipo _ base v) if (f -> size == tamanho) printf (“Fila cheia!”);return;

f -> elementos [f -> fim] = v;

f -> fim = incrementar (f -> fim);f -> size++;

Aimplementaçãodovetorcircularrequerquesejarealizadoumincre-mento especial onde, a partir de uma posição corrente, o método retorna a posiçãoseguinteou,nocasodeatingirofinaldovetor,aposiçãocorrenteéespecificadacomosendonoiniciodaestrutura,nocaso0.

int incrementar (int pos)if (pos == tamanho - 1) return (0);else return (i++);


ConsiderandoaimplementaçãodoTADutilizandoalocaçãoestáticademe-mória resolva as questões a seguir:

1. ImplementeosalgoritmosCriar,RemovereVazia,deacordocomosres-pectivoscabeçalhosdefinidosnainterfacedoTAD.

2.Expliqueporqueémaisconvenientearealizaçãodaoperaçãodeinser-çãonofimederemoçãonoinicio.Comoseriasefosseaocontrario?

3.Escrevaumalgoritmoparaordenarfilas,sendoquenofinaldoproces-samentooselementosdafiladevemestardispostosemordemcrescentede seus valores.Determine qual a estrutura auxiliarmais adequadaparasuportaroprocesso.Determineacomplexidadedoseualgoritmo.

Implementação do TAD Fila usando ponteirosAimplementaçãodefilasutilizandoponteirossegueamesmaestra-

tégiaanalisadanaseçãoanterior.Comoteremosqueinserireretirarele-mentosdasextremidadesopostasdalista,representandooinícioeofimdafila,éprecisoutilizardoisponteiros,ini e fi m, que apontam respectivamente paraoprimeiroeparaoúltimonódafila.Apartirdestanecessidadesefazindispensávelaimplementaçãodafilautilizandoumnódiferenciado,cha-mado de headeroucabeçalho,paraconterestesponteiros.Essasituaçãoéilustradanafiguraabaixo:

Adefiniçãodaestruturadedadosqueimplementaaabordagemdes-crita é a seguinte:

typedef struct no *no _ ptr;

typedef struct no tipo _ base elemento;

no _ ptr prox;

;


Aestruturadedadosenvolveadefiniçãodeumalistadeelementos,nomesmoformatoemquefoidefinidaparaocasodelistasepilhas.Adicional-mente,aestruturacorrespondenteaonócabeçalhoprecisaserespecificadaumavezqueincluicamposdiferenciados.

struct cabeçalho no _ ptr ini;

no _ ptr fim;

;

Finalmente,afilaédefinidacomosendoumponteiroaonócabeçalho.typedef struct cabeçalho *Fila;

Apartir da interface especificadapara oTADfila, as operaçõesdecriaçãoeverificaçãopelafilavaziaseguemasmesmasestratégiasanterior-mentedescritas.

Adecisãodeprojetoemrelaçãoàsoperaçõesdeinserçãoeremoçãoenvolveestabeleceremqualextremidadedafilacadaumaseráexecutada.Emparticular,alógicanaimplementaçãodaoperaçãoderemoçãodeumelemento em uma lista implementada com ponteiros, requer a procura pelo elemento anterior na lista, de forma a atualizar o ponteiro para o próximo elemento (Ver remoção em listas).O custo desta procura pelo anterior éO(n).Estasituaçãopodeserevitadasearemoçãoacontecesemprenoiniciodalista,umavezquenãoexisteanteriorquepreciseseratualizado.Estaconstatação determina que a escolha mais conveniente em termos de com-plexidadeéquecadanovoelementosejainseridonofimdalistaenquantoquearemoçãodeumelementosejarealizadanoinício.

Nocasodaoperaçãodeinserção,ondeoelementoéinseridonofimdalista,nasituaçãoespecíficadeinserçãodoprimeiroeúnicoelemento,am-bos os ponteiros ini e fim precisam ser atualizados apontando para o único nóinseridonafila.Emqualqueroutrocaso,somenteoponteiroqueindicaofinaldafilaseráatualizado.

void Inserir (Fila* f, tipo _ base dado) no _ ptr novo = (no _ ptr) malloc (sizeof (no));novo -> elemento = dado;

novo -> prox = NULL;

if (f -> fim != NULL) f -> fim -> prox = novo;else f -> ini = novo;

f -> fim = novo;

Analogamente,afunçãopararemoverumelementodafiladeveatu-alizar ambos os ponteiros no caso em que for removido o último e único elementoexistente,tornandoafilavazia(ini e fimnulos).


1.ImplementeosalgoritmosCriar,RemovereVazia,deacordocomosres-pectivoscabeçalhosdefinidosnainterfacedoTADFilautilizandopon-teiros.

2. Expliqueporqueémaisconvenientearealizaçãodaoperaçãodeinser-çãonofimederemoçãonoinicio.Comoseriasefosseaocontrário?

3.UtilizandoasoperaçõesdefinidasnainterfacedoTADimplementecomoaplicaçãoumaoperaçãoquelibereamemóriaalocadapelafila.Deter-mineacomplexidadedoseualgoritmo.

4.UtilizandoasoperaçõesdefinidasnainterfacedoTADFila,escrevaumalgoritmo que forneça o maior, o menor e a média aritmética dos elemen-tosdeumaFila.

5.UtilizandoasoperaçõesdefinidasnainterfacedosTADFilaePilhaes-crever um algoritmo que leia um número indeterminado de valores intei-ros.Considerequeovalor0(zero)finalizaaentradadedados.Paracadavalorlido,determinarseeleéumnúmeroparouímpar.Seonúmeroforpar,entãoincluí-lonaFILAPAR;casocontrárioincluí-lonaFILAÍM-PAR.Apósotérminodaentradadedados,retirarumelementodecadafilaalternadamente (iniciando-sepelaFILA ÍMPAR)atéqueambasasfilasestejamvazias.Seoelementoretiradodeumadasfilasforumva-lorpositivo,entãoincluí-loemumaPILHA;casocontrário,removerumelementodaPILHA.Finalmente,escreveroconteúdodapilha.

NestaunidadefoiapresentadootipoabstratodedadosLista,apartirdadefiniçãodasuainterface.Otipoabstratofoiimplementadodeacordocom duas abordagens tradicionais: vetores e ponteiros, analisando as van-tagens e desvantagens de cada uma das abordagens de acordo com as ca-racterísticasdasaplicaçõeseoperaçõesmaisfrequentes.

OsTADsPilhaeFilaforamdescritoseimplementadoscomovariantesdoTADLista.EstesTADssãoamplamentedifundidosedecomprovadauti-lidadenaresoluçãoemodelagemdeproblemasdomundoreal.

CORMENT.H.,LEISERSONC.E.,RIVESTR.L.,STEINC.(2001). Intro-duction to Algorithms.McGraw-HilleTheMitPress.



KNUTHD.E.(1971).Mathematical Analysis of Algorithms.ProciedingsIFIPCongress71,vol.1,NorthHolland,135-143.

SZWARCFITERJ.l.,MARKENZONL.(2010).Estruturas de Dados e Seus Algoritmos.3ª.Edição.LTC.

WIRTHN.(1986).Algorithms and Data Strutures.Prentice-Hall.


Unidade

Objetivos:

• Diversas aplicações requerem de uma organização e manipulação de dados mais complexa daquela propiciada através de estruturas lineares, analisadas na unidade anterior.Umaárvoreéumaestruturadedadosnão linearmuitoeficienteparaarmazenar informação de forma a representar relacionamentos de aninhamento ouhierarquiaentreoselementosenvolvidos.Nestaunidadesãoapresentadososconceitos iniciais relativos a árvores e a sua representação clássica e implementação atravésdadefiniçãodotipoabstratocorrespondente.Árvoresbináriasdebuscaebalanceadas(AVL)sãointroduzidas.

Árvores

4


Capítulo 1Árvores

Vetoreselistassãoestruturasdedadoschamadasdeunidimensio-nais ou lineares, e portanto, não são adequadas para representarmos dados quedevemserdispostosdemaneirahierárquica.Porexemplo,aestruturahierárquicadediretórios(pastas),aninhamento,etc.Estruturasdedadosnão lineares, como árvores, são ideais para representar este tipo de relacio-namento.

Ailustraçãoaseguirrepresentaàesquerdaoaninhamentodeconjun-tos e à direita a representação hierárquica deste aninhamento utilizando umaárvore.

Umaárvoreécompostaporumconjuntodenós.Existeumnór, deno-minado raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r.Essesnósraízesdassub-árvoressãoditosfilhosdonópai,r.

Onúmerodefilhospermitidopornóeasinformaçõesarmazenadasem cada nó diferenciam os diversos tipos de árvores existentes:

• Árvoresbinárias,ondecadanótem,nomáximo,doisfilhos.• Árvoresgenéricas,ondeonúmerodefilhoséindefinido.A formamais natural para definirmos uma estrutura de árvore é

usandorecursividade.UmaárvoreTéumconjuntofinitoden nós ou vér-tices, tais que:


• Se T é um conjunto vazio, ou seja n = 0, a árvore é nula, ou vazia, ou• Existeumnóespecial,r,chamadoraizdaárvore;• Os demais nós constituem um conjunto vazio ou são particionados

em conjuntos disjuntos não vazios, as sub-árvores de r;• Cadasub-árvore,porsuavez,tambéméumaárvore.Sejam T uma árvore e v um nó, tal que v ε T, Tv é a sub-árvore de T que

tem vcomoraiz.Definem-seasseguintespropriedades:• Ograudesaídadonovéonúmerodesub-árvoresqueelepossui.• O grau da árvore Téomaiorgraudentreosdetodososseusnós.• Osfilhosdev são as raízes das sub-árvores de v.• Umnóquenãotemdescendenteséchamadodefolhaouterminal.Umapropriedadefundamentaldetodasasárvoreséquesóexisteum

caminhodaraizparaqualquernó.Comisto,podemosdefiniraaltura de uma árvore como sendo o comprimento do caminho mais longo da raiz até umadasfolhas.Assim,aalturadeumaárvorecomumúniconóraizézero.

• Umcaminho em T é uma sequência de nós v1, v2,...,vm, tal que para cada par (vi, vi+1), vi é pai de vi+1.Ocomprimentodocaminhoém-1.

• O nível do nó v é o número de nós no caminho da raiz até v.Oníveldonóraizé0,pordefinição.

• Aalturadeumnóv é o número de nós no maior caminho de v até umdosseusdescendentes.Folhas têmaltura1.Aalturadaraizdeterminaaalturadaárvore.

Árvore binária Emumaárvorebinária,cadanótemzero,umoudoisfilhos.Dema-

neirarecursiva,podemosdefinirumaárvorebináriacomosendo:• Umaárvorevazia;ou• Umnó raizv tendo duas sub-árvores, identificadas como a sub-

árvore da direita (sad)easub-árvoredaesquerda(sae)dev.

Peladefinição,umasub-árvoredeumaárvorebináriaésempreespe-cificadacomosendoasae ou a sad de uma árvore maior, e qualquer das duassub-árvorespodeservazia.

UmaárvorebináriaT éumconjuntofinitoden nós ou vértices, tais que:• Se T é um conjunto vazio, ou seja, n=0, a árvore é nula ou vazia, ou• Existeumnóespecial,r,chamadoraizdaárvore;• Os demais nós constituem um conjunto vazio ou são particiona-

dos em dois conjuntos disjuntos: sub-árvore esquerda e direita de r, cujasraízessãochamadasdefilhoesquerdoedireitoder;

• Cadasub-árvore,porsuavez,tambéméumaárvorebinária;

Pesquise sobre aplicações da estrutura de dados árvore.


Umaárvore estritamente binária é aquela em que cada nó possui zero oudoisfilhos,comorepresentadonafiguraaseguir.

Umaárvore binária completa é aquela cujos nós com sub-árvore va-ziaslocalizam-senoúltimoounopenúltimonível.Umexemplodeárvorebináriacompletaéilustradonafiguraabaixo.

Umaárvore binária cheia é aquela cujos nós com sub-árvores vazias localizam-setodosnoúltimonível.Logo,elatambéméestritamentebinária.

Umexemplodeutilizaçãodeárvoresbinárias estánaavaliaçãodeexpressões.Nessaárvore,osnós folhasrepresentamoperandoseosnósinternosoperadoresbinários.Umaárvorequerepresenta,porexemplo,aexpressão(5+9)*(3-7)+7éilustradanaseguintefigura:


Dependendo do percurso da árvore a mesma expressão pode ser re-presentadaemformaexpressõesinfixas,prefixasepósfixas.

1. Pesquisesobreaplicaçõesdaestruturadedadosárvorebinária.


Capítulo 2Árvore binária de busca

Umaárvoredebuscaéumaárvorebináriacomapropriedadedequepara todo no x na árvore, os valores de todas as chaves na sub-árvore es-querda são menores do que o valor chave em x, e que os valores de todas as chaves na sub-árvore direita são maiores do que o valor chave em x.Estadefinição seaplica recursivamentea cadanódaárvore.Assumimosquecada nó na árvore possui um valor chave, e em principio não é considera-daaocorrênciadechavesrepetidas.Nocasodasárvoresrepresentadasaseguir,apropriedadedeordenaçãopodeserverificadaemtodososnósnaárvoreesquerda.Naárvoredireita,apropriedadenãoseverificaumavezquenasub-árvoreesquerdadonóraizapareceumnócomchavemaior(5)àquelaencontradanaraiz(4).

Como a profundidade média das árvores binárias de busca é O(log n), asoperaçõessobreelasexecutadastambém.

Desde que todos os elementos na árvore seguem um critério de ordem osoperadores<,>e=podemseraplicadosdeformaaestabelecercompa-raçõesentreeles.

Definição do TAD Árvore Binária de Busca O conjunto de operações necessário para a manipulação correta e sa-

tisfatóriadeumaárvorebináriadebuscaédefinidoaseguir.


InterfacedoTADABB

/* Retorna uma árvore vazia.no _ ptr Inicializar (void)

/* Cria e retorna uma árvore inicializada.no _ ptr Rriar (element _ type c, no _ ptr e, no _ ptr d)

/*Insere um dado na árvore.int Inserir (no _ ptr pai, no _ ptr filhoEsq)

/*Busca por um determinado elemento e retorna o nó corres-pondente, ou null caso não seja encontrado.

no _ ptr Buscar (no _ ptr a, element _ type c)

/* Retorna o conteúdo de um nó.element _ type Conteudo (no _ ptr a)

/* Retorna o filho esquerdo de um nó.tree _ ptr retornaSAE (no _ ptr a)

/* Retorna o filho direito de um nó.tree _ ptr retornaSAD (no _ ptr a)

/*Remove o elemento de uma determinada posição.int Remove (no _ ptr pai, no _ ptr no)

/* Retorna 1 se o nó for nulo, ou 0 em caso contrário.int Vazia (no _ ptr a)

Implementação do TAD Árvore Binária de Busca O armazenamento de árvores pode utilizar alocação dinámica ou es-

tática, cujas vantagens e desvantagens foram analizadas em unidades an-teriores.Noentanto,porsetratardeumaestruturamaiscomplexaopoten-cialdesperdíciodeespaçopodeserreduzidopelautilizaçãodeponteiros.Adefiniçãodaestruturadedadossurgenaturalmenteapartirdadefiniçãorecursivadaárvore.Cadanónaárvorepossui,alémdocampodeinforma-ção,doisponteiros,queapontamparacadaumadassuassub-árvores.

typedef struct no _ Árvore *no _ ptr;

struct no _ Árvore

element _ type info;

no _ ptr esq;

no _ ptr dir;

;


Da mesma forma que uma lista encadeada é representada por um ponteiro para o primeiro nó, a estrutura da árvore como um todo é repre-sentada por um ponteiro para o nó raiz, a partir do qual todos os nós da árvorepodemseralcançados.

typedef no _ ptr ABB;

Como uma árvore é representada pelo endereço do nó raiz, uma árvo-re vazia tem que ser representada pelo valor NULL.

ABB Inicializar (void) return NULL;

Para criar árvores não vazias, podemos ter uma operação que cria um nó raiz contendo a informação e os ponteiros às suas duas sub-árvores, à esquerdaeàdireita.Essafunçãotemcomovalorderetornooendereçodonó raiz criado e inicializado, como segue:

ABB Criar (element _ type c, ABB sae, ABB sad)p = (ABB) malloc (sizeof (no _ Árvore));

p -> info = c;

p -> esq = sae;

p -> dir = sad;

return p;

AsduasfunçõesInicializar e Criarrepresentamosdoiscasosdadefi-nição recursiva de árvore binária: uma árvore binária é vazia (a = Inicializar ();)ouécompostaporumaraizeduassub-árvores(a=Criar(c,sae,sad);).

Asoperaçõesquepossibilitamaconsultadosconteúdosdoscamposquecompõemonósãoapresentadasaseguir.OmétodoConteudo retorna a informação contida no nó, enquanto que retornaSAE retorna a sub-árvore esquerdadonó.AnalogamenteométodoretornaSAD retorna a sub-árvore direita.

char Conteudo (ABB a)return (a -> info);

ABB retornaSAE (ABB a) return (a -> esq);

Abuscaporumconteúdoemumaárvorebináriadebusca levaemcontaocritériodeordenaçãoestabelecidoentreosnósqueacompõem.Des-ta forma, enquanto a chave procurada não for encontrada, se for menor do


que a chave que se encontra no nó da árvore, a procura continua na sub-ár-voredaesquerda,enocasocontrárionasub-árvoredireita,recursivamente.

no _ ptr Buscar (element _ type x, ABB T) if (T == NULL) return NULL; if (x < T -> info) return (Buscar (x, T -> esq)); else if (x > T -> info) return (Buscar (x, T -> dir)); else return T;

O processo de inserção na árvore segue a mesma lógica do algoritmo Buscar.Seoelementoforencontradonadaéfeito,umavezquenãoestamosconsiderandoaocorrênciadechavesrepetidas.Emoutrocaso,oelementoéinserido.Notequesejaqualforachaveaserinserida,ainserçãosempreaconteceemumnófolha.Oexemploaseguirilustraainserçãodachavecomvalor(12).

Duplicações podem ser manipuladas mantendo um campo extra no registrodonóindicandoafreqüênciadaocorrência.Estasoluçãoémaisefi-ciente uma vez que replicar nós na árvore tornaria a árvore mais profunda aumentando o custo médio requerido nas operações sobre as árvores, além dealocarmaisespaçodememória.

no _ ptr Inserir (element _ type x, ABB T) if (T == NULL) T = (ABB) malloc (sizeof (no _ Árvore)); T -> element = x; T -> esq = T -> dir = NULL; else if (x < T -> info) T -> esq = Inserir (x, T -> esq); else if (x > T -> info) T -> dir = Inserir (x, T -> dir); return T;


Naremoçãováriaspossibilidadesdevemserconsideradas.Seonóquevaiserremovidoéfolhaaremoçãoéimediata.

Seonótemsomenteumfilhoelepodeserremovidoajustandoospon-teirosentreseupaieseufilhodemododerealizarumby pass encima do nó.Porexemplo,considereaárvoreaseguir,ondeonócorrespondenteaodado(5)precisaserremovido.Oprocessoaserseguidoédescritonaárvorequeapareceàdireita.

Seonóaserremovidotemdoisfilhosaestratégiageralconsisteemreemplazar a chave do nó com a menor chave da sub-árvore direita (ou maiordasub-árvoreesquerda),erecursivamenteremoveressenó.Comoofilhomaisesquerdodasub-árvoredireitanãopodeterfilhoesquerdo,asegundaremoçãoémaisfácil.Oexemploaseguirilustraaremoçãodonócujoconteúdoé(2),quepossuidoisfilhos.Nessecasoonóésubstituídopelofilhomaisaesquerdadasub-árvoredireita(ouomenordosmaiores).Posteriormente,onóutilizadonasubstituiçãoprecisaserremovido(3)dasub-árvorecorrespondente.

O método Remover recebe por parâmetro o ponteiro ao nó que será re-movido.Esteponteiropodetersidoobtidoapartirdaexecuçãodaoperaçãodebuscaporumconteúdoespecífico.Oalgoritmotambémprecisadopon-teiro correspondente ao nó pai do nó que será removido, já que o respectivo ponteiroprecisaserajustado.

O código realiza dois passes na árvore para encontrar e remover o menornódasub-árvoredireita.Estaineficiênciapodeserremovidaescre-vendo uma função delete_min.


void Remover (element _ type x, ABB pai, ABB no) no _ ptr tmp _ no, filho;

if (no -> esq != null && v -> dir != null) tmp _ cell = buscaMin (no -> dir); no -> info = tmp _ cell -> info;

no -> dir = Remover (no -> info, no -> dir);

else tmp _ no = no;

if(no -> esq == NULL filho = no -> dir; if(no -> dir == NULL ) filho = no -> esq;

if (pai -> dir ==T) pai -> dir = filho;

else pai -> esq = filho;

free (tmp _ no);

O método auxiliar que procura o nó que contem o conteúdo mínimo possuiduasversões,umarecursivaeoutraiterativa.

no _ ptr buscaMin (ABB T) if (T == NULL ) return NULL;

else if (T -> esq == NULL ) return (T); else return (buscaMin (T -> esq));

no _ ptr buscaMin (ABB T) if (T != NULL) while (T -> esq != NULL) T = T -> esq; return T;

Os dois algoritmos possuem uma lógica simples, no entanto a versão nãorecursivapodesermaiseficienteemtermodecustoespacialetemporaldoqueaversãorecursiva.


Escrevaumafunçãoqueverifiqueseumaárvoreécheia.Umaárvoreéditacheiasetodososnósquenãosãofolhastêmosdoisfilhos,istoé,nãopodeexistirnócomapenasumfilho.Afunçãodeveretornar1nocasodaárvoresercheiaou0nocasodenãoser.Nocasodaárvoreservazia,afunçãodeveretornar1.

int cheia (tree _ ptr a) if (vazia (a)) return (1); else if ((vazia (retornaSAE (a)) && !vazia (retornaSAD (a)) ||((!vazia (retornaSAE (a)) && vazia (retornaSAD(a)) return (0); else return cheia (retornaSAE (a)) && cheia (retornaSAD(a));

Ordens de percurso em árvores bináriasO percurso de todas as sub-árvores executando alguma ação de trata-

mento em cada nó, pode ser feito seguindo uma das seguintes ordens:• pré-ordem: trata raiz, percorre sae, percorre sad;• ordem simétrica: percorre sae, trata raiz, percorre sad;• pós-ordem: percorre sae, percorre sad, trata raiz.

Por exemplo, no caso de imprimir o conteúdo dos nós de uma árvore binária, os algoritmos que implementam esta ação de acordo com cada per-cursosãoapresentadosacontinuação.

void ImprimirPosordem (no _ ptr a)if ( !Vazia(a) ) ImprimirPosordem (retornaSAE(a)); ImprimirPosordem (retornaSAD(a)); printf (Conteudo(a)); return;


void ImprimirSimetrica (no _ ptr a)

if ( !Vazia(a) ) ImprimirSimetrica (retornaSAE(a));

printf (Conteudo(a)); ImprimirSimetrica (retornaSAD(a));

return;

void ImprimirPreordem (no _ ptr a)

if ( !Vazia(a) ) printf (Conteudo(a)); ImprimirPreordem (retornaSAE(a));

ImprimirPreordem (retornaSAD(a));

return;

Por exemplo, dada a árvore de expressão a seguir, como resultado dos percursos apresentados, as expressões resultantes são as seguintes:

Inordem:5+9*3-7+7Preordem:+*+59–377Posordem:59+37-*7+

1. Crie a árvore binária de acordo com a seguinte sequência de números, na ordem:

a)1,2,3,4,5,6,7.Analiseaárvorebináriaobtidaemtermodedesem-penhonaexecuçãodasoperaçõessobreela.

b)20,5,12,36,27,45,9,2,6,17,40.


c)Apartirdaárvoreobtidanoincisoanterior,removerosnós:9,aseguiro5,efinalmenteo20.

2. Implemente um algoritmo que determine se uma árvore binária de busca éefetivamenteumaárvorebináriadebusca.

3. Implemente o método que retorna o maior elemento a partir de um deter-minado nó cujo cabeçalho é: no _ ptr buscaMAX (ABB T). Implemente ométodonasuaversãorecursivaenãorecursiva.

4. Dada uma árvore binária de busca, onde cada nó é constituído pelas seguintes informações:NOME,SEXO (‘M’ou ‘F’), IDADEePESO.Sa-bendoqueaárvorefoiconstruídacomachaveNOMEequejáexisteumponteirochamadoRAIZqueapontaparaonóraizdaárvore,construirum algoritmo que, a partir desta árvore, gere duas listas ordenadas por NOME,umaparahomenseoutraparamulheres.

5.Escrevaumalgoritmorecursivoqueencontreomaiorvalorarmazenadoemumaárvorebináriadebuscajáconstruída.

6.Adapteosalgoritmosdeinserçãoeremoçãoemárvoresbináriasdebus-ca de forma a tratar a ocorrência de conteúdos-chave repetidos, manten-doumcontadordeocorrênciasemcadanó.

7. Para a árvore binária a seguir, escreva as sequências de nós visitados apósaexecuçãodospercursospré-ordem,inordemepós-ordem.Codifi-queosalgoritmoscorrespondentesacadaumdospercursos.

8. UtilizandoasoperaçõesdefinidasnainterfacedoTADABBdenúmeros,escrevaummétodoqueretornequantosnósdeumaABBarmazenamvalores contidos em um intervalo [x1, x2].

Relação entre o número de nós de uma árvore binária e sua altura

A cada nível o número potencial de nós numa árvore binária vai dobran-do, de forma que para uma altura h da árvore existe um número máximo de nós, dado por:

2 0 + 2 1 + 2 2 + ... + 2 h-1 + 2 h = 2 h+1 - 1 nós


Portanto, uma AB de altura h pode ter no máximo O (2h) nós. A partir desta definição temos que o número de nós em uma AB é dada por n = 2h nós. Para despejar h temos que aplicar a definição de logaritmo: log n = h. log 2. Portanto uma árvore binária com n nós pode ter uma altura mínima de O (log n).

Por outro lado, se a árvore tem altura h, deve existir um caminho de comprimento h da raiz até um dos nós, digamos n0, n1, ... nh, e todos os h+1 nós deste caminho devem ficar em níveis diferentes. Assim, a árvore deverá ter pelo menos h+1 nós.

Esta relação entre o número de nós e a sua altura é importante, pois significa que a partir da raiz, qualquer nó pode ser alcançado em no máximo O (log n) passos. Note que se tivéssemos n nós numa lista linear o número máximo de passos seria O (n).

A altura da árvore é uma medida do tempo necessário para encontrar um nó. Esta propriedade atinge a eficiência máxima quando a árvore binária é balanceada, ou seja, todos os nós internos, ou quase todos possuem dois filhos.

É fácil prever que após várias operações de inserção e remoção, a árvore tende a ficar desbalanceada. Em especial, a operação de remoção numa ABB dependendo da estratégia utilizada (substituição do nó a ser removido pelo maior da sub-árvore esquerda ou o menor da sub-árvore direita), favorece sistematicamente uma das sub-árvores.

A solução a este problema consiste em sempre manter a altura das sub-árvores no mínimo, ou próximo do mínimo. Para isso é necessário de proces-sos de inserção e remoção mais complexos que mantenham as sub-árvores balanceadas.


Capítulo 3Árvores AVL

UmaAVLéumaárvorebináriadebuscadinamicamenteequilibrada ou balanceada, na qual se busca manter, a um custo razoável, um tempo de busca próximo àquele que se conseguiria se a árvore fosse completa, o que garante que a altura da árvore é O(log n).OnomeAVLdeve-seaosseuscriadores,osmatemáticosADEL’SON-VEL’SKIIeLANDIS.

Apropriedadedebalanceamentoconsisteemmanterassub-árvoresesquerda e direita de cada nó, na mesma altura, podendo diferir no máximo em1nível.Afiguraaseguirilustraumaárvore,ondearaizseencontrabalanceada uma vez que a suas sub-árvores esquerda e direita possuem a mesmaaltura,noentantoosnósinternosnãosatisfazemessapropriedade.

Com esta restrição, todas as operações sobre árvores podem ser exe-cutadas em tempo O(log n),excetopossivelmenteainserção.Noentanto,para manter a propriedade de balanceamento, além dos algoritmos de per-curso, inclusão e exclusão já discutidos, são necessários algoritmos que restabeleçamoequilíbrioapósinclusõeseexclusões,casoalgumnófiquedesregulado.Porexemplo,nainserção,podeserprecisoatualizarainfor-mação de balanceamento para os nós no caminho de volta para a raiz, pois somenteaquelesnóstiveramassuassub-árvoresalteradas.Nocasodasárvores binárias de busca representadas a seguir, a árvore da esquerda se encontra balanceada uma vez que todos os nós mantem suas sub-árvores comumadiferençadeatéumnível.Jáaárvoredadireitaapresentaumdesbalanceamentonaraiz.


Ainserçãode6.5naprimeiraárvoreprovocaráodesbalanceamentodonó8.Apropriedadedebalanceamentoérestauradaatravésdeoperaçõesde rotação.

Seja αonodesbalanceado.Desdequetodonótemnomáximodoisfilhoseodesbalanceamentodaalturarequerqueaalturadasduassub-árvores deferem em 2, a violação da propriedade pode acontecer como con-sequênciadeoperaçõesdeinserçãoouremoção.

O fator de balanceamento (FB)deumdeterminadonór é calculado como a diferencia entre a altura da sub-árvore esquerda de r e da sub-árvo-re direita de r.Seovalorobtidoformenorouiguala1onóestábalanceado.Casocontrárioonóseencontradesbalanceado.OFBdeumnófolhaé0.

Algoritmoquecalculaaalturadeumnó

int Altura (ABB no)int Alt _ Esq, Alt _ Dir;

if (no = NULL) Altura := -1

else Alt _ Esq := Altura (retornaSAD (no));

Alt _ Dir := Altura (retornaSAE (no));

if (Alt _ Esq > Alt _ Dir)

Altura := 1 + Alt _ Esq

else Altura := 1 + Alt _ Dir;

Nocasoemqueforconstatadoodesbalanceamentoemumdetermi-nadonó,quatrosituaçõespossíveispodemserconstatadas.

• Tipo I : Se a sub-árvore esquerda é maior que a sub-árvore direita (FB>1),easub-árvoreesquerdadestasub-árvoreesquerdaémaiorque a sub-árvore direita dela, então realizar uma rotaçãosimplespara a direita;

• Tipo II : Se a sub-árvore esquerda é maior que a sub-árvore direita (FB>1),easub-árvoreesquerdadestasub-árvoreesquerdaéme-


nor ou igual que a sub-árvore direita, então realizar uma rotaçãodupla para a direita;

• Tipo III: Se a sub-árvore esquerda é menor que a sub-árvore direita (FB<-1),easub-árvoredireitadestasub-árvoredireitaémenor ou igual que a sub-árvore esquerda dela, então realizar uma rotaçãodupla para a esquerda;

• Tipo IV: Se a sub-árvore esquerda é menor que a sub-árvore direita (FB<-1),easub-árvoredireitadestasub-árvoredireitaémaior que a sub-árvore esquerda dela, então realizar uma rotação simplespara a esquerda.

Apartirdassituaçõesapresentadas,qualquer tipodedesbalancea-mentopodesercorrigidoaplicandoumadas4rotaçõesdescritas.

ExemploComeçando a partir de uma árvore vazia, são inseridos os números de

(1),(4)e(7).Oprimeiroproblemaacontecenainserçãodo(7):apropriedade


debalanceamentoévioladanaraiz.Pararesolveréexecutadaumarotaçãosimplesaesquerda.

A seguir é inseridaa chave (9), semprejuízodobalanceamentodaárvore.Ainserçãodo(8)provocaumanovaviolaçãononó(7)(etambémnaraizdaárvore).Reparequenestecasoumarotaçãosimplesaesquerdanãoresolveoproblema.

Odesbalanceamentononó(7)éresolvidoemdoispassos,atravésdeumarotaçãoduplaaesquerda.Noprimeiropassoérealizadaumarota-çãosimplesadireitaenvolvendoasub-árvoredonódesbalanceado.Jánosegundo passo, uma rotação a esquerda envolvendo o nó desbalanceado devolveobalanceamentoàárvore.

Ainserçãodo(12)provocaodesbalanceamentodaraizdesdequeasub-árvoreesquerdadealtura0,enquantoqueadireitatemaltura2.pararesolveréexecutadaumarotaçãosimplesaesquerda.


Comoresultadodarotação,onócomachave(8)setornaanovaraizdaárvore,ecomisso,asuasub-árvoreesquerda(7)setransformananovasub-árvoredireitado(4).

Continuandooexemplo,a inserçãodachave(10)desbalanceiaonó(9),desencadeandoumanovarotaçãoduplaaesquerda.

ÉimportantesalientarqueseaárvorenãofosseAVL,oresultadodasinserçõesteriageradoumaárvoredealtura5,enquantoqueaAVLobtidaapartirdamesmasequenciadeinserçãopossuialtura2.

1.Considerandoqueaaltura(h)deumaárvoreédadapelocaminhomaislongo desde a raiz até uma folha, explique com as suas palavras a re-laçãoexistenteentrealtura (h)deumaárvorebináriaeaquantidade(mínimaemáxima)denós.

a)Qualarelaçãoentreaaltura(h)deumaárvoreeotemporequerido(custo)paraencontrarumnó?

b)Emqualsituaçãoabuscaemumaárvorebináriapodeatingirefici-ência máxima?


2.DefinaumaárvoreAVLestabelecendoassuaspropriedades,vantagensedesvantagensdasuautilização.

3. Dadaaseguinteárvore(bináriadebusca)AVL,simuleoprocessodein-serção e remoção das seguintes chaves na árvore na ordem dada: inser-ção25-inserção70-inserção15-inserção12-inserção18-remoção15.Verifiqueacadapassoseapropriedadedebalanceamentocontinuasendomantida.Emcasodedesbalanceamento,indicaronódesbalance-adoeasoperaçõesderotaçãoindicadaspararesolveroproblema.

4.Considerandoaseguintesequênciadecaracteres:A,Z,B,Y,C,X,D,P,E,V,F.SimuleaconstruçãopassoapassodeumaárvoreAVLdecarac-teres, e indique em que situações ocorrem rotações simples ou duplas, à direitaouàesquerda,dosvárioselementosdaárvore.

5.Considerandoaseguintesequênciadenúmeros:inserção50,inserção20,inserção30,inserção25,inserção10,inserção15,remoção20,in-serção20,inserção40.Simuleaconstruçãopassoapassodeumaárvo-reAVLdenúmeroscomasequênciaacima,eindiqueemquesituaçõesocorrem rotações simples ou duplas, à direita ou à esquerda, dos vários elementosdaárvore.

Nestaunidadeforamapresentadososconceitosfundamentaissobreárvoreseárvoresbinárias.OTADÁrvoreBináriadeBuscafoidefinidoeim-plementado, e alguns exemplos de utilização foram ilustrados, assim como osdiferentespercursospossíveissobreaestrutura.

Adicionalmente,aconceituaçãosobreárvoresbináriasbalanceadas,esua importância em relação ao aumento no desempenho das operações re-alizadasfoirelatada.Apropriedadedebalanceamentoeasestratégiaspararestabeleceroequilibrionaárvoreforamdetalhadoseilustrados.


AHO,J.E.Hopcroft,andJ.D.Ullman.Data structures and algorithms.Addison-Wesley,Reading,Mass.,1983.


HOROWITZandS.Sahni(1987).Fundamentals of data structures, Com-puterSciencePress.EditoraCampus.




Unidade

Objetivos:

• A eficiência alcançada para resolver o problema da busca ou recuperação deinformaçãoapartirdeumaestruturadedadoséumindicadordaeficiênciadaestrutura. Nesta unidade são apresentados métodos específicos de busca queobjetivam reduzir a complexidade em relação aos métodos de busca padrão apresentados em unidades anteriores. Em particular, é apresentado o uso detabelasdeíndicesquepossibilitamoacessodiretoàinformação,idealmente.Nodomínioespecificodetratamentodecadeiasabuscadigitaléapresentadacomosoluçãoparaoproblemadecasamentodepadrões.Finalmente,ofuncionamentodeestruturasauto-ajustáveisédescrito.

Busca avançada

5


Capítulo 1Tabela de dispersão

O armazenamento e recuperação da informação são possivelmente as funcionalidadesmaisimportantesrequeridasdeumcomputador.Deformageral, a informação é organizada em estruturas que possibilitam que os da-dospossamserrecuperadosdamemóriaeinterpretadosquandonecessário.

A pesquisa por um determinado dado requer que seja estabelecidoum critério, que geralmente é baseado na existência de uma chave de pes-quisa que possibilita que ocorrências da informação sejam corretamente identificadas.

Diversas estratégias podem ser utilizadas para realizar uma pesquisa porregistrosemumatabela.Aescolhapelamaisadequadadependeprin-cipalmentedasnecessidadesecaracterísticasdaaplicaçãoespecífica.Osdois principais fatores que influenciamnesta escolha são o tamanhodaentrada, ou seja a quantidade de elementos a serem processados e as ope-raçõesmaisfrequentementeexecutadassobreaestrutura.

Existemdiversosmétodosdepesquisaamplamenteutilizados.Den-tre eles, a pesquisa sequencial é o método mais simples onde, a partir do primeiro registro, a pesquisa é realizada em forma sequencial seguindo a ordemapresentadapeloselementos.Oprocessocontinuaatéqueachaveforencontradaouatabelaforpercorridacompletamentesemsucesso.EstaestratégiafoiutilizadanométododebuscaimplementadonoTADLista.Oesforço requerido nesta busca é O(n), uma vez que no pior cenário, a lista precisaráserpercorridanasuatotalidade.

Aárvoredebuscae suasvariantesabordadanaUnidade4 éumaestruturadedadosmuitoeficienteparaarmazenamentoerecuperaçãodeinformação.Nestecaso,ocustodemandaráemmédiaO(log n).

Tantoapesquisasequencialcomoaaplicadaemárvoresdebusca,sãobaseadasnacomparaçãoentrechaves.Diferentemente,atécnicabaseadaem transformação de chave ou hashing utiliza uma função de transforma-ção aritmética a partir da qual uma chave é mapeada para um endereço de memória utilizando as chamadas tabelas de dispersão ou tabelas de hash.Aseguirofuncionamentodatabeladedispersãoéapresentado.

Seja, por exemplo, a distribuição de expedientes de funcionários de uma empresa ao longo de um arquivo de pastas, onde cada pasta indica ainicialdosobrenomedofuncionário.Aprincipioéconsideradoquenãoexiste ordem para a colocação dos expedientes dentro de cada pasta do arquivo.Nessecasoosobrenomeseriaachaveeainicialoendereçodear-mazenamento.

Emciênciadacomputaçãoatabeladedispersão(dehashing, no in-glês),éumaestruturadedadosespecial,queassociachavesdepesquisaavalores.Seuobjetivoé,apartirdeumachavesimples,fazerumabuscarápidaeobterovalordesejadoemtempoconstante.

A chave de pesquisa é ocampo do registro a par-tir do qual o registro pode ser referenciado de forma unívoca.Cadaregistronoconjunto possui um cam-po chave único o que pos-sibilitaasuaidentificaçãoapartirdele.


Autilizaçãodetabeladedispersãoparaoarmazenamentoerecupe-raçãodainformaçãovisatornarestasoperaçõesmaiseficientesemtermosde esforço, em relação aos outros mecanismos de busca estudados, alcan-çando uma complexidade média de O(1). O ganho com relação a outras es-truturasassociativas(comoumvetorsimples)passaasermaiorconformeaquantidadededadosaumenta.Emcontrapartida,emumatabeladedis-persãoévirtualmenteimpossívelestabelecerumaordemparaoselementos.Emoutraspalavras,afunçãodedispersãoestabeleceumaindexaçãosobreaschavesmasnãopreservaaordementreelas.

O método de pesquisa com uso de transformação de chave envolve duasetapas.

1. Desenvolver e aplicar a função de transformação aritmética do valor dachaveparaumendereçonamemória.

2.Dependendodaquantidadedechavesedaeficiênciadafunçãodetransformação na geração de endereços, pode ser necessário ela-borar uma estratégia de tratamento para colisões para tratar os casosemqueduaschavesgeremomesmoendereço.

Considere a existência de n chaves a serem armazenadas na tabela T, de dimensão m.Atabelaéconsideradaumaestruturasequêncial,portantoas posições ou endereços se encontram no intervalo [0, m – 1].Seonúmerode chaves n for igual ao número de posições na tabela, m, e, além disso, os valores das chaves forem de 0 a m – 1, então, cada chave x poderia ser ar-mazenada no endereço xcorrespondente.

Tabelas de dispersão são tipicamente utilizadas para indexação degrandesvolumesdeinformação,taiscomobasesdedados.Outrosexem-plos de uso das tabelas de dispersão são as tabelas de transposição em jogosdexadrezparacomputador.

A função de dispersãoAfunçãodedispersãoéaresponsávelporgerarumíndiceapartirde

determinadachave.Adefiniçãodafunçãoédefundamentalimportância,uma vez que se não for adequada para o tratamento dos dados em questão, amanipulaçãodatabelateráummaudesempenho.

O ideal para a função de dispersão é que sejam sempre fornecidos índicesúnicosparaaschavesdeentrada.A funçãoperfeitaseriaaque,paraquaisquerentradasAeB,sendoAdiferentedeB,fornecessesaídasdiferentes.QuandoasentradasAeBsãodiferentese,passandopelafun-ção de dispersão, geram a mesma saída, acontece uma colisão.Deformasimplificadatemosque:Pos (elemento) = H (elemento, n), onde H é a função de dispersão aplicada ao elemento, considerando o tamanho ndatabela.

A ocorrência de colisõespode ser abordada do ponto de vista probabilis-tico. O paradoxo do ani-versário estabelece que, se tomadas aleatoriamen-te50pessoas,pelomenosduas pessoas teriam a mesma data de aniversá-riooucolisão.


Noexemplo,afunçãodedispersão é aplicada sobre a chave nome, paraobterumíndicedeacessoaovetorondeoregistroéarmazenado.Oregistropodeagregarvárioscamposdeinformação,alémdocampochave.

Noentanto,naprática,édifícilencontrarumafunçãodedispersãoperfeita que consiga espalhar de forma uniformemente esparsa as chaves aolongodaestrutura.Dandosequênciaaoexemploacima,aaplicaçãodafunção de dispersão para o nome Luiza pode vir a gerar o mesmo índice do que Luiz (790),provocandoumacolisão.Estasituaçãoéindesejávelumavezquereduzodesempenhodosistema.Noentantoémuitocomumacontecer,é por isso que diversas técnicas de tratamento de colisões tem sido propos-tasnaliteratura.

ExemplodefunçãodedispersãoUmafunçãodedispersãomuitosimplesenvolvetransformarumca-

racter emumvalornumérico. Isto,na linguagemC,poderia ser feitodaseguinte forma:

int hashExemplo(char * chave)

return (chave[0]-65);

Dada sua simplicidade esta função causaria muitas colisões, no en-tanto pode ser utilizada como parte de uma função mais complexa que possibiliteummelhorespalhamentodosdados.

Na prática, funções dedispersão perfeitas ou quase perfeitas são en-contradas apenas onde a colisão é intolerável, como por exemplo em aplica-ções de criptografia, ouquando o conteúdo da ta-bela armazenada é conhe-cidopreviamente.


1.Definaoconceitodetabeladedispersãoedescrevaoprocessoenvolvidonaaplicaçãodestatécnica.

2.Estabeleçavantagensedesvantagensemrelaçãoaoutrosmecanismosdearmazenamentoerecuperaçãodeinformação.

3. Pesquise na literatura sobre funções de dispersão comumente utilizadas equetemdemostradodesempenhoaceitável.

a)Métododadivisão

b)Métododadobra

4.Apresenteumexemplopráticodegeraçãodeumatabeladedispersãoutilizandoosmétodospesquisadosnoitemanterior.

O tratamento das colisões envolve geralmente a utilização de alguma outra estrutura de dados em conjunção com as tabelas de dispersão, tal comoumalistaencadeadaouatémesmoárvoreárvoresbalanceadas(AVL).Emoutrasoportunidadesacolisãoésolucionadadentrodaprópriatabela.

Estratégias para resolução de colisõesConsiderando que a ocorrência de colisões é praticamente inevitável,

um bom método de resolução de colisões é essencial, independentemente da qualidadedafunçãodedispersãoutilizada.

Há diversos algoritmos de resolução de colisão, mas os mais conheci-dossãoosdeencadeamentoesondagem.

Encadeamento Autilização de listas encadeadas é a soluçãomais simples para o

tratamentodecolisões.Nestecaso,apartirdoíndiceemconflitoémantidoum ponteiro para uma lista encadeada onde são armazenados os registros emconflito.Ainserçãonatabelarequereinserçãodentrodalistaencade-ada.Analogamente,aremoçãorequeratualizarosíndicesdentrodalista.OTADlistanasuaversãoencadeadaatravésdeponteirosfoiapresentadonaUnidade3.

Graficamente, a solução de colisões através de listas encadeadas érepresentadaaseguir.AsituaçãodecolisãoentreaschavesLuiz e Luiza seria resolvida adicionando o registro correspondente à chave repetida na listaassociadaaoíndice.


Estasoluçãoadicionaumníveldeindireçãoàsoperaçõesdeinserçãoe recuperação da informação, uma vez que o registro não mais é acessado diretamente a partir da chave, no entanto, o custo de acesso continua se mantendobaixo.Estruturasdedadosalternativaspodemserutilizadasnolugardaslistasencadeadas.Porexemplo,apartirdautilizaçãodeárvoresbináriasbalanceadas(AVL)épossívelmelhorarotempomédiodeacessoda tabela dispersão para O(log n) ao invés de O(n) demandado no caso da utilizaçãodelistas.

Técnicas de sondagemEmcontrapartidaàtécnicadeencadeamento,astécnicasdesonda-

gem para o tratamento de colisões não fazem uso de nenhuma estrutura auxiliarparaoarmazenamentodainformação.Emcasodecolisão,osre-gistrosemconflitosãoarmazenadosdentrodaprópriatabela,utilizandobuscaspadronizadasatéencontrarumregistrovazioouoregistrobuscado.

Outras formas mais complexas de implementar a técnica de sondagem consiste em determinar a posição do novo elemento em colisão a partir de umafunçãoquadrática,incrementandooíndiceexponencialmente.Destaforma, caso a chave procurada não se encontre na posição 10, em uma se-gundatentativaseráprocuradanaposição100,1000,eassimpordiante.

Umaterceirapossibilidadeenvolveaaplicaçãodeumanova funçãode dispersão (também chamado de double hashing),cujachavedeentradaseráovalorgeradopelafunçãoanterior.Estasoluçãopodeserútilemcasosmuitoespecíficos,comenormesquantidadesdedados,noentantoasobre-carganosistemanemsemprejustificaaexperiência.


1.Expliqueoconceitodecolisãoeporqueacontecem.

2. Pesquise as diferentes formas de resolução de colisão e analise suas van-tagensedesvantagens.Exemplifique.


Capítulo 2Busca digital

O problema de busca geralmente considera a comparação entre uma chave desejada e as chaves que compõem um conjunto, que pode ser estru-turado de formas convenientes no intuito de melhorar o desempenho das operações.Diferentemente,nocasodabuscadigital,achaveéconstituidade um conjunto de caracteres ou dígitos pertencentes a um alfabeto apro-priado.Nestecasoespecífico,acomparaçãoentrechavesérealizadadígitoadígito,individualmente.

Abuscadigitalfuncionadeformasimilaràbuscaemdicionários,de-compondoapalavraletraaletra(caracteroudígito),ondeaprimeiraletrada palavra determina um índice de página onde se encontram as palavras iniciadasporaquelaletra.

Os métodos de busca digital são particularmente úteis quando as chavessãograndesedetamanhovariável.Apartirdestapesquisaépos-sível localizar todas as ocorrências de uma determinada cadeia em um tex-to, com tempo de resposta O(log n)emrelaçãoaotamanhodotexto.Esteproblema é conhecido como casamento de cadeias, no contexto de proces-samento de cadeias de caracteres.

O processamento de cadeias de caracteres envolve duas classes de problemas: casamento de cadeias (do inglês, pattern matching)ecompres-sãodecadeias.

O problema de casamento de cadeias envolve a procura pela ocorrên-ciadeumdeterminadopadrãoemumtextoqueestásendoeditado.For-malmente, o texto T é considerado um vetor de tamanho n e o padrão P um vetor de tamanho m, com m < = n.OselementosquecompõemT e P perten-cemaumalfabetofinitodetamanhoc.DadasduascadeiasT e P, deseja-se saber as ocorrências de P em T.

Acompressãodetextoestárelacionadacomarepresentaçãodeumtexto original de forma a ocupar menos espaço, ou seja utilizando um nú-meromenordebits.

Métodos mais modernos de compressão de cadeias possibilitam oacesso direto a texto comprimido sem necessidade de descomprimir o texto, permitindomelhoraraeficiênciadesistemasderecuperaçãodeinformaçãoeaumentaraeconomiadeespaço.

No,métododebuscadigital,tantoopadrãoprocuradoquantootextosão pré-processados a partir da construção de índices de forma a reduzir a complexidade das operações para um custo O(log n).Noentanto,otempodepré-processamentoécompensadopormuitasoperaçõesdebusca.

Aseguirsãoapresentadosbrevementeostiposdeíndicesmaisconhe-cidos para o pré-processamento de cadeias de forma a agilizar o desempe-nhodasbuscas.

As cadeias aparecem noprocessamento de texto em linguagem natural, di-cionários, sequenciamen-todeDNA,processamentodeimagens,etc.Emcadadomínio, um alfabeto es-pecíficoéutilizado.Exem-plos de alfabetos: 0, 1, a, b,c,...,z,0,1,...9.


Árvore digitalAestruturamaisapropriadapararealizarabuscadigitaléatravésda

árvoredigital.Formalmente, uma sequência S = s1, ..., sn um conjunto de n chaves

em que cada si é formada por uma sequência de elementos dj denominados dígitos.Supõe-sequeexisteemS o total de m dígitos distintos que determi-nam o alfabeto ordenado de S.Osprimeirosp dígitos de uma chave com-põemoprefixodetamanhopdachave.

UmaárvoredigitalparaSéumaárvorem-áriaT, não vazia, tal que:1. Se o nó véoj-éssimofilhodeseupai,entãov corresponde ao dígito

dj do alfabeto S, 1 <= j <= m.

2. Para cada nó v,asequênciadedígitosdefinidapelocaminhodesdea raiz de T até vcorrespondeaumprefixodealgumachavedeS.

Naanálisedeumtextoemlinguagemnatural,S seria o conjunto de frases do texto, onde si é cada frase que pode ser buscada e n o número de frases, e m=26.

Emumcasoespecíficodaárvoredigital,noentantoomaisutilizado,temos a árvore digital binária, onde o grau da árvore é m = 2.Oalfabetoconsideradonestecasoé0,1.Apartirdaconstruçãodaárvoredigitalcomestas características, as chaves a serem consideradas nas buscas envolvem sequênciasbinárias.

Chaves Árvoredigitalbinária

00

0010

010

010111

010110

00100

11

110

1101

A partir da árvore gerada é possível observar que algumas chavesbináriassãoprefixosdeoutraschavespertencentesàmesmacoleção.Porexemplo, o caminho da raiz até o nó com conteúdo † correspondente à chave 010queéprefixodachave010110correspondenteaocaminhoatéonó ‡.

Cadanónaárvorepertenceaumachave(oumais)doconjunto.Porexemplo o nó com † correspondeàchave010,efazparte(prefixo)daschaves010111etambém010110.Deacordocomaimplementaçãodaárvoredigital,cada nó na árvore envolve um campo adicional contendo um ponteiro para ainformaçãocorrespondendeàchavedetectada.Porexemplo,nocasodonó†existiriaumponteirodeformaalocalizarnotextoachave010.Ospon-teiros de nós que não correspondem ao último dígito de uma chave válida seriamnulos(NULL).


Umavezcriadaaárvore,abuscaacontececomoresultadodopercur-soapartirdaraiz:ofilhoesquerdorepresentaodígito0eofilhoràdireitarepresentaodígito1.Notequeabusca localizanãosomenteumachaveválidacompleta,mastambémprefixos.Abuscaporprefixospodeserdegrandeutilidadedependendodaaplicação,comoporexemplolinguística.

1.Expliquecomofuncionaabuscadigitaleseupapelnocontextodepro-cessamentodecadeias.Mencioneáreasdeaplicaçãodestetipodebusca.

2.Pesquisesobrecompressãodetextosemlinguagemnatural.

3.Criegraficamenteumaárvoredigitalbináriaapartirdoseguintecon-junto de chaves: 00, 0000, 00010, 00011, 0101100, 0101101, 10, 101, 1010.


Capítulo 3Estruturas autoajustáveis

Asoperaçõesdeinserçãoeremoçãodeelementosaplicadassobreumadeterminada estrutura de dado afetam necessariamente a forma da estru-tura.Jáaoperaçãodebuscaéinocuanosentidoemque,aprincipio,nãoproduznenhumaalteraçãonaformadaestrutura.Nocasodeestruturasautoajustáveis, a operação de busca pode alterar a forma da estrutura de dadoobjetivandomelhorarodesempenhoembuscasfuturas.Porexemplo,no caso de ser detectada certa frequência na procura por um determinado componente em uma lista ou árvore, a posição ou nível do componente na lista ou na árvore, respectivamente, pode ser alterado, de forma a agilizar asfuturasbuscaspelomesmocomponente.

Apartirdestecomportamento,acomplexidadeordináriadeumaope-ração calculada individualmente, e de forma independente, para o pior caso nasuaexecuçãonãoémaisadequada.Emcontrapartida,acomplexida-de amortizada considera a configurações da estrutura ao longo de umasequência de operações executadas, avaliando as consequências de cada execução,deformaacumulada.

O conceito de autoajuste pode ser aplicado a diversas estruturas de dados,taiscomolistas,conjuntoseárvores.

Listas autoajustáveisOTADLista foiabordadonaUnidade3.Comofoivisto,o tipo lista

pode ser implementado utilizando a abordagem de alocação de memória estática(vetores)oudinámica(ponteiros).Considerandoquenasuaversãomais simples não é estabelecido um critério de ordenação entre os elemen-tos, alguns elementos na lista podem ser requisitados mais frequentemente doqueoutros.Apartirdestaconstatação,umalistaautoajustável imple-menta estratégias para reduzir o tempo de acesso em operações subsequen-tes.Aestratégiageralconsisteemposicionarosnósmaisprocuradosmaispróximos do inicio da lista, de forma que em futuras buscas possam ser alcançadosmaisrapidamente.Estaestratégiapodeserimplementadauti-lizandodiversosmétodos.

O método de mover para frente transfere o nó procurado para o inicio dalista.Reparequedependendodaimplementaçãoutilizadaparaimple-mentaralista,estaoperaçãopodesercustosa.Poroutrolado,nóscombai-xa probabilidade de acesso podem ser eventualmente acessados, tornando maiscustosasasbuscarpornóscommaiorprobabilidade.

Nométododetransposição uma vez acessado o nó procurado, este é transferidoparaaposiçãoimediatamenteanterior.Namedidaemqueonóforacessado,maispróximodoinicioseráposicionado.

Aimplementaçãodométododecontador de frequências envolve a in-corporação de um campo adicional na estrutura do nó da lista, responsável


pormanteronúmerodeacessosefetuadosaorespectivonó.Estecampoéutilizadocomochaveparaaordenaçãodecrescentedoselementosnalista.Ou seja que os nós mas frequentemente acessados são localizados no inicio, eportantomaisrapidamentealcançados.

Algunsmétodoshíbridosenvolvemacombinaçãodosmétodosante-rioresdeformaatirarvantagemdosbeneficiosereduzirasdesvantagensdosmétodosnoseuformatoindividual.

1.Expliqueofuncionamentodasestruturasdedadosautoajustáveis.

2.QuaisseriamasadaptaçõesrequeridasparaqueoTADListaapresenta-donaUnidade3setorneTADListaAutoajustável?

a)Definaanovaestruturadedados.

b)Implementeouadapteasoperaçõesnecessárias.

3. Pesquise sobre uma outra estrutura estudada ao longo desta disciplina quepossasetornarautoajustável.Descrevaascaracterísticasdefun-cionamentoeasadaptaçõesnecessárias.

Nestaunidade foramapresentadasdiversas estratégias para arma-zenamentoerecuperaçãodeinformação.Inicialmenteforamapresentadasas tabelas de dispersão ou hash, como uma solução para o acesso direto ou semidireto à informação a partir da geração de índices, obtidos como resultado de um processo de transformação tendo como base o valor chave doregistro.Mecanismosdetratamentodecolisõesnocasodegeraçãodeíndicesrepetidosforamindicados.

Emrelaçãoaoprocessamentodecadeiasdecaracteres,foiapresenta-da a teoria sobre busca digital, que possibilita estabelecer o casamento de chaves,constituídasporcaracteresoudígitos,etexto.Comesteobjetivo,aestruturadeárvoredigitalfoiapresentada.

Finalmente, o funcionamento de estruturas autoajustáveis, com foco nasuaexemplificaçãoatravésdelistasfoidescrito,indicandoasestratégiasdeimplementaçãoaseremseguidas.

De forma geral, todos estes mecanismos e estratégias objetivam tornar maiseficienteoarmazenamentoeposteriorrecuperaçãodainformação,deforma a tornar os algoritmos mais acessíveis e capazes de lidar melhor com acomplexidadecadavezmaiorrequeridapelasaplicaçõesatuais.


AHO,J.E.Hopcroft,andJ.D.Ullman.Data structures and algorithms.Addison-Wesley,Reading,Mass.,1983.


HOROWITZandS.Sahni(1987). Fundamentals of data structures, Com-puterSciencePress.EditoraCampus.




Mariela Inés Cortés ÉdoutoraemInformáticapelaPontifíciaUniversidadeCatólicadoRio

deJaneiro(2003)emestreemSistemasdeComputaçãopeloIntitutoMilitardeEngenhariadoRiodeJaneiro(1999).SuaalmamateréaUniversidadeNacionaldeLaPlata,ondecompletouosestudosdegraduaçãoemCiênciasdaComputação.EspecialistanaáreadeEngenhariadeSoftware, atual-menteéprofessoraadjuntanaUniversidadeEstadualdoCeará,vinculadaao Curso de Ciências da Computação, onde ministra dentre outras, a dis-ciplinadeEstruturadeDados.Adicionalmente,coordenaoLaboratóriodeQualidadeePadrõesdeSoftware(LAPAQ)elideraoGrupodeEngenhariadeSoftwareeSistemasInteligentes(GESSI).

Documents

Estrut Dados Material