Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Introdução 1 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Estruturas de Dados • EMENTA: Recursividade, Quick sort; Divisão e Conquista, Guloso, Backtracking; Complexidade; Alocação dinâmica de memória: Listas encadeadas; Árvores.. • OBJETIVOS: Aprofundar os conhecimentos em estruturas de dados no sentido de uma sólida formação que os capacitem a construir aplicativos de propósito geral. Levá-los a conhecer os fundamentos teóricos da estrutura de dados e como estes fundamentos implicam na definição de um sistema. • METODOLOGIA DE ENSINO: Nas aulas teóricas os conceitos serão expostos por meio de utilização de lousa, retroprojetor, datashow, sendo disponibilizado para os alunos o material de apoio utilizado. Serão propostas atividades individuais ou em grupo para melhor fixação dos conceitos. As aulas práticas serão no laboratório de informática utilizando como ferramenta de apoio a linguagem de programação C. Todas as aulas práticas serão duas das quatro aulas no período. • SISTEMA DE AVALIAÇÃO: O critério de avaliação deverá ser composto por 03 notas oficiais (AV1, AV2 e AV3), oriundas de instrumentos diversificados de avaliação. Para a composição da média serão consideradas as duas maiores notas obtidas entre a AV1, AV2 e AV3, sendo que as duas maiores notas serão somadas e divididas por 2, considerando-se aprovado o aluno que obtiver média final maior ou igual a 6,0 (seis). 2 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Bibliografia • BIBLIOGRAFIA BÁSICA: • PEREIRA, Silvio do Lago; Estruturas de Dados Fundamentais – Conceitos e Aplicações. 4ª ed. São Paulo, Érica, 2000, 264 p. • ASCENCIO, Ana Fernanda Gomes. Lógica de programação com Pascal. Ed. Makron Books, 1999, 355 p. • VILLAS, Marcos Viana. Estruturas de Dados: Conceitos e Técnicas de Implementação. Ed. Campus, 1993. • Schildt, Herbert. C Completo e Total. São Paulo : Pearson : Makron Books, 2006, c1997 • Aho, Alfred V. The design and analysis of computer algorithms Massachussets, EUA : Addison- Wesley, c1974. • BIBLIOGRAFIA COMPLEMENTAR: • Pereira, Vania C.S. Algorítmos e lógica de programação: 100 exercícios resolvidos em pseudocódigo e linguagem C Isbn: 978-85-912397-0-2. São Paulo, 2011 • ZIVIANI, Nivio. Projeto de algoritmos com implementação em Pascal e C. Ed. Thomson, 2000. • BUCKNALL, Julian. Algoritmos e Estruturas de dados com Delphi. Ed. Berkeley, 2002 3 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Revisão de Pilhas 4 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Pilhas • Uma pilha é uma lista linear em que apenas as operações de acesso, inserção e remoção são possíveis. • Todas estas operações deve ser realizadas num mesmo extremo denominado topo. • Devido às características das operações da pilha, o último elemento a ser inserido será o primeiro a ser retirado. • Estruturas desse tipo são conhecidas como "LIFO" (last in, first out). • Exemplo: • Em uma rua sem saída, tão estreita que apenas um carro passa por vez, o primeiro carro a sair será o último a ter entrado. Observe ainda que não podemos retirar qualquer carro e não podemos inserir um carro de tal forma que ele não seja o último. 5 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações com Pilhas • Operações básicas • Seja P uma variável do tipo pilha e X um elemento qualquer • push(p, x) - Procedimento que insere X no topo de P. (Empilha) • pop(p) - Função que remove o elemento do topo da pilha P devolvendo o valor do topo para a rotina que a chamou. (Desempilha) • top(p) - Função que retorna uma cópia do elemento do topo de P, devolvendo o valor do topo da pilha P para a rotina que a chamou. (Copia) • Operações auxiliares • init(p) – Procedimento que esvazia a Pilha P. (Inicia / Esvazia) • isfull(p) – Função que retorna um valor lógico informando se a pilha está cheia. Verdadeiro se estiver cheia ou Falso caso contrário. (Pilha cheia) • isempty(p) – Função que retorna um valor lógico informando se a pilha está vazia. Verdadeiro se estiver vazia ou Falso caso contrário. (Pilha vazia) 6 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de uso de pilhas Dado um número inteiro, positivo em base decimal, convertê-lo para binário. 13 (decimal) = 1101 (binário) 7 13 2 1 6 2 0 3 2 1 1 2 1 0 # include <stdio.h> # include <stdlib.h> # include "pilhas.h" int main() { int n, r; tpPilha p; printf("Digite um inteiro positivo: "); scanf("%d", &n); init ( &p ); do { r = n % 2; push ( &p, r ); n = n/2; } while (n != 0); printf("\n\nCorrespondente ao Binario => "); while ( isEmpty ( &p ) == 0) { r = pop ( &p ); printf("%d", r); } printf("\n\n\n"); system("pause"); return 0; } Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Pilhas no Controle de Variáveis e Sub-Rotinas 1 # include <stdio.h> 2 void A( ) { 3 int A1, A2; 4 ... 5 } 6 void B ( ) { 7 float B1, B2; 8 ... 9 A ( ); 10 ... 11 } 12 int main( ) { 13 int P1, P2; 14 A ( ); 15 ... 16 B( ); 17 ... 18 } 8 Pilha 1 Pilha 2 UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Revisão de Ponteiros 9 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Alocação de Memória • Da área de memória que é reservada ao programa, uma parte é usada para armazenar as instruções a serem executadas e a outra é destina ao armazenamento de dados. • Quem determina quanto de memória será usado para as instruções é o compilador. • Alocar área para armazenamento de dados, entretanto, é responsabilidade do programador. • Quando a quantidade de memória utilizada pelos dados é previamente conhecida e definida no próprio código-fonte do programa, trata-se de alocação estática. • Quando o programa é capaz de criar novas variáveis durante sua execução, dizemos que a alocação é dinâmica. 10 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Ponteiros • PONTEIRO é ... • uma variável especial que contém o endereço de memória de outra variável. • variável que contém endereços de posições de memória alocadas na memória. 11 VARIÁVEL PONTEIRO endereço de memória de outra variável ptr 1FFA VARIÁVEL DINÂMICA conteúdo do tipo que se deseja “acessar” <sem nome> (endereço 1FFA) 5 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Ponteiros – Comandos básicos < tipo de dado > *< identificador > ; • Declara uma variável do tipo ponteiro. • Pode haver um ponteiro (ou apontador) para qualquer tipo de variável. (void*) malloc(tamanho em bytes); • Aloca dinamicamente, durante a execução do programa, células de memória. • Esta função devolve um ponteiro void que deveser ser convertido para o tipo desejado. • O tamanho em bytes pode ser determinado utilizando a função sizeof() que retorna o tamanh em bytes que um tipo de dados ocupa. Exemplo: int *ptr; ptr = ( int * ) malloc ( sizeof ( int ) ) ; free (ponteiro) • Libera as células de memória alocadas dinamicamente. • Exemplo free ( ptr ); • Para manipulação de valores utilizando ponteiros temos dois operadores: • O operador * devolve o valor contido no endereço apontado pela variável ponteiro; • O operador & devolve o endereço de memória alocado de uma variável. 12 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Estruturas de Dados – TADS Exemplo 13 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include < stdio.h > # include < stdlib.h > int main ( ) { int *x, *y; int a, b; a = 27; b = 43; x = &a; y = &b; printf ( "*x = %d x = %d \n", *x, x ) ; printf ( "*y = %d y = %d \n\n", *y, y ) ; *x = *y ; printf ( "*x = %d x = %d \n", *x, x ) ; printf ( "*y = %d y = %d \n\n", *y, y ) ; *x = 27; y = x ; printf ( "*x = %d x = %d \n", *x, x ) ; printf ( "*y = %d y = %d \n\n", *y, y ) ; system ( "pause" ) ; return 0 ; } Declaração das variáveis ponteiro Recebe o endereço de memória da variável a. Ex.: 4A9B Recebe o endereço de memória da variável b. Ex.: 4AAB atribui a informação que está no endereço 4AAB para o endereço 4A9B a variável y está apontada para o endereço de x 4A9B UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Revisão de Arquivos 14 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Arquivos • Um arquivo é semelhante a um vetor, exceto por alguns motivos: • o vetor fica armazenado na memória RAM; o arquivo fica armazenado em disco; • o vetor deve ter um tamanho fixo, definido em sua declaração; o tamanho do arquivo pode variar durante a execução do programa. • Os vetores são manipulados através de um índice de controle, enquanto os arquivos são manipulados por um ponteiro de registro. • As estruturas de dados tipo arquivo são apropriadas para organizar: • grande quantidade de dados • informações processadas por diversas aplicações • informações que requisitam armazenamento permanente • Vantagens e desvantagens no uso de arquivos • Vantagem: • Os dados não são perdidos entre uma execução e outra do programa. • Desvantagem: • O acesso a disco é muito mais lento do que o acesso à memória. 15 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Arquivos • Tipos de arquivo • Tipo Texto • Estão capacitados a armazenar palavras, frases e também dados numéricos. Os números, entretanto, serão armazenados como um caractere do tipo alfanumérico. Ao serem lidos de um arquivo e passados para a memória, os dados numéricos são convertidos para o seu formato original. • Tipo Binário • usa o sistema binário para armazenar tanto as informações numéricas, quanto as informações literais, através do código ASCII, compostos por uma sequencia de bytes. • Arquivos textos são legíveis devido a forma que os dados foram gravados, mas consumem mais espaço para armazenamento e para acessar uma informação é necessário percorrer sequencialmente o arquivo tornando a busca lenta. • Arquivos binários não são legíveis uma vez que os dados são gravados do mesmo modo que estão na memória e consomem menos espaço de memória para o armazenamento. O acesso a uma informação em um arquivo binário é pode ser direto tornando a busca mais rápida. 16 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Tabela com modos de abertura de arquivos 17 Modo Significado "r" Abre um arquivo texto para leitura. O arquivo deve existir antes de ser aberto. "w" Abrir um arquivo texto para gravação. Se o arquivo não existir, ele será criado. Se já existir, o conteúdo anterior será destruído. "a" Abrir um arquivo texto para gravação. Os dados serão adicionados no fim do arquivo ("append"), se ele já existir, ou um novo arquivo será criado, no caso de arquivo não existente anteriormente. "rb" Abre um arquivo binário para leitura. Igual ao modo "r" anterior, só que o arquivo é binário. "wb" Cria um arquivo binário para escrita, como no modo "w" anterior, só que o arquivo é binário. "ab" Acrescenta dados binários no fim do arquivo, como no modo "a" anterior, só que o arquivo é binário. "r+" Abre um arquivo texto para leitura e gravação. O arquivo deve existir e pode ser modificado. "w+" Cria um arquivo texto para leitura e gravação. Se o arquivo existir, o conteúdo anterior será destruído. Se não existir, será criado. "a+" Abre um arquivo texto para gravação e leitura. Os dados serão adicionados no fim do arquivo se ele já existir, ou um novo arquivo será criado, no caso de arquivo não existente anteriormente. "r+b" Abre um arquivo binário para leitura e escrita. O mesmo que "r+" acima, só que o arquivo é binário. "w+b" Cria um arquivo binário para leitura e escrita. O mesmo que "w+" acima, só que o arquivo é binário. "a+b" Acrescenta dados ou cria uma arquivo binário para leitura e escrita. O mesmo que "a+" acima, só que o arquivo é binário Exemplo de manipulação de Arquivo Binário # include < stdio.h > # include < stdlib.h > # include < string.h > typedef struct { char nome [ 51 ] ; char ra [ 11 ] ; float nota ; int falta ; } tpLista ; 18 int main ( ) { tpLista regChamada; FILE *arqChamada; arqChamada = fopen("alunos.dat", "a+b"); if (arqChamada == NULL) arqChamada = fopen("alunos.dat", "w+b"); if (arqChamada == NULL) { printf ( "\nO arquivo não pode ser criado!\n\n" ) ; system ( "pause" ) ; exit ( 1 ) ; } FILE tipo de dado para uma variável ponteiro para um arquivo fopen função para abrir um arquivo deve receber os parâmetros nome do arquivo e o modo de abertura Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de manipulação de Arquivo Binário Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC do { system ( "cls" ) ; printf ( "Para encerrar digite '.' no campo Nome\n\n" ) ; printf ( "Nome.... : " ) ; fflush ( stdin ) ; gets ( regChamada.nome ) ; if ( strcmp ( regChamada.nome, "." ) != 0 ) { printf ( "Ra...... : " ) ; fflush ( stdin ) ; gets ( regChamada.ra ) ; printf ( "Nota.... : " ) ; scanf ( "%f", ®Chamada.nota ) ; printf ( "Faltas.. : " ) ; scanf ( "%d", ®Chamada.falta ) ; if ( fwrite ( ®Chamada, sizeof ( tpLista ), 1, arqChamada ) == NULL ) break; } } while ( strcmp ( regChamada.nome, "." ) != 0 ) ; 19 fwrite - Função que grava os dados em um arquivo do tipo binário. - Deve receber quatro parâmetros: - variável que contém os dados a serem gravados; - número de bytes dos dados a serem gravados; - número de vezes que a gravação será executada; e - nome do arquivo onde os dados serão gravados. Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de manipulação de Arquivo Binário system ( "cls" ) ; rewind ( arqChamada ) ; while ( 1 ) { fread ( ®Chamada, sizeof ( tpLista ), 1, arqChamada ) ; if ( feof ( arqChamada ) ) break ; printf ( "Ra....: %s\n", regChamada.ra ) ; printf ( "Nome..: %s\n", regChamada.nome ) ; printf ( "Nota..: %.1f\n", regChamada.nota ) ; printf ( "Faltas: %d\n\n", regChamada.falta) ; } fclose ( arqChamada ) ; system ( "pause" ) ; return 0 ; } 20 rewind recoloca o leitor de posição no início do arquivo. fread lê os dados de um arquivo do tipo binário. Deve receber 4 parâmetros: - variável que receberá os dados lidos; - número de bytes dos dados que serão lidos; - número de vezes que a leitura será executada; e - nome do arquivo onde os dados estão gravados. feof informa se o final do arquivo foi atingido ou não, retornando 0 ou 1 para F ou V fclose fecha um arquivo aberto com a função fopen Exemplo de manipulação de Arquivo Texto #include < stdio.h > #include < conio.h > #include < stdlib.h > #include < string.h > int main ( ) { FILE *arq ; char nome [ 30 ] ; int idade, cont = 0 ; float altura ; arq = fopen ( "dados.txt", "w" ) ; if ( arq == NULL ) { printf ( "\nErro na criação do arquivo dados.txt" ) ; getch ( ) ; exit ( 1 ) ; } 21 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de manipulação de Arquivo Texto for ( ; ; ) { system ( "cls" ) ; printf ( "Nome (. para finalizar): " ) ; fflush ( stdin ) ; gets ( nome ) ; if ( strcmp ( nome, "." ) == 0 ) break ; printf ( "Idade: " ) ; scanf ( "%i", &idade ) ; printf ( "Altura: “ ) ; scanf ( "%f", &altura ) ; fprintf ( arq, "%s %i %.2f \n", nome, idade, altura ) ; } fclose ( arq ) ; 22 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de manipulação de Arquivo Texto printf ( "\nAbertura e leitura do arquivo gravado\n" ) ; arq = fopen ( "dados.txt", "r" ) ; if ( arq == NULL ) { printf ( "\nErro na abertura do arquivo dados.dat" ) ; getch ( ) ; exit ( 1 ) ; } while ( !feof ( arq ) ) { fscanf ( arq, "%s %i %f \n", nome, &idade, &altura ) ; printf ( "\n Nome = %s Idade = %i Altura = %.2f", nome, idade, altura ) ; ++cont ; } fclose ( arq ) ; printf ( "\n\nArquivo com %d registros. Fechando o arquivo.\n", cont ) ; getch ( ) ; return 0 ; } 23 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Recursão 24 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Recursão • Trata-se de uma subrotina que chama a si mesma, porém, como todo algoritmo deve ser finito, isto é, deve terminar após ter executado uma quantidade finita de passos. • Exemplos: • Ler um livro: • (a) Ler uma página • (b) Ler uma página e Ler o resto do livro. • Examinar lista: • (a) Examinar um elemento • (b) Examinar um elemento e Examinar lista restante. Uma Imagem Recursiva 25 Uma imagem recursiva Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Recursão • Para garantir que uma chamada recursiva não criará um “looping” que será executado infinitamente, é necessário que ela esteja condicionada a uma expressão lógica que, em algum instante, torna-se-á falsa e permitirá que a recursão termine. 26 # include <stdio.h> # include <stdlib.h> int main ( ) { int num, fat; fat = 1; printf ( "Digite um numero => " ) ; scanf ( "%d", &num ) ; while ( num > 0 ) { fat = fat * num; num - - ; } printf ( "\n\nFatorial = %d.\n\n", fat ); system ( "pause" ) ; return 0 ; } # include <stdio.h> # include <stdlib.h> int fat ( int n ) { if ( n == 0 ) return 1; else return ( n * fat ( n-1 ) ) ; } int main ( ) { int num; printf ( "Digite um numero => " ) ; scanf ( "%d", &num ) ; printf ( "\n\nFatorial = %d.\n\n", fat ( num ) ); system ( "pause“ ) ; return 0; } Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC • Invocações geradas e valores retornados para o cálculo de fat ( 5 ) . Fatorial é o produto dos números naturais desde 1 até o inteiro N. Por definição 0! = 1. Exemplo : 5! = 5 * 4 * 3 * 2 * 1 ⇒ 5! = 120. 5! = 5 * 4! 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0! int fat ( int n ) { if ( n == 0 ) return 1; else return ( n * fat ( n-1 ) ) ; } Recursão 27 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Fat (5)⇒ 5 * fat (4)⇒ 5 * 24 ⇒ 120 Fat (4)⇒ 4 * fat (3)⇒ 4 * 6 ⇒ 24 Fat (3)⇒ 3 * fat (2)⇒ 3 * 2 ⇒ 6 Fat (2)⇒ 2 * fat (1)⇒ 2 * 1 ⇒ 2 Fat (1)⇒ 1 * fat (0)⇒ 1 * 1 ⇒ 1 Fat (0)⇒ 1 Quando aplicar recursão? • É preciso analisar o problema e verificar se realmente vale a pena encontrar uma solução recursiva. • A decisão de usá-la ou não deverá ser tomada após a comparação das possíveis soluções recursiva e iterativa. • Se bem utilizada, pode tornar o algoritmo claro, simples e conciso. • Embora a recursão seja uma ferramenta bastante interessante para resolução de problemas, nem sempre ela poderá ser empregada , pois a solução mais eficiente é através do modo iterativo. 28 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de uso de recursão - MDC • MDC – Máximo Divisor Comum • O primeiro tem que ser maior que o segundo; • Dividir o primeiro pelo segundo; • O segundo passa a ser o primeiro e o segundo será o resto da divisão; • Quando o segundo for igual a zero o primeiro será o MDC. 29 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include <stdio.h> # include <stdlib.h> int mdc ( int p, int s ); int main ( ) { int x, y ; printf ( "Digite o 1o. numero => " ) ; scanf ( "%d", &x ) ; printf ( "\nDigite o 2o. numero => “ ) ; scanf ( "%d", &y ) ; printf ( "\n\nMDC = %d\n\n", mdc ( x, y ) ) ; system ( "pause" ) ; return 0; } int mdc ( int p, int s ) { if ( s > p ) return ( mdc ( s, p ) ); else if ( s == 0 ) return ( p ); else return ( mdc ( s, p % s ) ); } Exercícios: Recursão - 1 30 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC 1) Escrever uma função recursiva chamada Potencia que receberá os parâmetros X e Y (argumentos inteiros e positivos), retornando o resultado, usando a seguinte definição: Potencia retorna X, se Y=1 ou Potencia retorna X * Potencia(X,Y-1). 2) Qual será o valor impresso após a execução do programa abaixo? # include <stdio.h> # include <stdlib.h> int f_rec ( int x, int y ) { if (x == 0) return ( y ); else return ( f_rec ( x-1, y+1 ) ); } int main( ) { int x, y, k; x = 7; y = 1; k = f_rec ( x, y ); printf("Resultado => %d\n\n", k); system("pause"); return 0; } 3) Escreva uma função void recursiva que receba um número inteiro positivo n, e exiba na tela os números inteiros entre n e 0, inclusive. Exemplo n = 5 será exibido 5 4 3 2 1 0 Exercícios: Recursão - 2 4) Considerando a função a seguir, a chamada p(5) causa: void p ( int n ) { if ( n != 0 ) { p ( n – 2 ) ; printf("%d", n ) ; } } a) Apenas a exibição dos números 1, 3 e 5 nessa ordem b) A exibição dos números 1, 3 e 5 nessa ordem, seguido de erro de estouro de pilha c) Apenas a exibição dos números 5, 3 e 1 nessa ordem d) A exibição dos números 5, 3 e 1 nessa ordem, seguido de erro de estouro de pilha e) Apenas erro de estouro de pilha 5) Faça uma função recursiva para achar um elemento num vetor. A função deve retornar o índice do elemento no vetor ou -1 caso ele não exista. 31 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exercícios: Recursão - 3 6) Qual será o valor impresso após a execução do programa ao lado? # include<stdio.h> # include <stdlib.h> int x = 0, a; int rec ( int n, int i ); int main( ) { a = rec (5,2); printf("Resultado = %d\n\n",a); system("pause"); return 0; } int rec ( int n, int i ) { if ( i > 9 ) return ( x ); else { x = n + i ; return ( rec ( n , i + 1 ) ); } } 32 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exercícios: Recursão - 4 33 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC 7) O que será impresso após a execução do programa abaixo, sabendo que x = “arara” ? # include <stdio.h> # include <stdlib.h> # include <string.h> int pal(char a[6], int ini, int fim); int main( ) { char x[6]; int i, f, result; gets(x); i = 0; f = strlen(x)-1; result = pal(x, i, f); if (result) printf("Verdadeiro\n\n"); else printf("Falso\n\n"); system("pause"); return 0; } int pal(char a[6], int ini, int fim) { if (a[ini] == a[fim]) if (ini == fim) return 1; else return pal(a, ++ini, --fim); else return 0; } UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Quick Sort 34 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Quick Sort • É um método dos mais utilizados para ordenação de valores e de forma geral um dos mais eficientes. • Trata de um método de ordenação baseado no conceito da Divisão e Conquista e também em trocas (como na ordenação “bubble sort”). • Para a ordenação dos dados primeiramente o vetor deve ser dividido em tres partes onde: • Uma parte deve conter apenas um elemento identificado como pivô. • Uma parte deve conter todos os elementos com valores menores ou iguais ao pivo. Todos estes valores devem estar antes do índice que contém o valor do pivô. • Uma parte deve conter todos os elementos com valores maiores ao pivô. Todos estes valores devem estar depois do índice que contém o valor do pivô. • Atendidos os requisitos acima aplica-se recursivamente a técnica em cada um dos subvetores, enquanto a quantidade de elementos for maior ou igual a dois. 35 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Quick Sort • Escolha do pivô pode feita aleatóriamente ou o elemento do meio do vetor. • A partir da escolha do pivô inicia-se as comparações entre os valores da seguinte forma: • Comparar v[0], v[1], ... até encontrar um elemento v[a] > pivô; • Comparar, a partir do final do vetor, os elementos v[n-1],v[n-2], ... Até encontrar v[b]<=pivô. • Uma vez encontrados os valores trocar v[a] com v[b] • Retomar a busca, para cima a partir de v[a+1], e para baixo, a partir de v[b-1]; • Terminar o processo de busca, quando os valores de a e b se inverterem, sendo que o valor do pivô estará em sua posição correta em relação aos valores da vetor conforme as regras descritas no slide anterior. 36 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Quick Sort 37 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC void quick(int v[MAX], int inicio, int fim) { int baixo, alto, meio, pivo, k; baixo = inicio; alto = fim; meio = (int) ((baixo + alto) / 2); pivo = v[meio]; while (baixo <= alto) { while (v[baixo] < pivo) baixo++; while (v[alto] > pivo) alto--; if (baixo < alto) { k = v[baixo]; v[baixo++] = v[alto]; v[alto--] = k; } else if ( baixo == alto ) { baixo++; alto--; } } if(alto > inicio) quick(v, inicio, alto); if(baixo < fim) quick(v, baixo, fim); } Quick Sort 38 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC baixo alto meio v[0] v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] v[9] 0 8 4 41 21 93 95 31 43 45 13 11 85 41 > 31 e 11 < 31, então trocar 41 e 11 2 7 4 11 21 93 95 31 43 45 13 41 85 93 > 31 e 13 < 31, então trocar 93 e 13 3 4 4 11 21 13 95 31 43 45 93 41 85 95 > 31 e 31 = 31, então trocar 95 e 31 1 2 1 11 21 13 31 95 43 45 93 41 85 21 = 21 e 13 < 21, então trocar 21 e 13 0 1 0 11 13 21 31 95 43 45 93 41 85 4 9 6 11 13 21 31 95 43 45 93 41 85 95 > 45 e 41 < 45, então trocar 95 e 41 4 5 4 11 13 21 31 41 43 45 93 95 85 7 9 8 11 13 21 31 41 43 45 93 95 85 95 = 95 e 85 < 95, então trocar 95 e 85 7 8 7 11 13 21 31 41 43 45 93 85 95 95 = 93 e 85 < 93, então trocar 93 e 85 7 8 7 11 13 21 31 41 43 45 85 93 95 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include <stdio.h> # include <stdlib.h> # define MAX 8 void quick ( int v [ MAX ], int inicio, int fim ); int main ( ) { int vetor [ MAX ] = { 12, 1, 56, 16, 8, 19, 23, 49 }; int i; printf ( "Vetor Desordenado:\n" ); for ( i = 0; i < MAX; i++ ) printf ( "%d ", vetor [ i ] ); printf ( "\n\n" ); quick ( vetor, 0, MAX – 1 ); printf ( "\n\nVetor Ordenado:\n" ); for ( i = 0; i < MAX; i++ ) printf ( "%d ", vetor [ i ] ); printf ( "\n\n" ); system ( "pause" ); return 0; } void quick ( int v [ MAX ], int inicio, int fim ) { int baixo, alto, meio, pivo, k; baixo = inicio; alto = fim; meio = ( int ) ( ( baixo + alto ) / 2 ); pivo = v [ meio ]; while ( baixo <= alto ) { while ( v [ baixo ] < pivo ) baixo ++; while ( v [ alto ] > pivo ) alto --; if ( baixo <= alto ) { k = v [ baixo ]; v [ baixo ++ ] = v [ alto ]; v [ alto -- ] = k; } else if ( baixo == alto ) { baixo ++; alto --; } } if ( alto > inicio ) quick ( v, inicio, alto ); if ( baixo < fim ) quick ( v, baixo, fim ); } Exemplo 1 39 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include <stdio.h> # include <stdlib.h> # include <string.h> # define MAX 8 void quick ( char v[MAX][15], int inicio, int fim ); int main( ){ char vetor[ MAX ] [ 15 ] = {"Lucas", "Mariano", "Alberto", "Douglas", "Leonardo", "Mateus", "Flavio", "Luiz"}; int i; printf ( "Vetor Desordenado:\n" ); for ( i = 0; i < MAX; i++ ) printf ( "%s\n", vetor [ i ] ); printf ( "\n\n" ); system ( "pause" ); quick ( vetor, 0, MAX-1 ); system ( "cls" ); printf ( "Vetor Ordenado:\n" ); for ( i = 0; i < MAX; i++ ) printf ( "%s\n", vetor[i] ); printf ( "\n\n" ); system ( "pause" ); return 0; } void quick ( char v [ MAX ] [ 15 ], int inicio, int fim ){ int baixo, alto, meio; char k [ 15 ], pivo [ 15 ]; baixo = inicio; alto = fim; meio = ( int ) ( ( baixo + alto ) / 2 ); strcpy ( pivo, v [ meio ] ); while ( baixo <= alto ) { while ( strcmp ( v [ baixo ], pivo ) < 0 ) baixo ++; while ( strcmp ( v [ alto ], pivo ) > 0 ) alto --; if ( baixo <= alto ) { strcpy ( k, v [ baixo ] ); strcpy ( v [ baixo ++ ], v [ alto ] ); strcpy ( v [ alto -- ], k ); } else if ( baixo == alto ) { baixo ++; alto --; } } if ( alto > inicio ) quick ( v, inicio, alto ); if ( baixo < fim ) quick ( v, baixo, fim ); } Exemplo 2 40 UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Listas encadeadas 41 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Alocação de Memória • Antes de abordarmos listas encadeadas vamos relembrar os conceitos de alocação de memória e ponteiros. • Da área de memória que é reservada ao programa, uma parte é usada para armazenar as instruções a serem executadas e a outra é destina ao armazenamento de dados. • Quem determina quanto de memória será usado para as instruções é o compilador. • Alocar área para armazenamento de dados,entretanto, é responsabilidade do programador. • Quando a quantidade de memória utilizada pelos dados é previamente conhecida e definida no próprio código-fonte do programa, trata-se de alocação estática. • Quando o programa é capaz de criar novas variáveis durante sua execução, dizemos que a alocação é dinâmica. 42 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Ponteiros • PONTEIRO é ... • uma variável especial que contém o endereço de memória de outra variável. • variável que contém endereços de posições de memória alocadas na memória. 43 VARIÁVEL PONTEIRO endereço de memória de outra variável ptr 1FFA VARIÁVEL DINÂMICA conteúdo do tipo que se deseja “acessar” <sem nome> (endereço 1FFA) 5 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Ponteiros – Comandos básicos < tipo de dado > *< identificador > ; • Declara uma variável do tipo ponteiro. • Pode haver um ponteiro (ou apontador) para qualquer tipo de variável. (void*) malloc(tamanho em bytes); • Aloca dinamicamente, durante a execução do programa, células de memória. • Esta função devolve um ponteiro void que deve ser ser convertido para o tipo desejado. • O tamanho em bytes pode ser determinado utilizando a função sizeof() que retorna o tamanh em bytes que um tipo de dados ocupa. Exemplo: int *ptr; ptr = ( int * ) malloc ( sizeof ( int ) ) ; free (ponteiro) • Libera as células de memória alocadas dinamicamente. • Exemplo free ( ptr ); • Para manipulação de valores utilizando ponteiros temos dois operadores: • O operador * devolve o valor contido no endereço apontado pela variável ponteiro; • O operador & devolve o endereço de memória alocado de uma variável. 44 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo 45 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include <stdio.h> # include <stdlib.h> # include <string.h> int main ( ) { int *x, *y; x = ( int * ) malloc ( sizeof ( int ) ) ; y = ( int * ) malloc ( sizeof ( int ) ) ; *x = 27 ; *y = 43 ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; *x = *y ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; *x = 27 ; y = x ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; free ( x ) ; system ( "pause" ) ; return 0 ; } # include <stdio.h> # include <stdlib.h> int main ( ) { int * x, * y ; int a, b ; a = 27 ; b = 43 ; x = &a ; y = &b ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; *x = *y ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; *x = 27 ; y = x ; printf ( "Valor: %d - %d \n\n", *x , *y ) ; system ( "pause") ; return 0 ; } Exemplo 46 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC # include <stdio.h> # include <stdlib.h> # include <string.h> int main ( ) { char *x, *y; x = ( char * ) malloc ( 12 * sizeof ( char ) ) ; y = ( char * ) malloc ( 12 * sizeof ( char ) ) ; strcpy ( x, "Estruturas" ) ; strcpy ( y, "de Dados" ) ; printf ( "%s %s\n\n", x, y ) ; strcpy ( y, x ) ; printf ( "%s %s\n\n", x, y ) ; strcpy ( y, "de Dados" ) ; printf ( "%s %s\n\n", x, y ); x = y ; printf ( "%s %s\n\n", x, y ) ; free( x ) ; system ( "pause" ) ; return 0 ; } Exercícios: Ponteiros - 1 • Codifique um programa que contenha uma variável ponteiro que aponte para um vetor de 5 elementos do tipo inteiro, insira dados neste vetor e mostre os mesmos. • Codifique um programa que contenha um vetor de 5 elementos do tipo ponteiro para um char, insira dados neste vetor e mostre os mesmos. 47 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exercícios: Ponteiros - 2 O que será impresso após a execução do programa abaixo? # include <stdio.h> # include <stdlib.h> # include <string.h> int main ( ) { int *p1, *p2, p3 ; char *x1, *x2, x3 [ 7 ] ; p1 = ( int * ) malloc ( sizeof ( int ) ) ; p2 = ( int * ) malloc ( sizeof ( int ) ) ; x1 = ( char * ) malloc ( 7 * sizeof ( char ) ) ; x2 = ( char * ) malloc ( 7 * sizeof ( char ) ) ; *p1 = 7 ; strcpy ( x1,"teste" ) ; *p2 = 15 ; strcpy ( x2, "aula" ) ; p3 = 11 ; strcpy ( x3, "prova" ) ; p1 = p2 ; p2 = &p3 ; strcpy ( x2, x3 ) ; strcpy ( x1, x3 ) ; printf ( "%d \n", *p1 ) ; printf ( "%d \n", *p2 ) ; printf ( "%d \n", p3 ) ; printf ( "%s \n", x1 ) ; printf ( "%s \n", x2 ) ; printf ( "%s \n", x3 ) ; system ( "pause" ) ; return 0 ; } 48 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Listas Encadeadas • Por meio de ponteiros podemos alocar espaço para uma informação na memória e liberar este mesmo espaço quando não for mais necessário. • Quando precisamos guardar várias informações na memória, independente da quantidade, podemos utilizar uma estrutura conhecida como Lista Encadeada. • Uma lista encadeada é uma sequência de informação armazenadas em algum lugar da memória, sendo que as mesmas estão ligadas entre si por um endereço (pointer). • Um lista encadeada é criada a partir da estrutura de um registro (estrutura STRUCT). 49 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Estrutura de uma lista encadeada • A estrutura mais básica deste registro conterá dois tipos de campos: • O primeiro tipo serão os campos utilizados para armazenar as informações propriamente ditas e • O segundo tipo será um campo do tipo ponteiro que irá armazenar o endereço da próxima informação existente na memória. • Para declarar a estrutura de uma lista encadeada devemos criar um tipo struct como por exemplo: struct reg { char nome[51]; int idade; char sexo; struct reg *proximo; } tpLista; 50 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Início proximosexoidadenome proximosexoidadenome proximosexoidadenome Exemplo de Lista Encadeada – Declarações iniciais #include <stdio.h> #include <stdlib.h> typedef char tpElem ; typedef struct registro { tpElem dado ; struct registro *prox ; } tpLista ; void insere ( tpLista *noatual, tpElem x ) ; void mostra ( tpLista *noatual ) ; tpLista* procura(tpLista *noatual, tpElem x) ; int retira ( tpLista *noatual, tpElem x ) ; void esvazia( tpLista *noatual ) ; tpLista *lista = NULL ; 51 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função main( ) int main( ) { tpElem valor ; insere( lista, 'b' ) ; insere( lista, 'd' ) ; insere( lista, 'c' ) ; insere( lista, 'a' ) ; mostra( lista ) ; printf( "\n\nDado a ser procurado: " ) ; scanf( "%c", &valor ) ; if ( procura ( lista , valor ) == NULL ) printf( " Nao achou...\n\n" ) ; else printf( " Achou...\n\n" ) ; fflush( stdin ) ; printf( "Dado a ser retirado: " ) ; scanf( "%c", &valor ) ; if ( retira ( lista , valor ) == 0 ) printf( " Nao encontrado...\n\n\n" ) ; else printf( " Valor retirado...\n\n\n" ) ; mostra( lista ) ; esvazia( lista ) ; printf( "\n\n\n" ) ; system( "pause" ) ; return 0 ; } 52 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função insere( ) void insere ( tpLista *noatual, tpElem x ){ tpLista *novono ; if ( noatual == NULL ) { lista=( tpLista * ) malloc( sizeof( tpLista )); lista->dado = x ; lista->prox = NULL ; } else { while( noatual->prox != NULL ) noatual = noatual->prox ; novono=(tpLista *) malloc(sizeof(tpLista));novono->dado = x ; novono->prox = NULL ; noatual->prox = novono ; } } 53 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função mostra( ) void mostra ( tpLista *noatual ) { printf( "Valores atuais na lista => " ) ; while( noatual != NULL ) { printf( "%c ",noatual->dado ) ; noatual = noatual->prox ; } } 54 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função procura( ) tpLista* procura(tpLista *noatual, tpElem x) { while ( noatual != NULL ) { if ( x == noatual->dado ) return noatual ; else noatual = noatual->prox ; } return NULL ; } 55 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função retira( ) int retira ( tpLista *noatual, tpElem x ) { tpLista *libera ; if ( noatual == NULL ) return 0 ; else if ( x == noatual->dado ) { libera = noatual ; lista = noatual->prox ; free( libera ) ; return 1 ; } else { while ( noatual->prox != NULL ){ if ( x == noatual->prox->dado ) { libera = noatual->prox ; noatual->prox = libera->prox ; free( libera ) ; return 1 ; } else noatual = noatual->prox ; } } return 0 ; } 56 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de Lista Encadeada – função esvazia( ) void esvazia( tpLista *noatual ) { while ( noatual != NULL ) { lista = noatual->prox ; free( noatual ) ; noatual = lista ; } } 57 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC inicio anterior nome idade sexo proximo anterior nome idade sexo proximo anterior nome idade sexo proximo Lista duplamente encadeada • A lista duplamente encadeada, é baseada em um registro (struct) contendo dois campos do tipo ponteiro e os campos que armazenarão os dados. • Cada nó da lista deve estar ligado a seu antecessor e a seu sucessor, ou seja, cada nó tem um ponteiro para o nó anterior e um ponteiro para o próximo nó. • Assim é possível percorrer a lista do início ao fim e vice-versa. 58 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – Declarações iniciais typedef char tpElem ; typedef struct registro { tpElem dado ; struct registro *ant ; struct registro *prox ; } tpLista ; void insere ( tpLista *noatual, tpElem x ) ; void mostra ( tpLista *noatual ) ; tpLista* procura(tpLista *noatual, tpElem x) ; int retira ( tpLista *noatual, tpElem x ) ; void esvazia( tpLista *noatual ) ; tpLista *lista = NULL ; 59 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função main() int main( ) { tpElem valor, resposta ; insere( lista, 'a' ) ; insere( lista, 'b' ) ; insere( lista, 'c' ) ; insere( lista, 'd' ) ; insere( lista, 'e' ) ; insere( lista, 'f' ) ; insere( lista, 'g' ) ; insere( lista, 'h' ) ; mostra( lista ) ; printf( "\n\nDado a ser procurado: " ) ; fflush(stdin); scanf( "%c", &valor ) ; if ( procura ( lista , valor ) == NULL ) printf( "* * * Nao achou * * *\n\n" ) ; else printf( "* * * Achou * * *\n\n" ) ; fflush( stdin ) ; printf( "Dado a ser retirado: " ) ; scanf( "%c", &valor ) ; if ( retira ( lista , valor ) == 0 ) printf( "* * * Nao encontrado * * *\n\n\n" ) ; else printf( "* * * Valor retirado * * *\n\n\n" ) ; mostra( lista ) ; esvazia( lista ) ; system( "pause" ) ; return 0 ; } 60 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função insere() void insere ( tpLista *noatual, tpElem x ){ tpLista *novono ; novono=(tpLista *) malloc(sizeof(tpLista)); novono->dado = x ; if ( noatual == NULL ) { lista = novono; lista->ant = NULL ; lista->prox = NULL; } else { while( noatual->prox != NULL ) noatual = noatual->prox ; novono->ant = noatual; novono->prox = NULL ; noatual->prox = novono ; } } 61 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função procura() tpLista* procura(tpLista *noatual, tpElem x){ while ( noatual != NULL ) { if ( x == noatual->dado ) return noatual ; else noatual = noatual->prox ; } return NULL ; } 62 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função mostra() void mostra ( tpLista *noatual ){ tpLista *noant; printf( "Sequencia normal ====> " ) ; while( noatual != NULL ){ printf( " %c ",noatual->dado ) ; noant = noatual->ant; noatual = noatual->prox ; } printf( "\nSequencia invertida => " ) ; while (noant != NULL) { printf( " %c ",noant->prox->dado ) ; noant = noant->ant; } printf( " %c ",lista->dado ) ; } 63 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função retira() int retira ( tpLista *noatual, tpElem x ){ tpLista *libera ; if ( noatual == NULL ) return 0 ; else if ( x == noatual->dado ){ libera = noatual ; lista = noatual->prox ; lista -> ant = NULL; free( libera ) ; return 1 ; } else{ while ( noatual->prox != NULL ){ if ( x == noatual->prox->dado ) { libera = noatual->prox ; noatual->prox = libera->prox ; if (libera->prox != NULL) libera->prox->ant = libera->ant; free( libera ) ; return 1 ; } else noatual = noatual->prox ; } } return 0 ; } 64 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lista Duplamente Encadeada – função esvazia() void esvazia( tpLista *noatual ){ while ( noatual != NULL ){ lista = noatual->prox ; free( noatual ) ; noatual = lista ; } } 65 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Árvores 66 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Introdução • Listas encadeadas, Filas e Pilhas, têm como base as listas lineares, podendo ser estáticas ou dinâmicas. Mesmo tendo uma série de aplicações na manipulação de dados alguns problemas são observados: • A lista sequencial é eficiente para pesquisa de dados, mas não apresenta bom desempenho para inserir e remover dados; • A lista encadeada é eficiente para inserir e remover dinamicamente de dados, mas não apresenta bom desempenho para pesquisar dados. • A estrutura de dados Árvore é uma lista não linear com desempenho mais eficiente para as operações de inserção, busca e remoção de dados, pois representam um conceito de hierarquias. 67 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Exemplo de uma árvore de estados brasileiros 68 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão • Uma árvore é composta por um conjunto de nós. Uma árvore contém um nó inicial identificado por raiz, podendo ter ou não outros nós, chamados de subárvores. • Usualmente uma árvore é representada graficamente com a raiz para cima.Raiz e Subárvores 69 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Subárvores Raiz • Uma árvore é um conjunto finito de um ou mais nós de tal modo que os conjuntos de nós desdobrados a partir da raiz são chamados de subárvores. • Seguindo o conceito acima, uma subárvore também é uma árvore e assim sucessivamente. Subárvores 70 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Subárvore Raiz Subárvore Subárvore • A raiz de uma árvore é chamada de pai dos nós de suas subárvores. • As raízes das subárvores de um nó pai são chamados de filhos deste nó. • Os filhos de um mesmo nó pai são denominados irmãos. • Duas regras a respeito de pais: • A raiz não tem pai. • Todos os outros nós têm somente um pai. • Um nó que não tem filho é chamado de folha. Nós Pai, Filhos, Irmãos e Folhas 71 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão FILHOS PAI IRMÃOS Nós Pai, Filhos, Irmãos e Folhas 72 Nó Pai Nós Filhos Paraíba Pará, Bahia, Alagoas Pará Amapá, Goiás Bahia - Alagoas Paraná, Maranhão, Ceará Amapá Amazonas, Piauí, Roraima, Rondônia Goiás - Paraná - Maranhão Acre, Sergipe Ceará - Amazonas - Piauí - Roraima - Rondônia - Acre - Sergipe - Irmãos Pará, Bahia, Alagoas Amapá, Goiás Paraná, Maranhão, Ceará Amazonas, Piauí, Roraima, Rondônia Acre, Sergipe Folhas Bahia Goiás, Paraná, Ceará Amazonas, Piauí, Roraima, Rondônia, Acre, Sergipe Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Grau de um nó e Grau de uma árvore • Grau de um nó corresponde ao número de subárvores do próprio nó, ou seja a quantidade de filhos que este nó tem. • Um nó folha tem grau 0, visto que mão tem filhos. • O grau da árvore é definido pelo nó, de maior grau, que ela possui. 73 GRAU DA ÁRVORE: 4 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Pará grau 2 Amapá grau 4 Acre grau 0 • Nível ou profundidade de um nó é definido a partir da raiz da árvore que é identificado por zero. • Os níveis seguintes são definidos com base na soma de uma unidade ao nível do seu nó pai. Nível de um nó 74 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Nível 3 Nível 2 Nível 1 Nível 0 Altura de um nó e Altura uma árvore • A altura de um determinado nó em uma árvore é a distância entre o nó e o seu descendente mais afastado, ou seja, o caminho desde o nó até o descendente mais distante. Um nó folha, consequentemente tem altura 0 • A altura ou profundidade de uma árvore é definida com base no nível máximo entre todos os nós da árvore, ou seja, é a altura da raiz 75 ALTURA DA ÁRVORE: 3 Nó Altura Paraíba 3 Pará, Alagoas 2 Amapá, Maranhão 1 Bahia, Goiás, Paraná, Ceará, Amazonas, Piauí, Roraima, Rondônia, Acre, Sergipe 0 Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Floresta • Quando eliminamos um nó raiz de uma árvores, as suas subárvores formam duas árvores disjuntas, ou sejam árvores separadas. • A este conjunto de árvores disjuntas damos o nome de floresta. • Por exemplo, se eliminarmos o nó raiz da árvore de bandeiras dos estados brasileiros, teremos uma Floresta formada por três árvores disjuntas. 76 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Pará Maranhão Formas de representação: Hierárquica 77 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre CearáParaná Bahia SergipeRoraimaPiauí Goiás Amazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão • Também conhecido como Diagrama de Venn ou Conjuntos aninhados Formas de representação: Diagrama de Inclusão 78 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Paraíba Bahia Alagoas Maranhão Sergipe Acre CearáParaná Pará Goiás Amapá Roraima Piauí Amazonas Rondônia Formas de representação: Parenteses aninhados 79 ( Paraíba ( Pará ( Amapá ) ( Goiás ( Piauí ) ) ) ( Bahia ) ( Alagoas ( Ceará ( Acre ) ( Sergipe ) ) ) ) Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre SergipePiauí Amapá Pará Goiás Paraíba Bahia Alagoas Ceará Árvores: Exercícios • Observe a árvore abaixo, representada na forma hierárquica, e responda: a) qual a altura da árvore? b) quantos nós folhas a árvore possui? c) em qual nível está o nó que contem a letra Q? d) qual o grau do nó que contém a letra E? e) os nós que contém as letras H, L, R, Q, S e G são todos irmãos? Justifique sua resposta. 80 A J P B ED T C H L S G I F R Q U MY Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Árvores: Exercícios • Observe a árvore abaixo, representada na forma de parênteses aninhados, monte a árvore na forma de representação hierárquica e responda: a) quais os nós folha? b) o grau da árvore? c) quais os filhos do nó que contém a letra C? ( A (B) ( C (D (G) (H)) (E) (F (I)) ) ) 81 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Árvores: Exercícios • Observe a árvore abaixo, representada na forma hierárquica, e monte o diagrama de inclusão 82 C E B DA H G I JG I F I Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC • O que caracteriza uma árvore como ÁRVORE BINÁRIA são as suas conexões com os outros nós. • Para cada nó, uma árvore binária é permitido no máximo duas subárvores. • Alguns nós possuem apenas uma subárvores. • Em uma árvore binária é necessário sempre distinguir a subárvore esquerda e direita. • As definições quanto a raiz, pai, filho, irmãos, folhas, grau, nível e altura, são as mesmas já vistas. Árvore Binária 83 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre SergipePiauí Amapá Pará Goiás Paraíba Alagoas Ceará • Consideramos uma árvore binária cheia se todos os nós tiverem duas subárvores, exceto os nós folhas, que estarão na mesma altura. Árvore Binária Cheia 84 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre Ceará SergipeRoraima PiauíAmazonas Rondônia Alagoas Amapá Paraíba Pará Maranhão Bahia Goiás Paraná Árvores de Busca Binária • Árvore binária, é denominada ÁRVORE DE BUSCA BINÁRIA se: • Todosos elementos armazenados na subárvore esquerda são menores que do que o elemento armazenado na raiz; • Todos os elementos armazenados na subárvore direita são iguais ou maiores que do que o elemento armazenado na raiz. • As subárvores esquerda e direita também são árvores de busca binária. 85 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre Bahia Sergipe Piauí GoiásAmapá Paraíba Maranhão Amazonas Paraná Alagoas Ceará RoraimaPará Rondônia Árvore de Busca Binária - Exercício • Assinale quais são as árvores de busca binária 86 a) F J E G H I B CA c) F C E B DA H G I J b) I C M S B DA R O d) 5 2 4 2 31 7 9 6 5 8 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC • Analise os dados representados pelo diagrama de inclusão, construa a representação na forma hierárquica e para casa árvore responda: a) Qual a altura da árvore?; b) Quantos nós tem cada nível?; c) Qual a raiz da árvore? ; d) É uma árvore binária?; e) Se for uma árvore binária: É uma árvore cheia?; É uma árvore de busca binária? Obs. Considere a disposição de cada nó na representação gráfica como sendo filho esquerdo ou direito. Árvore de Busca Binária - Exercício 87 Profa. Vânia Cristina de Souza Pereira - 2012 - Material de Apoio ao Aluno - Notas de Aula – Pesquisa e Ordenação C F EB A G Da) A CB D F Eb) 1 2 9 3 4 10 13 5 6 11 7 8 12 1415 c) Atravessamento em Árvores de Busca Binária • Uma vez criada uma árvore, como fazer para percorrer todos os seus nós? • Que critérios usar? Ir inicialmente para a esquerda ou direita? De cima para baixo? 88 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre PiauíGoiásAmapá Maranhão Amazonas Paraná Alagoas Ceará RoraimaPará Rondônia Atravessamento em Árvores Binárias • Significa percorrer de forma sistemática, por cada um de seus nodos, realizando um certo processamento. • Tipos básicos de atravessamento: • em-ordem • pré-ordem • pós-ordem • Os tipos de atravessamento são facilmente compreendidos se fizermos uma analogia entre eles e as notações segundo uma expressão aritmética pode ser escrita: infixa, prefixa e pósfixa. 89 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Atravessamento • Considerando a expressão infixa A + B, podemos usar a seguinte representação na forma de árvore binária: • O atravessamento em-ordem da árvore será o acesso aos dados da seguinte maneira: • Vai para o nó esquerdo, mostra o valor do nó, vai para o nó direito (ERD). • Exemplo: A + B • O atravessamento pré-ordem da árvore será o acesso aos dados da seguinte maneira: • Mostra o valor do nó, vai para o nó esquerdo, vai para o nó direito (RED). • Exemplo: + A B • O atravessamento pós-ordem da árvore será o acesso aos dados da seguinte maneira: • Vai para o nó esquerdo, vai para o nó direito, mostra o valor do nó (EDR). • Exemplo: A B + 90 + A B Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Atravessamento Préordem 91 Maranhão, Amazonas, Alagoas, Acre, Amapá, Ceará, Goiás, Paraná, Pará, Roraima, Piauí, Rondônia Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre PiauíGoiásAmapá Maranhão Amazonas Paraná Alagoas Ceará RoraimaPará Rondônia 1 2 3 4 5 6 7 11 12 109 8 Atravessamento Emordem 92 Acre, Alagoas, Amapá, Amazonas, Ceará, Goiás, Maranhão, Pará, Paraná, Piauí, Rondônia, Roraima Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre PiauíGoiásAmapá Maranhão Amazonas Paraná Alagoas Ceará RoraimaPará Rondônia 7 4 2 1 3 5 6 10 11 128 9 Atravessamento Pósordem 93 Acre, Amapá, Alagoas, Goiás. Ceará, Amazonas, Pará, Rondônia, Piauí, Roraima, Paraná, Maranhão Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Acre PiauíGoiásAmapá Maranhão Amazonas Paraná Alagoas Ceará RoraimaPará Rondônia 12 6 3 1 2 5 4 9 8 107 11 • Monte as ABB e faça os atravessamentos préordem, emordem e pósordem. a) 12, 4, 8, 26, 2, 5, 20, 22, 10, 13 b) F, H, I, B, C, A, G, B, E c) Ivani, Paulo, Marli, Carla, Ester, Alice, Sofia, Denis d) Percorrendo-se uma ABB foram produzidas as seguintes sequências emordem ( A B C D E F G H I J L ) e pósordem ( A B D E C G H L J I F ) . A partir destas informações monte a ABB. e) Ache as expressões geradas a partir da árvore abaixo desenhada após atravessarmos através dos tipos préordem , emordem e pósordem. Atravessamentos - Exercícios 94 + a b +f g h * c + * *d Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas typedef char tpElem; typedef struct registro { struct registro* esq; tpElem dado; struct registro*dir; } tpArvore; tpArvore *raiz = NULL; 95 Estrutura básica de Árvore de Busca Binária Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Inserção • É uma operação bastante simples. Basta verificar se a árvore não está vazia. • Se estiver, a inserção será na própria raiz • Se a árvore não estiver vazia, deve-se verificar se o novo elemento é menor do que a raiz • Sendo verdadeiro, a inserção será na sub-árvore esquerda • Sendo falso, a inserção será na sub-árvore direita. 96 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Inserção void insere ( tpArvore **t, tpElem x ) { if ( *t == NULL ) { *t = ( tpArvore * ) malloc ( sizeof ( tpArvore ) ); ( *t ) -> esq = NULL; ( *t ) -> dir = NULL; ( *t ) -> dado = x; } else if ( x < ( *t ) -> dado ) insere( & ( ( *t ) -> esq ), x ); else insere( & ( ( *t ) -> dir ), x ); } 97 Inserção de dados em uma Árvore de Busca Binária Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Busca • Considerando uma árvore de busca binária T e um elemento x a ser procurado entre seus nós, existem 4 possibilidades: • Se T é uma árvore vazia, não há o que procurar; • Se a raiz de T armazena o elemento x, a solução é imediata; • Se x é menor que o valor da raiz T, a busca prossegue na subárvore esquerda de T; • Se x é maior que o valor da raiz T, a busca prossegue na subárvore direita de T. 98 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Busca tpArvore* busca ( tpArvore *t, tpElem x ) { if ( t == NULL ) return NULL; else if ( t -> dado == x ) return t; else if ( x < t -> dado ) return busca ( t -> esq, x ); else return busca ( t -> dir, x ); } 99 Inserção de dados em uma Árvore de Busca Binária Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC 100Operações Básicas - Atravessamento void emordem ( tpArvore *t ) { if (t != NULL) { emordem ( t -> esq ); printf (" %c ", t -> dado ); emordem ( t -> dir ); } } void preordem ( tpArvore *t ) { if ( t != NULL ) { printf (" %c ", t -> dado ); preordem ( t -> esq ); preordem ( t -> dir ); } } void posordem ( tpArvore *t ) { if( t != NULL ) { posordem ( t -> esq ); posordem ( t -> dir ); printf (" %c ", t -> dado ); } } Atravessamentos em uma Árvore de Busca Binária Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações Básicas - Remoção • Podemos considerar que a remoção de um nó de uma árvore é a rotina mais trabalhosa para ser desenvolvida e compreendida. • Ainda assim, após analisarmos todos os possíveis casos, a remoção parecerá bastante simples. • Por uma questão de simplificação , vamos admitir que inicialmente o elemento a ser removido encontra-se na raiz da árvore de busca binária T, então, as seguintes hipóteses devem ser avaliadas: • A raiz não possui filhos: • A solução é imediata. Podemos removê-la e anular T; • Se a raiz possui um único filho: • Podemos remover o nó raiz e o nó filho toma seu lugar; • Se a raiz possuir dois filhos, não é possível quem ambos assumam o lugar do pai. Neste ponto surgem algumas perguntas: • Qual das duas subárvores deve assumir o lugar do nó pai removido? • O que deve ser feito com a subárvore que não foi a escolhida? • Seu nó ficaria órfão? 101 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações básicas - Remoção • A resposta para as questões anteriores é: • Devemos buscar o nó que armazena o menor elemento na subárvore direita de T, este nó deve ser removido e o elemento armazenado por ele entrará na raiz da árvore T. • Para entender a solução adotada precisamos lembrar da definição de árvore de busca binária. • Não podemos ter elementos maiores nem iguais à raiz numa subárvore esquerda; • Não podemos ter elementos menores que a raiz numa subárvore direita. • Então, se tomarmos o menor elemento da subárvore direita e o posicionarmos na raiz, então continua valendo a definição. • Sabemos que o maior elemento numa árvore binária ordenada encontra-se no nó que ocupa a posição mais à direita possível. • Este nó certamente não terá um filho direito, pois se o tivesse não seria o maior da árvore; • Pode, entretanto, ter um filho esquerdo (menor). 102 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Operações básicas - Remoção void remover ( tpArvore **t, tpElem x ) { tpArvore *aux; if ( *t != NULL ) { if ( x < ( *t ) -> dado ) remover ( & ( *t ) -> esq, x ); else { if ( x > ( *t ) -> dado ) remover ( & ( *t ) -> dir, x ); else { if ( ( *t ) -> esq != NULL && ( *t ) -> dir != NULL ) { aux = minimo ( ( *t ) -> dir ); ( *t ) -> dado = ( aux -> dado ); remover ( & ( *t ) -> dir, ( *t ) -> dado ); } else { aux = *t; if ( ( *t ) -> esq == NULL ) *t = ( *t ) -> dir; else *t = ( *t ) -> esq; free ( aux ); } } } } } 103 tpArvore* minimo ( tpArvore *t ) { if ( t == NULL ) return NULL; else if ( t -> esq == NULL ) return t; else return minimo ( t -> esq ); } Remoção de dados em uma Árvore de Busca Binária Função auxiliar para identificar o menor valor da sub arvore direita I D P B G L T A C F H J O R E M Q S N I D P B G L T A C F H J O R M Q S N 104 I D P B G L T A C F H J O R M Q S N I D P B G L A C F H J O M Q S N R 105 J D P B G L A C F H O M Q S N R I D P B G L A C F H J O M Q S N R 106 UNIVERSIDADE NOVE DE JULHO - UNINOVE Pesquisa e Ordenação Material disponível para download em: www.profvaniacristina.com Árvores Balanceadas (AVL) 107 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC • Inserir dados em uma árvore busca binária de forma aleatória pode gerar uma árvore tendendo somente para um lado, ou seja, uma das subárvores (direita ou esquerda) terá mais nós que a outra. • Uma árvore de busca binária não balanceada tem um custo alto para acessar os dados, pois a probalbilidades de acesso não são identicas entre si. • Por exemplo: Árvores Balanceadas - AVL 108 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC E G J I L M A C D B N P OF H G F E H M A C B N P O D LI J Árvore Balanceada Árvore Degenerada • Para procurar o nó contendo, por exemplo, a letra L o percurso na árvore balanceada será muito mais rápido que o percurso na árvore desbalanceada. • Na primeira árvore foram utilizados menos passos que na segunda árvore, portanto árvores binárias são mais eficientes quando estão balanceadas. Árvores Balanceadas - AVL 109 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC E G J I L M A C D B N P OF H G F E H M A C B N P O D LI J Árvore Balanceada Árvore Degenerada Árvores Balanceadas - AVL 110 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC • Uma árvore é considerada uma AVL se para cada nó da árvore, as alturas das subárvores esquerda e direita sejam iguais ou tenham uma diferença de apenas uma unidade. Exemplo de uma árvore AVL Exemplo de uma não árvore AVL C TD F J H P C D F J H P 1 00 1 0 1 -1 3-2 1-2 0-0 0-0 1-00-0 1-0 1 0 1 0 1 -2 3-2 0-21-0 0-0 0-0 1-0 Árvores Balanceadas - AVL • A denominação AVL é uma referência aos matemáticos russos , Adelson-Velskii e Landism que criaram em 1962 o conceito de árvore balanceada. • Uma árvore AVL é uma árvore de busca binária que controla a diferença de altura entre as subárvores esquerda e direita. Essa diferença é conhecida como “fator de balanceamento” de n e deve constar em cada nó de uma árvore balanceada. Os valores válidos são -1, 0 ou 1. • Uma árvore de busca binária pode perder o efeito de sua eficiência se os dados forem inseridos aleatóriamente, podendo ficar semelhante a uma lista encadeada ou um vetor ordenado. • A inserção de dados em uma AVL é composta por duas partes: • Inserir um nó utilizando os mesmos conceitos da inserção em uma ABB, que pode ocasionar o aumento da altura da subárvore em que foi inserido. • Verificar se a árvore resultante é ou não uma AVL, por meio do fator de balanceamento (FB). • Para cada novo nó inserido o campo fator de balanceamento recebe inicialmente o valor zero e os nós ancestrais (anteriores) devem ter seus campos de fator de balanceamento atualizados. • Se a árvore não estiver balanceada será necessário fazer um rebalanceamento por meio da movimentação dos nós, chamado de rotação. 111 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Rotações em uma AVL • A rotação em uma AVL para que ela fique balanceada pode ser: • Rotação simples para a esquerda • Rotação simples para a direita • Rotação dupla para a esquerda (esquerda + direita) • Rotação dupla para a direita (direita +esquerda) • Dicas para identificar uma árvore degenerada, quando a rotação deve ser simples ou dupla e se a rotação é para a esquerda ou direita a) FB precisa ser igual a 2 ou -2 b) Observe o FB do nó pai e do nó filho • Se os sinais forem iguais ( + + ou - -) então a rotação é simples. • Se os sinais forem diferentes ( + - ou - +) então a rotação é dupla. c) Se o FB for positivo a rotação é para a esquerda d) Se o FB for negativo a rotação é para a direita 112 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Rotação simples paraa direita 113 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC No nó com FB = -2 a) Considerar o nó pai (X) e seu filho esquerdo (Y) b) Y passa a ser o pai e X passa a ser o filho direito de Y c) O filho direito de Y passa a ser o filho esquerdo de X d) Y mantém seu filho esquerdo X Y Lembre-se das dicas: • FB precisa ser igual a 2 ou -2 • Se os sinais do FB dos nós pai e filho forem iguais ( + + ou - -) então a rotação é simples. • Se o FB for negativo a rotação é para a direita E -2 F 0 C -1 A 1 B 0 D 0 A 1 B 0 C 0 E 0 D 0 F 0 Rotação simples para a esquerda 114 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC No nó com FB = 2 a) Considerar o nó pai (X) e seu filho direito(Y) b) Y passa a ser o pai e X passa a ser o filho esquerdo de Y c) O filho esquerdo de Y passa a ser o filho direito de X d) Y mantém seu filho direito Lembre-se das dicas: • FB precisa ser igual a 2 ou -2 • Se os sinais do FB dos nós pai e filho forem iguais ( + + ou - -) então a rotação é simples. • Se o FB for positivo rotação é para a esquerda C 1 G 0 F -1 B -1 D 1 A 0 C 1 F 1 X YD 2 B -1 G 0 A 0 Rotação dupla para a direita 115 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lembre-se das dicas: • FB precisa ser igual a 2 ou -2 • Se os sinais do FB dos nós pai e filho forem diferentes ( + - ou - +) então a rotação é dupla. • Se o FB for positivo a rotação é para a esquerda • Se o FB for negativo a rotação é para a direita No nó com FB = 1 fazer a primeira rotação para a esquerda Fazer a segunda rotação no nó com FB = -2 para a direita C 0 F 0 B 0 A 0 D 0 E 1 Y X E -2 F 0 D -1 C 0 A 0 B 1 Y X E -2 F 0 A 0 C 0 D -2 B 0 Rotação dupla para a esquerda 116 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC Lembre-se das dicas: • FB precisa ser igual a 2 ou -2 • Se os sinais do FB dos nós pai e filho forem diferentes ( + - ou - +) então a rotação é dupla. • Se o FB for positivo a rotação é para a esquerda • Se o FB for negativo a rotação é para a direita No nó com FB = -1 fazer a primeira rotação para a direita Fazer a segunda rotação no nó com FB = 2 para a esquerda I 0 H -1 D 0 A 0 E 2 B -1 G -1 F 0 C 2 X Y H 1 I 0 G 0 E 0 F 0 D 0 A 0 B -1 C 1 E 2 X Y I 0 H 1 F 0 D 0 G 1 A 0 B -1 C 2 AVL - Exercícios • Com base nos valores 5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 11, desenhe a árvore AVL e determine o FB de cada nó. • Construa uma árvore AVL com os seguintes valores: 10, 20, 30. A cada inserção, atualize o FB de cada nó, e, se for preciso, faça o balanceamento. • Insira os valores 25 e 27. A cada inserção, atualize o FB de cada nó, e, se for preciso, faça o balanceamento. 117 Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Compartilhar