Baixe o app para aproveitar ainda mais
Prévia do material em texto
ESTRUTURA DE DADOS II Professor Me. Rogério de Leon Pereira GRADUAÇÃO Unicesumar Reitor Wilson de Matos Silva Vice-Reitor Wilson de Matos Silva Filho Pró-Reitor de Administração Wilson de Matos Silva Filho Pró-Reitor de EAD Willian Victor Kendrick de Matos Silva Presidente da Mantenedora Cláudio Ferdinandi NEAD - Núcleo de Educação a Distância Direção Operacional de Ensino Kátia Coelho Direção de Planejamento de Ensino Fabrício Lazilha Direção de Operações Chrystiano Mincoff Direção de Mercado Hilton Pereira Direção de Polos Próprios James Prestes Direção de Desenvolvimento Dayane Almeida Direção de Relacionamento Alessandra Baron Head de Produção de Conteúdos Rodolfo Encinas de Encarnação Pinelli Gerência de Produção de Conteúdos Gabriel Araújo Supervisão do Núcleo de Produção de Materiais Nádila de Almeida Toledo Coordenador de conteúdo Danillo Xavier Saes Qualidade Editorial e Textual Daniel F. Hey, Hellyery Agda Design Educacional Nádila de Almeida Toledo; Camila Zaguini Silva Fernando H. Mendes; Rossana Costa Giani Projeto Gráfico Jaime de Marchi Junior José Jhonny Coelho Arte Capa Arthur Cantareli Silva Editoração Thayla Daiany Guimarães Cripaldi Fernando Henrique Mendes Revisão Textual Jaquelina Kutsunugi, Keren Pardini, Maria Fernanda Canova Vasconcelos, Nayara Valenciano, Rhaysa Ricci Correa e Susana Inácio Ilustração Robson Yuiti Saito C397 CENTRO UNIVERSITÁRIO DE MARINGÁ. Núcleo de Educação a Distância; PEREIRA, Rogério de Leon. Estrutura de dados II. Rogério de Leon Pereira. Reimpressão Maringá-Pr.: UniCesumar, 2018. 139 p. “Graduação EaD”. 1. Análise de Sistemas. 2. Estrutura de Dados. 3. EaD. I. Título. ISBN 978-85-8084-578-5 CDD - 22 ed. 005.3 CIP - NBR 12899 - AACR/2 Ficha catalográfica elaborada pelo bibliotecário João Vivaldo de Souza - CRB-8 - 6828 Impresso por: Viver e trabalhar em uma sociedade global é um grande desafio para todos os cidadãos. A busca por tecnologia, informação, conhecimento de qualidade, novas habilidades para liderança e so- lução de problemas com eficiência tornou-se uma questão de sobrevivência no mundo do trabalho. Cada um de nós tem uma grande responsabilida- de: as escolhas que fizermos por nós e pelos nos- sos farão grande diferença no futuro. Com essa visão, o Centro Universitário Cesumar – assume o compromisso de democratizar o conhe- cimento por meio de alta tecnologia e contribuir para o futuro dos brasileiros. No cumprimento de sua missão – “promover a educação de qualidade nas diferentes áreas do conhecimento, formando profissionais cidadãos que contribuam para o desenvolvimento de uma sociedade justa e solidária” –, o Centro Universi- tário Cesumar busca a integração do ensino-pes- quisa-extensão com as demandas institucionais e sociais; a realização de uma prática acadêmica que contribua para o desenvolvimento da consci- ência social e política e, por fim, a democratização do conhecimento acadêmico com a articulação e a integração com a sociedade. Diante disso, o Centro Universitário Cesumar al- meja ser reconhecido como uma instituição uni- versitária de referência regional e nacional pela qualidade e compromisso do corpo docente; aquisição de competências institucionais para o desenvolvimento de linhas de pesquisa; con- solidação da extensão universitária; qualidade da oferta dos ensinos presencial e a distância; bem-estar e satisfação da comunidade interna; qualidade da gestão acadêmica e administrati- va; compromisso social de inclusão; processos de cooperação e parceria com o mundo do trabalho, como também pelo compromisso e relaciona- mento permanente com os egressos, incentivan- do a educação continuada. Seja bem-vindo(a), caro(a) acadêmico(a)! Você está iniciando um processo de transformação, pois quan- do investimos em nossa formação, seja ela pessoal ou profissional, nos transformamos e, consequente- mente, transformamos também a sociedade na qual estamos inseridos. De que forma o fazemos? Criando oportunidades e/ou estabelecendo mudanças capa- zes de alcançar um nível de desenvolvimento compa- tível com os desafios que surgem no mundo contem- porâneo. O Centro Universitário Cesumar mediante o Núcleo de Educação a Distância, o(a) acompanhará durante todo este processo, pois conforme Freire (1996): “Os homens se educam juntos, na transformação do mundo”. Os materiais produzidos oferecem linguagem dialó- gica e encontram-se integrados à proposta pedagó- gica, contribuindo no processo educacional, comple- mentando sua formação profissional, desenvolvendo competências e habilidades, e aplicando conceitos teóricos em situação de realidade, de maneira a inse- ri-lo no mercado de trabalho. Ou seja, estes materiais têm como principal objetivo “provocar uma aproxi- mação entre você e o conteúdo”, desta forma possi- bilita o desenvolvimento da autonomia em busca dos conhecimentos necessários para a sua formação pes- soal e profissional. Portanto, nossa distância nesse processo de cres- cimento e construção do conhecimento deve ser apenas geográfica. Utilize os diversos recursos peda- gógicos que o Centro Universitário Cesumar lhe possi- bilita. Ou seja, acesse regularmente o AVA – Ambiente Virtual de Aprendizagem, interaja nos fóruns e en- quetes, assista às aulas ao vivo e participe das discus- sões. Além disso, lembre-se que existe uma equipe de professores e tutores que se encontra disponível para sanar suas dúvidas e auxiliá-lo(a) em seu processo de aprendizagem, possibilitando-lhe trilhar com tranqui- lidade e segurança sua trajetória acadêmica. Professor Me. Rogério de Leon Pereira Possui graduação em Tecnologia em Processamento de Dados pelo Centro de Ensino Superior de Maringá (1999) e mestrado em Ciência da Computação pela Universidade Estadual de Maringá (2006). Atualmente é analista de informática da Universidade Estadual de Maringá. Tem experiência na área de Ciência da Computação, com ênfase em desenvolvimento de sistemas Web. A U TO R SEJA BEM-VINDO(A)! Dizem que todo homem precisa ter um filho, plantar uma árvore e escrever um livro. O que é um livro senão um filho que a gente cuida, alimenta, coloca embaixo do braço e investe toda a sua energia e aos poucos vê o seu crescimento e amadurecimento? O que é um livro senão uma árvore que de forma inocente (ou não) é plantada na mente e no coração das pessoas e que um dia poderá dar flores, talvez até frutos. O que é um livro senão um aglomerado de páginas com letras que juntas formam pala- vras e com frases e parágrafos formam um... livro... muito óbvio. Essa obra é uma continuação ao trabalho realizado no livro Estrutura de Dados I. Aqui damos seguimento ao assunto de forma mais aprofundada. Abrimos as portas falando sobre os algoritmos de busca em largura e busca em profun- didade, que são as principais técnicas de busca em grafos. Irei apresentar também a fascinante estrutura conhecida como árvore binária, muito utilizada para a manipulação de grandes massas de dados tanto na memória principal como secundária. O próximo passo será investigar alguns algoritmos de pesquisa como a busca sequen- cial, busca binária, árvore binária de busca, dentre outros conceitos pertinentes ao as- sunto. Fecharemos o conteúdo falando sobre algoritmos de ordenação. São tantos e tão inte- ressantes que foram reservadas duas unidades inteiras para eles. Para aproximar mais o conteúdo acadêmico com a realidade do mercado, inserimos dois excelentes artigos que mostram como as técnicas de ordenação e de pesquisa são utilizadas na solução de problemas no dia a dia de um profissional de TI. Espero que goste dessa pequena colherada de conhecimento e que ela sirva para atiçar a sua fome pelo saber, pela tecnologia e pelaciência da computação. APRESENTAÇÃO ESTRUTURA DE DADOS II 8 - 9 SUMÁRIO 8 - 9 UNIDADE I BUSCA EM GRAFOS 15 Introdução 16 Busca em Profundidade 19 Busca em Largura 22 Algoritmo de Dijkstra 28 Considerações Finais UNIDADE II ÁRVORES BINÁRIAS 37 Introdução 37 Árvore Binária 39 Árvore Estritamente Binária 41 Árvore Binária Completa 42 Implementando Árvore Binária em C 49 Uma Árvore Binária Diferente 52 Considerações Finais SUMÁRIO 10 - 11 UNIDADE III OPERAÇÕES DE BUSCA 63 Introdução 63 Conceitos Básicos 66 Operação de Busca Sequencial 67 Busca Sequencial Indexada 69 A Busca Binária 72 Busca Por Interpolação 74 Busca em Árvores 79 Considerações Finais UNIDADE IV TÉCNICAS DE ORDENAÇÃO 85 Introdução 85 Preparando o Ambiente de Testes 94 Ordenação por Bubblesort (Método da Bolha) 97 Ordenação por Selectionsort 99 Ordenação por Mergesort 103 Considerações Finais SUMÁRIO 10 - 11 UNIDADE V TÉCNICAS DE ORDENAÇÃO OTIMIZADAS 109 Introdução 109 Ordenação Por Quicksort 113 Ordenação por Insertionsort 115 Ordenação por Shellsort 119 Considerações Finais 127 CONCLUSÃO 129 REFERÊNCIAS 131 GABARITO U N ID A D E I Professor Me. Rogério de Leon Pereira BUSCA EM GRAFOS Objetivos de Aprendizagem ■ Conhecer os principais algoritmos de busca em grafos e a sua aplicação. Plano de Estudo A seguir, apresentam-se os tópicos que você estudará nesta unidade: ■ Busca em profundidade ■ Busca em largura ■ Algoritmo de Dijkstra 14 - 15 INTRODUÇÃO Essa unidade dá o pontapé inicial no estudo de estruturas de dados mais avan- çadas. Veremos aqui os dois principais algoritmos de busca em grafos que são a base para técnicas mais complexas e eficientes. Veremos de perto o funcionamento do algoritmo de Dijkstra que é uma das melhores soluções de busca de caminhos de menor custo em grafos. Como leitura complementar foi inserido um artigo muito interessante dos professores Figueiredo e Gonzaga. Eles mostram um problema real de torres de transmissão, como o modelaram em um grafo e os algoritmos que usaram para procurar a melhor solução. O artigo é bem extenso e envolve alguns conceitos matemáticos que podem não ser de primeira necessidade para o aluno. Por isso deixei só as partes perti- nentes ao nosso conteúdo e no final há o link para o artigo completo para aqueles que quiserem se aprofundar no assunto. Lembre-se que se um problema puder ser modelado em um grafo, exis- tem diversos algoritmos prontos que podem ser utilizados ou adaptados para solucioná-lo. ©SHUTTERSTOCK 14 - 15 Introdução Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . ©SHUTTERSTOCK 16 - 17 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I BUSCA EM PROFUNDIDADE Um grafo é uma estrutura formada por pelo menos um vértice (nó) e por um conjunto de arestas (arcos) que pode estar vazio. Cada aresta liga sempre dois nós do grafo. No algoritmo de busca em profundidade, o grafo precisa ser conexo, ou seja, a partir de um nó qualquer é possível navegar por suas arestas visitando todos os demais vértices. Essa técnica faz com que todo um segmento do grafo seja visitado até o final antes que uma nova porção seja investigada. O Programa 1.1 mostra o algoritmo em linguagem C da técnica de busca em profundidade. A partir de um primeiro nó, o algoritmo coloca todos os vértices adjacentes em uma pilha e marca esse nó como visitado. Em seguida, ele pega o primeiro nó empilhado e repete o processo. A busca segue até que o alvo seja encontrado ou que a pilha esteja vazia. A função buscaProfunda recebe quatro parâmetros. O primeiro é um pon- teiro chamado grafo com a estrutura a ser pesquisada. Depois é o inteiro alvo que tem o valor que estamos procurando, o inteiro inicio que define de onde a pesquisa deve começar e o parâmetro tamanho que indica quantos nós exis- tem no grafo. 16 - 17 Busca em Profundidade Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . //Função de Busca em Profundidade int buscaProfunda(int *grafo, int alvo, int inicio, int tamanho){ struct str_no pilha[tamanho]; int indice = 0; int achou = 0; //procura o nó inicial while(achou == 0){ if (grafo->id == inicio){ achou = 1; } else { grafo = grafo->proximo; } } achou = 0; //procura o nó alvo pilha[indice] = grafo; indice++; while (indice > 0 && achou ==0){ if (grafo->id == alvo){ achou = 1; } else { while (grafo->proximo != Null){ grafo = grafo->proximo; pilha[indice] = grafo; indice++; } //desempilha grafo = pilha[indice]; indice--; } } return(grafo); } Programa 1.1 – O Algoritmo de Busca em Profundidade A primeira parte do algoritmo não é tão relevante, seu objetivo é encontrar a posição na lista de onde a pesquisa deve ser iniciada. Vamos ver no Programa 1.2 mais a fundo o processo de empilhamento e desempilhamento que são o cerne da busca em profundidade. 18 - 19 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I //procura o nó alvo pilha[indice] = grafo; indice++; while (indice > 0 && achou ==0){ if (grafo->id == alvo){ achou = 1; } else { while (grafo->proximo != Null){ grafo = grafo->proximo; pilha[indice] = grafo; indice++; } //desempilha grafo = pilha[indice]; indice--; } } return(grafo); Programa 1.2 – Busca em Profundidade em detalhes A pilha está vazia, então empilhamos a posição inicial da pesquisa. Temos uma variável indice que é usada para controlar o fluxo na pilha. O laço se repete enquanto houverem itens empilhados ou até que a busca seja concluída com sucesso. Verificamos se o item atual é o item alvo, se for, alteramos o valor da vari- ável achou e o laço será encerrado. No caso contrário o algoritmo visita os nós adjacentes ao nó atual e coloca-os na pilha. Acontece aí o processo de desempi- lhamento no qual o último nó adjacente visitado será o ponto de partida para a próxima pesquisa. Isso faz com que a pesquisa desça por um caminho até encontrar um nó que não tenha mais vértices adjacentes, nesse momento, o algoritmo inicia uma nova busca a partir do último nó empilhado. Observe esse comportamento na Figura 1. 18 - 19 Busca em Largura Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Figura 1: Exemplo de busca em profundidade Fonte: <http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Depthfirst.png/200px-Depthfirst. png> BUSCA EM LARGURA A busca em largura se assemelha ao seu parente mais próximo que acabamos de estudar, a busca em profundidade. A principal diferença é que os nós visitados são enfileirados ao invés de empilhados. Isso garante que sejam percorridos primeiramente todos os nós mais próximos do nó atual, depois os menos dis- tantes, os mais distantes e assim por diante. Observe a Figura 2. A pesquisa foi iniciada no nó 1 usando o algoritmo de busca em largura. Ele irá visitar primeiroo nó 2, depois o 3, o 4 e assim por diante. 20 - 21 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I 1 3 42 5 6 7 8 9 10 11 12 Figura 2: Ordem que os nós são pesquisados na busca em largura Fonte: <http://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg> Se fôssemos aplicar a busca em profundidade no mesmo grafo começando pelo nó 1, a sequência seria: 1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12 e 8. Um resultado bem diferente, não acha? O Programa 1.3 traz o algoritmo de busca em largura implementado na lin- guagem C. Seu funcionamento é o mesmo que o Programa 1.1 com a diferença que substituímos a estrutura de pilha pela fila para armazenar os vértices visita- dos durante a busca no grafo. //Função de Busca em Largura int buscaLargura(int *grafo, int alvo, int inicio, int tamanho){ struct str_no fila[tamanho]; int indice = 0; int achou = 0; //procura o nó inicial while(achou == 0){ if (grafo->id == inicio){ achou = 1; } else { grafo = grafo->proximo; } } achou = 0; 20 - 21 Busca em Largura Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . //procura o nó alvo fila[indice] = grafo; indice++; while (indice > 0 && achou ==0){ if (grafo->id == alvo){ achou = 1; } else { while (grafo->proximo != Null){ grafo = grafo->proximo; fila[indice] = grafo; indice++; } //desenfileira grafo = pilha[0]; for (int i = 1; i < indice; i++){ pilha[i-1] = pilha[i]; } indice--; } } return(grafo); } Programa 1.3 – Busca em Largura Dois algoritmos praticamente idênticos com apenas um pequeno detalhe. Um usa uma estrutura em pilha para guardar os nós visitados e o outro a estrutura de fila. Esse pequeno detalhe faz com que a busca seja totalmente diferente. 22 - 23 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I ALGORITMO DE DIJKSTRA Em 1956, o cientista da computação holandês Edsger Dijkstra concebeu um algo- ritmo que em sua homenagem passou a ser chamado de algoritmo de Dijkstra. Sua publicação ocorreu em 1958 e tem como objetivo solucionar o problema do caminho mais curto entre dois vértices em grafos conexos com arestas de pesos não negativos. O algoritmo de Dijkstra assemelha-se ao de busca em largura que acabamos de estudar, mas é considerado um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. A estratégia gulosa é muito interessante ao se tra- tar de problemas complexos ou para análises em grandes quantidades de dados. Imagine um GPS que precise buscar o caminho do ponto onde você está e um determinado endereço. Internamente o mapa das ruas são armazenadas em forma de grafos e para achar o caminho entre dois pontos basta realizar uma busca no grafo. Porém, como praticamente todas as ruas de uma região são interligadas, a quantidade de caminhos possíveis será muito grande, por isso ignorar cami- nhos de custo inicial elevado ajuda a diminuir de forma significativa a região de busca da melhor solução. O algoritmo de Dijkstra leva em consideração uma matriz de custos. Cada entrada na matriz tem armazenado o custo (peso) da aresta entre dois vértices. Durante a visita aos vértices adjacentes, o programa inclui na fila apenas os vér- tices de menor custo. O Programa 1.4 traz a implementação completa do algoritmo de Dijkstra. Ele tem um menu de opções, permite a criação de um grafo e do peso de suas arestas. Ele calcula os caminhos mais curtos quaisquer dois pontos no grafo. 22 - 23 Algoritmo de Dijkstra Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . //Bibliotecas #include <stdio.h> #include <stdlib.h> #include <math.h> //Variáveis int destino, origem, vertices = 0; int custo, *custos = NULL; //Prototipação void dijkstra(int vertices,int origem,int desti- no,int *custos); void menu_mostrar(void); void grafo_procurar(void); void grafo_criar(void); //Função principal int main(int argc, char **argv) { int opt = -1; //Laço principal do menu do { //Desenha o menu na tela menu_mostrar(); scanf(“%d”, &opt); switch (opt) { case 1: //cria um novo grafo grafo_criar(); break; case 2: //procura os caminhos if (vertices > 0) { grafo_procurar(); } break; } } while (opt != 0); printf(“\nAlgoritmo de Dijkstra finaliza- do...\n\n”); system(“pause”); return 0; } Programa 1.4 – Algoritmo de Dijkstra em C 24 - 25 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I //Implementação do algoritmo de Dijkstra void dijkstra(int vertices,int origem,int destino,int *custos) { int i, v, cont = 0; int *ant, *tmp; int *z; /* vertices para os quais se conhece o caminho minimo */ double min; double dist[vertices]; /* vetor com os custos dos caminhos */ /* aloca as linhas da matriz */ ant = (int*) calloc (vertices, sizeof(int *)); if (ant == NULL) { system(“color fc”); printf (“** Erro: Memoria Insuficiente **”); exit(-1); } tmp = (int*) calloc (vertices, sizeof(int *)); if (tmp == NULL) { system(“color fc”); printf (“** Erro: Memoria Insuficiente **”); exit(-1); } z = (int *) calloc (vertices, sizeof(int *)); if (z == NULL) { system(“color fc”); printf (“** Erro: Memoria Insuficiente **”); exit(-1); } for (i = 0; i < vertices; i++) { if (custos[(origem - 1) * vertices + i] !=- 1) { ant[i] = origem - 1; dist[i] = custos[(origem-1)*vertices+i]; } else { ant[i]= -1; dist[i] = HUGE_VAL;} z[i]=0; } z[origem-1] = 1; dist[origem-1] = 0; /* Laco principal */ do { /* Encontrando o vertice que deve entrar em z */ min = HUGE_VAL; for (i=0;i<vertices;i++){ if (!z[i]){ if (dist[i]>=0 && dist[i]<min) { min=dist[i];v=i; } } } 24 - 25 Algoritmo de Dijkstra Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . /* Calculando as distancias dos novos vizinhos de z */ if (min != HUGE_VAL && v != destino - 1) { z[v] = 1; for (i = 0; i < vertices; i++){ if (!z[i]) { if (custos[v*vertices+i] != -1 && dist[v] + custos[v*vertices+i] < dist[i]) { dist[i] = dist[v] + custos[v*vertices+i]; ant[i] =v; } } } } } while (v != destino - 1 && min != HUGE_VAL); /* Mostra o Resultado da busca */ printf(“\tDe %d para %d: \t”, origem, destino); if (min == HUGE_VAL) { printf(“Nao Existe\n”); printf(“\tCusto: \t- \n”); } else { i = destino; i = ant[i-1]; while (i != -1) { tmp[cont] = i+1; cont++; i = ant[i]; } for (i = cont; i > 0 ; i--) { printf(“%d -> “, tmp[i-1]); } printf(“%d”, destino); printf(“\n\tCusto: %d\n”,(int) dist[destino-1]); } } void grafo_criar(void){ do { printf(“\nInformeo numero de vertices (no minimo 3 ): “); scanf(“%d”, &vertices); } while (vertices < 3 ); if (!custos) { free(custos); } custos = (int *) malloc(sizeof(int)*vertices*ver- tices); //Se o compilador falhou em alocar espaço na memória if (custos == NULL) { system(“color fc”); printf (“** Erro: Memoria Insuficiente **”); exit(-1); } 26 - 27 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I //Preenchendo a matriz com -1 for (int i = 0; i <= vertices * vertices; i++){ custos[i] = -1; } do { system(“cls”); printf(“Entre com as Arestas:\n”); do { printf(“Origem (entre 1 e %d ou ‘0’ para sair): “, vertices); scanf(“%d”, &origem); } while (origem < 0 || origem > vertices); if (origem) { do { printf(“Destino (entre 1 e %d, menos %d): “, vertices, origem); scanf(“%d”, &destino); } while (destino < 1 || destino > vertices || destino == origem); do { printf(“Custo (positivo) do vertice %d para o vertice %d: “, origem, destino); scanf(“%d”,&custo); } while (custo < 0); custos[(origem-1) * vertices + destino - 1] = custo; } } while (origem); } //Busca os menores caminhos entre os vértices void grafo_procurar(void){ int i, j; system(“cls”); system(“color 03”); printf(“Lista dos Menores Caminhos no Grafo Dado: \n”); for (i = 1; i <= vertices; i++) { for (j = 1; j <= vertices; j++) { dijkstra(vertices, i,j, custos); } printf(“\n”); } system(“pause”); system(“color 07”); } 26 - 27 Algoritmo de Dijkstra Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Eu separei para você a parte principal do algoritmo de Djkstra no Programa 1.5. A variável min irá guardar o menor valor encontrado. Ela é inicializada com um valor muito grande. A constante HUGE_VAL está presente na biblioteca math.h e foi criada para essa finalidade. Em seguida, existe um laço de repetição em que é verificado se a distância entre o vértice atual e o vértice adjacente é menor do que o contido na variável min. Se for o valor da variável é atualizado e o processo repete até que o vértice não tenha mais nós adjacentes. min = HUGE_VAL; for (i=0;i<vertices;i++){ if (!z[i]){ if (dist[i]>=0 && dist[i]<min) { min=dist[i];v=i; } } } Programa 1.5 – O coração de Djkstra E na prática como se aplica? Digamos que você trabalhe para uma empresa aérea. Cada aeroporto é um nó e cada voo entre dois aeroportos é uma aresta. Você pode possuir uma tabela na qual conste o preço da passagem entre dois trechos; ou ainda existir uma segunda tabela que tenha a duração dos voos entre as cidades. //Desenha o menu na tela void menu_mostrar(void){ system(“cls”); printf(“Implementacao do Algoritmo de Dijask- tra\n”); printf(“Opcoes:\n”); printf(“\t 1 - Adicionar um Grafo\n”); printf(“\t 2 - Procura Os Menores Caminhos no Gra- fo\n”); printf(“\t 0 - Sair do programa\n”); printf(“? “); } 28 - 2928 - 29 BUSCA EM GRAFOS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I No balcão de venda, o algoritmo de Dijkstra pode procurar a melhor rota entre a origem e o destino levando em consideração o valor da passagem ou o tempo de duração do voo. Imagine a aplicação dessa técnica no ramo da logística, ou no roteamento de pacotes m uma rede comercial ou na escolha do fornecedor com melhor rela- ção custo por tempo de entrega. O algoritmo de Dijkstra é muito utilizado em situações onde é preciso mini- mizar custos ou otimizar recursos. CONSIDERAÇÕES FINAIS Nesta unidade, vimos os dois principais métodos de busca em grafos, a busca em profundidade e a busca em largura. Ambas as técnicas são simples e bem parecidas, alterando apenas a forma como os vetores visitados são armazenados. Esses algoritmos são a base para praticamente todas as demais soluções para a busca de caminho em grafos conexos. O próprio algoritmo de Dijkstra, que tivemos a oportunidade de estudar, é um algoritmo de busca em largura modificado para uma solução específica, que é encontrar o menor caminho entre dois vértices para grafos em que pos- suam pesos nas arestas. O conhecimento dessas técnicas é muito importante, pois, se um problema puder ser modelado na forma de um grafo, existem diversos algoritmos que podem ser utilizados ou adaptados para encontrar a solução, como você verá no artigo Aplicação de métodos de busca em grafos com nós parcialmente orde- nados à locação de torres de transmissão apresentado no final dessa unidade. 28 - 2928 - 29 Separei um artigo muito interessante para você. É um trabalho que mostra na prática como a estrutura de grafos e algoritmos de busca são aplicados para a solução de pro- blemas reais. Como o artigo é muito extenso e o seu conteúdo um pouco denso, resolvi fazer alguns recortes deixando os pontos mais importantes em relação à nossa matéria. Convido você a acessar o link no final do artigo e fazer uma leitura completa e se apro- fundar ainda mais sobre o assunto. APLICAÇÃO DE MÉTODOS DE BUSCA EM GRAFOS COM NÓS PARCIALMENTE ORDENADOS À LOCAÇÃO DE TORRES DE TRANSMISSÃO Por: João Neiva de Figueiredo; Clóvis C. Gonzaga RESUMO Este artigo aborda o problema de locação ótima de torres de transmissão como uma aplicação de métodos de busca em grafos com nós parcialmente ordenados com uma modelagem que aplica a este problema pela primeira vez o conceito de relações de preferência entre nós. São primeiramente apresentados resultados sobre grafos e algoritmos de busca. As restrições eletro- mecânicas e topográficas à obtenção do caminho de custo mínimo são descritas, são definidos os nós, arcos, custos e caminhos, além de outros componentes do grafo e são descritos os algoritmos de otimização utilizados. O trabalho introduz e demons- tra a validade de relações de preferência entre nós, que são utilizadas (juntamente com comparações de custos) no processo de eliminação de caminhos. Este procedi- mento aumenta a eficiência dos algoritmos de otimização utilizados. Introdução Este artigo apresenta algoritmos para otimi- zação da locação de torres de transmissão e baseia-se numa modelagem inovadora do problema de locação de torres como um problema de decisões seqüenciais com a construção recorrente de um grafo atra- vés da aplicação repetida de um operador sucessor. O trabalho introduz um processo de eliminação de caminhos no grafo base- ado em relações de preferência entre nós que não havia sido utilizado anteriormente para resolver este tipo de problema e que resulta em aumento de eficiência na deter- minação de uma linha de transmissão de custo mínimo. O objetivo do trabalho é apresentar uma modelagem original para o problema de locação de torres de trans- missão que apresenta melhorias sobre algoritmos consagrados por incorporar a estes relações de preferência entre nós. Acreditamos que esta forma de modela- gem tem amplas aplicações em outros tipos de problemas. Descrição do problema. O projeto de uma linha de transmissão com- preende diversas etapas: especificação das características elétricas da linha, escolha do traçado, determinação de caracterís- ticas mecânicas das torres, levantamento topográfico e, finalmente, a locação das 30 - 31 torres de transmissão sobre o traçado escolhido. Da etapa de determinação de características mecânicas das torres resulta a definição dos tipos de torres que serão utilizadas na linha.Resulta também desta etapa a especificação detalhada de todos os limites mecânicos que cada tipo de torre pode suportar, as diversas alturas disponí- veis para cada tipo de torre e o custo de cada par (tipo, altura) de torre. As restri- ções mecânicas são numerosas e incluem esforço transversal máximo, esforço verti- cal mínimo para os cabos de transmissão e para os cabos pára-raios, trações longitu- dinais e transversais para cadeias em torres de suspensão bem como outras restrições particulares a torres de ancoragem e de sus- pensão. Os custos de cada torre dependem apenas de seu tipo e altura. A etapa seguinte é a especificação das restrições topográficas com o completo levantamento do perfil do terreno ao longo do traçado da linha. As restrições topo- gráficas incluem a altura de segurança do cabo (altura mínima do cabo ao solo), a topografia do terreno, trechos de locação proibida (como, por exemplo, rios e estra- das a serem cruzados pela linha) e pontos de locação obrigatória. O cabo suspenso entre duas torres toma o formato de uma catenária, que neste trabalho (e normal- mente) é aproximada por uma parábola. Ela deve necessariamente superar uma distân- cia mínima do solo em todos os pontos do perfil topográfico (a altura de segurança). A catenária de segurança é a catenária virtual que tangencia o perfil topográfico, partindo do ponto na torre que representa sua altura decrescida da altura de segurança naquele ponto do traçado. Neste trabalho, o termo catenária é utilizado para significar catená- rias de segurança, as ilustrações mostram torres com catenárias de segurança e as tor- res têm suas alturas decrescidas da altura de segurança. Ao final desta etapa são conhecidas as restrições mecânicas e as restrições topográficas para o problema e têm-se todos os dados para iniciar o pro- cesso de otimização – os tipos e alturas (e conseqüentemente custos) das torres de transmissão, bem como a descrição com- pleta do perfil topográfico do terreno. Os esforços mecânicos a que está subme- tida uma torre somente são determinados quando são conhecidas as localizações e alturas das duas torres adjacentes a ela, ou seja, o tipo e conseqüentemente o custo de uma torre depende de sua localização e também da localização e altura da torre que a precede e da torre que a segue no tra- çado. Conseqüentemente o procedimento de locação de torres passa pelo exame de trechos de perfil topográfico imediata- mente à frente da última torre locada para identificar a melhor opção para a locação da próxima torre e determinar o tipo e o custo da torre anterior. Como será descrito abaixo, modelamos este problema através da utilização de um grafo que incorpora todas as opções possíveis de locação para a linha. Este grafo é criado recursivamente através de um operador sucessor aplicado de forma seqüencial às torres que com- põem o extremo de linha de transmissão mais promissor a cada momento. Após um breve resumo da literatura será descrita a modelagem bem como os algoritmos para solução do problema. O algoritmo de Dijkstra O algoritmo de Dijkstra pode ser aplicado diretamente ao problema. Devido ao fato de o problema ser de natureza con- 30 - 31 tínua, dificilmente dois caminhos terão o mesmo nó terminal. Conseqüentemente haverá poucas eliminações de caminhos, e as listas podem crescer explosivamente. Mesmo com a utilização de tolerâncias para comparações entre nós, o número de eliminações pode ser insuficiente. O melhor método para reduzir as listas consiste na utilização de uma relação de preferência entre nós, descrita abaixo. O algoritmo A* O algoritmo A*, que reduz o número de expansões feitas por Dijkstra, depende de uma subestimativa para o custo de uma linha de transmissão entre um nó dado e o fim do perfil topográfico. Esta subesti- mativa pode ser facilmente obtida através do cálculo do custo de uma linha remanes- cente que tenha mesmo comprimento em um “perfil topográfico perfeito” com ondu- lações acompanhando as catenárias entre as torres. Conclusão Este trabalho apresentou um algoritmo para otimização de locação de torres de transmissão que propõe a otimização global de todo o traçado e utiliza algorit- mos eficientes de busca em grafos, com a incorporação de uma relação de prefe- rência entre nós além de comparações de custo. Este procedimento resulta em um aumento de eficiência na determinação de uma linha de transmissão de custo mínimo. A modelagem em teoria de grafos utilizada foi detalhada, foram descritos os algorit- mos que se beneficiam da incorporação de relações de preferências entre nós, e foi descrita a relação de preferência entre nós com demonstração de sua validade. Referências Bibliográficas (1) Bob, R.; Dabekis, C. & Fullerton, F. (1963). Electronic Computer Permits Optimized Tower Spotting of Electric Transmission Towers. IEEE Transactions on Power Appa- ratus and Systems, 66. (2) Çalis, H. (1992). A Computer Program for Optimization of Tower Spotting. Tese de Mestrado, Gazi University, Ankara, Turquia. (3) Cherdshant, S. (1997). A Computer Pro- gram for the Selection of Optimum Stations and Heights of Transmission Towers. Tese de Mestrado, King Mongkut Institute of Tech- nology, Bangkok, Tailândia. (4) Gonzaga, C. (1978). Busca de Caminhos em Grafos e Aplicações. I Reunião de Mate- mática Aplicada, IBM, RJ. (5) Gonzaga, C. (1973). Estudo de Algorit- mos de Busca em Grafos e Sua Aplicação a Problemas de Planejamento. Tese de Dou- torado, COPPE–UFRJ, Rio de Janeiro. (6) Hart, P.; Nilsson, N. & Raphael, B. (1968). A Formal Basis for the Heuristic Deter- mination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cyber- netics, 4(2). (7) Neiva de Figueiredo, J. (1978). Locação Ótima de Torres de Transmissão Utilizando Teoria de Grafos. Dissertação de Mestrado. COPPE/UFRJ. (8) Neiva de Figueiredo, J.; Gonzaga, C. & Maculan, N. (1979). Localização Ótima de Torres de Transmissão Utilizando Teoria de Grafos. Revista Brasileira de Pesquisa Opera- cional, II(2), 12-22. 32 - 3332 - 33 (9) Nilsson, N. (1971). Problem Solving Methods in Artificial Intelligence. McGraw- -Hill Computer Science Series. FIGUEIREDO, João Neiva de; GONZAGA, Clóvis C. Aplicação de métodos de busca em grafos com nós parcialmente orde- nados à locação de torres de tranmissão. Pesqui. Oper. Rio de Janeiro, v. 23, n. 1, jan. 2003. Available from <http://www. scielo.br/scielo.php?script=sci_arttex- t&pid=S0101-74382003000100015&l- ng=en&nrm=iso>. Access on 06 Fev. 2013. <http://dx.doi.org/10.1590/S0101- 74382003000100015.> 32 - 3332 - 33 1. Qual é a principal diferença entre a Busca em Largura e a Busca em Profundida- de? 2. Em que caso a Busca em Largura é mais eficiente que a Busca em Profundidade? 3. O que diferencia o algoritmo de Dijkstra e a busca em largura? 4. Digite no seu computador o Programa 1.4. Entre com o Grafo (ou parte dele) abaixo e faça simulações de busca de caminho mais curto entre duas cidades. Campo Mourão Cascavel 125 150 175 200 220 90 135 110150 205 275 12530 25 20 20 10 35 90 Foz do Iguaçu Guarapuava Irati Ponta Grossa Curitiba OurinhosLondrinaArapongas Mandaguari Maringá Jandaia do Sul Apucarana Fonte: <http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/IA/ResolProb/MapaParana.gif> U N ID A D E II Professor Me. Rogério de Leon Pereira ÁRVORES BINÁRIAS Objetivos de Aprendizagem ■ Conhecer a estrutura de árvore binária. ■ Aprender sobre árvore estritamente binária. ■ Reconhecer uma árvore binária completa. ■ Implementar uma árvore binária em linguagem C. Plano de Estudo A seguir, apresentam-se os tópicosque você estudará nesta unidade: ■ Árvore Binária ■ Árvore Estritamente Binária ■ Árvore Binária Completa ■ Implementando Árvore Binária em C ■ Uma Árvore Binária diferente 36 - 37 INTRODUÇÃO Nesta unidade, estudaremos uma estru- tura de dados útil para várias aplicações: a árvore binária. Defi niremos algumas formas dessa estrutura de dados e mos- traremos como podem ser implementadas na linguagem C. A árvore como estrutura é muito utilizada para organizar infor- mações armazenadas tanto na memória principal como na secundária. Isso se dá devido ao fato de ser fácil e rápida a pes- quisa de dados em árvores. Daremos foco no entendimento da estrutura e não na sua defi nição matemática. ÁRVORE BINÁRIA Segundo Tenenbaum (1995, p. 303), Uma árvore binária é um conjunto fi nito de elementos que está vazio ou é particionado em três subconjuntos disjuntos. O primeiro subcon- junto contém um único elemento, chamado raiz da árvore. Os outros dois subconjuntos são em si mesmos árvores binárias, chamadas su- bárvores esquerda e direita da árvore original. Uma subárvore esquer- da ou direita pode estar vazia. Cada elemento de uma árvore binária é chamado nó da árvore. A Figura 3 apresenta um exemplo de árvore binária. Essa árvore possui 9 nós, sendo A o nó raiz da árvore. Ela possui uma subárvore esquerda com raiz em B e uma direita com raiz em C. A subárvore com raiz em B possui uma subár- vore esquerda com raiz em D, e a direita com raiz em E. A subárvore com raiz em C possui uma subárvore esquerda vazia e uma subárvore direita com raiz ©shutterstock 36 - 37 Introdução Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . 38 - 39 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II em F. As árvores binárias com raiz em D, G, H e I possuem subárvore direita e esquerda vazias. A C B D E F H IG Figura 3: Um exemplo de árvore binária Fonte: o autor Se A é o nó raiz de uma árvore binária e tem uma subárvore com raiz em B, então se diz que A é pai de B e B é filho esquerda de A. Na mesma forma, se A tem uma subárvore direita com raiz em C, diz-se que A é pai de C e C é filho direita de A. Um nó sem filhos é chamado de folha. Na árvore representada pela Figura 3 os nós D, G, H e I são considerados folhas. Os nós D e E são ambos filhos de B, dessa forma podemos considerá-los como nós irmãos. Também podemos classificar os nós de acordo com a sua hereditariedade. O nó B é ancestral dos nós D, E e G, da mesma forma que esses três nós são descendentes de B. Uma árvore binária é um tipo de grafo que tem regras específicas na sua construção. Cada nó tem no máximo dois filhos e um único pai, excetuando- se o nó raiz da árvore principal que é órfão. 38 - 39 Árvore Estritamente Binária Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Quando se percorre uma árvore a partir da raiz em direção às folhas, diz-se que está caminhando na árvore para baixo ou que está descendo na árvore. De forma análoga, quando se está percorrendo uma árvore a partir de uma de suas folhas em direção à raiz, diz--se que está caminhando para cima ou subindo na árvore. Se fôssemos fazer uma analogia entre uma árvore na informática e uma árvore real (planta), na computação as árvores seriam representadas de cabeça para baixo. ÁRVORE ESTRITAMENTE BINÁRIA Uma árvore é considerada estritamente binária se todo nó que não for folha tenha sempre subárvores direita e esquerda não vazias. Na Figura 4, temos um exemplo de árvore estritamente binária. São considerados folhas os nós C, D, F e G. Os nós A, B e E possuem subárvores esquerda e direita não vazias. A C B D E G F Figura 4: Um exemplo de árvore estritamente binária Fonte: o autor. A árvore apresentada na Figura 3 não pode ser considerada como uma árvore estritamente binária já que o nó C possui uma subárvore esquerda vazia, e o nó E possui uma subárvore direita vazia. 40 - 41 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II A quantidade de nós presentes em uma árvore estritamente binária se dá pela fórmula ( ) 1*2 −= fn em que f é o número de folhas na árvore. Vamos testar essa fórmula a partir da árvore representada pela Figura 4. A árvore possui 4 folhas, quais sejam os nós: C, D, F e G. Aplicando-se a fórmula temos: ( ) 1*2 −= fn Como f = 4, substituímos o valor de f na fórmula: ( ) 14*2 −=n Realizamos a multiplicação e, em seguida, a subtração: ( ) 18 −=n Temos então que: 7=n A árvore possui exatamente 7 nós: A, B, C, D, E, F e G. Também podemos calcular a quantidade de folhas em uma árvore estrita- mente binária pela dedução da fórmula ( ) 1*2 −= fn : ( ) 1*2 −= fn Adicionando 1 em ambos os lados da igualdade: ( ) 11*21 +−=+ fn Efetuando-se o cálculo: ( )fn *21 =+ Dividindo ambos os lados da igualdade por 2: ( ) 2 *2 2 1 fn = + Efetuando-se o cálculo: fn =+ 2 1 40 - 41 Árvore Binária Completa Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Vamos inverter os lados da igualdade para deixar a variável isolada à esquerda: 2 1+ = nf No caso da árvore estritamente binária da Figura 4, sabemos que possui 7 nós. Colocando na fórmula: 2 17 + =f Realizando a soma e, em seguida, a divisão: 2 8 =f Temos que: 4=f A árvore possui exatamente 4 folhas: C, D, F e G. ÁRVORE BINÁRIA COMPLETA O nó raiz de uma árvore binária é considerado como de nível 0. A partir dela, cada nó possui um nível a mais do que o seu pai. Por exemplo, na árvore biná- ria da Figura 5, o nó C está no nível 1, F está no nível 2 e o nó M no nível 3. A profundidade de uma árvore binária é dada pelo maior nível de qualquer folha na árvore. Isso equivale ao tamanho do percurso mais distante da raiz até uma folha qualquer. Dessa forma, a profundidade da árvore da Figura 5 é 3. Quando uma árvore estritamente binária possuir todas as folhas no último nível, ela é chamada de árvore binária completa. A Figura 5 demonstra uma árvore binária completa de profundidade 3. 42 - 43 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II A C B E D I H K J G F M L O N Figura 5: Um exemplo de árvore binária completa Fonte: o autor IMPLEMENTANDO ÁRVORE BINÁRIA EM C Existem várias formas de implementar uma árvore binária. A mais simples dela é usar um vetor de nós. Cada nó possui pelo menos três valores: pai, esquerda e direita. O atributo pai vai apontar para a posição no vetor do pai do nó. O atributo esquerda vai armazenar a posição da raiz da subárvore esquerda, e o atributo direita guarda a posição da raiz da subárvore direita. Vamos adicionar mais um atributo dado que irá armazenar o valor do nó. //Estrutura struct str_no { char dado; int esquerda; int direita; int pai; }; Programa 2.1 – Estrutura do nó 42 - 43 Implementando Árvore Binária em C Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Com a estrutura já definida no Programa 2.1, vamos criar uma variável do tipo vetor de str_no.Esse vetor terá o tamanho definido por uma constante chamada tamanho. Precisaremos também de uma variável do tipo inteiro que servirá de índice para o nosso vetor. //Constantes #define tamanho 100 //Variáveis struct str_no arvore[tamanho]; int indice=0; Programa 2.2 – Variáveis Para inserir um nó na árvore, eu preciso saber o seu valor, quem é o seu pai e se ele é um filho esquerda ou direita. Mesmo sabendo quem é o pai, antes de fazer a inserção no vetor eu preciso encontrar a sua localização. Vou criar uma função chamada arvore_procura que retorna um valor inteiro (posição no vetor) e tem como parâmetro o nome do pai. //Procura nó int arvore_procura(char dado){ if (indice != 0){ for (int i = 0; i<indice; i++){ if (arvore[i].dado == dado) { return (i); } } } else { return (0); } } Programa 2.3 – Procurando um nó na árvore 44 - 45 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II Note que o Programa 2.3 faz uma verificação no valor da variável indice. Se o valor for 0 significa que a árvore está vazia e o valor a ser inserido será a raiz da árvore. A função leva em conta de que o pai está presente na árvore, já que não foi previsto nenhum tipo de retorno de erro para o caso do pai não ser encontrado. Já fizemos a leitura do valor a ser inserido e já sabemos quem é o seu pai e qual a sua descendência. Por meio da função demonstrada no Programa 2.3 pas- samos o valor do pai como parâmetro e obtivemos como retorno a sua posição no vetor. Agora estamos prontos para a inserção do novo nó na árvore. Vamos criar uma função nova, chamada arvore_insere. Ela terá como parâ- metro um valor inteiro que representa a posição do pai no vetor, o valor dado digitado pelo usuário e a sua posição de descendência (se é filho do lado esquerdo ou direito). //Inserir nó void arvore_insere(int pai, char dado, int lado){ switch (lado){ case E: arvore[pai].esquerda = indice; arvore[indice].dado = dado; arvore[indice].pai = pai; arvore[indice].esquerda = -1; arvore[indice].direita = -1; indice++; break; case D: arvore[pai].direita = indice; arvore[indice].dado = dado; arvore[indice].pai = pai; arvore[indice].esquerda = -1; arvore[indice].direita = -1; indice++; break; } } Programa 2.4 – Inserindo um nó na árvore 44 - 45 Implementando Árvore Binária em C Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . No Programa 2.2, criamos uma variável chamada indice que guarda a pri- meira posição livre da arvore. O parâmetro pai recebido na função indica qual a posição do nó pai. Se o novo nó for filho esquerdo, atribuiremos o valor de indice ao atributo esquerdo na arvore na posição pai (linha 5, Programa 2.4). No caso de filho direito, colocamos o valor de indice no atributo direito (linha 13, Programa 2.4). O próximo passo é guardar o nome do nó no atributo dado e a referência do pai. Vamos marcar com -1 os valores de esquerda e direita para identificar que ambos os ponteiros não apontam para uma subárvore. Esses passos estão demonstrados no Programa 2.4 nas linhas 6 a 10 para filho esquerda e 14 a 18 para filho direita. O Programa 2.5 traz uma implementação completa de uma Árvore Binária em linguagem C. Ele traz a declaração de bibliotecas, constantes e variáveis auxi- liares, função principal, função para desenhar o menu de opções dentre muitas outras linhas de código. //Bibliotecas #include <stdio.h> #include <stdlib.h> //Constantes #define tamanho 100 #define E 0 #define D 1 #define R -1 //Estrutura struct str_no { char dado; int esquerda; int direita; int pai; }; //Variáveis struct str_no arvore[tamanho]; int lado,indice=0; int opt=-1; char pai, no; 46 - 47 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II //Prototipação void arvore_insere(int pai, char dado, int lado); int arvore_procura(char dado); void menu_mostrar(void); //Função principal int main(void){ int temp; do { menu_mostrar(); scanf(“%d”, &opt); switch (opt){ case 1: printf(“\nDigite o valor do PAI: “); scanf(“%c”,&pai); scanf(“%c”,&pai); printf(“Digite o valor do NO: “); scanf(“%c”,&no); scanf(“%c”,&no); printf(“Digite o lado da subarvore (E=%d/ D=%d/R=%d): “, E,D,R); scanf(“%d”,&lado); temp = arvore_procura(pai); arvore_insere(temp,no,lado); break; case 2: printf(“Digite o valor do NO: “); scanf(“%c”,&no); scanf(“%c”,&no); temp = arvore_procura(no); printf(“No %c\nFilho Esquerda: %c \nFilho Direita: %c\n\n”, arvore[temp].dado, arvore[arvore[temp].esquerda].dado, arvore[arvore[temp].direita].dado); system(“pause”); break; } }while (opt!=0); system(“pause”); return(0); } 46 - 47 Implementando Árvore Binária em C Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . //Inserir nó void arvore_insere(int pai, char dado, int lado){ switch (lado){ case E: arvore[pai].esquerda = indice; arvore[indice].dado = dado; arvore[indice].pai = pai; arvore[indice].esquerda = -1; arvore[indice].direita = -1; indice++; break; case D: arvore[pai].direita = indice; arvore[indice].dado = dado; arvore[indice].pai = pai; arvore[indice].esquerda = -1; arvore[indice].direita = -1; indice++; break; case R: arvore[indice].dado = dado; arvore[indice].pai = -1; arvore[indice].esquerda = -1; arvore[indice].direita = -1; indice++; break; } } //Procura nó int arvore_procura(char dado){ if (indice != 0){ for (int i = 0; i<indice; i++){ if (arvore[i].dado == dado) { return (i); } } } else { return (0); } } 48 - 49 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II Programa 2.5 – Implementação de Árvore Binária em C LINGUAGEM C Acabamos de ver uma forma de armazenar uma árvore binária em um vetor. Essa implementação é bem simples e rápida, mas longe do ideal. Voltamos ao mesmo problema de estruturas anteriores onde muita memória é alocada na execução do programa para uma aplicação que pode ou não precisar de todo o espaço reservado na memória. O Programa 2.5 procura sempre a primeira posição livre no vetor para posi- cionar um novo nó na árvore. Dessa forma, a ordenação da estrutura estará diretamente ligada à ordem que os nós foram adicionados. //Desenha o menu na tela void menu_mostrar(void){ system(“cls”); for (int i = 0; i < indice; i++){ printf(“| %c “,arvore[i].dado); } printf(“\n1 - Inserir um NO na arvore”); printf(“\n2 - Pesquisar um NO na arvore”); printf(“\n0 - Sair...\n\n”); } 48 - 49 Uma Árvore Binária Diferente Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . UMA ÁRVORE BINÁRIA DIFERENTE Outra forma de armazenar uma árvore binária em um vetor é reservar as posições de acordo com o nível e descendênciade cada nó. O primeiro nó a ser armaze- nado é a raiz da árvore e ele ficará na primeira posição do vetor, lembrando que os vetores em C começam na posição 0. A CB D E F Figura 6: Uma árvore binária com 6 nós e profundidade 3 Fonte: o autor Vamos simular a inserção da árvore representada pela Figura 6 em um vetor de 16 posições. O primeiro nó a ser inserido será a raiz da árvore A e ocupará a posição 0 do vetor. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A Como nosso objetivo é manter a árvore indexada dentro do vetor, vamos reservar a primeira posição p logo após o nó para armazenar o filho esquerdo e a segunda posição p para o filho direito. Assim, para um nó armazenado em uma posição p qualquer, seu filho esquerdo estará na posição p+1 e seu filho direito na posição p+2. Vamos inserir os nós B e C no vetor. ©shutterstock © SH U TT ER ST O CK 50 - 51 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C O nó A está na posição p=0, então é esperado que seu filho esquerdo esteja na posição p+1=1 e o filho direito na posição p+2=2 do vetor, o que é verdade. Vamos inserir agora os nós D e E. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E Usando a fórmula que foi proposta, para encontrar os filhos de B na posição 1 do vetor, o filho esquerdo estará na posição p+1=2 e o direito na posição p+2=3, o que não é verdade, logo a fórmula que propusemos não serve para resolver o problema de ordenação de árvore binária em vetor de dados. Uma árvore binária cresce de forma geométrica já que cada nó tem dois filhos que, por sua vez, são duas subárvores que podem estar vazias ou não. Independente de o filho existir, seu espaço precisa ser reservado no vetor. Como todo nó em uma árvore binária tem dois filhos, vamos modificar a fórmula para 2*p+1 para o filho esquerdo e 2*p+2 para o filho direito, sendo p a posição do nó no vetor. 50 - 51 Uma Árvore Binária Diferente Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Aplicando as novas fórmulas para o nó A que está na posição 0, temos que 2*p+1=1 é a posição de B (filho esquerdo de A) e 2*p+2=2 é a posição de C (filho direito de A). Para B que está na posição 1, temos que 2*p+1=3 que é a posição de D (filho esquerdo de B) e 2*p+2=4 é a posição de D (filho direito de B). O nó C é uma folha, podemos dizer que ele não tem filhos ou que seus filhos são árvores vazias. Como o nosso objetivo é manter o vetor ordenado, a posição dos filhos de C será reservada aplicando a fórmula proposta. Assim a posição 2*p+1=5 ficará disponível para o filho esquerdo de C e 2*p+2=6 para o seu filho direito. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E - - O próximo será D, que também é uma folha. Então será reservado no vetor as posições 2*p+1=7 e 2*p+2=8. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E - - - - O último nó de nível 2 (E) possui um filho direito (F) que será armazenado na posição 2*p+2=10 do vetor criado para a nossa árvore binária. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E - - - - - F No primeiro momento, podemos pensar que essa não é uma boa abordagem. Se a árvore não for binária completa, existirão vários espaços vazios no vetor lembrando uma memória fragmentada. Por outro lado, estaremos ocupando exatamente a mesma quantidade de memória que a implementação anterior. A principal diferença é que nesse modelo os nós da árvore estarão indexados, assim é possível obter as informações de forma rápida e precisa, utilizando-se do índice ao invés de percorrer toda a estrutura. Uma árvore binária também pode ser criada dinamicamente. Basta ter um ponteiro esquerdo e direito que apontará para os filhos e um ponteiro para o pai. Esse material criado pelo Prof. Paulo Feofiloff da USP traz um resumo dos principais termos relacionados a árvores binárias, além de exemplos ilustra- dos e trechos de código em linguagem C. <http://www.ime.usp.br/~pf/algoritmos/aulas/bint.html>. 52 - 5352 - 53 ÁRVORES BINÁRIAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II CONSIDERAÇÕES FINAIS Nesta unidade, foi apresentada ao aluno uma nova estrutura de dados: a árvore binária. Ela lembra muito um grafo, porém essas duas estruturas se diferem pelos seguintes motivos: 1. O grafo pode não ter nenhuma aresta e contém no mínimo um único vértice. 2. Uma árvore pode ser vazia e todos os nós podem ser de no máximo grau 3, sendo que cada nó tem um único pai e dois filhos. Vimos duas formas de representar essa poderosa estrutura pelo uso de vetores. No primeiro modelo o vetor vai sendo preenchido à medida que a árvore é lida. Cada nó entra na árvore na primeira posição livre da variável. A segunda implementação possui uma abordagem focada em indexar os nós dentro do vetor, posicionando-os de acordo com a sua ascendência e descendência. A importância da estrutura de árvore binária e da sua representação inde- xada ficará clara na próxima unidade quando tratarmos dos mais usuais métodos de pesquisa em memória. 52 - 5352 - 53 1. Faça a implementação em linguagem C de uma estru- tura de árvore binária para a criação de uma árvore di- nâmica, seguindo os seguintes passos: a. Crie um atributo para armazenar o valor do nó. b. Crie um ponteiro para o pai. c. Crie um ponteiro para o filho esquerdo. d. Crie um ponteiro para o filho direito. 2. Para cada árvore abaixo, identifique os seus componentes seguindo o exemplo da letra a. a) A CB D Raiz A Nós A, B, C, D Folhas C, D Com um filho B Com dois filhos A Nível 0 A Nível 1 B, C Nível 2 D Nível 3 Profundidade 2 54 - 55 b) A C B D E F H I G Raiz Nós Folhas Com um filho Com dois filhos Nível 0 Nível 1 Nível 2 Nível 3 Profundidade c) A C B D E G F 54 - 55 Raiz Nós Folhas Com um filho Com dois filhos Nível 0 Nível 1 Nível 2 Nível 3 Profundidade d) A C B E D I H K J G F M L ON Raiz Nós Folhas Com um filho Com dois filhos Nível 0 Nível 1 Nível 2 Nível 3 Profundidade 56 - 57 e) A CB D E F Raiz Nós Folhas Com um filho Com dois filhos Nível 0 Nível 1 Nível 2 Nível 3 Profundidade 3. O que uma árvore precisa para ser considerada uma árvore estritamente binária? 4. Quais são as características de uma árvore binária completa? 5. Para cada árvore dada, preencha o seu vetor de forma indexada, conforme o exemplo da letra a. a. A C B D 56 - 57 0 1 2 3 4 5 6 7 8 9 A B C D b. A C B D E F H IG 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c. A C B D E G F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 58 - 59 d. A C B E D I H K J G F M L O N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 e. A CB D E F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Material Complementar MATERIAL COMPLEMENTAR 58 - 59 Algoritmos Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Editora: Elsevier Sinopse: Este livro apresenta um texto abrangente sobre o moderno estudo de algoritmos para computadores. É uma obra clássica, cuja primeira edição tornou-se amplamente adotada nas melhores universidades em todo o mundo, bem como padrão de referência para profissionais da área. Nesta terceira edição, totalmente revista e ampliada, asmudanças são extensivas e incluem novos capítulos, exercícios e problemas; revisão de pseudocódigos e um estilo de redação mais claro. A edição brasileira conta ainda com nova tradução e revisão técnica do Prof. Arnaldo Mandel, do Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo. Elaborado para ser ao mesmo tempo versátil e completo, o livro atende a alunos dos cursos de graduação e pós-graduação em algoritmos ou estruturas de dados. U N ID A D E III Professor Me. Rogério de Leon Pereira OPERAÇÕES DE BUSCA Objetivos de Aprendizagem ■ Aprender os conceitos básicos de busca. ■ Estudar diferentes algoritmos de busca. Plano de Estudo A seguir, apresentam-se os tópicos que você estudará nesta unidade: ■ Conceitos básicos ■ Operação de busca sequencial ■ Busca sequencial indexada ■ A busca binária ■ Busca por interpolação ■ Busca em árvores 62 - 63 INTRODUÇÃO Nesta unidade, estudaremos alguns métodos de como pesquisar grandes quan- tidades de dados em busca de uma determinada informação. Veremos como a organização dos dados torna o processo de busca mais eficiente. Como a operação de busca é uma tarefa muito comum na ciência da computação, o conhecimento desses métodos é de suma importância para todo o profissional que deseja se tornar um bom programador. CONCEITOS BÁSICOS Antes de nos aprofundarmos no estudo de algoritmos de busca, vamos tratar de alguns termos que utilizaremos nesta unidade. Uma tabela ou arquivo é um conjunto de registros. Um registro é um conjunto de dados. Existe uma chave associada a cada registro, se ela estiver dentro do próprio registro ela é chamada de chave interna, chave embutida ou incorporada. No caso da chave ficar fora do registro ela é chamada de chave externa. Para todos os registros dentro de uma tabela pelo menos um dos campos pre- cisa ter um valor único para assim diferenciar cada um dos registros. Esse campo é chamado de chave primária. Por exemplo, vamos imaginar que temos uma tabela de clientes. Cada registro dessa tabela representa um cliente e cada cliente possui um conjunto de dados, conforme a Figura 7. © sh ut te rs to ck 62 - 63 Introdução Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . 64 - 65 OPERAÇÕES DE BUSCA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. III TABELA: CLIENTES Registro CPF Nome Rua CEP Telefone Figura 7: Exemplo da Tabela clientes e os dados de um Registro Posso identificar os clientes pelo nome? Não pode, porque existem homôni- mos, ou seja, pessoas com o mesmo nome como José Maria da Silva, Roberto Carlos dos Santos etc. Também não posso usar a Rua ou o CEP, pois vários clientes podem morar na mesma localidade. Se eu e a minha esposa formos clientes dessa empresa, nosso Telefone também aparecerá mais de uma vez na tabela. Para esse caso específico, sobrou o CPF (Cadastro de Pessoa Física), que é realmente único, não existem duas pessoas no Brasil com o mesmo CPF. Se nenhum dos campos do registro fosse potencial para servir de chave primária, poderíamos criar um novo campo chamado codigo ou id e atribuir um número único para cada um dos registros. Ainda pensando nesse exemplo, imagine que a empresa dona dessas infor- mações pretenda fazer uma ação de marketing e tenha como objetivo atingir apenas os clientes que residam em uma determinada cidade, bairro ou em uma rua específica. Posso estar fazendo uma busca na Tabela clientes pelos campos Rua ou CEP. Quando um atributo com informações não únicas é utilizado em uma pesquisa ele é chamado de chave secundária. Todo campo de um registro em uma tabela pode servir como chave em po- tencial, dependendo da informação desejada ou da regra de busca utilizada. ©s hu tte rst ock 64 - 65 Conceitos Básicos Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Como você deve ter aprendido, as grandes massas de dados ficam armazenados em dispo- sitivos de memória secundária, como disco rígido, disco óptico, fita magnética, memória flash, dentre outros. Porém, todo dado para ser manipulado precisa neces- sariamente estar na memória principal. Como a relação entre as duas memórias é desproporcio- nal, ou seja, um computador tem Gb de memória RAM enquanto possui Tb de memória de armazenamento, somente uma pequena parcela dos dados pode ser analisada por vez. Dessa forma, é muito mais inteligente carregar apenas uma tabela de cha- ves do que todos os registros de um arquivo. Encontrada a referência desejada, busca-se no disco apenas a porção desejada de informação. Alguns algoritmos são especializados em realizar buscas em arquivos de chaves primárias, outros por chaves secundárias. Alguns são mais rápidos em arquivos menores, outros ideais para grandes quantidades de informações. Um algoritmo de busca tem como objetivo, a partir de um argumento x rece- bido, encontrar em uma tabela um registro que possua uma chave x equivalente. Ele irá retornar todos os dados do registro, ou o índice da sua posição em um vetor ou ainda um ponteiro para uma posição na memória. Se não houver no arquivo um registro compatível com o argumento pes- quisado, o algoritmo não obtém sucesso na sua busca e retorna uma mensagem de erro, um índice inválido ou um ponteiro nulo. Segundo Tenenbaum (1995), uma busca com sucesso é chamada recuperação. 66 - 67 OPERAÇÕES DE BUSCA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. III OPERAÇÃO DE BUSCA SEQUENCIAL A busca sequencial é de longe a forma mais simples de pesquisa. Ela pode ser utilizada tanto para o caso em que a tabela está armazenada em um vetor como em uma lista ligada. A partir da primeira posição no vetor (ou do primeiro nó da lista), com- para-se o valor atual da estrutura com o argumento x passado. Repete-se esse procedimento com cada um dos valores até que seja encontrado o valor dese- jado ou o final da tabela. O Programa 3.1 traz um exemplo de busca sequencial em C. A função bus- caSequencial recebe três parâmetros: o vetor vec a ser pesquisado, o argumento arg a ser procurado e o tamanho tam do vetor. São criadas duas variáveis locais. A variável i serve de índice para percorrer o vetor, enquanto a variável achou é usada para identificar se a busca foi con- cluída antes do final do vetor. Como os vetores em C começam pela posição 0, a variável i também foi ini- cializada com esse valor, para que a pesquisa realmente dê início pelo começo do vetor. A variável achou foi inicializada com -1. Durante o laço de repetição é verificado se a variável de controle i atingiu o tamanho máximo tam recebido como parâmetro. O valor de i é incrementando sempre no final do laço, garantindo que a busca percorra o vetor até o final. Adicionalmente o laço possui outra regra de parada que verifica o valor da vari- ável achou. Ela foi inicializada com -1, porém, se o valor for encontrado, a sua posição no vetor será atribuída ao valor de achou. Ao final a função retorna o valor da variável achou. Ele será -1 se a busca tiver falhado ou no caso contrário a posição do registro no vetor. ©shutterstock 66 - 67 Busca Sequencial Indexada Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . //Funçãoode Busca Sequencial int buscaSequencial(int vec[], int arg, int tam){ int i = 0, achou = -1; while ((i < tam) && (achou == -1)){ if (vec[i]==arg){ achou = i; } i++; } return(achou); } Programa 3.1 - Busca Sequencial Se considerarmos que os registros no vetor não estão organizados de forma alguma, a pesquisa poderá encontrar o valor desejado na primeira ou na última posição da estrutura. Imagine que a tabela seja muito grande e buscar alguma informação procurando em todos os registro pode ter um custo computacional muito elevado. Uma maneira de melhorar isso é a técnica de busca sequencial indexada. BUSCA SEQUENCIAL INDEXADA Não é possível prever qual será o valor buscado em uma pesquisa e nem a posi- ção onde o registro está armazenado no vetor, menos ainda se ele está ou não presente na tabela. Tudo depende do que está armazenado e o que se costuma pesquisar. Se em uma tabela de clientes as buscas são feitas por pessoas que habitem na mesma região demográfica para efetuar ações mais pre- cisas e eficazes de marketing, uma boa ideia seria criar um índice específico ordenado por cidade, estado ou CEP. Se o síndico do prédio onde você mora entrega o boleto do con- domínio começando pelos apartamentos do último andar até o 68 - 69 OPERAÇÕES DE BUSCA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. III térreo, seria interessante que houvesse um índice com o número do apartamento ordenado de forma decrescente. Em uma loja de departamentos especializada em produtos de moda feminina é muito provável que o usuário busque uma cliente do sexo feminino ao invés de um homem, por isso os dados devem ser ordenados primeiro por gênero. Se for observado que alguns argumentos específicos sejam procurados com mais frequência, esses registros podem ser movidos para uma região mais pró- xima do início da tabela, fazendo com que futuras buscas sejam cada vez mais rápidas. Tenenbaum (1995) fala de um método em particular, muito simples e que traz bons resultados chamado método da transposição, no qual o regis- tro recuperado com sucesso é trocado pelo registro imediatamente anterior. Imagine um vetor de valores inteiros que esteja ordenado de forma crescente. A busca sequencial procuraria o valor desejado em cada uma das posições até encontrá-lo ou chegar ao final do arquivo, o que ocorrer primeiro. Mesmo no caso do registro não existir na tabela, todo o arquivo será percorrido. Porém, como sabemos que a estrutura está ordenada de forma ascendente, no momento em que for encontrado um número maior do que o que está sendo procurado, não há mais necessidade de continuar a pesquisa, porque certamente o valor procurado não estará no restante da tabela. Nessa linha de raciocínio, podemos dizer que compensa classificar um arquivo antes de pesquisar infor- mações dentro dele. A técnica de busca sequencial indexada consiste em criar uma tabela auxi- liar ao arquivo de dados. Nessa tabela, deve constar pelo menos dois campos: a chave de busca e o endereço do registro na tabela original. A tabela de índice pode ser ordenada de forma ascendente, descendente ou de qualquer outra forma que seja mais compatível com as principais buscas que utilizarão a chave con- tida na tabela auxiliar. Mais uma vez mencionando uma suposta tabela de clientes como exemplo, fisicamente os registros estão gravados em disco pela ordem como os clientes são cadastrados no sistema. Se a busca for efetuada pelo número do CPF do cliente, uma nova tabela é criada contendo o CPF e a posição original do regis- tro na tabela de clientes. 68 - 69 A Busca Binária Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . A BUSCA BINÁRIA A forma mais eficiente de efetuar pesquisa em um arquivo ordenado sem a neces- sidade de tabelas auxiliares é a busca binária. A estratégia consiste em comparar o argumento chave ao elemento do meio da tabela. Se forem iguais, a busca terá terminado com sucesso. No caso contrário, o vetor será divido em duas meta- des, e a pesquisa será repetida na metade inferior se o argumento for menor do que o valor do meio da tabela ou na parte superior se o argumento for maior. A cada iteração, a busca binária reduz a quantidade de possíveis candida- tos pela metade. Vale ressaltar que essa estratégia funciona apenas em estruturas cujos dados se encontram ordenados. Sua implementação em vetores não é muito complexa e um exemplo em C é apresentado no Programa 3.2. Esse algoritmo não pode ser utilizado com listas dinâmicas devido às carac- terísticas da sua estrutura. Mesmo criando um ponteiro especial que aponte para o meio da lista, toda vez que o problema for dividido, a lista precisará ser percor- rida novamente para achar o meio da nova metade da lista, o que torna o tempo de execução do algoritmo muito extenso. Se todos os valores de um vetor estiverem ordenados de forma crescente, uma pesquisa pode ser interrompida assim que um valor maior do que o procurado for visitado. O mesmo acontece de forma análoga para um vetor ordenado de forma decrescente. 70 - 71 OPERAÇÕES DE BUSCA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. III //Função de Busca Binária int buscaBinaria(int vec[], int arg, int tam){ int menor, maior, meio; menor = 0; maior = tam-1; while (menor <= maior){ meio = (menor + maior)/2; if (arg == vec[meio]){ return(meio); } if(arg < vec[meio]){ maior = meio - 1; } else { menor = meio + 1; } } return(-1); } Programa 3.2 - Busca Binária A função buscaBinaria do Programa 3.2 recebe três parâmetros: o vetor vec que será pesquisado, o argumento arg que será procurado e o tamanho tam do vetor. São criadas três variáveis internas, uma para marcar a posição de início (menor) da pesquisa, o limite a ser pesquisado (maior) e para marcar o meio do vetor. A variável menor é inicializada com valor 0, que na linguagem C representa o início do vetor. A variável maior é inicializada com o valor tam-1 já que um vetor de tamanho n vai de 0 até n-1. O laço será repetido enquanto a variável menor for menor ou igual a vari- ável maior. Nele será calculada a posição do meio entre menor e maior. Se o argumento arg estiver na posição meio do vetor vec, a função retorna o valor de meio e o algoritmo concluiu a recuperação. Se a recuperação ainda não foi concluída, é preciso atualizar o valor da vari- ável meio. Como sabemos que o vetor se encontra ordenado, se o argumento arg for menor do que o conteúdo no vetor vec na posição meio, então a busca deverá ser feita entre a posição menor e a metade. Caso contrário, a busca deve continuar entre a metade e o final do vetor. 70 - 71 A Busca Binária Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Vamos simular uma busca binária em um vetor ordenado de 10 posições, demonstrado na Figura 8. O valor do argumento a ser encontrado é 5. a. A variável menor será inicializada com 0 e maior com 9 (tamanho – 1). b. Para o cálculo do meio do vetor fazemos: ( ) 2 maiormenormeio += ( ) 2 90 + =meio ( ) 2 9 =meio 5,4=meio Como a variável meio é do tipo inteiro, a posição que indica a metade do vetor é 4. O valor contido no vetor na posição meio é 16, que é maior do que o argu- mento pesquisado 5. c. Como o valor não foi encontrado, o laço é repetido e a busca se dá entre as posições 0 a 3. ( ) 2 maiormenormeio
Compartilhar