51182526 Apostila ED (Arvore Binaria)

  • View
    320

  • Download
    0

Embed Size (px)

Text of 51182526 Apostila ED (Arvore Binaria)

CENTRO FEDERAL DE EDUCAO TECNOLGICA DA PARABA COORDENAO DO CURSO DE TECNOLOGIA EM TELEMTICA

APOSTILA DE

ESTRUTURA DE DADOSPROF. CNDIDO EGYPTO

JOO PESSOA / PB JULHO / 2003

SUMRIO

1 INTRODUO .................................................................................. 3 2 LISTAS ............................................................................................... 4 3 LISTAS ORDENADAS .................................................................... 16 4 PILHAS ............................................................................................. 22 5 FILAS ................................................................................................ 27 6 RVORES ........................................................................................ 34 7 RVORE BINRIA......................................................................... 39 8 PESQUISA DE DADOS................................................................... 45 9 RVORE BINRIA DE PESQUISA .............................................. 49 10 RVORE AVL ............................................................................... 53 11 INDEXAO ................................................................................. 61 12 HASHING....................................................................................... 63 13 RVORE-B .................................................................................... 66 14 CLASSIFICAO DE DADOS .................................................... 74

3

1 INTRODUOO que uma Estrutura de Dados (ED)? Tipos de Dados Estruturas de Dados e Tipos Abstratos de Dados

Embora estes termos sejam parecidos, eles tm significados diferentes. Em linguagens de programao, o tipo de dados de uma varivel define o conjunto de valores que a varivel pode assumir. Por exemplo, uma varivel do tipo lgico pode assumir o valor verdadeiro ou falso. Uma declarao de varivel em uma linguagem como C ou Pascal especifica: 1. 2. 3. 4. O conjunto de valores que pode assumir. O conjunto de operaes que podemos efetuar. A quantidade de bytes que deve ser reservada para ela. Como o dado representado por esses bytes deve ser interpretado (por exemplo, uma cadeia de bits pode ser interpretada como um inteiro ou real...).

Ento, tipos de dados podem ser vistos como mtodos para interpretar o contedo da memria do computador. Mas podemos ver o conceito de Tipo de Dados de uma outra perspectiva: no em termos do que um computador pode fazer (interpretar os bits...) mas em termos do que os usurios desejam fazer (somar dois inteiros...) Este conceito de Tipo de Dado divorciado do hardware chamado Tipo Abstrato de Dado - TAD. Estrutura de Dados um mtodo particular de se implementar um TAD. A implementao de um TAD escolhe uma ED para represent-lo. Cada ED construda dos tipos primitivos (inteiro, real, char,...) ou dos tipos compostos (array, registro,...) de uma linguagem de programao. No importa que tipo de dados estaremos trabalhando, a primeira operao a ser efetuada em um TAD a criao. Depois, podemos realizar incluses e remoes de dados. A operao que varre todos os dados armazenados num TAD o percurso, podendo tambm ser realizada uma busca por algum valor dentro da estrutura. Exemplos de TAD: Lineares: Listas Ordenadas Pilhas Filas Deques

No Lineares: rvores Grafos

4

2 LISTASSo estruturas formadas por um conjunto de dados de forma a preservar a relao de ordem linear entre eles. Uma lista composta por ns, os quais podem conter, cada um deles, um dado primitivo ou composto. Representao: L1 Sendo: L1 1 elemento da lista L2 Sucessor de L1 Ln-1 Antecessor de Ln-1 Ln ltimo elemento da lista. Exemplos de Lista: Lista Telefnica Lista de clientes de uma agncia bancria Lista de setores de disco a serem acessados por um sistema operacional Lista de pacotes a serem transmitidos em um n de uma rede de computao de pacotes. L2 L3 ... Ln-1 Ln

Operaes Realizadas com Listas: Criar uma lista vazia Verificar se uma lista est vazia Obter o tamanho da uma lista Obter/modificar o valor do elemento de uma determinada posio na lista Obter a posio de elemento cujo valor dado Inserir um novo elemento aps (ou antes) de uma determinada posio na lista Remover um elemento de uma determinada posio na lista Exibir os elementos de uma lista Concatenar duas listas

FORMAS DE REPRESENTAO: a) Seqencial: Explora a sequencialidade da memria do computador, de tal forma que os ns de uma lista sejam armazenados em endereos sequenciais, ou igualmente distanciados um do outro. Pode ser representado por um vetor na memria principal ou um arquivo seqencial em disco. L pato1

cabra2

rato3

anta4

macaco5 6 7

...MAX

b) Encadeada: Esta estrutura tida como uma seqncia de elementos encadeados por ponteiros, ou seja, cada elemento deve conter, alm do dado propriamente dito, uma referncia para o prximo elemento da lista. Ex: L = pato, cabra, rato, anta, macaco pato cabra rato anta macaco

L

5

2.1 LISTA SEQENCIALUma lista representada de forma seqencial um conjunto de registros onde esto estabelecidas regras de precedncia entre seus elementos. O sucessor de um elemento ocupa posio fsica subsequente. A implementao de operaes pode ser feita utilizando array e registro, associando o elemento a(i) com o ndice i (mapeamento seqencial).

CARACTERSTICAS os elementos na lista esto armazenados fisicamente em posies consecutivas; a insero de um elemento na posio a(i) causa o deslocamento a direita do elemento de a(i) ao ltimo; a eliminao do elemento a(i) requer o deslocamento esquerda do a(i+1) ao ltimo; Mas, absolutamente, uma lista seqencial ou vazia ou pode ser escrita como (a(1), a(2), a(3), ... a(n)) onde a(i) so tomos de um mesmo conjunto A. Alm disso, a(1) o primeiro elemento, a(i) precede a(i+1), e a(n) o ltimo elemento.

Assim as propriedades estruturadas da lista permitem responder a questes tais como: se uma lista est vazia se uma lista est cheia quantos elementos existem na lista qual o elemento de uma determinada posio qual a posio de um determinado elemento inserir um elemento na lista eliminar um elemento da lista

Conseqncia: As quatro primeiras operaes so feitas em tempo constante. As demais, porm, requerero mais cuidados. Vantagem: acesso direto indexado a qualquer elemento da lista tempo constante para acessar o elemento i - depender somente do ndice.

Desvantagem: movimentao quando eliminado/inserido elemento tamanho mximo pr -estimado

Quando usar: listas pequenas insero/remoo no fim da lista tamanho mximo bem definido

Vamos tentar evitar as desvantagens anteriores ao usar endereos no consecutivos (Lista Encadeada).

6 OPERAES BSICAS A seguir, apresentaremos a estrutura de dados e as operaes bsicas sobre listas, implementadas na linguagem C. Definio da ED: #define MAX ________ typedef ______ telem; typedef struct { telem v[MAX]; int n; } tlista; /* tamanho mximo da lista */ /* tipo base dos elementos da lista */ /* vetor que contm a lista */ /* posio do ltimo elemento da lista */ /* tipo lista */

tlistan vPato0

cabra1

rato2

anta3

macaco4 5 6

...MAX-1

Operaes simples utilizando lista seqencial: 1) Criar uma lista vazia void criar (tlista *L) { L->n = 0; }

2) Verificar se uma lista est vazia int vazia (tlista L) { return (L.n == 0); }

3) Verificar se uma lista est cheia int cheia (tlista L) { return (L.n == MAX); }

4) Obter o tamanho de uma lista int tamanho (tlista L) { return (L.n); }

5) Obter o i-simo elemento de uma lista int elemento (tlista L, int pos, telem *dado) { /* O parmetro dado ir receber o elemento encontrado */ /* Retorna 0 se a posio for invlida. Caso contrrio, retorna 1 */ if ( (pos > L.n) || (pos L->n + 1) ) for (i=L->n; i>=pos; i--) L->v[i] = L->v[i-1]; L->v[pos-1] = dado; (L->n)++; return (1); } return (0);

8) Remoo do elemento de uma determinada posio Requer o deslocamento esquerda dos elementos v(p+1)...v(n) int remover (tlista *L, int pos, telem *dado) { /* O parmetro dado ir receber o elemento encontrado */ /* Retorna 0 se a posio for invlida. Caso contrrio, retorna 1 */ int i; if ( (pos > L->n) || (pos v[pos-1]; for (i=pos; in)-1; i++) L->v[i-1] = L->v[i]; (L->n)--; return (1); }

8

PRTICA DE LABORATRIO01. Faa um programa que: a) crie uma lista L; b) exiba o seguinte menu de opes:EDITOR DE LISTAS 1 EXIBIR LISTA 2 INSERIR 3 REMOVER 4 EXIBIR ELEMENTO 5 EXIBIR POSIO 6 ESVAZIAR ESC SAIR DIGITE SUA OPO:

c) leia a opo do usurio; d) execute a opo escolhida pelo usurio; e) implemente a estrutura de dados LISTA em uma biblioteca chamada L_SEQ (com implementao seqencial e usando o inteiro como tipo base), contendo apenas as operaes bsicas de listas (citadas anteriormente); f) na opo de exibir lista, devem ser exibidos o tamanho da lista e os seus elementos; g) na opo de insero, deve ser lido o valor do elemento a ser inserido e a posio onde ser efetuada a insero; h) na opo de remoo, deve ser lido a posio do elemento a ser removido; i) na opo de exibir elemento, deve ser lido a posio do elemento; j) na opo de exibir posio, deve ser lido o valor do elemento; k) as operaes de exibir e esvaziar a lista devem estar inseridas no programa principal; l) aps a execuo de cada opo, o programa deve retornar ao menu para nova opo do usurio ou o encerramento do programa (atravs da tecla ESC).

EXERCCIOS LISTA SEQUENCIAL01. Inclua, na biblioteca L_SEQ, as funes abaixo especificadas (obs: no faa uso das funes j implementadas). a) inserir um dado elemento na primeira posio de uma lista; b) inserir um dado elemento na ltima posio de uma lista; c) modificar um elemento de uma lista, sendo dado a