Estrutura de Dados UAB-UECE: Computação, EAD e Formação de Professores

F iel a sua missão de interiorizar o ensino superior no estado Ceará a UECE como uma instituição que participa do Sistema Universidade Aberta do Brasil vem ampliando a oferta de cursos de graduação e pósgraduação na modalidade de educação a distância e gerando experiências e possibili dades inovadoras com uso das novas plataformas tecnológicas decorren tes da popularização da internet funcionamento do cinturão digital e massificação dos computadores pessoais Comprometida com a formação de professores em todos os níveis e a qualificação dos servidores públicos para bem servir ao Estado os cursos da UABUECE atendem aos padrões de qualidade estabelecidos pelos normativos legais do Governo Fede ral e se articulam com as demandas de desenvolvi mento das regiões do Ceará Estrutura de Dados Mariela Inés Cortés Computação Computação Estrutura de Dados Universidade Estadual do Ceará Universidade Aberta do Brasil Computação Química Física Matemática Pedagogia Artes Plásticas Ciências Biológicas Geografia Educação Física História 9 12 3 Mariela Inés Cortés Estrutura de Dados Pedagogia Computação 3ª edição Fortaleza Ceará 2015 Computação Química Física Matemática Pedagogia Artes Plásticas Ciências Biológicas Geografia Educação Física História 9 12 3 Editora da Universidade Estadual do Ceará EdUECE Av Dr Silas Munguba 1700 Campus do Itaperi Reitoria Fortaleza Ceará CEP 60714903 Fone 85 31019893 Internet wwwuecebr Email edueceuecebr Secretaria de Apoio às Tecnologias Educacionais Fone 85 31019962 Copyright 2015 Todos os direitos reservados desta edição à UABUECE 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 Presidenta da República Dilma Vana Rousseff Ministro da Educação Renato Janine Ribeiro Presidente da CAPES Carlos Afonso Nobre Diretor de Educação a Distância da CAPES Jean Marc Georges Mutzig Governador do Estado do Ceará Camilo Sobreira de Santana Reitor da Universidade Estadual do Ceará José Jackson Coelho Sampaio ViceReitor Hidelbrando dos Santos Soares PróReitora de Graduação Marcília Chagas Barreto Coordenador da SATE e UABUECE Francisco Fábio Castelo Branco Coordenadora Adjunta UABUECE Eloísa Maia Vidal Diretor do CCTUECE Luciano Moura Cavalcante Coordenador da Licenciatura em Informática Francisco Assis Amaral Bastos Coordenadora de Tutoria e Docência em Informática Maria Wilda Fernandes Editor da EdUECE Erasmo Miessa Ruiz Coordenadora Editorial Rocylânia Isidio de Oliveira Projeto Gráfico e Capa Roberto Santos Diagramador Francisco José da Silva Saraiva Conselho Editorial Antônio Luciano Pontes Eduardo Diatahy Bezerra de Menezes Emanuel Ângelo da Rocha Fragoso Francisco Horácio da Silva Frota Francisco Josênio Camelo Parente Gisafran Nazareno Mota Jucá José Ferreira Nunes Liduina Farias Almeida da Costa Lucili Grangeiro Cortez Luiz Cruz Lima Manfredo Ramos Marcelo Gurgel Carlos da Silva Marcony Silva Cunha Maria do Socorro Ferreira Osterne Maria Salete Bessa Jorge Silvia Maria NóbregaTherrien Conselho Consultivo Antônio Torres Montenegro UFPE Eliane P Zamith Brito FGV Homero Santiago USP Ieda Maria Alves USP Manuel Domingos Neto UFF Maria do Socorro Silva Aragão UFC Maria Lírida Callou de Araújo e Mendonça UNIFOR Pierre Salama Universidade de Paris VIII Romeu Gomes FIOCRUZ Túlio Batista Franco UFF Editora Filiada à C828e Cortés Mariela Inés Estrutura de dados Mariela Inés Cortés 3 ed Fortale za CE EdUECE 2015 120 p il 200cm x 255cm Computação Inclui referências ISBN 9788578264406 1 Estrutura de dados computação I Título CDD 0051 Dados Internacionais de Catalogação na Publicação Sistema de Bibliotecas Biblioteca Central Prof Antônio Martins Filho Thelma Marylanda Silva de Melo CRB3 623 Bibliotecária Sumário Apresentação 5 Capítulo 1 Introdução à complexidade de Algoritmos 7 Introdução 9 1 O que é análise de algoritmos 10 2 Medidas de Complexidade 12 3 Comparação entre algoritmos 14 4 Operações com a notação O 18 Capítulo 2 Representações de Dados 23 1Modelagem Conceitual 25 2 Tipo de dados 26 3 Tipo abstratos de dados 29 4 Critérios para a escolha da estrutura de dados adequada 32 41 Uso da memória 32 Capítulo 3 Listas 37 Introdução 39 1 Definição do TAD Lista40 11 Implementação do TAD Lista usando alocação estática 41 12 Implementação do TAD Lista usando alocação dinâmica 47 Capítulo 4 Pilhas 57 Introdução 59 1 Implementações do TAD Pilha usando vetores 61 2 Implementação do TAD Pilha usando ponteiros 63 Capítulo 5 Filas 67 Introdução 69 1 Implementação do TAD Fila usando vetores 70 2 Implementação do TAD Fila usando ponteiros 74 Capítulo 6 Árvores 81 Introdução 83 1 Árvore binária 85 2 Árvore binária de busca 88 21 Definição do TAD Árvore Binária de Busca 88 22 Implementação do TAD Árvore Binária de Busca 89 23 Ordens de percurso em árvores binárias 95 3 Árvores AVL 98 Capítulo 7 Busca avançada 107 1 Tabela de dispersão 109 11 A função de dispersão 111 12 Estratégias para resolução de colisões 113 2 Busca digital 114 21 Árvore digital 115 3 Estruturas autoajustáveis 117 31 Listas autoajustáveis 117 Sobre a autora 120 Apresentação O constante aumento da complexidade dos sistemas e suas demandas com putacionais relacionadas a tempo e espaço impõem o desafío de projetar so luções algorítmicas cada vez mais eficientes Neste contexto as estruturas de dados e seus algoritmos têm um papel fundamental uma vez que constituem os blocos construtores utilizados na resolução dos mais diversos problemas em todas as areas da computação O objetivo do presente livro é apresentar de forma clara e amigável di ferentes estruturas de dados e seus algoritmos de manipulação analisando a estratégia mais eficiente para a sua implementação em termos de comple xidade Esta análise envolve a utilização de técnicas de projeto associadas a técnicas de programação as quais são adequadas às caracteristicas da aplicação específica O livro está organizado em 7 capítulos Os primeiros fornecem as ba ses necessárias para a análise e o projeto de uma boa solução algorítmica incluindo conceitos básicos sobre complexidade tipos e estruturas de da dos O capítulo 3 apresenta o conceito central de Listas a partir do qual duas importantes e amplamente utilizadas estruturas são derivadas Pilhas e Filas a quem os capítulos 4 e 5 O capítulo 6 apresenta a estrutura de Árvore sua conceituação im plementação e algoritmos de manipulação básicos Mais especificamente nesta parte são exploradas as Árvores Binárias de Busca analizando suas características e as implicações em relação à eficiência Neste contexto a fundamentação e funcionamento das árvores balanceadas AVL são apresentados Finalmente no capítulo 7 são descritas as técnicas avan çadas de pesquisa aplicadas sobre estruturas de dados específicas tais como tabelas de dispersão busca digital e estruturas autoajustáveis O conteúdo apresentado destinase principalmente para professo res e alunos de graduação em Ciências da Computação ou áreas afins fornecendo um embassamento teórico e uma clara noção das estratégias a serem seguidas na implementação dos algoritmos para a manipulação eficiente das estruturas de dados mais amplamente utilizadas A autora Capítulo 2 Representações de Dados Capítulo 1 Introdução à complexidade de Algoritmos Estrutura de Dados 9 Objetivos Neste capítulo é introduzido o conceito de complexidade de algoritmos Este conceito é central na Ciência da Computação uma vez que possi bilita avaliar e comparar soluções algorítmicas fornecendo os insumos necessários para determinar qual é o algoritmo mais adequado para re solver determinada classe de problemas Introdução Um algoritmo determina um conjunto de regras não ambíguas as quais es pecificam para cada entrada uma seqüência finita de operações gerando como resultado uma saída O algoritmo representa uma solução para um pro blema se para cada entrada gera uma resposta correta sempre que dispor de tempo e memória suficientes Um algoritmo pode ser implementado através de diferentes programas1 Ou seja diferentes implementações podem ser propostas a partir de um único algoritmo Esta situação nos coloca na dificuldade de escolher qual é a melhor solução para o problema específico Assim sendo apenas resolver o proble ma parece não ser suficiente uma vez que diferentes soluções podem ser ide alizadas a partir de algoritmos para a resolução de um único problema Neste contexto se torna necessário um mecanismo que permita determinar se uma solução é melhor do que uma outra de forma a fornecer uma ferramenta de apoio à decição em relação à qualidade das soluções propostas De forma geral a qualidade de um programa depende do ponto de vis ta Por um lado 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 levando em conta diferentes níveis de experiência Compatibilidade do programa com outros programas ou versões de progra mas de forma a facilitar a troca de informação com outros sistemas existentes Desempenho em relação à velocidade de execução e tempo de resposta Quantidade de memória utilizada pelo programa durante a sua execução aspecto que pode se tornar um fator limitante Os últimos dois itens estão diretamente ligados à quantidade de dados a serem processados ou seja ao tamanho da entrada 1 Programa codifica um algoritmo para ser executado no computador resolvendo um problema É fundamental que o programa produza a solução com dispêndio de tempo e memória Importância de Projeto e Analise de Algoritmos MARIELA INÉS CORTÉS 10 Por outro lado critérios que podem ser determinantes desde o ponto de vista da organização desenvolvedora incluem Portabilidade do código entre diferentes plataformas Documentação e padronização do código Facilidade de evolução e manutenção Reusabilidade do código permitindo que porções de um programa sejam re aproveitadas para desenvolver outros produtos aumentando a produtividade A correta avaliação destes critérios é influenciada por diversos fatores tais como características do hardware sistema operacional linguagens e com piladores plataforma etc Estes fatores são considerados acidentais uma vez que não estão diretamente relacionados à qualidade da solução Em contra partida os fatores essenciais são inerentes à solução e determinantes para a sua qualidade O tempo gasto e o espaço físico na memória são considerados fatores essenciais Consequentemente é preciso de um método formal para medir o tempo e a memória requeridos pelo algoritmo independentemente das características de plataforma de hardware e software sendo utilizadas 1 O que é análise de algoritmos A análise de algoritmos é o coração da Ciência da Computação e tem por objetivo estabelecer medidas de desempenho dos algoritmos com vistas à geração de algoritmos cada vez mais eficientes Adicionalmente fornece fun damentos para a escolha do melhor algoritmo para a resolução de um proble ma específico com base na sua complexidade computacional O tempo de execução e o espaço de memória alocado são os dois fatores principais que determinam a complexidade computacio nal de uma algoritmo Complexidade temporal consiste no número aproximado de instruções executadas Complexidade espacial consiste na quantidade de memória utilizada 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 tamanho da entrada sendo processada Como exemplos temos que Ordenar 100000 elementos leva mais tempo que ordenar 10 elementos A abertura de um editor de textos leva mais tempo e consume mais memória quando é aberto com um arquivo grande do que com um arquivo pequeno Estrutura de Dados 11 Além do tamanho da entrada as características apresentadas na or ganização dos dados também podem influenciar na eficiência de um algo ritmo em relação a uma outra solução Por exemplo o desempenho de um algoritmo específico para ordenar um conjunto onde os dados se encontram parcialmente ordenados pode ser muito diferente se utilizado para ordenar um conjunto de dados totalmente desordenados considerando conjuntos de igual tamanho Logo é importante estabelecer de que forma o tamanho e caracte rísticas da entrada podem influenciar no comportamento do algoritmo Em alguns casos se o algoritmo não é recursivo não contem iterações e não usa al goritmos com essas características o número de passos necessários pode ser inde pendente do tamanho da entrada e consequentemente a complexidade temporal é constante Um exemplo de algoritmo com estas características2 é o algoritmo que imprime HELLO WORD que possui complexidade constante include stdioh main Printf Hello Word Considerando que é impossível fazer uma predição exata do tempo e memória a serem utilizados a estratégia consiste em estabelecer uma aproxi mação com base em conceitos e modelos matemáticos Para refletir 1 Descreva com suas palavras a relação entre os conceitos de algoritmo e programa 2 Determine em quais casos e de que forma as especificações a seguir podem depen der do tamanho ou organização dos dados da entrada Justifique a sua resposta a Procurar o maior elemento em uma sequência b Modificar o conteúdo de uma variável c Imprimir o conteúdo de uma sequência de elementos d A partir dos dados de uma pessoa nome data de nascimento sexo determinar se a pessoa é maior de 18 anos 2 A principal característica de um algoritmo recursivo é a ocorrência de chamadas a ele próprio Para avaliar a complexidade de um algoritmo recursivo é preciso analisar quantas vezes a função vai ser chamada e quantas operações acarretam cada chamada MARIELA INÉS CORTÉS 12 2 Medidas de Complexidade De forma geral a complexidade de um algoritmo é determinada pela quan tidade de trabalho requerido sobre um determinado tamanho da entrada O trabalho depende diretamente do número de operações básicas efetuadas Considere o problema de estabelecer se um determinado elemento pertence a um conjunto de 100 elementos A solução mais simples para este problema envolve uma pesquisa sequencial onde o elemento procurado é comparado a cada um dos elementos pertencentes ao conjunto O número de comparações realizadas irá depender dos diversos cenários possíveis A prin cipio podemos analizar duas situações o elemento é encontrado na primeira comparação realizada ou o elemento não existe no conjunto No primeiro caso seria preciso somente uma comparação enquanto que no último caso todo o conjunto precisaria ser checado envolvendo portanto 100 comparações Situação 1 Elemento procurado 10 Conjunto de elementos 10 7 50 13 99 5 22 2 66 29 15 88 77 0 1 2 3 4 5 6 7 94 95 96 97 98 99 100 Neste caso na primeira comparação o logaritmo encontra o elemento pro curado A comparação é a seguinte Elemento procurado é igual ao primeiro elemento do vetor RSim 1010 Situação 2 Elemento procurado 10 Conjunto de elementos 10 7 50 13 99 5 22 2 66 29 15 88 77 0 1 2 3 4 5 6 7 94 95 96 97 98 99 100 Neste caso o elemento é comparado com todos os elementos do vetor e não é encontrado As comparações são as seguintes 1 Elemento procurado é igual ao primeiro elemento do vetor Rnão 105 2 Elemento procurado é igual ao segundo elemento do vetor Rnão 107 100 Elemento procurado é igual ao centésimo elemento do vetor Rnão 100 A partir das situações apresentadas podemos concluir que a complexi dade de um algoritmo pode ser estabelecida utilizando uma estratégia pessi mista ou máxima ou otimista ou mínima Na estratégia pessimista o algoritmo é analisado levando em conta o cenário mais adverso o que normalmente irá resultar no maior tempo de execução Este critério normalmente é o mais utili zado uma vez que estabelece uma cota ou limite superior no tempo requerido Em oposição a esta abordagem a complexidade otimista ou mínima é obtida quando o problema é analisado levando em conta um cenário ideal demandando portanto menos tempo de execução Pode ainda ser conside rado um caso médio ou esperado correspondente à média dos tempos de execução de todas as entradas de tamanho n Estas estratégias podem ser utilizadas tanto para estabelecer a complexidade espacial quanto temporal dos algoritmos A análise para o cálculo destas medidas pode ser realizada empirica mente isto é com base na experiência e na observação prática exclusivamen te sem se basear em nenhuma teoria No entanto a medição obtida pode ser influenciada por fatores acidentais referentes à plataforma específica como por exemplo a capacidade de processamento do computador sendo utilizado Consequentemente a execução de um algoritmo em um determinado computador pode ter um desempenho diferente à medição resultante a partir da execução do mesmo algoritmo em um outro computador com característi cas diferentes Estas possíveis divergências tornam a abordagem baseada na medição empírica pouco confiável Para refletir 1 Determine o caso otimista e o caso pessimista a partir das seguintes especificações a Encontrar o maior elemento de um vetor desordenado de inteiros b Encontrar o maior elemento de um vetor ordenado de forma decrescente de intei ros c Remover um dado elemento de um vetor de inteiros d Idem anterior considerando um vetor ordenado em forma crescente 2 Considere o problema de encontrar o maior elemento de um vetor de inteiros O algoritmo a seguir apresenta uma solução simples para o problema int Max A Vetor int i Temp Temp A0 for i 1 i n i if Temp Ai Temp Ai return Temp a Determine o número de comparações realizadas entre os elementos de A conside rando que A contem n elementos b Descreva quais são as situações que representam o melhor caso o pior caso e o caso médio para o algoritmo MARIELA INÉS CORTÉS 14 3 Comparação entre algoritmos Como dito anteriormente para um dado problema podem existir diversos algo ritmos possíveis Cabe ao programador analisar as possibilidades e escolher o algoritmo mais adequado utilizando como critério básico a sua complexidade Uma abordagem amplamente adotada para analizar a complexidade de algoritmos é baseada na análise sobre as operações fundamentais que compõem o algoritmo a partir das quais é derivada uma função custo mode lando o comportamento que o algoritmo irá a adotar de acordo com os dados de entrada fornecidos Em particular quando consideradas entradas suficien temente pequenas o custo é reduzido mesmo no caso de algoritmos inefi cientes Já para tamanhos de entrada suficientemente grandes a escolha por um determinado algoritmo pode ser um problema crítico Logo a análise de algoritmos é interessante para valores grandes da entrada ou seja no caso de algoritmos que manipulam grandes quantidades de dados O estudo da complexidade consiste em determinar a ordem de magni tude do número de operações fundamentais realizadas pelo algoritmo des critas a partir da definição da função custo A partir desse estudo é possível realizar a comparação do comportamento assintótico através da análise dos gráficos3 correspondentes A comparação entre funções com base no critério de comportamento assintótico consiste no estudo do crescimento de funções para valores gran des de n no nosso caso referente ao tamanho da entrada A partir dessa aná lise as funções são classificadas em ordens onde cada ordem agrupa fun ções de crescimento semelhante O algoritmo assintoticamente mais eficiente é o melhor para todas as entradas Neste contexto uma função é considerada uma cota assintótica superior ou domina assintoticamente outra quando cres ce mais rapidamente do que outra graficamente o gráfico da primeira função fica por cima da segunda a partir de certo ponto m No caso geral nem sem pre é 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 ou seja o gráfico de f fica sempre por baixo do gráfico de g então a escolha para o algoritmo correspondente a f é óbvia 3 Comportamento observado de fn quando n tende a infinito Estrutura de Dados 15 Gráfico 1 f sempre é inferior a g Neste caso o algoritimo f é melhor 2 Se f às vezes é inferior a g e viceversa e os gráficos de f e g se intercep tam em um número infinito de pontos Neste caso consideramos que há empate e a função custo não ajuda a escolher um algoritmo Gráfico 2 Às vezes f é superior e às vezes g é superior e os gráficos se interceptam em um número infinito de pontos Empate 3 Se f às vezes é g inferior a g e viceversa e os gráficos de f e g se cortam em um número finito de pontos Portanto a partir de certo valor de n f é sempre superior a g ou é sempre inferior Neste caso consideramos melhor aquele algoritmo que é inferior ao outro para grandes valores de n Gráfico 3 Se os gráficos se interceptam uma quantidade finita de vezes o melhor é aquele que menor que o outro para valores grandes de n MARIELA INÉS CORTÉS 16 As funções mais comumente encontradas em análise de programas considerando n como tamanho da entrada são fn k Constante fn k n Linear fn n log n Logarítmica fn k n2 Quadrática fn k n3 Cúbica fn nk Polinomial fn k en Exponencial A figura a seguir representa a ordem de crescimento das funções mais comumente utilizadas na representação da complexidade dos algoritmos Comparativamente podemos concluir que na medida em que o tamanho da entrada n aumenta a função linear n cresce mais rapidamente do que a fun ção logn que por sua vez cresce mais lentamente do que a função quadrá tica n2 e assim por diante Sempre é possível determinar a taxa de crescimento relativo de duas funções fn e gn calculando Lim fn gn x A partir deste cálculo existem os seguintes valores possíveis 0 então gn é limite superior para fn c então fn e gn tem complexidades equivalentes infinito então fn é limite superior para gn No caso de funções oscilantes como o caso de senn ou cosn ne nhuma afirmação pode ser feita Estrutura de Dados 17 Para refletir 1 Considere os algoritmos A e B com complexidades CAn 1000 n2 CBn 0 1 n3 Determine a partir de qual valor de n CB domina assintoticamente CA 2 Para um determinado problema P temos algoritmos A B C e D com as seguintes complexidades CAn 100 n log n CBn 1000 n CCn 4 n2 CDn 10 5 en Classificar os algoritmos do melhor até o pior em termos de complexidade sempre considerando valores grandes da variável n tamanho da entrada Justifique A notação utilizada para denotar a dominação assintótica foi introduzida por Knuth em 1968 De acordo com esta notação a expressão gn Ofn expressa que fn domina assintóticamente gn A expressão pode ser lida da seguinte forma gn é da ordem no máximo de fn As definições a seguir formalizam a notação de Knuth4 A notação mais comumente usada para medir algoritmos é O uma vez que determina um limite superior da complexidade Definição A função custo Cn é OFn se existem constantes positivas c e m tais que Cn c Fn quando n m A definição acima afirma que existe algum ponto m a partir do qual c Fn é sempre pelo menos tão grande quanto Cn Assim se os fatores cons tantes são ignorados Fn é pelo menos tão grande quanto Cn Como exemplo seja gn n 12 Logo gn é On2 quando m 1 e c 4 uma vez que n 12 4n2 para n 1 Em outras palavras quanto dizemos que Cn OFn estamos garan tindo que a função Cn não cresce mais rápido do que Fn Assim Fn é um limite superior para Cn De forma geral os termos de menor peso e os fatores podem sempre ser eliminados uma vez que para valores grandes da variaveis estes compo nentes se tornam despresiveis Assim O4n3 10n2 e On3 são sinônimos mas o segundo termo é mais preciso Se um algoritmo é O1 significa que o número de operações funda mentais executadas é limitado por uma constante Intuitivamente se gn 2 n2 então gn On4 gn On3 e gn On2 Todas as respostas são tecnicamente corretas mas a menor é a melhor resposta 4 Donald Ervin Knuth nascido em Milwaukee em 10 de Janeiro de 1938 é um cientista computacional de renome e professor emérito da Universidade de Stanford É o autor do livro The Art of Computer Programming uma das principais referências da Ciência da Computação É considerado o criador do campo de Análise de Algoritmos e fez diversas e importantes contribuições a vários ramos da teoria da computação MARIELA INÉS CORTÉS 18 Outras definições formais Limite inferior Ω A notação Ω é usada para especificar o limite inferior da complexidade de um algoritmo Complexidade exata Ө A notação Ө é usada para especificar exatamente a complexidade de um algoritmo Limite superior estrito o Enfim a notação o é usada para especificar que a complexidade de um algoritmo e inferior estritamente a certa função Para refletir 1 Suponha gn n e fn n2 demostre qual das seguintes afirmações é verdadeira a fn Ogn b gn Ofn 2 Determine a ordem máxima para as seguintes funções e justifique a sua resposta detalhando os valores de c e n adequados a gn 3n3 2n2 n b hn n2 n 1 4 Operações com a notação O Algumas operações que podem ser realizadas com a notação O são apresen tadas a seguir fn Ofn c Ofn Ofn onde c é uma constante Ofn Ofn Ofn OOfn Ofn Ofn Ogn Omax fn gn Ofn Ogn Ofn gn fn Ogn Ofn gn Estas operações foram demostradas matematicamente na literatura e tem aplicação direta para o cálculo do tempo de execução de trechos de programas Por exemplo a regra da soma Ofn Ogn pode ser utili zada para calcular o tempo de execução de uma sequência de trechos ou sentenças de programas Aplicando essa regra somente será considerado Estrutura de Dados 19 o trecho que tiver atribuído o custo máximo dentre os trechos ou sentenças considerados no sumatório Aplicando a abordagem de dividir para conquistar a complexidade de um algoritmo pode ser determinada a partir da complexidade das suas partes De forma geral a análise da complexidade é feita em forma particular para cada algoritmo mas existem conceitos gerais que só dependem das estrutu ras algorítmicas ou comandos de controle utilizados no algoritmo 1 Sequência ou conjunção é um tipo de comando que no fluxo lógico do programa é executado e o controle passa para o próximo comando na sequência A análise da complexidade neste caso envolve a aplicação da regra da soma para a notação O com base na complexidade dos comandos 2 Seleção ou disjunção é um tipo de comando que no fluxo de execução permite que desvios possam ser feitos a partir do resultado da avaliação de uma condição executando um bloco de comandos e outros não A análise sempre é feita considerando o pior caso Consequentemen te na avaliação da complexidade é considerado o desvio que envolve a execução do bloco de comandos mais custoso a partir da avaliação da condição Adicionalmente a avaliação da condição consome tempo constante 3 Repetição é um tipo de comando que no fluxo de execução do programa permite que um bloco de comandos seja repetido enquanto uma condição é satisfeita Além da checagem da condição O1 o custo de um comando de re petição envolve o custo do bloco envolvido multiplicado pelo número de vezes que será executado no pior caso Vale ressaltar que pode existir aninhamento de comandos de repetição Neste caso a análise é feita de dentro para fora O laço pode ser definido for ou indefinido while 4 Um comando de atribuição possibilita que um valor possa ser atribuído a uma variável Um comando de atribuição consome tempo constante MARIELA INÉS CORTÉS 20 Para refletir Por exemplo dado um vetor v de números inteiros de tamanho n retornar o maior elemento deste vetor 1 int Maximo int v int n 2 int i n 3 int max 4 5 if n 0 printf Vetor vazio 6 else 7 max v0 8 for i 1 i n i 9 if vi maxmax vi 10 11 return max 12 O número n de elementos do vetor representa o tamanho da entrada O programa contém um comando de iteração 8 que contém um comando de desição que por sua vez contém apenas um comando de atribuição 9 O comando de atribuição requer tempo constante O1 para ser executado assim como a avaliação do comando de desição Considerando o pior caso o comando de atribuição sempre será executado O tempo para incrementar o índice do laço e avaliar sua condição de terminação também é O1 e o tempo combinado para executar uma vez o laço composto pelas linhas 8 e 9 é Omax1 1 O1 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ão o tempo gasto no laço 8 é On 1 x 1 On 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 O1 Por outro lado utilizando a regra da soma no vamente temos que a execução das linhas 7 8 e 9 consome Omax1 n 1 On 1 No pior caso temos que a execução do bloco 5 consome On 1 Finalmente o comando 11 é executado em tempo O1 Aplicando novamente a regra da soma entre 5 e 11 temos que Omaxn 1 1 On 1 Portanto a complexidade temporal do algoritmo Maximo é linear Simplificando a análise a quantidade de trabalho do algoritmo pode ser determinada pela quantidade de execuções da operação fundamental Estrutura de Dados 21 No entanto pode existir mais de uma operação fundamental com pesos di ferentes Neste caso a regra de soma para a notação O pode ser aplicada Para refletir Considere o algoritmo buscaBinaria descrito a seguir 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 arraymeio return meio else if chave arraymeio sup meio 1 else inf meio 1 return 1 não encontrado 1 Descreva o funcionamento do algoritmo buscaBinaria Qual situação re presenta o pior caso e o melhor 2 Considerando a execução do algoritmo buscaBinaria em um vetor com 15 elementos quantas repetições número de passos são necessários para o algoritmo detectar que uma determinada chave de busca não se encontra no vetor 3 Determine a complexidade temporal do algoritmo buscaBinaria analisan do passoapasso a complexidade de cada comando Síntese do capítulo Neste capítulo foi apresentado um estudo introdutório sobre os fundamentos da teoria sobre complexidade de algoritmos Esta teoria é de fundamental importância uma vez que possibilita determinar a melhor solução para um determinado tipo de problema assim como também elaborar projetos de algoritmos cada vez mais eficientes MARIELA INÉS CORTÉS 22 Referências CORMEN T H LEISERSON C E RIVEST R L STEIN C 2001 Intro duction to Algorithms McGrawHill e The Mit Press KNUTH D E 1968 The Art of Computer Programming Vol 1 Funda mental Algorithms AddisonWesley KNUTH D E 1971 Mathematical Analysis of Algorithms Procedings IFIP Congress 71 vol 1 North Holland 135143 WIRTH N 1986 Algorithms and Data Strutures PrenticeHall ZIVIANI N 2005 Projeto de Algoritmos com implementações em Pas cal e C 2da Edição Thomson Capítulo 3 Listas Estrutura de Dados 25 Objetivos Neste capítulo é descrito o processo de abstração seguindo para a mode lagem e desenvolvimento de uma solução computacional a partir de um problema do mundo real Neste contexto os conceitos de tipos de dados estruturas e tipos abstratos são introduzidos ressaltando sua importância para a adequada modelagem manipulação e representação na memória do computador 1Modelagem Conceitual Para que um problema do mundo real possa ser resolvido computacional mente é necessário utilizar métodos e técnicas que possibilitem a modelagem adequada do problema de forma que possa ser interpretado e processado pelo computador para gerar uma solução Os modelos são utilizados para representar o mundo real de forma simpli ficada com o objetivo de facilitar o gerenciamento da complexidade Um mode lo reflete os aspectos considerados importantes para o desenvolvimento da apli cação deixando em um segundo plano os aspectos que não são relevantes A modelagem de situações do mundo real é alcançada através de um processo de abstração a partir do qual somente as propriedades relevantes para a aplicação são consideradas no modelo Figura 1 MARIELA INÉS CORTÉS 26 O processo de abstração envolve a observação das entidades pre sentes no domínio do problema para a correspondente representação no domínio computacional No nível mais baixo de abstração a representação dos dados a nível de máquina acontece de acordo a padrões de bits5 e bytes de memória No en tanto as linguagens de programação modernas possibilitam que o programa dor possa trabalhar com objetos relativamente complexos em um nível mais alto de abstração tornando transparente ao desenvolvedor a manipulação dos dados ao nível da sua representação interna no computador Esta facili dade é alcançada através da utilização de uma variedade de tipos de dados 2 Tipo de dados O tipo de dados associado a uma variável numa linguagem de programação define o conjunto de valores que a variável pode assumir Isto é a declaração da variável como sendo de um tipo específico determina 1 A quantidade de bits que devem ser reservados na memória 2 Como o dado representado por esse padrão de bits deve ser interpretado pe uma cadeia de bits pode ser interpretada como sendo um inteiro ou real Os tipos têm geralmente associações com valores na memória ou va riáveis Consequentemente tipos de dados podem ser vistos como métodos para interpretar o conteúdo da memória do computador o que pode variar conforme o sistema operacional e a linguagem de implementação Na sua maioria as linguagens de programação exigem que um comando declarativo que define uma variável especifique também o tipo de dados associado à variável Es tas linguagens são chamadas de fortemente tipadas Em contrapartida as linguagens fracamente tipadas permitem que a definição do tipo correspondente a uma variável possa ser determinada dinamicamente em tempo de execução Os tipos de dados podem ser classificados em dois grupos primitivos ou básicos e compostos ou estruturados Os tipos de dados primitivos são fornecidos pela linguagem de progra mação como um bloco de construção básico Dependendo da implementa ção da linguagem os tipos primitivos podem ou não possuir correpondência direta com objetos na memória6 Exemplos de tipos primitivos comuns são inteiro real caractere booleano dentre outros Além de estabelecer um esquema predeterminado de armazenamento a definição de um tipo de dados primitivo estabelece também um conjunto de operações predefinidas sobre aquele tipo Consequentemente a definição 5 Bit significa dígito binário do ingles BInary digiT Um bit é a menor unidade de informação que pode ser armazenada ou transmitida Um bit pode assumir somente 2 valores 0 ou 1 verdadeiro ou falso O conjunto de 8 bits é denominado de Byte O sistema operacional SO é um programa ou conjunto de programas responsável por gerenciar todos os recursos do sistema tais como comandos do usuário arquivos memória etc 6 A memória é o dispositivo que permite a um computador armazenar dados de forma temporária ou permanente Estrutura de Dados 27 de uma variável como instância de um desses tipos determina o conjunto de operações que podem ser realizadas utilizando essas variáveis Por exemplo ao considerar variáveis do tipo primitivo inteiro int as operações permitidas se traduzem nos operadores aritméticos válidos para os valores desse tipo no caso soma subtração multiplicação divisão inteira DIV e resto da divisão inteira MOD Estas operações são implementadas de forma nativa por qualquer linguagem de programação e seu desenvolvimento fica trans parente ao usuário Dada a complexidade das entidades do domínio do problema a serem modeladas e representadas no universo computacional o fosso semântico7 gap semântico envolvendo a descrição de alto nível de uma entidade do mínio do problema e a descrição de baixo nível domínio da solução pode ser inconciliável Neste contexto a possibilidade de definir tipos de dados que possibilitem a representação destas entidades de forma mais próxima da rea lidade facilita o processo de abstração assim como contribui para a redução do fosso semântico entre ambos os domínios O programador pode definir tipos de dados próprios que mais corres pondam às necessidades de suas aplicações Linguagens de programação atuais permitem aos programadores definir tipos de dados adicionais utilizan do os tipos primitivos e as estruturas como blocos construtivos Por exemplo para definir a variável Empregado com esta estrutura heterogênea em C seria struct Empregado char Nome9 int Idade float Qualificação No entanto se a estrutura for muito frequente o programa pode ficar vo lumoso e difícil de ser lido O método mais adequado consiste em descrever a estrutura de dados correspondente uma única vez associandoa a um nome descritivo e utilizar esse nome todas as vezes que for necessário typedef struct char Nome9 int Idade float Qualificação TipoEmpregado 7 O fosso semântico representa a diferença entre uma descrição de alto nível e outra de baixo nível relativa a uma mesma entidade MARIELA INÉS CORTÉS 28 Esta declaração define um novo tipo denominado TipoEmpregado que pode ser usado para declarar variáveis da mesma forma como um tipo primitivo TipoEmpregado Empregado A partir desta definição é possível gerar as correspondentes variá veis instância as quais irão assumir valores nos atributos dependendo do tipo Por exemplo valores válidos para uma variável do tipo Empregado podem ser Nome João Soares Idade 25 anos Qualificação 858 Um tipo definido pelo usuário é essencialmente um modelo 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 uma ocorrência real deste tipo A forma conceitual dos dados é materializada pela estrutura de dados utilizada na implementação do tipo Uma estrutura de dados é uma forma par ticular de se implementar um tipo e é construída dos tipos primitivos eou compostos de uma linguagem de programação e por este motivo são chama dos de tipos compostos ou estruturados Um tipo composto envolve um conjunto de campos e membros orga nizados de forma coerente onde o tamanho total da estrutura corresponde à soma dos tamanhos dos campos constituintes Exemplos de tipos estrutura dos são registros vetores matrizes arquivos árvores dentre outros A escolha por uma estrutura de dados é determinante na qualidade e esforço requerido para o desenvolvimento da solução As estruturas de da dos e algoritmos são escolhidos com base em critérios diversos tais como desempenho restrições de plataforma de hardware e software capacidade do equipamento volume de dados etc As estruturas de dados dividemse em homogêneas e heterogêneos As estruturas homogêneas são conjuntos de dados formados por componentes do mesmo tipo de dado pe vetores matrizes pilhas listas etc Em contrapartida as estruturas heterogêneas são conjuntos de dados formados por componentes pertencentes a tipos de dados diferentes pe registros A escolha de uma estrutura de dados apro priada pode tornar um problema complicado em uma solução bastante trivial Diferentemente do que acontece na definição de tipos de dados básicos onde um conjunto de operações de manipulação é fornecido pela linguagem de progamação soma subtração no caso dos tipos estruturados definidos Estrutura de Dados 29 pelo usuário apenas novos esquemas de armazenamento são definidos Isto significa que a principio não são fornecidos meios para definir as operações a serem executadas sobre instâncias de tais estruturas Consequentemente algoritmos de manipulação precisam ser desenvolvidos de forma a possibilitar a correta utilização e acesso às novas estruturas definidas Para refletir 1 Defina os conceitos de tipo de dado básico e tipo de dado definido pelo usuário 2 Cite como exemplos tipos de dados básicos que você conhece e detalhe suas carac terísticas e as operações permitidas sobre esses tipos 3 Defina um tipo de dado estruturado que descreva de forma adequada e completa as seguintes informações a Livro b Círculo c Filme d Pessoa e Aluno f Item de estoque g Conta bancaria 3 Tipo abstratos de dados Um tipo de dado definido pelo usuário incrementado com a definição e im plementação das operações necessárias para a sua manipulação constitui um Tipo Abstrato de Dados TAD conceito central no contexto do Paradigma Orientado a Objetos8 A utilização de TADs permite que linguagens de progra mação de propósito geral sejam personalizadas para um domínio de aplicação mais específico Uma vez definidos podem ser empregados como primitivas da linguagem e possibilitam o desenvolvimento de componentes de software reusáveis e extensíveis TADs estendem a noção de tipo de dado estrutura de dados ope rações com base na utilização de técnicas de ocultamento da informação referente à estrutura de dados utilizada e à implementação das operações definidas Este objetivo é alcançado através de uma clara separação entre interface e implementação A seguir é apresentado como exemplo a definição do tipo abstrato Retângulo Um retângulo pode ser definido pela sua largura e altura A especi ficação do tipo retângulo pode ser definida como typedef struct float altura largura TipoRetangulo 8 O paradigma orientado a objetos envolve um conjunto de técnicas métodos e ferramentas para análise projeto e implementação de sistemas de software baseado na composição e interação de componentes de software denominados de objetos MARIELA INÉS CORTÉS 30 A partir destas informações é possível calcular sua área e perímetro Portanto além 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ções de manipulação inicia valores do retangulo void iniciaretangulo 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 calcula o valor do perímetro float Perimetro calcula o valor da área float Area protótipos das operações Finalmente todos os métodos implementados na linguagem de progra mação Exemplos da implementação de alguns dos métodos são apresenta dos a seguir void iniciaretangulo float a float l altura a largura l float Altura return altura O construtor é um método distinguido que tem como função principal a de instanciar o objeto corretamente para seu uso posterior Protótipos na linguagem C define o cabeçalho das funções Estrutura de Dados 31 float Perimetro return 2 altura largura O projeto9 de um tipo abstrato é uma tarefa difícil pois este deve ser idealizado de forma a possibilitar a sua utilização por parte de terceiros favorecendo o reuso e agilizando o processo de desenvolvimento de sof tware A atividade de projeto envolve a escolha de operações adequadas delineando seu comportamento consistente de forma que estas possam ser combinadas para realizar funções mais complexas a partir de opera ções simples No intuito de aumentar o reuso das operações estas devem ser de finidas de forma coesa e ter um comportamento coerente com um pro pósito específico e evitando considerar diversos casos especiais em um mesmo código O conjunto de operações que integram a interface do TAD deve ofere cer todas as operações necessárias para que os usuários possam manipular a estrutura adequadamente Um bom teste consiste em checar se todas as propriedades do objeto de um determinado tipo podem ser acessadas A escolha pela representação mais adequada ao problema envolve uma análise aprofundada uma vez que cada representação possível possui diferentes vantagens e desvantagens Para refletir 1 Defina os conceitos de Tipo Abstrato de Dados Estabeleça o relacionamento que vincula ambos conceitos 2 Defina TADs para os tipos de dados estruturados para as entidades listadas a seguir especi ficando detalhadamente a interface completa A interface deve incluir todas as operações necessárias para a correta manipulação do tipo dentre elas os métodos de inicialização modificação e consulta a Livro b Círculo c Filme d Pessoa e Aluno f Item de estoque g Conta bancária 3 Implemente dois TADs do exercício anterior utilizando a linguagem de programação da sua escolha ou pseudocódigo próximo da linguagem 9 A fase de projeto produz uma descrição computacional do que o software deve fazer e deve ser coerente com as especificações geradas na análise de acordo com os recursos tecnológicos existentes MARIELA INÉS CORTÉS 32 4 Critérios para a escolha da estrutura de dados adequada Como dito anteriormente a interface do TAD independe da implementação e portanto diferentes estruturas de dados podem ser utilizadas como esquema de armazenamento na memória10 para seus atributos A partir do esquema utilizado os dados podem ser armazenados e recuperados A forma em que a alocação de memória acontece pode ser um fator determinante para a escolha de uma determinada estrutura de dados 41 Uso da memória Informalmente podemos dizer que existem três maneiras de reservarmos es paço de memória para o armazenamento de informações Uso de variáveis globais e estáticas O espaço reservado para uma vari ável global existe enquanto o programa estiver sendo executado Uso de variáveis locais Neste caso o espaço fica reservado apenas en quanto a função que declarou a variável está sendo executada sendo liberado para outros usos quando a execução da função termina Por este motivo a função que chama não pode fazer referência ao espaço local da função chamada As variáveis globais ou locais podem ser simples ou vetores sendo que no caso dos vetores é preciso informar o número má ximo de elementos ou tamanho do vetor A partir do tamanho informado o compilador reserva o espaço correspondente Requisições ao sistema em tempo de execução Este espaço alocado dinamicamente permanece reservado até que explicitamente seja libera do pelo programa Uma vez que o espaço é liberado fica disponível para outros usos Se o espaço alocado não for liberado explicitamente pelo programa este será automaticamente liberado quando a sua execução terminar A seguir é ilustrada esquematicamente a alocação da memória pelo sistema operacional 10 A memória é o dispositivo que permite a um computador guardar dados de forma temporária ou permanente Estrutura de Dados 33 Quando requisitamos ao siste ma operacional para executar um determinado programa o código em linguagem de máqui na do programa deve ser carre gado na memória O sistema operacional reserva também o espaço necessário para arma zenarmos as variáveis globais e estáticas utilizadas ao longo do programa O restante da me mória é utilizado pelas variáveis locais e pelas variáveis aloca das dinamicamente 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 pertence à pilha de execução e quando a função termina é desempilhado e liberado A parte da memória não ocupada pela pilha de execução pode ser requisitada dinamicamente Se ao longo de diversas chamadas a função a pilha cresce atingindo o espaço disponível existente dizemos que ela estourou e o programa é abor tado com erro Similarmente se o espaço de memó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 exemplo podemos imprimir a mensagem Memória insuficiente e interromper a execução do programa Como mencionado anteriormente a alocação de memória pode acon tecer em tempo de compilação estática ou em tempo de execução dinâmi ca No caso da alocação de memória em forma estática o espaço destinado para o armazenamento dos dados possui um tamanho fixo que não pode ser modificado ao longo da execução do programa Adicionalmente a alocação de memória acontece em espaços contí guos isto é um do lado do outro Exemplos de alocação estática de memória são variáveis globais e vetores No caso do vetor a partir de certo endereço ε que armazena o primeiro elemento a1 do vetor os elementos subsequentes podem ser acessados diretamente incrementando em k o endereço inicial do vetor onde k é o tamanho de memória ocupado por cada elemento do vetor Figura 2 MARIELA INÉS CORTÉS 34 Figura 3 Em contrapartida no caso de alocação dinâmica a memória é geren ciada sob demanda ou seja os espaços de memória são alocados e de salocados dependendo da necessidade durante a execução do programa Consequentemente a alocação não acontece necessariamente de forma contígua ou sequencial podendo os dados ficarem esparsos na memória do computador A partir desta configuração onde os dados são armazenados de forma não sequencial o acesso é alcançado através de variáveis do tipo ponteiro11 indicando o endereço de memória correspondente A seguir é ilustrada esquematicamente a distribuição dos elementos in tegrantes de uma cadeia ao longo da memória Na primeira coluna é indicado o endereço correspondente ao conteúdo A coluna ponteiro indica o endereço do próximo elemento na cadeia Note que o segundo elemento não ocupa o endereço consecutivo ao a1 Endereço Conteúdo Ponteiro Observação L3FFB a1 1D34 Primeiro elemento acessado a partir de L 1D34 a2 BD2F BD2F a3 AC13 1500 an2 16F7 16F7 an1 5D4A 5D4A an null Último elemento da cadeia O endereço null indica que o elemento não tem sucessor A partir das características de cada uma das abordagens para a aloca ção dos dados vantagens e desvantagens podem ser estabelecidas Alocação estática Vantagem Possibilita acesso direto ao local da memória uma vez que os dados se encontram armazenados de forma contígua ou sequencial Consequentemente em alguns casos as operações de busca podem ter custo constante O1 Desvantagem É preciso determinar em tempo de codificação quanto es paço é necessário Esta estimativa pode ser difícil de ser estabelecida 11 O ponteiro ou apontador é um tipo de dado que armazena o endereço de um outro dado A partir do ponteiro o dado que se encontra no respectivo endereço pode ser acessado e manipulado Estrutura de Dados 35 e está sujeita a flutuações ao longo da execução Consequentemente o espaço pode resultar insuficiente ou pode ter sido sobreestimado Por outro lado a alocação sequencial na memória prejudica as operações de inserção e remoção uma vez que a sequencialidade dos dados precisa ser preservada Com isso no pior caso o custo destas operações pode ser de On por conta dos deslocamentos necessários para abrir ou fe char espaços para inserção e remoção respectivamente Alocação dinâmica Vantagem não é necessário fixar o tamanho da estrutura a priori uma vez que a alocação de memória é feita sob demanda em tempo de execução Com isso é evitado o desperdício de espaço e o risco de ficar sem espaço é reduzido Consequentemente não existe restrição encima do número de inserções e remoçõ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 elementos se encontram esparsos na memória Desvantagem o gerenciamento dos dados diretamente da memória pode ser trabalhoso e propenso a erros Como conseqüência da não linearida de na alocação dos dados o acesso a um determinado elemento i tor na necessário o percurso pelos i 1 elementos anteriores na sequência Esta propriedade que caracteriza o acesso sequencial aos dados torna a operação de busca por um elemento de custo On Síntese do capítulo Neste capítulo foi apresentado o conceito de abstração e seus níveis e a sua importância no processo de modelagem Tipos de dados básicos e estrutura dos foram definidos neste contexto como meios de representar e interpretar as informações manipuladas pela aplicação Adicionalmente o conceito de tipo abstrato é estabelecido como um mecanismo de extensão e customiza ção de linguagens de programação no intuito de facilitar o desenvolvimento de sistemas TADs são caracterizados por suas operações as quais são en capsuladas junto à sua estrutura sendo acessíveis exclusivamente através da interface especificada garantindo independência da implementação utilizada A independência de representação torna possível alterar a representação de um tipo sem que seus clientes sejam afetados Finalmente noções de gerên cia de memória foram introduzidas focando nas principais características que influenciam na escolha pela alocação estática ou dinâmica da memória Uma análise dos fatores que contribuem na tomada de decisão foi apresentada MARIELA INÉS CORTÉS 36 Referências CORMEN T H LEISERSON C E RIVEST R L STEIN C 2001 Intro duction to Algorithms McGrawHill e The Mit Press TENENBAUM A M LANGSAM Y AUGENSTEIN M J 1995 Estrutu ras de Dados Usando C Makron BooksPearson Education WIRTH N 1986 Algorithms and Data Structures PrenticeHall ZIVIANI N 2005 Projeto de Algoritmos com implementações em Pas cal e C 2da Edição Thomson Listas 31 Introducción a las listas Una lista es una colección ordenada de objetos Estos objetos pueden ser números letras palabras o incluso otras listas Las listas se utilizan comúnmente en programación para almacenar y manipular conjuntos de datos relacionados En Python las listas se crean utilizando corchetes y los elementos se separan por comas Ejemplo milista 1 2 3 4 5 32 Acceder a los elementos de una lista Para acceder a un elemento específico de una lista utilizamos su índice Los índices en Python comienzan en 0 por lo que el primer elemento tiene índice 0 el segundo índice 1 y así sucesivamente Ejemplo primerelemento milista0 printprimerelemento Salida 1 33 Modificar elementos de una lista Podemos modificar un elemento de la lista asignando un nuevo valor a su índice correspondiente Ejemplo milista2 10 printmilista Salida 1 2 10 4 5 34 Añadir elementos a una lista Para añadir elementos a una lista podemos usar el método append para agregar un solo elemento al final de la lista Ejemplo milistaappend6 printmilista Salida 1 2 10 4 5 6 También podemos usar insert para añadir un elemento en una posición específica Ejemplo milistainsert1 15 printmilista Salida 1 15 2 10 4 5 6 35 Eliminar elementos de una lista Para eliminar elementos de una lista podemos usar el método remove para eliminar la primera aparición de un valor específico Ejemplo milistaremove10 printmilista Salida 1 15 2 4 5 6 También podemos usar del para eliminar un elemento en un índice específico Ejemplo del milista1 printmilista Salida 1 2 4 5 6 36 Recorrer una lista Podemos recorrer una lista utilizando un bucle for para acceder a cada elemento de la lista Ejemplo for elemento in milista printelemento 37 Operaciones comunes con listas Longitud de la lista lenmilista devuelve el número de elementos en la lista Concatenar listas lista1 lista2 crea una nueva lista que contiene los elementos de lista1 seguidos por los de lista2 Repetir listas lista n crea una nueva lista que repite los elementos de la lista original n veces 38 Listas anidadas Las listas pueden contener otras listas como elementos creando listas anidadas Esto permite representar estructuras más complejas como matrices Ejemplo matriz 1 2 3 4 5 6 printmatriz01 Salida 2 Estrutura de Dados 39 Objetivos Existem certas estruturas clássicas que se comportam como padrões uma vez que são utilizadas na prática em diversos domínios de aplica ção Neste capítulo é apresentada a estrutura de dados Lista e o corres pondente Tipo Abstrato detalhando a sua interface e apresentando duas implementações vetores e ponteiros Variantes do tipo abstrato listas na forma de Pilhas e Filas de ampla utilização prática são descritas Introdução Um conjunto de elementos pode ser intuitivamente representado através de uma lista linear Listas são estruturas extremamente flexíveis que possibilitam uma ampla manipulação das informações uma vez que inserções e remoções podem acontecer em qualquer posição Uma lista pode ser definida como uma estrutura linear12 finita cuja or dem é dada a partir da inserção dos seus elementos componentes As listas são estruturas compostas constituídas por dados de forma a preservar a re lação de ordem linear entre eles Cada elemento na lista pode ser um dado primitivo ou arbitrariamente complexo Em geral uma lista segue a forma a1 a2 a3 an onde n determina o tamanho da lista Quando n 0 a lista é chamada nula ou vazia Para toda lista exceto a nula ai l segue ou sucede ai i n e ai 1 precede ai i 1 O primeiro elemento da lista é a1 e o último an A posição correspondente ao elemento ai na lista é i A lista pode ser representada visualizandose um vetor por exemplo As características básicas da estrutura de dados lista são as seguintes Homogênea Todos os elementos da lista são do mesmo tipo A ordem nos elementos é decorrente da sua estrutura linear no entanto os elementos não estão ordenados pelo seu conteúdo mas pela posição ocupada a partir da sua inserção Para cada elemento existe anterior e seguinte exceto o primeiro que não possui anterior e o último que não possui seguinte É possível acessar e consultar qualquer elemento na lista É possível inserir e remover elementos em qualquer posição 12 Uma estrutura é dita de linear uma vez que seus elementos componentes se encontram organizados de forma que todos a exceção do primeiro e último possuem um elemento anterior e um posterior somente MARIELA INÉS CORTÉS 40 1 Definição do TAD Lista Como apresentado na parte anterior a definição de um Tipo Abstrato de Dados TAD envolve a especificação da interface de acesso para a mani pulação adequada da estrutura a partir da qual são definidas em detalhe as operações permitidas e os parâmetros requeridos O conjunto de operações depende fortemente das características de cada aplicação no entanto é pos sível definir um conjunto de operações mínimo necessário e comum a todas as aplicações Interface do TAD Lista Cria uma lista vazia Lista Criar insere numa dada posição na lista int Inserir Lista l tipobase dado corrente pos Retorna o elemento de uma dada posição tipobase 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 tipobase dado Estrutura de Dados 41 Uma vez definida a interface esta pode ser implementada utilizando uma representação dos dados adequada Existindo mais de uma estrutura adequada a escolha depende principalmente das necessidades e caracterís ticas dos dados a serem manipulados pela aplicação A seguir o Tipo Abstrato Lista é implementado utilizando duas estruturas de dados comumente utilizadas e adequadas às necessidades cada uma com vantagens e desvantagens particulares 11 Implementação do TAD Lista usando alocação estática Na implementação de lista adotando alocação de memória estática os ele mentos componentes são organizados em posições contíguas de memória utilizando arranjos ou vetores Vantagens e desvantagens desta estrutura foram discutidas na parte 3 Em particular a utilização de vetores se torna adequada no caso em que exis te uma clara noção do tamanho da entrada a ser processada e uma perspec tiva que indica que as aplicações que irão utilizar o TAD não estarão execu tando muitas operações de inserção e remoção que possam vir a alterar sig nificativamente o tamanho preestabelecido A estruturação da lista utilizando alocação estática é apresentada graficamente a seguir Note que a partir do endereço correspondente ao primeiro elemento no vetor pos e conhecendo o tamanho c de cada componente na lista é possível calcular o endereço na memória de qualquer elemento armazenado no vetor Isso garante o acesso direto aos elemento em O1 A seguir é apresentada a definição da estrutura de dados e implemen tação13 das operações definidas na interface utilizando alocação estática de memória através da definição de vetores Considerando a utilização de aloca ção estática de memória o tamanho da estrutura de dados precisa ser deter minado em tempo de compilação define tamanho Como o protótipo da lista é definido de modo a ser implementado usando vetor ou outro recurso tornase necessário definir um tipo que possa ser utiliza do como elemento que é acessado nas operações ou corrente No caso desta implementação inicial utilizando vetor os elementos são acessados através de 13 A notação utilizada na implementação é próxima à linguagem C MARIELA INÉS CORTÉS 42 suas posições no vetor sendo que estas posições são representadas como in teriores que iniciam em 0 zero na primeira posição e seguem até n1 tamanho do vetor 1 Portanto tornase necessário definir o tipo corrente como inteiro typedef int corrente Uma lista é um tipo de dado que estrutura elementos cujo tipo pode ser arbitrariamente complexo envolvendo inclusive a utilização de outros TADs A definição a seguir especifica o tipo base dos elementos da lista como inteiros typedef int tipobase Os elementos da lista são organizados em um vetor de tamanho pre definido Adicionalmente um atributo contendo a quantidade de elementos da lista quantElem é incluído na estrutura no intuito de tornar mais fácil e ágil o acesso aos elementos e possibilitar o controle do crescimento da estrutura typedef struct tipobase vtamanho int quantElem noLista 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 do primeiro elemento da lista é possível calcular o endereço do último elemento e consequentemente da primeira posição disponível Isto é possível por conta da propriedade de armazenamento contíguo propiciada pela estrutura de dados Finalmente a lista é definida como um ponteiro à estrutura de dados onde os elementos são agregados typedef noLista Lista A criação de uma lista inicialmente vazia envolve a definição do ponteiro correspondente apontando a um endereço de memória reservado com tama nho adequado para o armazenamento da estrutura em particular o primeiro nó representando a cabeça da lista O tamanho da lista é inicializado em zero uma vez que inicialmente não contém elementos Lista Criar Lista l Lista malloc sizeof noLista if l NULL l quantElem 0 return l Na linguagem C a posição que corresponde ao primeiro elemento do vetor corresponde ao índice i 0 Em outras linguagens como por exemplo Pascal o primeiro elemento no vetor se encontra na posição i1 Estrutura de Dados 43 else printf Não existe memória suficiente return Normalmente a lista precisa ser percorrida de forma a realizar algum tipo de processamento sobre os dados que a compõem Consequentemente se torna necessário um mecanismo que possibilite checar no momento em que não seja possível processar mais nenhum elemento O método ultimoEle mento é responsável por fazer esta checagem int ultimoElemento Lista l corrente pos if pos 1 l quantelem return 1 else return 0 A execução de uma operação de remoção requer a existencia de no mínimo um elemento na lista A função Vazia é utilizada para informar se há elementos no vetor retorna o valor 1 no caso da lista se encontrar vazia e 0 em caso contrário int Vazia Lista l if l quantElem 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 pode inviabilizar a inserção de um novo elemento Este método é de fundamental 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 estouro da memória fazendo com que o programa termine com erro int Cheia Lista l if l quantElem tamanho return 1 else return 0 Uma função que pode ser definida para auxiliar a verificação de pró ximo elemento e a inserção é uma função vailadPos Esta recebe a lista e a posição atual e verifica se a posição é maior ou igual a zero e se a posição é maior que a quantidade de elementos 1 MARIELA INÉS CORTÉS 44 int validaPosLista l corrente pos ifpos 0pos l quantElem 1 return 1 else return 0 Adicionalmente o percurso ao longo dos elementos de uma lista re quer de uma operação que possibilite a movimentação ao longo da estrutura elemento a elemento A função proximoElemento 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 validaPosl pos return pos return 1 A operação de inserção é possivelmente uma das mais importantes uma vez que é através dela que a lista será construída Em particular o tipo lista não possui nenhuma restrição em relação à inserção podendo acontecer em qualquer posição Desta forma na hora de inserir um ele mento na lista é necessário informar qual a posição correspondente ao novo elemento seja no inicio meio ou fim da lista Considerando que a inserção nem sempre é possível por conta da limitação de espaço da es trutura de dados utilizada a função retorna 1 se a inserção foi realizada com sucesso e 0 em caso contrário Algoritmo 0 int Inserir Lista l tipobase dado corrente pos int i if validaPosl pos cheia l return 0 for i l quantelem i pos i l vi l vi1 Estrutura de Dados 45 l vpos dado l quantelem l quantelem1 return 1 Dependendo da posição onde o elemento será inserido o trabalho re querido pode ser estimado de forma a estabelecer o custo da função Pelo fato de se utilizar alocação estática e contígua de memória para o armazenamento 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 Para isso é necessário deslocar shift todos os elementos necessários desde a posição requerida até o final da lista Por exemplo se a lista possui 5 elementos e o novo elemento precisa ser inserido na posição 3 os últimos 3 elementos precisarão ser deslocados à direita para que a posição de inser ção requerida fique disponível para o novo elemento a ser inserido A situação é ilustrada na figura a seguir Figura 5 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 da lista em uma posição à direita Nete caso o custo requerido é On Analogamente à operação de inserção a operação de remoção exclui um elemento em qualquer posição portanto esta posição precisa ser informa da explicitamente O algoritmo é responsável por checar se a posição informa da representa uma posição válida dentro da estrutura Algoritmo 01 int Remover Lista l corrente pos int i if vazial validaPosl return 0 MARIELA INÉS CORTÉS 46 int dado l vpos for i pos 1 i l quantelem i l vi1 l vi l quantelem l quantelem1 return 1 Figura 6 Realizando uma análise análoga ao caso da inserção o custo para a remoção é On No caso em que seja necessário remover um elemento de acordo com algum conteúdo específico o elemento em questão precisa ser previamente localizado através da operação de Busca A partir da posição retornada pela busca caso o elemento seja efetivamente encontrado na estrutura a remo ção poderá ser efetivamente realizada A busca por um determinado elemento pode ser originada de duas for mas Na primeira variante a busca pode ser orientada por um determinado conteúdo retornando como resultado a sua posição na lista no caso em que o elemento for efetivamente encontrado caso contrário retorna 1 corrente Busca Lista l tipobase dado int i for i 0 i tamanhol i if l vi dado return i return 1 O pior caso possível para esta busca consiste na situação onde o ele mento procurado não se encontra na lista Nesta situação a lista será percorri da na totalidade sem sucesso passando pelos n elementos que determinam seu tamanho Consequentemente o custo desta operação no seu pior caso é On ou seja linear Estrutura de Dados 47 Na segunda variante a busca pode acontecer a partir de uma determi nada posição na lista retornando o elemento contido nessa posição tipobase Consulta Lista l corrente pos return l vpos1 A complexidade da busca neste caso é O1 uma vez que consiste no aces so direto à posição correspondente demandando para isso tempo constante Para refletir 1 Considerando a implementação do TAD utilizando alocação estática de memória resolva as questões a seguir a Explique por que o custo da remoção em uma lista implementada utilizando aloca ção estática e contígua de memória é On b Implemente a operação que retorna a quantidade de elementos na lista cujo ca beçalho é int tamanho lista l Determine a complexidade da operação implemen tada c Implemente o método auxiliar que verifique se uma determinada posição é válida isto é se encontra dentro dos limites do vetor O cabeçalho da operação é int vali daPos corrente pos 12 Implementação do TAD Lista usando alocação dinâmica Na implementação do Tipo Abstrato lista adotando alocação de memória di nâmica a alocação de memória é gerenciada sob demanda em tempo de execução Esta característica determina que os elementos componentes são organizados em posições nãocontíguas ficando espalhados ao longo da memória Consequentemente não é preciso estimar a priori o tamanho da estrutura uma vez que o espaço é alocado na medida da necessidade depen dendo das operações de inserção e remoção realizadas Vantagens e desvantagens desta estrutura foram discutidas na Parte 3 Em particular esta estrutura se torna adequada quando o tamanho da estrutura é desconhecido e pode variar de forma imprevisível No entanto a gerência da memória torna a implementação mais trabalhosa e propensa a erros podendo acarretar em perda de informação Adicionalmente o aces so aos dados é seqüencial no sentido que para acessar o elemento na po sição m se torna necessário percorrer os m 1 elementos anteriores Com isso no pior caso a busca por um elemento na lista demanda custo On A seguir é apresentada a definição da estrutura de dados e imple mentação das operações definidas na interface para o TAD Lista utilizando alocação dinâmica de memória através de ponteiros A notação utilizada na MARIELA INÉS CORTÉS 48 implementação é próxima à linguagem C Esta estrutura representa uma seqüência de elementos encadeados por ponteiros ou seja cada elemento deve conter além do dado propriamente dito uma referência para o próximo elemento da lista Graficamente a estrutura de dados para a implementação de listas utilizando ponteiros é a seguinte Por exemplo uma lista com valores de ponteiros a endereços reais tem a seguinte forma Figura 7 O espaço total de memória gasto pela estrutura é proporcional ao número de elementos nela armazenados para cada novo elemento in serido na estrutura é alocado um espaço de memória para armazenálo Consequentemente 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 acesso direto aos elementos da lista Isto implica que para percorrer todos os elementos da lista devemos explicitamente seguir o encadeamen to dos elementos Para isto é preciso definir a estrutura do nó como uma estrutura autoreferenciada contendo além do conteúdo de informação um ponteiro ao próximo elemento na sequência As definições a seguir imple mentam a estrutura correspondente typedef struct node noptr struct node tipobase elemento noptr prox Finalmente a lista é definida como um ponteiro ao primeiro nó da lista a partir do qual a sequência de nós é encadeada typedef noPTR Lista Estrutura de Dados 49 Uma lista é um tipo de dado que estrutura elementos cujo tipo pode ser arbitrariamente complexo envolvendo inclusive a utilização de outros TADs A definição a seguir especifica o tipo base dos elementos da lista como inteiros typedef int tipobase A implementação de listas com ponteiros requer um cuidado especial uma vez que qualquer erro na manipulação dos ponteiros pode acarretar em perda parcial ou total da lista de elementos Assim sendo a utilização de um ponteiro auxiliar para o percurso ao longo da lista pode ser de grande utilidade Com esse objetivo definimos um tipo Corrente a ser utilizado como cópia da lista de forma a possibilitar a sua manipulação com segurança typedef noptr Corrente A função que cria uma lista vazia utilizando alocação dinâmica de me mória é apresentada a seguir A função tem como valor de retorno a lista vazia inicializada isto é o valor de retorno é NULL pois não existem ele mentos na lista Lista Criar return NULL O método Inicializar posiciona o índice da posição corrente no inicio da lista Desta forma o ponteiro pos aponta para o mesmo local onde se encontra o primeiro elemento da lista Este método é útil quando a lista precisa ser per corrida desde o inicio 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 seguir retorna o ponteiro onde se localiza o próximo elemento na lista corrente proximoElemento corrente p return p prox A procura por um conteúdo na lista é realizada através da função Busca Esta função percorre a lista desde o inicio enquanto o elemento não for en contrado A função retorna a posição do elemento na lista em caso de suces so na procura ou NULL se o elemento não for encontrado MARIELA INÉS CORTÉS 50 corrente Busca Lista L tipobase 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ó referenciado pelo ponteiro corrente tipobase Consulta Lista L corrente p if p NULL return p elemento A remoção de um elemento da lista envolve a análise de duas situações a remoção do primeiro nó da lista ou de um nó em outra posição qualquer sem ser no inicio da lista A seguir o processo de remoção em cada caso é ilustrado No caso da remoção do primeiro elemento da lista é necessário que o ponteiro à lista seja atualizado indicando o novo primeiro elemento Figura 8 No caso de remoção de um elemento sem ser o primeiro o processo consiste em fazer um by pass sobre esse elemento através do ajuste correto dos ponteiros para posteriormente liberar a memória correspondente Para efetivar a remoção é preciso o nó anterior ao nó a ser removido que pode ser obtido a partir da função auxiliar Anterior Figura 9 A função Remover apresentada a seguir remove o elemento corres pondente a uma determinada posição pos passada por parâmetro Esta posi ção pode ser resultado de um processo de busca a partir de um determinado Estrutura de Dados 51 conteúdo Em ambos os casos é preciso liberar a memória correspondente ao nó removido A seguir é apresentado o algoritmo que implementa o processo de remoção Algoritmo 02 A função inerior retorna o nó anterior ao nó passado pos Ela percorre a toda a lista verificando se o próximo elemento é o elemento pos corrente AnteriorLista l corrente pos corrente ant null ifpos l corrente atual l whileatual null atual prox pos atual atual prox ant atual return 1 Na remoção encontramos duas situações 1 quando o elemento a ser removido é a primeira posição Nó anterior é null e 2 quando o elemento a ser removido não é o elemento da primeira posição Nó anterior não é null Figura 10 MARIELA INÉS CORTÉS 52 int RemoverLista l corrente pos corrente noAnterior Anterior Lpos corrente tmpcell pos ifnoAnterior NULL l l prox else noAnterior prox pos prox free tmpcell return 1 O algoritmo apresentado para a função remover utiliza uma função anterior Esta função anterior tem o papel de retornar o elemento que ante cede a posição atual Tendo em vista que para o elemento atual ser remo vido basta ligar o elemento anterior ao próximo A seguir a função anterior é apresentada corrente AnteriorLista l corrente pos corrente ant null ifpos NULL corrente atual l whileatual null atual prox pos atual atual prox ant atual return ant A inserção em uma lista pode acontecer em qualquer posição que pode ser no inicio no final ou qualquer outra posição no meio da lista O conteúdo do parâmetro pos representa a posição de inserção requerida para o elemen Estrutura de Dados 53 to novo a ser inserido no caso de inserção na cabeça da lista pos é null Neste caso o ponteiro L que apontava ao primeiro elemento da lista aponta agora para o novo elemento inserido Figura 11 Para qualquer outro valor de pos o processo de inserção acontece como ilustrado a seguir A lista precisa ser percorrida até a posição de inser ção requerida Nesse ponto o novo elemento será inserido atualizando os ponteiros correspondentes Figura 12 int Inserir Lista l tipobase dado corrente pos int i Corrente atual Inicializar l Lista novo Lista mallocsizeofstruct 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 MARIELA INÉS CORTÉS 54 else return 1 A função Vazia é utilizada para verificar se a lista possui ou não elemen tos armazenados A verificação consiste em checar se o ponteiro ao primeiro elemento é null int Vazia Lista L if L NULL return 1 else return 0 A função ultimoElemento é utilizada para verificar o final da lista Esta checagem consiste em determinar se o próximo elemento que se gue 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 tem po O1 Isto por que somente um número fixo de instruções é executado sem levar em conta o tamanho da lista Para Busca e Anterior o custo é On pois a lista inteira pode precisar ser percorrida se o elemento não se encontra ou for o último da lista Atividades de avaliação 1 Utilizando o TAD Lista definido nesta parte implemente como aplicação um programa que dadas duas listas A e B crie uma terceira lista L inter calando os elementos das duas listas A e B Lista Intercala Lista A Lista B Lista L cria corrente posL Inicializar L corrente posA Inicializar A corrente posB Inicializar B Estrutura de Dados 55 Assumimos que A e A tem o mesmo tamanho while not ultimoElementoposA not ultimoElemento posB Inserir L Consulta posA null posA proximoElemento posA Inserir L Consulta posB null posB proximoElemento posB returnL Considerando a implementação do TAD utilizando alocação dinámica de me mória resolva as questões a seguir 2 Implemente a operação que retorna a quantidade de elementos na lista cujo cabeçalho é int Tamanho Lista l Determine a complexidade da ope ração implementada 3 Implemente uma rotina para a remoção de uma lista desalocando a memó ria utilizada O cabeçalho da rotina é void Removelist Lista L 4 Implemente a rotina auxiliar chamada anterior usada na remoção de acor do com o seguinte cabeçalho corrente anterior Lista L corrente pos Esta rotina retorna a posição do elemento anterior a uma outra posição pos Se o elemento não for encontrado retorna NULL 5 Utilizando as operações definidas na interface do TAD Lista implemente um método que dadas duas listas L1 e L2 calcule L1 L2 união e L1 L2 interseção O resultado das operações deve ser retornado em uma terceira lista L3 6 Utilizando as operações definidas na interface do TAD Lista implemente um método que dada uma lista retorne uma segunda lista onde os ele mentos pertencentes à primeira estejam ordenados em forma crescente Determine a complexidade do seu algoritmo 7 Escreva um programa que utilizando o TAD Lista faça o seguinte a Crie quatro listas L1 L2 L3 e L4 b Insira sequencialmente na lista L1 10 números inteiros obtidos de forma randômica entre 0 e 99 c Idem para a lista L2 d Concatene as listas L1 e L2 armazenando o resultado na lista L3 MARIELA INÉS CORTÉS 56 e Armazene na lista L4 os elementos da lista L3 na ordem inversa f Exiba o conteúdo das listas L1 L2 L3 e L4 Texto Complementar 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 estabele cida 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 responsável pela busca por um determinado conteúdo na lista pode ser adaptado de forma a tornar a busca mais eficiente Lista circular A convenção consiste em manter a última célula apontando para a primeira Desta forma o teste por fim de lista nunca é satisfeito Com isso precisa ser estabelecido um critério de parada de forma a evitar que o percurso na lista não encontre nunca o fim 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 re querido e também aumenta o trabalho requerido nas inserções e remoções uma vez que existem mais ponteiros a serem ajustados Por outro lado simplifica a remoção pois não mais precisamos procurar a célula anterior On uma vez que esta pode ser acessada diretamente através do ponteiro correspondente Capítulo 4 Pilhas Estrutura de Dados 59 Introdução Em geral as operações de inserção e remoção realizadas sobre listas são custo sas No caso da implementação utilizando alocação de memória estática estas operações acarretam a movimentação dos elementos No caso da alocação di nâmica o deslocamento até a posição correta de inserção ou remoção envolve o percurso ao longo do encadeamento pelos elementos Em ambos os casos o custo destas operações é On Estas situações desfavoráveis podem ser contor nadas se os elementos a serem inseridos e removidos se encontram em posições determinadas especialmente como a primeira ou última posição Uma Pilha é uma lista com a restrição de que inserções e remoções são executadas exclusivamente em uma posição referenciada como fim ou topo Pilhas são conhecidas como estruturas LIFO do inglês Last In First Out ou último que entra primeiro que sai Em uma Pilha o único elemento acessível é o elemento que se encontra no topo Consequentemente a operação de busca ao longo da estrutura por exemplo não é uma operação aplicável para esta estrutu ra de dados Graficamente uma pilha pode ser representada da seguinte forma Figura 13 Objetivos MARIELA INÉS CORTÉS 60 O funcionamento de uma pilha pode ser facilmente interpretado a partir de uma analogia simples com uma pilha de livros pesados Livros são em pilhados um encima de outro sendo que o último livro empilhado é o que fica no topo da pilha e portanto é o único visível e que pode ser consultado sem precisar movimentar outros exemplares Por se tratar de livros pesados o acesso a um livro determinado na pilha requer que os livros encima deste se jam retirados um a um a partir do topo Desta forma o último livro empilhado será o primeiro a ser retirado da pilha A partir desta descrição o funcionamen to da pilha pode ser modelado de acordo com a seguinte interface Interface do TAD Pilha Cria uma pilha vazia Pilha Criar insere um novo elemento no topo da pilha int Push Pilha p tipobase dado consulta pelo elemento que se encontra no topo tipobase Top Pilha p Remove e retorna o elemento do topo tipobase 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 contrario int Cheia Pilha p Retorna a quantidade de elementos na pilha int Tamanho Pilha p Pilhas são listas portanto as abordagens de implementação utilizadas para listas são válidas para o caso da implementação de pilhas Considerando que a implementação de pilhas representa uma variação de listas boa parte da especificação e implementação de listas pode ser aproveitada O fato de máquinas modernas possuírem operações sobre pilhas como parte do conjunto de instruções faz desta estrutura uma abstração fundamental na Ciência da Computação depois do vetor Estrutura de Dados 61 1 Implementações do TAD Pilha usando vetores Levando em conta as restrições inerentes à própria estrutura de dados e as restrições na manipulação da pilha a estrutura projetada para a implementação de listas é modificada adicionando mais um campo de informação referente à localização do elemento que se encontra no topo da pilha Esta informação é indispensável na implementação das operações de inserção e remoção de forma a possibilitar o acesso direto ao local Com essa pequena alteração na estrutura de dados as operações passam a demandar tempo constante typedef int tipobase define tamanho struct estruturaPilha int topo tipobase elementos tamanho typedef struct estruturaPilha Pilha Em C uma pilha é definida como um ponteiro à estrutura que é passado por valor para as funções que irão modificar o conteúdo da pilha 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 topo para a primeira posição Algoritmo 1 Pilha Criar Pilha p Pilha Malloc sizeofestruturaPilha ifp NULL p topo 1 return p else printf Não existe memória suficiente return MARIELA INÉS CORTÉS 62 Na escolha pela extremidade do vetor a ser definida como o topo onde a inserção e remoção de elementos estará acontecendo é importante ana lisar os custos decorrentes desta escolha Como discutido anteriormente a propriedade de alocação contígua de memória traz como desvantagem a ne cessidade de movimentações dos elementos ao longo da estrutura de dados Nesse caso se o topo for escolhido como a primeira posição do vetor o custo da inserção e remoção seria de On Em contrapartida a definição de topo como sendo o último elemento inserido é mais conveniente uma vez que este pode ser acessado em tempo constante a partir do tamanho da estrutura Algoritmo 2 A operação de inserção de um elemento é feita no tipo da pilha caso a pilha não esteja cheia A seguir seguem os algoritmos de verificação de pilha cheia e de inserção int CheiaPilha p ifp topo tamanho 1 return 1 else return 0 int Cheia Pilha p ifCheia p 1 p topo p elementos p topo dado return 1 else return 0 A operação de remoção do elemento que se encontra no topo da pilha é descrita no algoritmo a seguir tipobase Pop Pilha p tipobase v v p elementos p topo p topo return v Estrutura de Dados 63 A remoção de um elemento somente é possível sempre que a pilha contiver pelo menos um elemento Nesse caso o elemento é copiado em uma variável auxiliar para seu retorno posterior decrementando em 1 conse quentemente a posição do último elemento A lógica seguida para a imple 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 elemento é removido da pilha O algoritmo que verifica se a pilha se encontra vazia ou não é basea do na informação contida no campo topo Considerando que o topo indica indiretamente a quantidade de elementos efetivamente contidos na pilha a checagem pela posição onde este elemento se encontra é utilizado para esta belecer se a pilha está vazia Nesse caso a função retorna 1 int Vazia Pilha p if p topo 0 return 1 else return 0 Uma estratégia similar pode ser utilizada para estabelecer se a pilha se encontra cheia só que neste caso a posição do elemento no topo precisa ser confrontada contra o tamanho total reservado para a estrutura de dados Para refletir Considerando a implementação do TAD utilizando alocação estática de memoria resol va as questões a seguir 1 Implemente o algoritmo que consulta e retorna o conteúdo correspondente ao elemento que se encontra no topo atendendo ao seguinte cabeçalho tipobase Top Pilha p 2 Explique por que é mais conveniente a definição do topo da pilha no final e não no inicio da estrutura 2 Implementação do TAD Pilha usando ponteiros No caso da implementação de pilhas utilizando alocação dinâmica de memó ria a desvantagem do acesso sequencial necessário para alcançar qualquer elemento da pilha pode ser contornado eficientemente uma vez que no caso da pilha as operações acontecem necessariamente a partir de um extremo A escolha pelo extremo da estrutura a ser considerado como topo irá a determi nar o custo envolvido na execução das operações enquanto que o acesso ao último elemento da pilha envolve custo On o acesso ao primeiro elemento é constante Consequentemente no caso da implementação da pilha utilizando ponteiros a definição do topo como sendo o inicio cabeça da lista da pilha é mais vantajoso em termos de desempenho e complexidade MARIELA INÉS CORTÉS 64 A estrutura de dados utilizada na implementação da pilha é idêntica aquela definida no caso de listas consequentemente a maior parte das ope rações são coincidentes tais como Criar e Vazia O nó pode ser visualizado de acordo com a ilustração a seguir Figura 14 typedef struct node noptr struct no dl tipobase elemento noptr prox typedef noptr Pilha A partir da decisão de projeto para o TAD Pilha de considerar o topo para as operações de inserção push e remoção pop na cabeça da lista de elementos cuidados especiais na implementação de tais operações são requeridos de forma a evitar perda de informação A seguir o algoritmo de criação da pilha Este é bom simples apenas devolve nulo como valor inicial da pilha Pilha Criar return NULL A operação Push responsável pela inserção de um novo elemento no topo da pilha consiste na alocação de memória para o novo elemento Se a alocaçã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 novo elemento No caso em que a inserção aconteça com sucesso o algorit mo retorna 1 e 0 em caso contrario Estrutura de Dados 65 int Push Pilha p tipobase x noptr novo noptr malloc sizeof struct no if notmp NULL printf Memoria insuficiente return 0 else novo elemento x novo prox p p novo return 1 Figura 15 A operação de desempilhar pop realiza a remoção de m elemento no inicio da pilha tipobase Pop Pilha p noptr temp if p NULL printf Pilha vazia return 0 else temp p int valor temp elemento p p prox freetemp return valor MARIELA INÉS CORTÉS 66 Figura 16 Atividades de avaliação Considerando a implementação do TAD utilizando alocação dinâmica de me moria resolva as questões a seguir 1 Implemente o algoritmo que consulta e retorna o conteúdo correspondente ao elemento que se encontra no topo atendendo ao seguinte cabeçalho tipobase Top Pilha p 2 Implemente uma operação que libere a memória alocada pela pilha Determine a complexidade do seu algoritmo 3 Explique por que é mais conveniente a definição do topo da pilha no inicio e não no fim da estrutura no caso de utilização de ponteiros 4 Utilizando as operações definidas na interface do TAD Lista e do TAD Pilha elabore um algoritmo que dada uma lista ordenada inverta a ordem dos elementos na lista utilizando para isso uma pilha Determine a complexi dade do seu algoritmo 5 Utilizando as operações definidas na interface do TAD Pilha escreva um algoritmo para ordenar pilhas sendo que no final do processamento os elementos da pilha devem estar dispostos em ordem crescente de seus valores Determine qual a estrutura auxiliar mais adequada para suportar o processo Determine a complexidade do seu algoritmo 6 Utilizando as operações definidas na interface do TAD Pilha escreva um al goritmo que forneça o maior o menor e a média aritmética dos elementos de uma pilha dada como entrada Capítulo 5 Filas Capítulo 6 Árvores Estrutura de Dados 69 Introdução Assim como pilhas filas são listas que possuem algumas restrições específi cas para a execução das operações de inserção e remoção Na fila as inser ções são realizadas em um extremo enquanto a remoção ocorre no outro A fila segue o modelo FIFO do inglês First In First Out ou seja que o primeiro que entra na fila é o primeiro em sair A estrutura de dados fila como seu próprio nome já sugere é seme lhante ao funcionamento de uma fila de banco Onde 1 Se não há ninguém na fila e chega uma pessoa está será o inicio e o fim da fila 2 A partir de então quaçquer pessoa que chegar irá para o final da fila após a pessoa que está no fim 3 Cada elemento a ser removido será do inicio da fila O primeiro que chega na fila é o primeiro que sai Figura 17 Interface do TAD Fila Cria uma fila vazia Fila Criar insere um novo elemento no topo da fila void Inserir Fila p tipobase dado Consulta pelo elemento que se encontra no topo Objetivos MARIELA INÉS CORTÉS 70 tipobase 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 1 Implementação do TAD Fila usando vetores Considerando que a operação de remoção acontece em uma extremi dade e a inserção na outra é interessante manter apontadores indican do ambos extremos da estrutura de forma que o acesso seja direto On Consequentemente a estrutura de dados fila inclui além do vetor que irá a comportar as informações correspondentes os índices correspondentes ao inicio e fim da fila e o tamanho da fila relativo ao número de elementos conti dos A seguinte figura mostra uma fila em algum estado intermediário Figura 18 De acordo com esta estratégia e depois da remoção de b e a e da inserção de f e 1 a situação da fila seria a seguinte Figura 19 Estrutura de Dados 71 A inserção de um elemento na fila incrementa o tamanho e o índice que indica o fim da fila enquanto que na remoção de um elemento o tamanho da fila é decrementado e o índice que indica o inicio é incrementado Esta estratégia evita a movimentação de elementos sempre que uma inserção ou remoção for realizada Com isso o custo de ambas operações fica constante Levando em conta as restrições inerentes à manipulação da fila a es trutura projetada para a sua implementação utilizando alocação de memória estática ou vetor precisa ser modificada em relação à pilha Neste caso é preciso indicar mais um campo de informação referente à localização do ele mento que se encontra no inicio da fila Esta informação é indispensável na implementação das operações de inserção e remoção de forma a possibilitar o acesso direto ao local Com essa pequena alteração na estrutura de dados as operações passam a ser executadas em tempo constante typedef int tipobase definindo o tipo base da fiça define tamanho struct estruturaFila int ini int fim int quantelementos tipobase elementos tamanho typedef struct estruturaFila Fila No entanto existe um problema potencial uma vez que a fila pode ficar aparentemente cheia no entanto vários elementos podem ter sido removidos podendo existir na verdade poucos elementos na fila observe a figura anterior na qual o fim está na ultima posição do vetor no entando há duas posições vazias no inicio do vetor A solução para contornar este problema é implementar o chamado incremento circular no vetor onde sempre que os índices de inicio ou de fim chegam no final do vetor estes são redefinidos na primeira posição do vetor Esta estratégia requer um cuidado especial na hora do percurso sobre a estrutura uma vez que o fim do vetor precisa ser determinado logicamente pe pela quantidade de elementos na fila e não mais fisicamente pelo fim da estrutura A figura a seguir exemplifica o funcionamento da fila utilização o vetor circular onde o conteúdo c foi removido e adicionado o conteúdo m MARIELA INÉS CORTÉS 72 Figura 20 A criação de uma fila vazia similarmente à criação de uma lista envolve a alocação de memória para a estrutura de dados respectiva e a posterior inicialização dos campos envolvidos no caso os índices de inicio e fim e a quantidade de elementos14 que precisam ser inicializados em 0 Algoritmo 3 Fila Criar Fila if f Fila malloc sizeof estruturaFila f ini 1 f fim 1 f quantelementos 0 returnf else printfNão existe memória suficiente return Considerando a inserção de elementos acontecendo no fim e a remoção no inicio o código das respectivas operações é apresentado a seguir No caso da inserção e levando em conta que o tamanho da es trutura de dados estática foi estabelecida em tempo de compilação é im portante verificar que exista espaço disponível para armazenar um novo elemento Após esta verificação o novo elemento é inserido na primeira posição livre indicada por fim Após isso tanto fim quando a quantidade de elementos precisam ser atualizados 14 Quando a fila está cheia sua quantidade de elementos é igual ao tamanho do vetor Estrutura de Dados 73 void inserir Fila f tipobase v if f quantelementos tamanho printf Fila cheia return f fim incrementar f fim iff quantelementos 0 f elementos f fim v f quantelementos A implementação do vetor circular requer que seja realizado um incre mento especial onde a partir de uma posição corrente o método retorna a posição seguinte ou no caso de atingir o final do vetor a posição corrente é especificada como sendo no inicio da estrutura no caso 0 int incrementar int pos if pos tamanho 1 return 0 else return pos Os elementos da fila são removidos do seu inicio Deste modo as operações de remoção movimentam o elemento ini onde o inicio passa uma posição para frente no vetor e a quantidade de elementos é reduzida em 1 Duas situações merecem o cuidado especial quando a fila está vazia quantidade de elementos igual é zero e quando a fila tem somente o elemento que será removido neste caso quando a quantidade de ele mentos para a ser zero inicio e fim devem receber o valor 1 para identificar que a fila está vazia int removerFila f if f quantelementos 0 printfFila vazia return int temp f elementosf ini MARIELA INÉS CORTÉS 74 f ini incrementarf ini f quantelementos iff quantelementos 0 f ini 1 f fim 1 returntemp Para refletir Considerando a implementação do TAD utilizando alocação estática de memória resol va as questões a seguir 1 Implemente os algoritmos Tamanho Cheia Topo e Vazia de acordo com os respec tivos cabeçalhos definidos na interface do TAD 2 Explique por que é mais conveniente a realização da operação de inserção no fim e de remoção no inicio Como seria se fosse ao contrario 3 Escreva um algoritmo para ordenar filas sendo que no final do processamento os elementos da fila devem estar dispostos em ordem crescente de seus valores De termine qual a estrutura auxiliar mais adequada para suportar o processo Determi ne a complexidade do seu algoritmo 2 Implementação do TAD Fila usando ponteiros A implementação de filas utilizando ponteiros segue a mesma estratégia anali sada na seção anterior Como teremos que inserir e retirar elementos das extre midades opostas da lista representando o início e o fim da fila é preciso utilizar dois ponteiros ini e fim que apontam respectivamente para o primeiro e para o último nó da fila A partir desta necessidade se faz indispensável a implemen tação da fila utilizando um nó diferenciado chamado de header ou cabeçalho para conter estes ponteiros Essa situação é ilustrada na figura abaixo Figura 21 Estrutura de Dados 75 A definição da estrutura de dados que implementa a abordagem descri ta é a seguinte typedef struct no noptr typedef struct no tipobase elemento noptr prox A estrutura de dados envolve a definição de uma lista de elemen tos no mesmo formato em que foi definida para o caso de listas e pilhas Adicionalmente a estrutura correspondente ao nó cabeçalho precisa ser es pecificada uma vez que inclui campos diferenciados struct cabeçalho noptr ini noptr fim Finalmente a fila é definida como sendo um ponteiro ao nó cabeçalho typedef struct cabeçalho Fila A partir da interface especificada para o TAD fila as operações de cria ção e verificação pela fila vazia seguem as mesmas estratégias anteriormente descritas Algoritmo 5 Fila Criar Fila f Fila mallocsiziofcabeçãlho iff NULL f ini NULL f fim NULL return else printfNão existe memória suficiente return MARIELA INÉS CORTÉS 76 Algoritmo 6 int VaziaFila f iff ini NULL return 1 else return 0 A decisão de projeto em relação às operações de inserção e remoção envolve estabelecer em qual extremidade da fila cada uma será executada Em particular a lógica na implementação da operação de remoção de um ele mento em uma lista implementada com ponteiros requer a procura pelo ele mento anterior na lista de forma a atualizar o ponteiro para o próximo elemen to Ver remoção em listas O custo desta procura pelo anterior é On Esta situação pode ser evitada se a remoção acontece sempre no inicio da lista uma vez que não existe anterior que precise ser atualizado Esta constatação determina que a escolha mais conveniente em termos de complexidade é que cada novo elemento seja inserido no fim da lista enquanto que a remoção de um elemento seja realizada no início Figura 22 No caso da operação de inserção onde o elemento é inserido no fim da lista na situação específica de inserção do primeiro e único elemento ambos os ponteiros ini e fim precisam ser atualizados apontando para o único nó inserido na fila Em qualquer outro caso somente o ponteiro que indica o final da fila será atualizado Estrutura de Dados 77 Algoritmo 7 int inserir Fila f tipobase dado noptr novo noptr malloc sizeof no novo elemento dado novo prox NULL if f fim NULL f fim prox novo else f ini novo f fim novo return1 Analogamente a função para remover um elemento da fila deve atuali zar ambos os ponteiros no caso em que for removido o último e único elemen to existente tornando a fila vazia ini e fim nulos MARIELA INÉS CORTÉS 78 Algoritmo 8 tipobase remover Fila f noptr temp if f NULL printfFila Vazia return0 else iff ini NULL printfFila Vazia else temp f ini int valor temp elemento f ini f ini prox iff ini NULL f ini NULL freetemp returnvalor Atividades de avaliação 1 Implemente os algoritmos Top e Tamanho de acordo com os respectivos cabeçalhos definidos na interface do TAD Fila utilizando ponteiros 2 Explique por que é mais conveniente a realização da operação de inserção no fim e de remoção no inicio Como seria se fosse ao contrário 3 Utilizando as operações definidas na interface do TAD implemente como aplicação uma operação que libere a memória alocada pela fila Determine a complexidade do seu algoritmo Estrutura de Dados 79 4 Utilizando as operações definidas na interface do TAD Fila escreva um al goritmo que forneça o maior o menor e a média aritmética dos elementos de uma Fila 5 Utilizando as operações definidas na interface dos TAD Fila e Pilha escre ver um algoritmo que leia um número indeterminado de valores inteiros Considere que o valor 0 zero finaliza a entrada de dados Para cada valor lido determinar se ele é um número par ou ímpar Se o número for par então incluílo na FILA PAR caso contrário incluílo na FILA ÍMPAR Após o término da entrada de dados retirar um elemento de cada fila alterna damente iniciandose pela FILA ÍMPAR até que ambas as filas estejam vazias Se o elemento retirado de uma das filas for um valor positivo então incluílo em uma PILHA caso contrário remover um elemento da PILHA Finalmente escrever o conteúdo da pilha Síntese do capítulo Neste capítulo foi apresentado o tipo abstrato de dados Lista a partir da defi nição da sua interface O tipo abstrato foi implementado de acordo com duas abordagens tradicionais vetores e ponteiros analisando as vantagens e des vantagens de cada uma das abordagens de acordo com as características das aplicações e operações mais frequentes Os TADs Pilha e Fila foram descritos e implementados como variantes do TAD Lista Estes TADs são amplamente difundidos e de comprovada utili dade na resolução e modelagem de problemas do mundo real Referências CORMEN T H LEISERSON C E RIVEST R L STEIN C 2001 Intro duction to Algorithms McGrawHill e The Mit Press KNUTH D E 1968 The Art of Computer Programming Vol 1 Funda mental Algorithms AddisonWesley KNUTH D E 1971 Mathematical Analysis of Algorithms Prociedings IFIP Congress 71 vol 1 North Holland 135143 SZWARCFITER J l MARKENZON L 2010 Estruturas de Dados e Seus Algoritmos 3ª Edição LTC MARIELA INÉS CORTÉS 80 WIRTH N 1986 Algorithms and Data Strutures PrenticeHall ZIVIANI N 2005 Projeto de Algoritmos com implementações em Pas cal e C 2da Edição Thomson Estrutura de Dados 83 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 parte anterior Uma árvore é uma estrutura de dados não linear muito eficiente para armazenar informação de forma a represen tar relacionamentos de aninhamento ou hierarquia entre os elementos envolvidos Nesta parte são apresentados os conceitos iniciais relativos a árvores e a sua representação clássica e implementação através da definição do tipo abstrato correspondente Árvores binárias de busca e balanceadas AVL são introduzidas Introdução Vetores e listas são estruturas de dados chamadas de unidimensionais ou lineares e portanto não são adequadas para representarmos dados que de vem ser dispostos de maneira hierárquica Por exemplo a estrutura hierárqui ca de diretórios pastas aninhamento etc Estruturas de dados não lineares como árvores são ideais para representar este tipo de relacionamento A ilustração a seguir representa à esquerda o aninhamento de conjuntos e à direita a representação hierárquica deste aninhamento utilizando uma árvore Figura 23 Uma árvore é composta por um conjunto de nós Existe um nó r denominado raiz que contém zero ou mais subárvores cujas raízes são ligadas diretamente a r Esses nós raízes das subárvores são ditos filhos do nó pai r MARIELA INÉS CORTÉS 84 Figura 24 O número de filhos permitido por nó e as informações armazenadas em cada nó diferenciam os diversos tipos de árvores existentes Árvores binárias onde cada nó tem no máximo dois filhos Árvores genéricas onde o número de filhos é indefinido A forma mais natural para definirmos uma estrutura de árvore é usando recursividade Uma árvore T é um conjunto finito de n nós ou vértices tais que Se T é um conjunto vazio ou seja n 0 a árvore é nula ou vazia ou Existe um nó especial r chamado raiz da árvore Os demais nós constituem um conjunto vazio ou são particionados em conjuntos disjuntos não vazios as subárvores de r Cada subárvore por sua vez também é uma árvore Sejam T uma árvore e v um nó tal que v ε T Tv é a subárvore de T que tem v como raiz Definemse as seguintes propriedades O grau de saída do no v é o número de subárvores que ele possui O grau da árvore T é o maior grau dentre os de todos os seus nós Os filhos de v são as raízes das subárvores de v Um nó que não tem descendentes é chamado de folha ou terminal Uma propriedade fundamental de todas as árvores é que só existe um caminho da raiz para qualquer nó Com isto podemos definir a altura de uma árvore como sendo o comprimento do caminho mais longo da raiz até uma das folhas Assim a altura de uma árvore com um único nó raiz é zero Estrutura de Dados 85 Um caminho em T é uma sequência de nós v1 v2 vm tal que para cada par vi vi1 vi é pai de vi1 O comprimento do caminho é m1 O nível do nó v é o número de nós no caminho da raiz até v O nível do nó raiz é 0 por definição A altura de um nó v é o número de nós no maior caminho de v até um dos seus descendentes Folhas têm altura 1 A altura da raiz determina a altura da árvore 1 Árvore binária Em uma árvore binária cada nó tem zero um ou dois filhos De maneira re cursiva podemos definir uma árvore binária como sendo Uma árvore vazia ou Um nó raiz v tendo duas subárvores identificadas como a subárvore da direita sad e a subárvore da esquerda sae de v Figura 25 Pela definição uma subárvore de uma árvore binária é sempre especi ficada como sendo a sae ou a sad de uma árvore maior e qualquer das duas subárvores pode ser vazia Uma árvore binária T é um conjunto finito de n nós ou vértices tais que Se T é um conjunto vazio ou seja n0 a árvore é nula ou vazia ou Existe um nó especial r chamado raiz da árvore Os demais nós constituem um conjunto vazio ou são particionados em dois conjuntos disjuntos subárvore esquerda e direita de r cujas raízes são chamadas de filho esquerdo e direito de r Cada subárvore por sua vez também é uma árvore binária Uma árvore estritamente binária é aquela em que cada nó possui zero ou dois filhos como representado na figura a seguir Pesquise sobre aplicações da estrutura de dados árvore MARIELA INÉS CORTÉS 86 Figura 26 Uma árvore binária completa é aquela cujos nós com subárvore vazias localizamse no último ou no penúltimo nível Um exemplo de árvore binária completa é ilustrado na figura abaixo Figura 27 Uma árvore binária cheia é aquela cujos nós com subárvores va zias localizamse todos no último nível Logo ela também é estritamente binária Figura 28 Estrutura de Dados 87 Um exemplo de utilização de árvores binárias está na avaliação de ex pressões Nessa árvore os nós folhas representam operandos e os nós inter nos operadores binários Uma árvore que representa por exemplo a expres são 5 9 3 7 7 é ilustrada na seguinte figura Figura 29 Dependendo do percurso da árvore a mesma expressão pode ser re presentada em forma expressões infixas prefixas e pósfixas No caso de percorrer uma árvore de forma infixa inicialmente a sub árvore esquerda é percorrida em seguida o nó raiz é percorrido por ultimo a subárvore direita é percorrida No caso da árvore acima ser percorrida de forma infixa o resultado seria 5 9 3 7 7 Neste caso o percurso resulta em uma expressão matemática válida No caso de percorrer uma árvore de forma prefixa inicialmente o nó raiz é percorrido em seguida a subárvore esquerda é percorrida por ultimo a sub árvore direita é percorrida No caso da árvore acima ser percorrida de forma prefixa o resultado seria 5 9 3 7 7 Observe que neste caso o percurso não resulta em uma expressão matemática válida No caso de percorrer uma árvore de forma pósfixa inicialmente a sub árvore esquerda é percorrida em seguida a subárvore direita é percorrida por ultimo o nó raiz é percorrido No caso da árvore acima ser percorrida de forma pósfixa o resultado seria 59 37 7 Observe que neste caso o per curso também não resulta em uma expressão matemática válida No próximo capítulo serão abordados estas formas de percursos em árvores Para refletir 1 Pesquise sobre aplicações da estrutura de dados árvore binária MARIELA INÉS CORTÉS 88 2 Árvore binária de busca Uma árvore de busca é uma árvore binária com a propriedade de que para todo no x na árvore os valores de todas as chaves na subárvore esquerda são menores ou iguais do que o valor chave em x e que os valores de todas as chaves na subárvore direita são maiores ou iguais do que o valor chave em x Esta definição se aplica recursivamente a cada nó da árvore Assumimos que cada nó na árvore possui um valor chave e em principio não é considerada a ocorrência de chaves repetidas No caso das árvores representadas a seguir a propriedade de ordenação pode ser verificada em todos os nós na árvore esquerda Na árvore direita a propriedade não se verifica uma vez que na subárvore esquerda do nó raiz aparece um nó com chave maior 5 àquela encontrada na raiz 4 Figura 30 Como a profundidade média das árvores binárias de busca é Olog n as operações sobre elas executadas também Desde que todos os elementos na árvore seguem um critério de ordem os operadores e podem ser aplicados de forma a estabelecer compa rações entre eles 21 Definição do TAD Árvore Binária de Busca O conjunto de operações necessário para a manipulação correta e satisfatória de uma árvore binária de busca é definido a seguir Interface do TAD ABB Retorna uma árvore vazia ABB Inicializar void Cria e retorna uma árvore inicializada ABB Rriar elementtype c noptr e noptr d Insere um dado na árvore noptr Inserir noptr pai noptr filhoEsq Busca por um determinado elemento e retorna o nó corres pondente ou null caso não seja encontrado noptr Buscar elementtype x ABB t Retorna o conteúdo de um nó elementtype Conteudo noptr a Retorna o filho esquerdo de um nó ABB retornaSAE noptr a Retorna o filho direito de um nó ABB retornaSAD noptr a Remove um elemento void Remove elementtype x pai ABB pai ABB nó Retorna 1 se o nó for nulo ou 0 em caso contrário int Vazia noptr a 22 Implementação do TAD Árvore Binária de Busca O armazenamento de árvores pode utilizar alocação dinámica ou estática cujas vantagens e desvantagens foram analizadas em partes anteriores No entanto por se tratar de uma estrutura mais complexa o potencial desperdício de espaço pode ser reduzido pela utilização de ponteiros A definição da es trutura de dados surge naturalmente a partir da definição recursiva da árvore Cada nó na árvore possui além do campo de informação dois ponteiros que apontam para cada uma das suas subárvores typedef struct noÁrvore noptr typedef int elementtype struct noÁrvore elementtype info MARIELA INÉS CORTÉS 90 noptr esq noptr dir Da mesma forma que uma lista encadeada é representada por um pon teiro para o primeiro nó a estrutura da árvore como um todo é representada por um ponteiro para o nó raiz a partir do qual todos os nós da árvore podem ser alcançados typedef noptr ABB Como uma árvore é representada pelo endereço do nó raiz uma árvore 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 à es querda e à direita Essa função tem como valor de retorno o endereço do nó raiz criado e inicializado como segue ABB Criar elementtype c ABB sae ABB sad p ABB malloc sizeof noÁrvore p info c p esq sae p dir sad return p As duas funções Inicializar e Criar representam os dois casos da defini ção recursiva de árvore binária uma árvore binária é vazia a Inicializar ou é composta por uma raiz e duas subárvores a Criar c sae sad As operações que possibilitam a consulta dos conteúdos dos campos que compõem o nó são apresentadas a seguir O método Conteudo retorna a informação contida no nó enquanto que retornaSAE retorna a subárvore es querda do nó Analogamente o método retornaSAD retorna a subárvore direita elementtype Conteudo ABB a return a info Estrutura de Dados 91 ABB retornaSAE ABB a return a esq A busca por um conteúdo em uma árvore binária de busca leva em con ta o critério de ordenação estabelecido entre os nós que a compõem Desta 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árvore da esquerda e no caso contrário na subárvore direita recursivamente noptr Buscar elementtype 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 Se o elemento for encontrado nada é feito uma vez que não estamos considerando a ocorrência de chaves repetidas Em outro caso o elemento é inserido Note que seja qual for a chave a ser inserida a inserção sempre acontece em um nó folha O exemplo a seguir ilustra a inserção da chave com valor 12 Figura 31 Duplicações podem ser manipuladas mantendo um campo extra no registro do nó indicando a freqüência da ocorrência Esta solução é mais efi 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 de alocar mais espaço de memória MARIELA INÉS CORTÉS 92 noptr Inserir elementtype x ABB T if T NULL T ABB malloc sizeof noÁrvore T element x T esq NULL 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 Na remoção várias possibilidades devem ser consideradas Se o nó que vai ser removido é folha a remoção é imediata Se o nó tem somente um filho ele pode ser removido ajustando os pon teiros entre seu pai e seu filho de modo de realizar um by pass encima do nó Por exemplo considere a árvore a seguir onde o nó correspondente ao dado 5 precisa ser removido O processo a ser seguido é descrito na árvore que aparece à direita Figura 32 Se o nó a ser removido tem dois filhos a estratégia geral consiste em reemplazar a chave do nó com a menor chave da subárvore direita ou maior da subárvore esquerda e recursivamente remover esse nó Como o filho mais esquerdo da subárvore direita não pode ter filho esquerdo a segunda remoção é mais fácil O exemplo a seguir ilustra a remoção do nó Estrutura de Dados 93 cujo conteúdo é 2 que possui dois filhos Nesse caso o nó é substituído pelo filho mais a esquerda da subárvore direita ou o menor dos maiores Posteriormente o nó utilizado na substituição precisa ser removido 3 da subárvore correspondente Figura 33 O método Remover recebe por parâmetro o ponteiro ao nó que será removido Este ponteiro pode ter sido obtido a partir da execução da operação de busca por um conteúdo específico O algoritmo também precisa do pon teiro correspondente ao nó pai do nó que será removido já que o respectivo ponteiro precisa ser ajustado O código realiza dois passes na árvore para encontrar e remover o me nor nó da subárvore direita Esta ineficiência pode ser removida escrevendo uma função deletemin void Remover elementtype x ABB pai ABB no noptr tmpno filho if no esq null v dir null tmpcell buscaMin no dir no info tmpcell info no dir Remover no info no dir MARIELA INÉS CORTÉS 94 else tmpno no ifno esq NULL filho no dir ifno dir NULL filho no esq if pai dir T pai dir filho else pai esq filho free tmpno O método auxiliar que procura o nó que contem o conteúdo mínimo possui duas versões uma recursiva e outra iterativa noptr buscaMin ABB T if T NULL return NULL else if T esq NULL return T else return buscaMin T esq noptr 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ão recursiva pode ser mais eficiente em termo de custo espacial e temporal do que a versão recursiva Estrutura de Dados 95 Para refletir Escreva uma função que verifique se uma árvore é cheia Uma árvore é dita cheia se todos os nós que não são folhas têm os dois filhos isto é não pode existir nó com apenas um filho A função deve retornar 1 no caso da árvore ser cheia ou 0 no caso de não ser No caso da árvore ser vazia a função deve retornar 1 int cheia treeptr a if vazia a return 1 else if vazia retornaSAE a vazia retornaSAD a vazia retornaSAE a vazia retornaSADa return 0 else return cheia retornaSAE a cheia retornaSADa 23 Ordens de percurso em árvores binárias O percurso de todas as subárvores executando alguma ação de tratamento 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ósordem 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 curso são apresentados a continuação void ImprimirPosordem noptr a if Vaziaa ImprimirPosordem retornaSAEa ImprimirPosordem retornaSADa printf Conteudoa return MARIELA INÉS CORTÉS 96 void ImprimirSimetrica noptr a if Vaziaa ImprimirSimetrica retornaSAEa printf Conteudoa ImprimirSimetrica retornaSADa return void ImprimirPreordem noptr a if Vaziaa printf Conteudoa ImprimirPreordem retornaSAEa ImprimirPreordem retornaSADa return Por exemplo dada a árvore de expressão a seguir como resultado dos percursos apre sentados as expressões resultantes são as seguintes Inordem 5 9 3 7 7 Preordem 5 9 3 7 7 Posordem 5 9 3 7 7 para refletir 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 Analise a árvore binária obtida em termo de desempenho na exe cução das operações sobre ela b 20 5 12 36 27 45 9 2 6 17 40 c A partir da árvore obtida no inciso anterior remover os nós 9 a seguir o 5 e final mente o 20 Estrutura de Dados 97 2 Implemente um algoritmo que determine se uma árvore binária de busca é efeti vamente uma árvore binária de busca 3 Implemente o método que retorna o maior elemento a partir de um determinado nó cujo cabeçalho é noptr buscaMAX ABB T Implemente o método na sua versão recursiva e não recursiva 4 Dada uma árvore binária de busca onde cada nó é constituído pelas seguintes informações NOME SEXO M ou F IDADE e PESO Sabendo que a árvore foi construída com a chave NOME e que já existe um ponteiro chamado RAIZ que aponta para o nó raiz da árvore construir um algoritmo que a partir desta árvore gere duas listas ordenadas por NOME uma para homens e outra para mulheres 5 Escreva um algoritmo recursivo que encontre o maior valor armazenado em uma árvore binária de busca já construída 6 Adapte os algoritmos de inserção e remoção em árvores binárias de busca de for ma a tratar a ocorrência de conteúdoschave repetidos mantendo um contador de ocorrências em cada nó 7 Para a árvore binária a seguir escreva as sequências de nós visitados após a exe cução dos percursos préordem inordem e pósordem Codifique os algoritmos correspondentes a cada um dos percursos 8 Utilizando as operações definidas na interface do TAD ABB de números escreva um método que retorne quantos nós de uma ABB armazenam valores contidos em um intervalo x1 x2 Texto Complementar 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 dobrando 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 h1 2 h 2 h1 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 h1 nós deste caminho devem ficar em níveis diferentes Assim a árvore deverá ter pelo menos h1 nós MARIELA INÉS CORTÉS 98 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 estra té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 processos de inserção e remoção mais complexos que mantenham as subárvores balanceadas 3 Árvores AVL Uma AVL é uma árvore binária de busca dinamicamente equilibrada ou ba lanceada 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 é Olog n O nome AVL devese aos seus criadores os matemáticos ADELSONVELSKII e LANDIS A propriedade de balanceamento consiste em manter as subárvores esquerda e direita de cada nó na mesma altura podendo diferir no máximo em 1 nível A figura a seguir ilustra uma árvore onde a raiz se encontra balan ceada uma vez que a suas subárvores esquerda e direita possuem a mesma altura no entanto os nós internos não satisfazem essa propriedade Figura 34 Com esta restrição todas as operações sobre árvores podem ser execu tadas em tempo Olog n exceto possivelmente a inserção No entanto para manter a propriedade de balanceamento além dos algoritmos de percurso in clusão e exclusão já discutidos são necessários algoritmos que restabeleçam o equilíbrio após inclusões e exclusões caso algum nó fique desregulado Por exemplo na inserção pode ser preciso atualizar a informação de balancea mento para os nós no caminho de volta para a raiz pois somente aqueles nós tiveram as suas subárvores alteradas Estrutura de Dados 99 No caso das á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 com uma diferença de até um nível Já a árvore da direita apresen ta um desbalanceamento na raiz Figura 35 A inserção de 65 na primeira árvore provocará o desbalanceamento do nó 8 A propriedade de balanceamento é restaurada através de opera ções de rotação Seja α o no desbalanceado Desde que todo nó tem no máximo dois fi lhos e o desbalanceamento da altura requer que a altura das duas subárvores deferem em 2 a violação da propriedade pode acontecer como consequência de operações de inserção ou remoção O fator de balanceamento FB de um determinado nó r é calculado como a diferencia entre a altura da subárvore esquerda de r e da subárvore direita de r Se o valor obtido for menor ou igual a 1 o nó está balanceado Caso contrário o nó se encontra desbalanceado O FB de um nó folha é 0 Algoritmo que calcula a altura de um nó int Altura ABB no int AltEsq AltDir if no NULL Altura 1 else AltEsq Altura retornaSAD no AltDir Altura retornaSAE no if AltEsq AltDir Altura 1 AltEsq MARIELA INÉS CORTÉS 100 else Altura 1 AltDir No caso em que for constatado o desbalanceamento em um determina do nó quatro situações possíveis podem ser constatadas Tipo I Se a subárvore esquerda é maior que a subárvore direita FB 1 e a subárvore esquerda desta subárvore esquerda é maior que a sub árvore direita dela então realizar uma rotação simples para a direita Figura 36 Tipo II Se a subárvore esquerda é maior que a subárvore direita FB 1 e a subárvore esquerda desta subárvore esquerda é menor ou igual que a subárvore direita então realizar uma rotação dupla para a direita Figura 37 Tipo III Se a subárvore esquerda é menor que a subárvore direita FB 1 e a subárvore direita desta subárvore direita é menor ou igual que a sub árvore esquerda dela então realizar uma rotação dupla para a esquerda Estrutura de Dados 101 Figura 38 Tipo IV Se a subárvore esquerda é menor que a subárvore direita FB 1 e a subárvore direita desta subárvore direita é maior que a subárvore esquerda dela então realizar uma rotação simples para a esquerda Figura 39 A partir das situações apresentadas qualquer tipo de desbalanceamen to pode ser corrigido aplicando uma das 4 rotações descritas Exemplo Começando a partir de uma árvore vazia são inseridos os números de 1 4 e 7 O primeiro problema acontece na inserção do 7 a propriedade de balanceamento é violada na raiz Para resolver é executada uma rotação simples a esquerda Figura 40 A seguir é inserida a chave 9 sem prejuízo do balanceamento da árvore A inserção do 8 provoca uma nova violação no nó 7 e também na raiz da árvore Repare que neste caso uma rotação simples a esquerda não resolve o problema MARIELA INÉS CORTÉS 102 Figura 41 O desbalanceamento no nó 7 é resolvido em dois passos através de uma rotação du pla a esquerda No primeiro passo é realizada uma rotação simples a direita envolven do a subárvore do nó desbalanceado Já no segundo passo uma rotação a esquerda envolvendo o nó desbalanceado devolve o balanceamento à árvore Figura 42 A inserção do 12 provoca o desbalanceamento da raiz desde que a subárvore es querda de altura 0 enquanto que a direita tem altura 2 para resolver é executada uma rotação simples a esquerda Figura 43 Estrutura de Dados 103 Como resultado da rotação o nó com a chave 8 se torna a nova raiz da árvore e com isso a sua subárvore esquerda 7 se transforma na nova subárvore direita do 4 Continuando o exemplo a inserção da chave 10 desbalanceia o nó 9 desencadean do uma nova rotação dupla a esquerda Figura 44 É importante salientar que se a árvore não fosse AVL o resultado das inserções teria gerado uma árvore de altura 5 enquanto que a AVL obtida a partir da mesma sequen cia de inserção possui altura 2 Atividades de avaliação 1 Considerando que a altura h de uma árvore é dada pelo caminho mais longo desde a raiz até uma folha explique com as suas palavras a relação existente entre altura h de uma árvore binária e a quantidade mínima e máxima de nós a Qual a relação entre a altura h de uma árvore e o tempo requerido custo para encontrar um nó b Em qual situação a busca em uma árvore binária pode atingir eficiência máxima 2 Defina uma árvore AVL estabelecendo as suas propriedades vantagens e desvantagens da sua utilização 3 Dada a seguinte árvore binária de busca AVL simule o processo de inser ção e remoção das seguintes chaves na árvore na ordem dada inserção 25 inserção 70 inserção 15 inserção 12 inserção 18 remoção 15 Verifique a cada passo se a propriedade de balanceamento continua sen do mantida Em caso de desbalanceamento indicar o nó desbalanceado e as operações de rotação indicadas para resolver o problema MARIELA INÉS CORTÉS 104 4 Considerando a seguinte sequência de caracteres A Z B Y C X D P E V F Simule a construção passo a passo de uma árvore AVL de carac teres e indique em que situações ocorrem rotações simples ou duplas à direita ou à esquerda dos vários elementos da árvore 5 Considerando a seguinte sequência de números inserção 50 inserção 20 inserção 30 inserção 25 inserção 10 inserção 15 remoção 20 inserção 20 inserção 40 Simule a construção passo a passo de uma árvore AVL de números com a sequência acima e indique em que situações ocorrem rotações simples ou duplas à direita ou à esquerda dos vários elementos da árvore Síntese do capítulo Neste capítulo foram apresentados os conceitos fundamentais sobre árvores e árvores binárias O TAD Árvore Binária de Busca foi definido e implementa do e alguns exemplos de utilização foram ilustrados assim como os diferen tes percursos possíveis sobre a estrutura Adicionalmente a conceituação sobre árvores binárias balanceadas e sua importância em relação ao aumento no desempenho das operações realizadas foi relatada A propriedade de balanceamento e as estratégias para restabelecer o equilibrio na árvore foram detalhados e ilustrados Estrutura de Dados 105 Referências AHO JE Hopcroft and JD Ullman Data structures and algorithms AddisonWesley Reading Mass 1983 CORMEN T H LEISERSON C E RIVEST R L STEIN C 2001 Intro duction to Algorithms McGrawHill e The Mit Press HOROWITZ and S Sahni 1987 Fundamentals of data structures Computer Science Press Editora Campus KNUTH D E 1968 The Art of Computer Programming Vol 1 Funda mental Algorithms AddisonWesley SZWARCFITER J l MARKENZON L 2010 Estruturas de Dados e Seus Algoritmos 3ª Edição LTC ZIVIANI N 2005 Projeto de Algoritmos com implementações em Pas cal e C 2da Edição Thomson Capítulo 7 Busca avançada Estrutura de Dados 109 Objetivos A eficiência alcançada para resolver o problema da busca ou recupera ção de informação a partir de uma estrutura de dados é um indicador da eficiência da estrutura Nesta parte são apresentados métodos específi cos de busca que objetivam reduzir a complexidade em relação aos mé todos de busca padrão apresentados em partes anteriores Em particular é apresentado o uso de tabelas de índices que possibilitam o acesso di reto à informação idealmente No domínio especifico de tratamento de cadeias a busca digital é apresentada como solução para o problema de casamento de padrões Finalmente o funcionamento de estruturas auto ajustáveis é descrito 1 Tabela de dispersão O armazenamento e recuperação da informação são possivelmente as funcionalidades mais importantes requeridas de um computador De forma geral a informação é organizada em estruturas que possibilitam que os dados possam ser recuperados da memória e interpretados quando ne cessário A pesquisa por um determinado dado requer que seja estabeleci do um critério que geralmente é baseado na existência de uma chave de pesquisa15 que possibilita que ocorrências da informação sejam cor retamente identificadas Diversas estratégias podem ser utilizadas para realizar uma pesquisa por registros em uma tabela A escolha pela mais adequada depende prin cipalmente das necessidades e características da aplicação específica Os dois principais fatores que influenciam nesta escolha são o tamanho da entra da ou seja a quantidade de elementos a serem processados e as operações mais frequentemente executadas sobre a estrutura Existem diversos métodos de pesquisa amplamente utilizados Dentre eles a pesquisa sequencial é o método mais simples onde a partir do primei ro registro a pesquisa é realizada em forma sequencial seguindo a ordem apresentada pelos elementos O processo continua até que a chave for en contrada ou a tabela for percorrida completamente sem sucesso Esta estra tégia foi utilizada no método de busca implementado no TAD Lista O esforço 15 A chave de pesquisa é o campo do registro a partir do qual o registro pode ser referenciado de forma unívoca Cada registro no conjunto possui um campo chave único o que possibilita a sua identificação a partir dele MARIELA INÉS CORTÉS 110 requerido nesta busca é On uma vez que no pior cenário a lista precisará ser percorrida na sua totalidade A árvore de busca e suas variantes abordada na Parte 4 é uma estrutura de dados muito eficiente para armazenamento e recuperação de informação Neste caso o custo demandará em média Olog n Tanto a pesquisa sequencial como a aplicada em árvores de busca são baseadas na comparação entre chaves Diferentemente a técnica baseada em 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 A seguir o funcionamento da tabela de dispersã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 a inicial do sobrenome do funcionário A principio é considerado que não existe ordem para a colocação dos expedientes dentro de cada pasta do arquivo Nesse caso o sobrenome seria a chave e a inicial o endereço de armazenamento Em ciência da computação a tabela de dispersão de hashing no in glês é uma estrutura de dados especial que associa chaves de pesquisa a valores Seu objetivo é a partir de uma chave simples fazer uma busca rápida e obter o valor desejado em tempo constante A utilização de tabela de dispersão para o armazenamento e recupera ção da informação visa tornar estas operações mais eficientes em termos de esforço em relação aos outros mecanismos de busca estudados alcançando uma complexidade média de O1 O ganho com relação a outras estruturas associativas como um vetor simples passa a ser maior conforme a quanti dade de dados aumenta Em contrapartida em uma tabela de dispersão é vir tualmente impossível estabelecer uma ordem para os elementos Em outras palavras a função de dispersão estabelece uma indexação sobre as chaves mas não preserva a ordem entre elas O método de pesquisa com uso de transformação de chave envolve duas etapas 1 Desenvolver e aplicar a função de transformação aritmética do valor da chave para um endereço na memória 2 Dependendo da quantidade de chaves e da eficiência da função de transformação na geração de endereços pode ser necessário elaborar uma estratégia de tratamento para colisões16 para tratar os casos em que duas chaves gerem o mesmo endereço Considere a existência de n chaves a serem armazenadas na tabela T de dimensão m A tabela é considerada uma estrutura sequêncial portanto 16 A ocorrência de colisões pode ser abordada do ponto de vista probabilistico O paradoxo do aniversário estabelece que se tomadas aleatoriamente 50 pessoas pelo menos duas pessoas teriam a mesma data de aniversário ou colisão Estrutura de Dados 111 as posições ou endereços se encontram no intervalo 0 m 1 Se o número de 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 arma zenada no endereço x correspondente Tabelas de dispersão são tipicamente utilizadas para indexação de grandes volumes de informação tais como bases de dados Outros exemplos de uso das tabelas de dispersão são as tabelas de transposição em jogos de xadrez para computador 11 A função de dispersão A função de dispersão é a responsável por gerar um índice a partir de deter minada chave A definição da função é de fundamental importância uma vez que se não for adequada para o tratamento dos dados em questão a manipu lação da tabela terá um mau desempenho O ideal para a função de dispersão é que sejam sempre fornecidos ín dices únicos para as chaves de entrada A função perfeita seria a que para quaisquer entradas A e B sendo A diferente de B fornecesse saídas diferen tes Quando as entradas A e B são diferentes e passando pela função de dis persão geram a mesma saída acontece uma colisão De forma simplificada temos que Pos elemento H elemento n onde H é a função de dispersão aplicada ao elemento considerando o tamanho n da tabela Figura 45 MARIELA INÉS CORTÉS 112 No exemplo a função de dispersão17 é aplicada sobre a chave nome para obter um índice de acesso ao vetor onde o registro é armazenado O registro pode agregar vários campos de informação além do campo chave No entanto na prática é difícil encontrar uma função de dispersão perfei ta que consiga espalhar de forma uniformemente esparsa as chaves ao longo da estrutura Dando sequência ao exemplo acima a aplicação da função de dispersão para o nome Luiza pode vir a gerar o mesmo índice do que Luiz 790 provocando uma colisão Esta situação é indesejável uma vez que reduz o de sempenho do sistema No entanto é muito comum acontecer é por isso que diversas técnicas de tratamento de colisões tem sido propostas na literatura Exemplo de função de dispersão Uma função de dispersão muito simples envolve transformar um caracter em um va lor numérico Isto na linguagem C poderia ser feito da seguinte forma int hashExemplochar chave return chave065 Dada sua simplicidade esta função causaria muitas colisões no entanto pode ser uti lizada como parte de uma função mais complexa que possibilite um melhor espalha mento dos dados Para refletir 1 Defina o conceito de tabela de dispersão e descreva o processo envolvido na apli cação desta técnica 2 Estabeleça vantagens e desvantagens em relação a outros mecanismos de armaze namento e recuperação de informação 3 Pesquise na literatura sobre funções de dispersão comumente utilizadas e que tem demostrado desempenho aceitável a Método da divisão b Método da dobra 4 Apresente um exemplo prático de geração de uma tabela de dispersão utilizando os métodos pesquisados no item anterior 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 como uma lista encadeada ou até mesmo árvore árvores balanceadas AVL Em outras oportunidades a colisão é solucionada dentro da própria tabela 17 Na prática funções de dispersão perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável como por exemplo em aplicações de criptografia ou quando o conteúdo da tabela armazenada é conhecido previamente Estrutura de Dados 113 12 Estratégias para resolução de colisões Considerando que a ocorrência de colisões é praticamente inevitável um bom método de resolução de colisões é essencial independentemente da qualidade da função de dispersão utilizada Há diversos algoritmos de resolução de colisão mas os mais conheci dos são os de encadeamento e sondagem a Encadeamento A utilização de listas encadeadas é a solução mais simples para o tratamento de colisões Neste caso a partir do índice em conflito é mantido um ponteiro para uma lista encadeada onde são armazenados os registros em conflito A inserção na tabela requer e inserção dentro da lista encadeada Analogamente a remoção requer atualizar os índices dentro da lista O TAD lista na sua ver são encadeada através de ponteiros foi apresentado na Parte 3 Graficamente a solução de colisões através de listas encadeadas é representada a seguir A situação de colisão entre as chaves Luiz e Luiza se ria resolvida adicionando o registro correspondente à chave repetida na lista associada ao índice Figura 46 Esta solução adiciona um nível de indireção às operações de inserção e recuperação da informação uma vez que o registro não mais é acessado MARIELA INÉS CORTÉS 114 diretamente a partir da chave no entanto o custo de acesso continua se man tendo baixo Estruturas de dados alternativas podem ser utilizadas no lugar das listas encadeadas Por exemplo a partir da utilização de árvores binárias balanceadas AVL é possível melhorar o tempo médio de acesso da tabela dispersão para Olog n ao invés de On demandado no caso da utilização de listas b Técnicas de sondagem Em contrapartida à técnica de encadeamento as técnicas de sondagem para o tratamento de colisões não fazem uso de nenhuma estrutura auxiliar para o armazenamento da informação Em caso de colisão os registros em conflito são armazenados dentro da própria tabela utilizando buscas padronizadas até encontrar um registro vazio ou o registro buscado 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 uma função quadrática incrementando o índice exponencialmente Desta for ma caso a chave procurada não se encontre na posição 10 em uma segun da tentativa será procurada na posição 100 1000 e assim por diante Uma terceira possibilidade envolve a aplicação de uma nova função de dispersão também chamado de double hashing cuja chave de entrada será o valor gerado pela função anterior Esta solução pode ser útil em casos muito específicos com enormes quantidades de dados no entanto a sobrecarga no sistema nem sempre justifica a experiência Para refletir 1 Explique o conceito de colisão e por que acontecem 2 Pesquise as diferentes formas de resolução de colisão e analise suas vantagens e desvantagens Exemplifique 2 Busca 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 estruturado de formas convenientes no intuito de melhorar o desempenho das opera ções Diferentemente no caso da busca digital a chave é constituida de um conjunto de caracteres ou dígitos pertencentes a um alfabeto18 apropriado Neste caso específico a comparação entre chaves é realizada dígito a dígi to individualmente 18 As cadeias aparecem no processamento de texto em linguagem natural dicionários sequenciamento de DNA processamento de imagens etc Em cada domínio um alfabeto específico é utilizado Exemplos de alfabetos 0 1 a b c z 0 1 9 Estrutura de Dados 115 A busca digital funciona de forma similar à busca em dicionários de compondo a palavra letra a letra caracter ou dígito onde a primeira letra da palavra determina um índice de página onde se encontram as palavras inicia das por aquela letra Os métodos de busca digital são particularmente úteis quando as chaves são grandes e de tamanho variável A partir desta pesquisa é possível localizar todas as ocorrências de uma determinada cadeia em um texto com tempo de resposta Olog n em relação ao tamanho do texto Este problema é conhecido como casamento de cadeias no contexto de processamento de cadeias de caracteres O processamento de cadeias de caracteres envolve duas classes de problemas casamento de cadeias do inglês pattern matching e compressão de cadeias O problema de casamento de cadeias envolve a procura pela ocor rência de um determinado padrão em um texto que está sendo editado Formalmente o texto T é considerado um vetor de tamanho n e o padrão P um vetor de tamanho m com m n Os elementos que compõem T e P pertencem a um alfabeto finito de tamanho c Dadas duas cadeias T e P desejase saber as ocorrências de P em T A compressão de texto está relacionada com a representação de um texto original de forma a ocupar menos espaço ou seja utilizando um número menor de bits Métodos mais modernos de compressão de cadeias possibilitam o acesso direto a texto comprimido sem necessidade de descomprimir o texto permitindo melhorar a eficiência de sistemas de recuperação de informação e aumentar a economia de espaço No método de busca digital tanto o padrão procurado quanto o texto são préprocessados a partir da construção de índices de forma a reduzir a complexidade das operações para um custo Olog n No entanto o tempo de préprocessamento é compensado por muitas operações de busca A seguir são apresentados brevemente os tipos de índices mais conhe cidos para o préprocessamento de cadeias de forma a agilizar o desempe nho das buscas 21 Árvore digital A estrutura mais apropriada para realizar a busca digital é através da árvore digital 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 MARIELA INÉS CORTÉS 116 dígitos Supõese que existe em S o total de m dígitos distintos que determi nam o alfabeto ordenado de S Os primeiros p dígitos de uma chave com põem o prefixo de tamanho p da chave Uma árvore digital para S é uma árvore mária T não vazia tal que 3 Se o nó v é o jéssimo filho de seu pai então v corresponde ao dígito dj do alfabeto S 1 j m 4 Para cada nó v a sequência de dígitos definida pelo caminho desde a raiz de T até v corresponde a um prefixo de alguma chave de S Na análise de um texto em linguagem natural 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 Em um caso específico da árvore digital no entanto o mais utilizado temos a árvore digital binária onde o grau da árvore é m 2 O alfabeto considerado neste caso é 0 1 A partir da construção da árvore digital com estas características as chaves a serem consideradas nas buscas envolvem sequências binárias Chaves Árvore digital binária 00 0010 010 010111 010110 00100 11 110 1101 Figura 47 A partir da árvore gerada é possível observar que algumas chaves biná rias são prefixos de outras chaves pertencentes à mesma coleção Por exem plo o caminho da raiz até o nó com conteúdo correspondente à chave 010 que é prefixo da chave 010110 correspondente ao caminho até o nó Cada nó na árvore pertence a uma chave ou mais do conjunto Por exem plo o nó com corresponde à chave 010 e faz parte prefixo das chaves 010111 e também 010110 De acordo com a implementação da árvore digital cada nó na árvore envolve um campo adicional contendo um ponteiro para a informação Estrutura de Dados 117 correspondende à chave detectada Por exemplo no caso do nó existiria um ponteiro de forma a localizar no texto a chave 010 Os ponteiros de nós que não correspondem ao último dígito de uma chave válida seriam nulos NULL Uma vez criada a árvore a busca acontece como resultado do per curso a partir da raiz o filho esquerdo representa o dígito 0 e o filhor à direita representa o dígito 1 Note que a busca localiza não somente uma chave váli da completa mas também prefixos A busca por prefixos pode ser de grande utilidade dependendo da aplicação como por exemplo linguística Para refletir 1 Explique como funciona a busca digital e seu papel no contexto de processamento de cadeias Mencione áreas de aplicação deste tipo de busca 2 Pesquise sobre compressão de textos em linguagem natural 3 Crie graficamente uma árvore digital binária a partir do seguinte conjunto de chaves 00 0000 00010 00011 0101100 0101101 10 101 1010 3 Estruturas autoajustáveis As operações de inserção e remoção de elementos aplicadas sobre uma de terminada estrutura de dado afetam necessariamente a forma da estrutura Já a operação de busca é inocua no sentido em que a principio não produz ne nhuma alteração na forma da estrutura No caso de estruturas autoajustáveis a operação de busca pode alterar a forma da estrutura de dado objetivando melhorar o desempenho em buscas futuras Por exemplo 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 as futuras buscas pelo mesmo componente A partir deste comportamento a complexidade ordinária de uma operação calculada individualmente e de forma independente para o pior caso na sua execução não é mais adequada Em contrapartida a comple xidade amortizada considera a configurações da estrutura ao longo de uma sequência de operações executadas avaliando as consequências de cada execução de forma acumulada O conceito de autoajuste pode ser aplicado a diversas estruturas de dados tais como listas conjuntos e árvores 31 Listas autoajustáveis O TAD Lista foi abordado na Parte 3 Como foi visto o tipo lista pode ser imple mentado utilizando a abordagem de alocação de memória estática vetores MARIELA INÉS CORTÉS 118 ou dinámica ponteiros Considerando que na sua versão mais simples não é estabelecido um critério de ordenação entre os elementos alguns elementos na lista podem ser requisitados mais frequentemente do que outros A partir desta constatação uma lista autoajustável implementa estratégias para redu zir o tempo de acesso em operações subsequentes A estratégia geral consis te em posicionar os nós mais procurados mais próximos do inicio da lista de forma que em futuras buscas possam ser alcançados mais rapidamente Esta estratégia pode ser implementada utilizando diversos métodos O método de mover para frente transfere o nó procurado para o inicio da lista Repare que dependendo da implementação utilizada para implementar a lista esta operação pode ser custosa Por outro lado nós com baixa pro babilidade de acesso podem ser eventualmente acessados tornando mais custosas as buscar por nós com maior probabilidade No método de transposição uma vez acessado o nó procurado este é transferido para a posição imediatamente anterior Na medida em que o nó for acessado mais próximo do inicio será posicionado A implementação do método de contador de frequências envolve a in corporação de um campo adicional na estrutura do nó da lista responsável por manter o número de acessos efetuados ao respectivo nó Este campo é utilizado como chave para a ordenação decrescente dos elementos na lista Ou seja que os nós mas frequentemente acessados são localizados no inicio e portanto mais rapidamente alcançados Alguns métodos híbridos envolvem a combinação dos métodos anterio res de forma a tirar vantagem dos beneficios e reduzir as desvantagens dos métodos no seu formato individual Atividades de avaliação 1 Explique o funcionamento das estruturas de dados autoajustáveis 2 Quais seriam as adaptações requeridas para que o TAD Lista apresentado na Parte 3 se torne TAD Lista Autoajustável a Defina a nova estrutura de dados b Implemente ou adapte as operações necessárias 3 Pesquise sobre uma outra estrutura estudada ao longo desta disciplina que possa se tornar autoajustável Descreva as características de funciona mento e as adaptações necessárias Estrutura de Dados 119 Síntese do capítulo Nesta parte foram apresentadas diversas estratégias para armazenamento e recuperação de informação Inicialmente foram apresentadas as tabelas de dispersão ou hash como uma solução para o acesso direto ou semidi reto à informação a partir da geração de índices obtidos como resultado de um processo de transformação tendo como base o valor chave do registro Mecanismos de tratamento de colisões no caso de geração de índices repe tidos foram indicados Em relação ao processamento de cadeias de caracteres foi apresen tada a teoria sobre busca digital que possibilita estabelecer o casamento de chaves constituídas por caracteres ou dígitos e texto Com este objetivo a estrutura de árvore digital foi apresentada Finalmente o funcionamento de estruturas autoajustáveis com foco na sua exemplificação através de listas foi descrito indicando as estratégias de implementação a serem seguidas De forma geral todos estes mecanismos e estratégias objetivam tornar mais eficiente o armazenamento e posterior recuperação da informação de forma a tornar os algoritmos mais acessíveis e capazes de lidar melhor com a complexidade cada vez maior requerida pelas aplicações atuais Referências AHO JE Hopcroft and JD Ullman Data structures and algorithms AddisonWesley Reading Mass 1983 CORMEN T H LEISERSON C E RIVEST R L STEIN C 2001 Intro duction to Algorithms McGrawHill e The Mit Press HOROWITZ and S Sahni 1987 Fundamentals of data structures Computer Science Press Editora Campus KNUTH D E 1968 The Art of Computer Programming Vol 1 Funda mental Algorithms AddisonWesley SZWARCFITER J l MARKENZON L 2010 Estruturas de Dados e Seus Algoritmos 3ª Edição LTC ZIVIANI N 2005 Projeto de Algoritmos com implementações em Pas cal e C 2da Edição Thomson MARIELA INÉS CORTÉS 120 Sobre a autora Mariela Inés Cortés É doutora em Informática pela Pontifícia Universidade Católica do Rio de Janeiro 2003 e mestre em Sistemas de Computação pelo Intituto Militar de Engenharia do Rio de Janeiro 1999 Sua alma mater é a Universidade Nacional de La Plata onde completou os estudos de gra duação em Ciências da Computação Especialista na área de Engenharia de Software atualmente é professora adjunta na Universidade Estadual do Ceará vinculada ao Curso de Ciências da Computação onde ministra den tre outras a disciplina de Estrutura de Dados Adicionalmente coordena o Laboratório de Qualidade e Padrões de Software LAPAQ e lidera o Grupo de Engenharia de Software e Sistemas Inteligentes GESSI A não ser que indicado ao contrário a obra Estrutura de Dados disponível em httpeducapescapesgovbr está licenciada com uma licença Creative Commons AtribuiçãoCompartilha Igual 40 Internacional CC BYSA 40 Mais informações em httpcreativecommonsorglicensesbysa40deedptBR Qualquer parte ou a totalidade do conteúdo desta publicação pode ser reproduzida ou compartilhada Obra sem fins lucrativos e com distribuição gratuita O conteúdo do livro publicado é de inteira responsabilidade de seus autores não representando a posição oficial da EdUECE F iel a sua missão de interiorizar o ensino superior no estado Ceará a UECE como uma instituição que participa do Sistema Universidade Aberta do Brasil vem ampliando a oferta de cursos de graduação e pósgraduação na modalidade de educação a distância e gerando experiências e possibili dades inovadoras com uso das novas plataformas tecnológicas decorren tes da popularização da internet funcionamento do cinturão digital e massificação dos computadores pessoais Comprometida com a formação de professores em todos os níveis e a qualificação dos servidores públicos para bem servir ao Estado os cursos da UABUECE atendem aos padrões de qualidade estabelecidos pelos normativos legais do Governo Fede ral e se articulam com as demandas de desenvolvi mento das regiões do Ceará Estrutura de Dados Mariela Inés Cortés Computação Computação Estrutura de Dados Universidade Estadual do Ceará Universidade Aberta do Brasil Computação Química Física Matemática Pedagogia Artes Plásticas Ciências Biológicas Geografia Educação Física História 9 12 3