Listas Lineares

Listas

Pilhas

Filas

Listas

Dentre as estruturas de dados não primitivas , as listas lineares são as de mais fácil manipulação

agrupa informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si

Listas

Um dos objetos de dados mais simples é a lista ordenada ou lista linear

Exemplos:

dias da semana: (segunda, terça, quarta, quinta, sexta, sábado, domingo)

Pode-se dizer que está vazia ou que pode ser escrita como

(a1,a2, ....., an)

onde ai são componentes de algum conjunto S.

Listas

Uma lista linear ou tabela é um conjunto de nós L[0], L[1], ......, L[n-1] tais que

suas propriedades estruturais decorrem unicamente da posição relativa dos nós dentro da seqüência linear

Tem-se

n>0, e L[0] é o primeiro nó

para 0 < k < n, o nó L[k] é precedido por L[k-1]

Listas

Operações mais freqüentes:

busca, inclusão e remoção

operações básicas- algoritmos eficientes

outras operações:

alteração de um elemento na lista

combinação de duas ou mais listas

ordenação segundo um campo

determinação do primeiro (ou último) nó

Listas

Outras Operações:

ler a lista da esquerda para a direita (ou direita para esquerda)

inserir um novo valor na posição i - tem que renumerar os elementos de i até comprimento da lista

determinação da cardinalidade da lista

etc..

Listas

Casos particulares:

se remoção e inserção apenas nas extremidades - deque (doble ended queue)

inserção/remoção em um único extremo - pilha

inserções em um extremo e remoções no outro - fila

Listas

Tipo de Armazenamento:

posição relativa (contígua ou não) de dois nós consecutivos na lista

posições contíguas: alocação seqüencial de memória

posições não contíguas: alocação encadeada

A escolha depende do tipo de operações que serão efetuadas na lista

Listas

Alocação seqüencial de memória

maneira mais simples

endereço real do (j+1) ésimo nó da lista se encontra c unidades adiante daquela correspondente ao j-ésimo nó

c é igual ao número de palavras de memória ocupada por um nó

ARRAY - alocação estática

Representação

array onde associa-se o elemento i da lista ao elemento de índice i do array

mapeamento seqüencial: usando a representação convencional de array estamos armazenando a[i] e a[i+1] em localizações consecutivas do array.

Permite recuperar ou modificar os valores dos elementos aleatórios dentro da lista em um espaço de tempo constante.

podemos ter acesso aos elementos da lista em qualquer dos dois sentidos, alterando os valores subscritos de maneira controlada.

Listas Ordenadas

Elemento 1

2

1

Listas Ordenadas

4

Elemento 3

Considerar um array de 5 posições

inserção

Pesquisa do elemento de número 3

Elemento 2

2

Elemento 4

5

Elemento 5

5

4

3

Elemento 1

1

Listas Ordenadas

6

Elemento 3

Considerar um array de 5 posições

Remoção do elemento de número 8

Pesquisa do elemento de número 5

Elemento 2

4

Elemento 4

8

Elemento 5

9

Elemento 4

9

Elemento 4

9

Listas Ordenadas

Array como forma de representação

operações de inserção e remoção:

exigem um esforço real

mover os elementos restantes para preservar o mapeamento seqüencial

nos conduz a considerar um mapeamento não seqüencial das lista ordenadas em arrays.

Listas - Alocação Seqüencial

A maneira mais simples de se manter uma lista linear - nós em posições contíguas

cada nó ocupa c unidades de memória

o nó j+1 está a c posições do nó j

array

alocação estática de memória

esta opção depende do conjunto de operações

Listas

Cada nó é formado por campos

cada campo armazena características diferentes dos nós da lista

lista de bancos - nome, número de clientes, capital

cada nó possui um identificador especial - chave

pode-se ter apenas chaves distintas

Listas

Chave

uma chave k[i] está associada ao nó r[i]

usualmente a chave é um campo do nó

é dito classificado pela chave quando
se i < j então k[i] precede k[j]

Listas

Os nós podem estar ordenados em função de suas chaves

posso buscar um registro em uma lista seqüencial ordenada pelas suas chaves

posso buscar um registro em uma lista seqüencial não ordenada

Busca Seqüencial

É o método mais simples de busca

Nós da lista estão em um array

não ordenado pela chave

ordenada pela ordem de chegada

Inserção

quando um novo registro deve ser inserido, colocamos ele ao final do array

Busca:

quando a busca deve ser efetuada, percorre-se o array seqüencialmente

Busca Seqüencial

1

5

3

2

9

7

1

5

3

2

9

7

Busca Seqüencial

1

5

3

2

9

7

1

5

3

2

9

7

4

Se posição igual a N então não existe no array

N = número de elementos

Definição da Estrutura de Dados

typedef struct

{int chave;

int info;} no;

no a[maxN];

int N;

Iniciando a Estrutura

{ N = 0; }

Busca Seqüencial

Busca Seqüencial

/* a é global */

int Busca_Sequencial (int v, int pos) {

while ( v != a [pos].chave && pos<N )

pos++;

return(pos); // Insucesso retorna >= N.

} // Sucesso retorna < N

pos: representa ponto inicial de busca

relevante para recuperação de vários registros com a mesma chave

dois testes a cada iteração

Busca Seqüencial

/* a é global */

int Busca_Seqüencial (int v, int pos)

{ a[N].chave = v;

if (pos<=N)

while ( v != a [pos].chave)

pos++;

return(pos);

}

pos: representa ponto inicial de busca

relevante para recuperação de vários registros com a mesma chave

um teste a cada iteração

Busca Seqüencial

A complexidade do pior caso é O(n) para os dois algoritmos

O segundo é de execução mais rápida pois o número de testes é menor a cada iteração

Int Insere_seq (int v)

{

a[N].chave = v;

N++;

return(N);

}

if (N == (maxN –1)) return(-1);

/*sem lugar no array */

Busca Seqüencial

Busca em uma Lista Classificada

Lista Classificada (crescente): ao identificar que o nó buscado não está na lista, não é necessário percorrer até o final - O(n)

int Busca_Sequencial (int v, int pos) {

if (pos<N) {

a[N].chave = v;

while ( v > a [pos].chave)

pos++;

if (v == a[pos].chave) return(pos);

}

return(N);

}

Busca Binária

Se o conjunto de nós é grande

o tempo de busca pode ser reduzido significantemente

Busca baseada em "dividir para conquistar"

divida um conjunto de registros em duas partes

determine a qual dessas duas partes a chave pertence e se concentre nessa parte

uma maneira razoável de dividir registros em partes é mante-los classificados

Busca Binária

Array de busca classificado

use índices do array para delimitar a parte sendo trabalhada

para verificar se uma dada chave t está na tabela

1. compare com a chave do elemento do meio

2. se a chave comparada for menor, o registro está na parte esquerda da tabela. Se for maior, está na parte direita

3. aplique esse método recursivamente

Busca Binária

int busca_binaria (int v)

{ int pos, e, d;

e = 0; d = N-1;

do { pos= (e + d)/ 2 ;

if (v < a[pos].chave)

d = pos-1;

else

e=pos+1;

} while ((v !=a[pos].chave)

&& (e <= d));

if (v == a[pos].chave)

return(pos);

else

return(N); }

Busca Binária

Esse método emprega os ponteiros e e d para delimitar o sub-arquivo onde está sendo efetuada a busca

cada hora no loop a variável pos é setada para o ponto do meio do intervalo corrente

existem três possibilidades, o loop termina com sucesso, o ponteiro da esquerda fica pos + 1 ou o ponteiro da direita fica pos - 1

o loop pode também terminar com insucesso quando esquerda maior que direita

Busca Binária

Manuseio de registros com a mesma chave nesse algoritmo

o índice retornado pode cair no meio de registros com a mesma chave

loops que buscam em ambas as direções tem que ser usados para recuperação de todos os registros

2

5

6

7

9

15

16

23

25

40

52

55

Busca Binária

==> Complexidade

Tipo de Dados Recursivo

Um tipo T recursivo, possui componentes que pertencem ao tipo T

é um mecanismo de estruturação para definir agregados de crescimento arbitrário

objetos do tipo recursivo podem ser implementados pelo uso de ponteiros

um componente é representado por uma posição contendo um ponteiro para o objeto

typedef struct no {

int a;

struct no *proximo} no;

Listas Encadeadas

Listas Encadeadas são definidas como primitivas em algumas linguagens

não em C

Vantagem sobre arrays :

podem crescer e diminuir em tempo de execução.

em particular, seu tam. máximo não precisa ser conhecido a priori

Provêem flexibilidade permitindo que os ítens sejam rearrumados eficientemente

custa perda no tempo de acesso a qualquer item arbitrário da lista

A

L

I

T

S

Listas Encadeadas

É um conjunto de itens organizado seqüencialmente, como um array.

em um array a organização é implícita
(pela posição)

em uma lista encadeada usa-se um arranjo explícito no qual um item é parte de um nó que também contém um link (um ponteiro) para outro nó - o próximo nó da lista.

Listas Encadeadas

Um item é representado por uma letra

Cada nó é representado por círculo

Cada link é representado por uma linha

Detalhes que devem ser considerados:

Todo nó possui um link

O link no último nó tem que especificar algum tipo de próximo
(aponta para z que aponta para si próprio ou NULL)
O início da lista (cabeça) que aponta para o 1º nó da lista.

A

L

I

T

S

head

z

A

L

I

T

S

head

z

Listas Encadeadas

Essa representação permite executar algumas operações de forma mais eficiente do que com um array.

Suponha que quero mover o T do fim da lista para o começo: só é necessário mudar três links

Faço nó T apontar para A

o nó contendo S apontar para z e

a cabeça apontar para T.

Listas Encadeadas

Mesmo que a lista seja muito longa, faço essa mudança estrutural mudando apenas 3 links.

Para inserção de um novo nó:

aloca-se memória para um nó e arruma-se os links;

no array seria necessário deslocar todos os elementos a partir do ponto de inserção;

apenas 2 links são alterados para esta operação não importa quão longa é a lista

A

L

I

T

S

head

z

X

Deleção de um ítem da lista encadeada:

faz com que ela dimunir de 1 nó

basta alterar o link do nó anterior ao deletado para igual ao do nó sendo deletado

o conteúdo de X (no exemplo) ainda existe , mas não é mais acessível pela lista

não é mais parte da lista

A

L

I

T

S

head

z

X

Listas Encadeadas

Listas Encadeadas

Lista Encadeada x Array

Deleção e Inserção são mais naturais na lista encadeada

Existem outras operações para as quais a lista não é natural

Encontrar o k-ésimo elemento da lista

em um array é simplesmente feito um acesso a a[k]

na lista é necessário percorrer k links.

Achar um item antes de um dado item

Listas Encadeadas

Duplamente encadeada

mantém ponteiro para cada direção:

um ponteiro para o próximo e um para o anterior

Simplesmente encadeada

mantém ponteiros para uma direção apenas

Listas Encadeadas

Exemplo

Suponha uma lista simplesmente encadeada.

Cada nó consiste de: 1 palavra com 1 floating point e outra com o ponteiro para o próximo nó

o fim da lista é marcado com um ponteiro com NULL

É desejável descobrir se algum nó possui um número igual a 1.0

Deve retornar Verdade se encontrar e Falso em caso contrário

Listas Encadeadas

typedef struct tipo_no {

float valor;

struct tipo_no *proximo;

} tipo_no;

tipo_no *head;

tipo_no *prox;

boolean Acha_1() {

boolean resultado;

prox = head;

/* pega o endereço do cabeça da lista*/

resultado = false;

//inicializa resultado

while (prox /*!= NULL*/

&& ! resultado)

{ / * se lista vazia já vai embora direto = para qdo chegar ao fim ou encontrar 1,0 */

if (prox->valor == 1.0)

resultado = true;

else

prox = prox->proximo;

}

return(resultado); }

Listas Encadeadas

Inserção e Deleção

alocação dinâmica de memória

malloc e free do C

o tamanho da lista pode crescer e diminuir

Exemplo de uso:

Rotina que toma conta do espaço livre de memória

lista de memória livre

Ao liberar memória então insiro na lista

Ao alocar memória então removo da lista

Listas Encadeadas

Exercício

Fazer rotinas para inserção, remoção, e localizar o n-ésimo elemento

Fazer rotina para localizar o elemento antes do de valor 5

Qual a melhor representação: simplesmente ou duplamente encadeada ?

Listas Encadeadas - Inserção

Vamos considerar uma lista em que cada nó possui um valor float

Vamos inserir antes do 1º elemento da lista

Estruturas sendo usadas

typedef struct tipo_no{

float valor;

struct tipo_no * proximo;

} tipo_no;

tipo_no * head;

head = NULL;

Protótipo da Função

boolean Insere(float);

head

Listas Encadeadas - Inserção

Typedef struct tipo_no{

float valor;

struct tipo_no * proximo;

} tipo_no;

tipo_no * head;

boolean Insere(float nvalor)

{ tipo_no * novo;

novo = malloc (sizeof(tipo_no));

if (!novo) //nao conseguiu alocar

return(false);

novo->valor = nvalor;

novo->proximo = head;

head = novo;

return(true);

}

Listas Encadeadas - Remoção

Vamos considerar uma lista em que cada nó possui um valor float

Vamos remover sempre o 1º elemento da lista

Se quiser remover de uma lista vazia?

Estruturas sendo usadas

Typedef struct tipo_no {

float valor;

tipo_no * proximo;

} tipo_no;

tipo_no * head;

tipo_no * prox;

Protótipo da Função

float Remove(void )

Listas Encadeadas - Remoção

Typedef struct tipo_no{

float valor;

struct tipo_no *proximo;

} tipo_no;

tipo_no *head;

float Remove()

{ tipo_no *a_del;

float resultado;

a_del = head;

head = head->proximo;

resultado = a_del->valor;

free(a_del);

return (resultado);

}

Listas Encadeadas - Busca N

Vamos considerar uma lista em que cada nó possui um valor float

Vamos buscar o N-esimo elemento

Se nao existir?

Estruturas sendo usadas

Typedef struct tipo_no {

float valor;

struct tipo_no * proximo;

} tipo_no;

tipo_no * head;

tipo_no * prox;

Protótipo da Função

boolean busca(int , float * );

Listas Encadeadas - Busca N

Typedef struct tipo_no {

float valor;

struct tipo_no *proximo;

} tipo_no;

tipo_no * head;

boolean busca ( int N,

float * avalor)

{ tipo_no * prox;

int i;

//percorre a lista até o elemento N

if (!head) // lista vazia

return (false);

prox = head;

for (i=1; i<N;i++) {

prox= prox->proximo;

if (!prox)

return (false);

}

// chegando aqui e porque existe

*avalor = prox->valor;

return(true);}

Listas Encadeadas - Busca elem. anterior a um dado valor

Vamos considerar uma lista em que cada nó possui um valor float

Vamos buscar o elemento que está na lista, e seja anterior a um elemento que tenha um dado valor.

Estruturas sendo usadas

Typedef struct tipo_nó {

float valor;

struct tipo_nó * proximo;

} tipo_nó;

tipo_nó * head;

tipo_nó * prox;

Protótipo da Função

boolean busca(float , float *);

Listas Encadeadas - Busca elem. anterior a um dado valor

Typedef struct tipo_no {

float valor;

struct tipo_no * proximo;

} tipo_no;

tipo_no * head;

boolean busca (float val_busca,

float * avalor)

{ tipo_no * prox, *ant;

int i;

ant = NULL;

prox =head;

/* percorre a lista até o elemento de valor = val_busca */

while(prox &&

prox->valor != val_busca)

{	ant = prox;

prox= prox->proximo;

}

if (!prox)

return (false);

// chegando aqui é porque existe

// prox = head e ant = NULL

// ou efetivamente existe

Listas Encadeadas - Busca elem. anterior a um dado valor

if (!ant) // anterior nulo

{	/* o numero anterior nao existe, o numero buscado e o 1o. da lista */

return (false);

}

// se chegar aqui entao existe

*avalor = ant->valor;

return(true);

}

Neste caso não é necessário lista duplamente encadeada

lista ordenada cujos elementos estão em ordem crescente

deseja-se imprimir em ordem crescente ou decrescente

DEVE-SE EMPREGAR DUPLAMENTE ENCADEADA

Exercício

Fazer um programa que:

Le números inteiros positivos

a) Calcular média destes números

b) Calcular mínimo e máximo destes números

c) Listar os N maiores

Média

Main()

{ int valor, soma, qtde; float media;

media = 0;

soma = 0;

qtde = 0;

scanf(&valor);

while(valor != -1)

{ soma = valor + soma;

qtde++;

scanf(&valor);

}

media = ((float)soma) /qtde;

printf(“Média = %f”,media); }

Mínimo e Máximo

Main()

{ int valor, min, max;

scanf(&valor);

min = valor;

max = valor;

while(valor != -1)

{if (min > valor) min = valor;

if (max < valor) max = valor;

scanf(&valor);

}

if(min == -1) printf(“Não entrou nenhum valor “);

else printf(“Mínimo = %d e Máximo = %d”,min, max); }

Listar os N maiores

Leio cada elemento

Já armazeno em uma lista de forma ordenada

Vou limitar o tamanho da lista a N para que esta não possa crescer indiscriminadamente

Depois basta percorrer a lista e imprimir cada elemento

Listar os N maiores

typedef struct t_no {

int valor;

struct t_no * proximo} t_no;

t_no *head = NULL, *novo;

int N=0;

int num_elem;

main()

{	int valor;

while (N<=0)

{ printf(“digite N”);

scanf(“%d”, &N);

}

scanf(“%d”, &valor);

//insere o primeiro. Existe pelo

//menos um nó na lista (N>0)

novo = malloc(sizeof(t_no));

novo->valor = valor;

novo->proximo = NULL;

head = novo;

num_elem=1;

scanf(“%d”,&valor)

while(valor != -1)

{	se_dos_maiores(valor);

scanf(“%d”, &valor); }

imprima_maiores();

}

Listar os N maiores

void se_dos_maiores(int valor)

{t_no * prox; *novo, *ant;

prox = head;

ant = NULL;

while(prox) // !=NULL

{	//percorro até encontrar um menor

if (prox->valor < valor)

break;

ant = prox;

prox= prox->proximo; }

//posso ter acabado ou achei

if (!prox) // se nulo

{// posso ja ter N elementos

if( num_elem == N)

return;

/*cheguei ao final da lista e todos sao maiores */

// senao inserir ao final

novo = malloc(sizeof(t_no));

novo->valor = valor;

novo->proximo = NULL;

ant->proximo = novo;

}

Listar os N maiores

else { // do prox nulo

/* estou inserindo no meio da lista */

// insiro antes de prox

// entre ant e prox

novo = malloc(sizeof(t_no));

novo->valor = valor;

novo->proximo = prox;

if (ant) {

ant->proximo = novo;

ant = novo; }

else head = novo;

}

// trato numero maximo de elem

if (num_elem<N)

num_elem++;

else

{ // tenho que remover o ultimo

//percorro a lista ate o final

while(prox->proximo) //!=NULL

{ ant = prox;

prox= prox->proximo;

}

//retiro o ultimo da lista

// mantenho em N

free(prox);

ant->proximo = NULL;

}

Estruturas de Dados de Acesso Restrito

Nos concentramos em estruturar dados de forma a inserir, deletar ou acessar itens arbitrariamente

Para muitas aplicações é necessário impor restrições de acesso aos dados

essas restrições são benéficas por:

podem aliviar a necessidade de usar estruturas de dados c/ mais detalhes
(manter controle de links ou índices)

permitem implementações mais simples e flexíveis, desde que menos operações são suportadas.

Estruturas de Dados de Acesso Restrito

Pilhas

A estrutura mais importante de acesso restrito é a PILHA

Apenas duas operações básicas estão envolvidas:

PUSH : Acrescentar no topo da pilha

POP: Retirar do topo da pilha

Uma pilha opera como uma pilha de livros

só pego livro de cima

só coloco livro em cima

isso significa que: um livro pode ficar muito tempo no fundo da pilha

As operações básicas da pilha são fáceis de implementar usando:

array

listas encadeadas

1o. elem.

2o. elem.

3o. elem.

1o. elem.

2o. elem.

3o. elem.

4o. elem.

1o. elem.

2o. elem.

3o. elem.

Pilhas

Pilhas

Representação baseada em array

Considere o índice 0 (zero) do array como sendo o fundo da pilha

O topo da pilha é dado por uma variável auxiliar TOPO que contém o índice da 1a posição livre do array

Pilha vazia: TOPO = 0

restrição: tamanho máximo

1o. elem.

2o. elem.

3o. elem.

4o. elem.

3

Pilhas

Inicialização da Pilha:

topo = 0 /* Pilha vazia */

int PUSH (float x) {

if(topo < MAX)

{ /* Possui espaço */

PILHA[topo] = x;

topo ++;

return(true);

}

else return(false); /* estouro da pilha */

}

Pilhas

#define VAZIA 9999999
/* um valor nunca alcançável pelos elementos armazenados na pilha */

float POP () {

if(topo != 0)

{ /* Possui elemento na pilha */

topo - -;

return(PILHA[topo]);

}

else return(VAZIA); /* pilha vazia */

}

Pilhas

topo e pilha são variáveis globais para as procedures que manipulam a pilha

é uma implementação simples, não usa área externa para ponteiros

aloca todo o espaço estaticamente

tamanho máximo de pilha

Representação baseada em lista encadeada

Considere a cabeça da lista como o topo da pilha

Pilha vazia: Topo.próximo = NULL

não possui restrição de tamanho máximo

Alocação dinâmica de memória

Pilhas

Pilha

Representação baseada em lista encadeada

PUSH

POP

Pilha

Representação baseada em lista encadeada

typedef struct tipo_no {

int chave;

struct tipo_no *próximo ;

} tipo_no;

tipo_no topo ;

void inic_pilha()

{ topo.próximo = NULL; }

Pilha

Representação baseada em lista encadeada

void push (int valor)

{ tipo_no * t;

t = malloc(sizeof(tipo_no))

if (t == NULL)

/* Acabou a memória */

else

{

t->chave = valor;

t->próximo = topo.próximo;

topo.próximo = t;

} }

Pilha

Representação baseada em lista encadeada

int pop ()

{ tipo_nó * t;

int valor;

t = topo.próximo;

if (t == NULL) /* pilha vazia */

return( valor flag de erro );

else

{ topo.próximo = t->próximo;

valor = t->chave;

free (t);

return(valor);

} }

Pilha

Representação baseada em lista encadeada

boolean pilha_está_vazia ()

{

if (topo.próximo == NULL)

return (true)

else return(false)

}

Exercício:

Vamos fazer um programa que converte uma expressão aritmética da forma em-fixada para pós-fixada.

Forma em-fixada: 5 *( (( 9+8 ) * ( 4*6 ) )+ 7)

Forma pós-fixada: 5 9 8 + 4 6 * * 7 + *

Pilha

void gera_polonesa_reversa () { char c = ' ';

do { /* só para inteiros */

while (c == ' ') getc(&c); / * tira brancos da frente */

if ( c == ‘)’ ) {

printf(“%c “, pop()) ;

getc(&c);

}

/* escreve o que está no topo da pilha-pilha de operadores */

if ((c == ‘+’) || (c == ‘*’) || (c == ‘/’) || (c == ‘-’)) {

push(c) ;/* operador - empilha */

getc(&c);

}

while ((c>=‘0’) && ( c<=‘9’ ) ) { /* se digito imprime na saída */

printf(“%c”,c); getc(&c); }

if (c != ‘(‘) printf (‘ ’)

else getc(&c);

} while (c!=CR) /* enquanto c != de carriage Return - constante */

while ( ! Pilha_esta_vazia() ) printf(“%c “, pop() )

}

Pilha

Filas

Outra estrutura de dados de acesso restrito e fundamental é chamada de fila

Novamente apenas duas operações básicas estão envolvidas:

inserir um item no fim da fila

remover um item do início

quem chega primeiro sai primeiro da fila

em uma pilha alguma coisa podia ficar toda vida no fundo, em uma fila, tudo é processado na ordem de chegada

pilhas LIFO

last in first out

filas

FIFO - first in first out

Representação de Filas

Lista Encadeada

Array

Filas

Filas

Representação baseada em array

um array pode ser usado se for estimado o tamanho máximo da fila

4o. elem.

3o. elem.

2o. elem.

1o. elem.

Filas

Tipos e Constantes

#define MAX 6

int fila [MAX]

int início, fim

Condição inicial

início = 0

fim = 0

Situação de fila vazia

Fila Cheia: ???

Filas

Funções

põe_fila

remove_fila

põe_fila

A fila representada em array possui tamanho máximo portanto, deve ser verificado se fila cheia antes de inserir

remove_fila

verificar se está vazia antes de remover

Filas

5o. elem.

4o. elem.

3o. elem.

2o. elem.

1o. elem.

6o. elem.

5o. elem.

4o. elem.

3o. elem.

2o. elem.

1o. elem.

6o. elem.

Filas

5o. elem.

4o. elem.

3o. elem.

2o. elem.

1o. elem.

6o. elem.

5o. elem.

4o. elem.

3o. elem.

2o. elem.

1o. elem.

6o. elem.

Filas

5o. elem.

4o. elem.

3o. elem.

2o. elem.

1o. elem.

6o. elem.

Para que se possa aproveitar as posições do array já liberadas, os índices início e fim se comportam de uma forma “circular”

Ao invés de simplesmente incrementar Fim faz-se (em PASCAL):

Fim = mod(Fim+1, MAX)

Em C:

Fim = (Fim + 1) % MAX;

Ao invés de simplesmente incrementar Início faz-se:

Início = mod(Início+1, MAX)

mod : função- resto de divisão inteira

Filas

5o. elem.

4o. elem.

3o. elem.

8o. elem.

7o. elem.

6o. elem.

Condição de fila cheia

Início = Fim é condição de fila vazia

As condições não podem ser iguais

Antes de inserir testa se Fim, após inserção, ficará igual a início

Neste caso já considera fila cheia

Um array de MAX posições representa uma fila de MAX-1 elementos

Põe_fila (int v) {

if (((Fim+1) % MAX) != Início ) {

/* fila não está cheia */

Fila[Fim]=v;

Fim = (Fim+1) % MAX;

}

}

Filas

Filas

int Remove_fila() {

int valor;

if( Início != Fim)

/* fila não está vazia */

{ valor = Fila[Início];

Início = (Início +1) % MAX;

return(valor); }

else /* fila vazia */

return(flag);

}

flag é um valor diferente de qualquer outro que possa ser armazenado na fila

por exemplo, se armazenamos números positivos então flag = -1

Filas

Representação baseada em lista encadeada

Fila com apenas um elemento

Fila Vazia??

Filas

Põe_fila

Remove_fila

Filas

Representação baseada em lista encadeada

Tipo de Dados

typedef struct tipo_no {

int valor; /* aqui pode ser de vários tipos */

/* representa o conteúdo do nó */

struct tipo_no * proximo }tipo_no;

Inicialização da Fila

tipo_no início, fim;

inicio.proximo = NULL;

fim.proximo = NULL;

Filas

Após a inserção do 1o. elemento

Inserção do 1o. elemento

Filas

void Insere (int v)

{ tipo_no * no_aux;

no_aux = malloc(sizeof(tipo_no))

no_aux->valor = v;

no_aux->proximo = NULL

if (fim.proximo == NULL) /* 1o. Da fila */

{ /*inicio e fim são nulos */

inicio.proximo = no_aux; }

else fim.proximo->proximo = no_aux;

fim.proximo = no_aux }

Filas

int Remove () {

tipo_no * no_aux; int valor;

if (inicio.proximo)/*!= NULL fila não vazia */ {

no_aux = inicio.proximo;

valor = no_aux->valor;

if (fim.proximo == inicio.proximo) /* so tem 1 */ {

/*inicio e fim ficam nulos */

inicio.proximo = NULL; fim.proximo = NULL; }

else

inicio.proximo = inicio.proximo->proximo;

free(no_aux);

return (valor);

}

else return (flag); /* fila vazia */

}

Filas

Remoção do último elemento

Após a remoção do último elemento

Filas e Pilhas Múltiplas

Alocar mais de uma pilha ou fila em uma mesma região de memória

Limitada a implementação por arrays

Duas pilhas

simples : uma cresce de cada lado do array

Mais de duas pilhas

dividir a área em tamanhos proporcionais aos tamanhos máximos das pilhas ou, se não souber, em pedaços iguais.

Filas e Pilhas Múltiplas
Duas Pilhas

Área de Memória

Filas e Pilhas Múltiplas
N Pilhas

Área de Memória

.

.

.

.

.

.

.

.

Filas de Prioridade

É uma estrutura de Dados onde a ordem dos elementos não está relacionada com a ordem de inserção

fila e pilha: ordem de inserção

Em Filas de Prioridade a ordem intrínseca dos elementos determina o resultado de suas operações básicas

Elas podem ser: Ascendente ou Descendente

Operações:

Insere: Insere um elemento

Remove: Remove o menor (ascendente) ou o maior (descendente)

Filas de Prioridade

Representação por Array:

representação de fila

sem diferenças na implementação da inserção

para remoção seria necessário retirar o menor ou maior elemento

elementos inseridos aleatoriamente

fila teria que ser toda percorrida para encontrar o elemento a remover

seria necessário “preencher o buraco” deixado pelo elemento sendo retirado

Filas de Prioridade

Representação por Array

valor = 7.

valor = 9

valor = 3

valor = 5.

valor = 5.

valor = 5.

valor = 7.

valor = 7

valor = 9

valor = 5.

valor = 5.

valor = 5.

Filas de Prioridade

Representação por Lista Encadeada

Os problemas vistos na representação por array são:

Achar o “menor”elemento

Remover um elemento: o que é sempre ruim para uma representação por array para lista.

A representação por Lista Encadeada já resolve o problema da remoção de um elemento

FALTA: agilizar a busca do menor elemento

Filas de Prioridade

Inserção: toda inserção de um elemento na lista deve respeitar sua forma de ordenação:

ascendente: os elementos da lista devem ser armazenados do menor para o maior

descendente: os elementos da lista devem ser armazenados do maior para o menor

Remoção: retira o primeiro elemento da lista

já é o menor ou o maior

Filas de Prioridade

Inserção

Insere 8

7

9

11

7

9

11

8

Filas de Prioridade

Representação baseada em lista encadeada

Tipo de Dados

typedef struct tipo_no {

int valor; /* aqui pode ser de vários tipos */

/* representa o conteúdo do nó */

struct tipo_no * proximo} tipo_no

Inicialização da Fila

tipo_no início;

inicio.proximo = NULL;

Remoção: remove o primeiro

Igual a rotina já apresentada

Filas de Prioridade

void Insere_em_ordem (int v)/* ascendente */ {

tipo_no *no_aux, *no_ant;

no_aux = malloc(sizeof(tipo_no))

no_aux->valor = v;

no_ant = &inicio; /* percorre a lista para encontrar posição */

while (no_ant->proximo != NULL) {

if (no_ant->proximo->valor < v ) no_ant = no_ant->proximo;

else break;

} /* achei o no anterior a inserção */

no_aux-> proximo = no_ant->proximo;

no_ant->proximo = no_aux;

}

Busca Seqüencial

Complexidade média: - nao vou falar

seja q a probabilidade de sucesso no resultado de busca

suponha que sejam idênticas as probabilidades da chave procurada se encontra em posições distintas da lista

para entradas distintas distintas que tenham chave na mesma posição são idênticas

algoritmo reconhece apenas n+1 entradas distintas

Métodos de Sort Elementares

Conceitos

Considere o processo de encontrar um número de telefone em uma lista telefônica

este processo é chamado de busca

é simplificado pelo fato dos nomes estarem em ordem alfabética

e se estivesse sem uma ordem?

Conceitos

Considere um busca de um livro em uma biblioteca

a cada livro é atribuída uma posição relativa a outros e portanto pode ser recuperado em um tempo hábil

Conceitos

Considere um conjunto de números em uma classificação seqüencial na memória do computador

é relativamente fácil encontrar um elemento particular

Um relatório necessita ser impresso ordenado para facilitar o manuseio pelos usuários

Terminologia básica

Arquivo:

é uma seqüência de n ítens

cada ítem é chamado de registro

arquivo de registros: r[0], r[1], ……….r[n-1]

Terminologia básica

Chave

uma chave k[i] está associada ao registro r[i]

usualmente a chave é um campo do registro

o arquivo é dito classificado pela chave quando
se i < j então k[i] precede k[j]

Terminologia básica

Um método de sort:

tem por objetivo rearrumar as chaves de forma que obedeçam a uma regra pré-definida (usualmente uma ordem numérica ou alfabética)

Terminologia básica

Se o arquivo a ser ordenado cabe na memória

pode ser representado em um array

o sort é dito interno.

Se o arquivo a ser ordenado fica em fita ou disco, o sort é dito externo

Terminologia básica

Sort interno X Sort externo

a diferença principal entre eles é que registros são facilmente acessíveis em um sort interno enquanto um sort externo tem que acessar registros seqüencialmente ou pelo menos em grandes blocos.

Todos os algoritmos que veremos são sorts internos

Terminologia básica

Um método de sort é dito estável se preserva a ordem relativa das chaves iguais em um arquivo

para uma lista classificada por ordem alfabética, uma nova classificação por grau, com um método estável, produz uma lista onde estudantes com o mesmo grau estão em ordem alfabética

um algoritmo não estável produz uma lista que não tem mais nada a ver com a inicial

Programas de sort podem operar sobre o registro ou sobre uma tabela de ponteiros

registro é muito grande: é feito o chamado "sort indireto"

os registros não são rearrumados e sim um índice

Terminologia básica

Índice é um array de ponteiros cujo primeiro ponteiro aponta para o menor registro e assim em diante

As chaves tanto podem ficar armazenadas com os registros (se forem grandes) ou com os ponteiros (se forem pequenas)

Terminologia básica

Sort por Seleção

Um dos algoritmos de sort mais simples funciona da seguinte forma:

ache primeiro o menor elemento do array e troque sua posição com o primeiro elemento

ache o segundo menor elemento e troque sua posição com o segundo elemento

continue até ter todo array classificado

para cada i de 0 a N-2, troca o menor elemento do array que vai de i a N-1 com a[i]

9

2

6

3

5

7

inicial

2

9

6

3

5

7

2

3

6

9

5

7

2

3

5

9

6

7

2

3

5

6

9

7

2

3

5

6

7

9

Cada passo acha o menor e o coloca em sua posição

Sort por Seleção

Sort por Seleção

void Seleção() {

int t, i,j,min;

for (i=0;i< N-1; i++) {

min = i;

for (j=i+1; j< N; j++) {

if (a[j]<a[min])

min = j;

}

t =a[min]; /* troca */

a[min]=a[i];

a[i] = t;

}

}

Bubble Sort

Um método elementar

percorrer o arquivo trocando elementos adjacentes, se necessário

quando nenhuma troca for necessária ao percorrer todo o arquivo, este está classificado

Buble Sort
passo 1

9

2

6

3

5

7

2

9

6

3

5

7

2

6

9

3

5

7

2

6

3

9

5

7

2

6

3

5

9

7

2

6

3

5

7

9

Buble Sort
passo 2

2

6

3

5

7

9

2

3

5

6

7

9

2

3

5

6

7

9

2

6

3

5

7

9

2

3

6

5

7

9

Buble Sort
passo 3

2

3

5

6

7

9

2

3

5

6

7

9

2

3

5

6

7

9

Não ocorreram trocas

Arquivo já está classificado

Buble Sort

void Bubble_sort() {

int i,j,t, trocas;

for (i = N-1; i>0; i--) {

trocas = 0;

for (j = 1; j <= i; j++) {

if (a[j-1] > a[j]) /* troca */ {

t = a[j-1]; a[j-1] = a[j]; a[j] = t;

trocas++;

}

}

if (trocas == 0) break;

}

}

Quicksort

É um algoritmo eficiente e popular

Naturalmente recursivo e sua implementação é complicada se recursão não estiver disponível

Algoritmo Básico

é um método de sort baseado em "dividir para conquistar"

particiona o arquivo em duas partes e classifica as partes independentemente.

a posição exata da partição depende do arquivo

Quicksort: algoritmo básico

Possui a seguinte estrutura:

void quicksort (int e, int d) {

int i;

if (d >e) {

// a chave do método é essa função

i = partition (e,d);

quicksort(e,i-1);

quicksort(i+1,d);

}

}

Quicksort: algoritmo básico

A primeira chamada é quicksort(0,N-1)

A função partition deve:

rearrumar o array para fazer valer as seguintes tres condições:

o elemento a[i] está em seu lugar final no array para algum i

todos os elementos em a[e] a a[i-1] são menores que a[i]

todos os elementos em a[i+1] a a[d] são maiores ou iguais a a[i]

Partition: implementação

arbitrariamente escolha a[r] para ser o elemento que estará na sua posição final

percorra o array da esquerda até que um elemento maior que a[r] seja encontrado

percorra o array da direita até um elemento menor que a[r]

esses dois elementos estão certamente fora de posição, então troque-os

Quicksort: algoritmo básico

Quicksort: algoritmo básico

É bom sempre parar a varredura toda vez que for igual

Continuando dessa forma garante-se que todos os elementos do array a esquerda são menores e os a direita são maiores

Quicksort: algoritmo básico

Quando os ponteiros de varredura se cruzam, o processo está quase completo: a única coisa que falta é trocar a[r] com o elemento mais a esquerda do sub-arquivo da direita que está na posição i

O quicksort se aplica no arquivo das posições (e a i-1) a (i+1, d)

i é o elemento que já está na sua posição

Quicksort: partition

9

6

3

5

2

7

2

6

3

5

9

7

2

6

3

5

7

9

7 é o número em sua posição

definitiva

partition retorna i = 4

int Partition(int e, int d) { /* a[] é global */

int v, i, j, t;

v = a[d]; i = e - 1; j = d;

do {

do { i = i+1; } while (a[i] < v); /* pela esquerda*/

do { j = j-1; } while (a[j] > v); /* pela direita */

t = a[i]; a[i] = a[j]; a[j] = t; /* troca */

} while (j > i);

// para desfazer a troca extra realizada quando j<=i e saiu do

// repeat interno. t já tem o valor de a[i]

a[j] = a[i];

a[i] = a[d] ;/* poe a[d] em seu lugar final */

a[d] = t;

return (i);

}

Quicksort

Se a chave mais a direita for a menor:

o algoritmo apresentado não funciona

Se a chave mais a direita for a maior:

o algoritmo apresentado não funciona

Colocar sentinelas nos loops

do{ i = i+1; } while (a[i] < v && i< d-1); /* pela esquerda*/

do{ j = j-1; } while (a[j] > v && j > 0); /* pela direita */

Quicksort: Partition

É difícil imaginar um loop interno mais simples

loops internos do quicksort envolvem simplesmente incrementar um ponteiro e uma comparação

é o que faz o quicksort ser realmente rápido

quando introduzimos outros testes no loop interno, perde-se em desempenho.

Pode-se garantir que a[d] nunca será o maior nem o menor

Quicksort: Partition

Pegue arbitrariamente 3 elementos de a:

a[d], a[e] e a[int((e+d)/2)]

Compare os 3 e tire aquele que tem seu valor no meio dos dois

Troque com a[d]

Execute o partition

Vantagem: acrescentam-se um número fixo de instruções fixas e não testes que variam com o tamanho do arquivo

Quicksort

Características:

um arquivo que já está classificado, somente fixa um elemento em cada chamada.

sub-arquivo da direita de tamanho 1

o algoritmo não é estável

Quicksort

Características:

quanto ao tratamento do cruzamento dos ponteiros na presença de chaves iguais

tanto faz ambos os ponteiros pararem, um andar e outro parar, nenhum parar

pode-se colocar dois elementos na posição se deixar o loop funcionar mais uma vez

mudanças devem ser feitas no algoritmo apresentado para arquivos com grande número de chaves repetidas

Problemas:

quero selecionar um subconjunto de registros tal que contenha os N de chaves maiores ou menores

quero encontrar um registro tal que sua chave esteja em uma posição do arquivo

Uma classificação completa não será necessária sempre

Quicksort

Quicksort na Seleção

Solução:

uma forma de proceder é classificar tudo e pegar o registro de uma dada posição ou os N maiores

pode-se fazer melhor usando o método QUICKSORT

Quicksort na Seleção

Solução:

a operação de achar uma posição é um caso especial da seleção de um conjunto de números k-menores

um algoritmo não pode garantir que um item em particular é o k-ésimo menor sem ter identificado os (k-1) elementos que são menores e os N-k elementos maiores.

Quicksort na Seleção

o método de particionamento do quicksort rearruma um array a e retorna um inteiro i tal que

a[0], ...a[i-1] são menores ou iguais a [i]

a[i+1] ..a[n] são maiores ou iguais a a[i]

se foi pedido o k-ésimo elemento do array e k = i então está feito

se k< i então tenho que tratar agora o sub-arquivo da esquerda caso contrário, o da direita.

Árvores Binárias

Árvores

Vamos considerar uma estrutura usada em muitas aplicações - a árvore

Uma árvore é um conjunto não finito de elementos onde

um elemento é chamado de raiz

os outros são divididos em subconjuntos disjuntos, onde cada um é uma árvore

cada elemento é um nó da árvore

Árvores

as estruturas vistas anteriormente são unidimensionais:

um item segue o outro

Árvores são estruturas encadeadas bi-dimensionais

definições básicas

terminologia associada a árvores

formas de representação no computador

Árvores

árvores são encontradas freqüência

muitas pessoas organizam seus ancestrais /ou descendentes: árvore genealógica

diagrama hierárquico de uma organização - grande corporação: decomposição

representa hierarquia

Terminologia

caminho em uma árvore:

é uma lista de nós distintos no qual nós sucessivos estão conectados por ramos da árvore

um nó é designado como raiz

uma propriedade de definição da árvore é a existência de exatamente um caminho entre a raiz e cada um dos nós da árvore

se existir mais de um caminho entre a raiz e um nó, não temos uma árvore e sim um grafo.

Terminologia

Terminologia

não existe direção nos ramos

nós normalmente pensamos que os ramos saem da raiz ou vão para a raiz, dependendo da aplicação

normalmente desenha-se árvore com a raiz no topo, e fala-se que o nó y está abaixo do nó x (e x acima de y) se x está no caminho de y para a raiz

Terminologia

cada nó (exceto a raiz) tem exatamente um nó acima

nó pai ou antecessor

os nós imediatamente abaixo de outro nó

nós filho ou descendente

filhos de um mesmo nó pai

nós irmãos

Terminologia

grau

é o número de subárvores de um nó

grau de A é 3 de N é 4 de J é 1

nós sem filhos são normalmente chamados terminais ou folhas

nós com pelo menos um filho são chamados não-terminais

Terminologia

qualquer nó é a raiz de uma sub-árvore consistindo dele e dos nós abaixo

nós terminais

podem não ter nome ou informação associada: especialmente nesse último caso nos referimos aos:

nós não terminais: nós internos

nós terminais: nós externos

Árvores

Árvores

A única diferença entre as duas árvores é a ordem na qual as sub-árvores estão arrumadas

A definição de árvore não faz distinção entre sub-árvores de uma árvore

Uma árvore ordenada é definida como uma árvore onde as sub-árvores formam um conjunto ordenado

Árvores

Em uma árvore ordenada vamos falar de primeiro, segundo e último irmão

o primeiro nó é o mais velho e o último é o mais novo

Árvores

Árvores ordenadas

é uma na qual a ordem de cada filho em cada nó é especificada

Árvores não ordenadas

é claro que os filhos são colocados em uma ordem ao desenhar a árvore, mas ela pode não ser significativa

Terminologia

Terminologia

os nós na árvore a dividem em níveis

o nível de um nó é o número de nós no caminho entre ele e a raiz

O nível da raiz é zero

o nível de um nó é o nível de seu pai + 1

o nível de C é 1

o nível de K é 3

o nível de P é 5

Terminologia

Altura de uma árvore

é o nível máximo entre nós da árvore

ou a distância máxima entre a raiz e qualquer nó

Floresta

um conjunto de árvores é chamado floresta

se removemos a raiz e os arcos que a ligam às sub-árvores, ficamos com uma floresta

Árvore Binária

é um conjunto finito de elementos que é ou vazio ou composto de três conjuntos disjuntos

o primeiro contém um único elemento, a raiz

os outros dois subconjuntos são árvores binárias

as sub-árvores da esquerda e da direita

As sub-árvores da esquerda ou da direita podem estar vazias

Árvore Binária

O conceito de árvores está diretamente ligado à recursão

Cada elemento da árvore é um nó

É uma árvore ordenada consistindo de dois tipos de nós

nós externos: sem filhos

nós internos: com exatamente dois filhos

Árvore Binária

Árvores Binárias

Desde que dois filhos de cada nó interno são ordenados, tem-se:

o filho da esquerda e

o filho da direita

Cada nó interno tem que ter filho de direita e de esquerda, sendo que um ou ambos podem ser nós externos

Árvores Binárias

o propósito da árvore binária é estruturar os nós internos

os nós externos servem apenas como "placeholders”

usamos os nós externos pois estão presentes na maioria das definições das árvores binárias

a presença dos nós externos indicam para nós com um filho se este é o filho da esquerda ou da direita da árvore binária

Árvores Binárias

uma árvore binária vazia:

consiste de nenhum nó interno e um nó externo

uma árvore binária é uma árvore ordenada, na qual cada nó tem 0, 1, ou 2 filhos

cada filho corresponde a uma árvore binária

Árvores Binárias

O número de sub-árvores a esquerda e a direita vazias (nós externos) em uma árvore binária com n nós é de n+1:

se n = 1 então 2 nós externos

se n = 2 então 3 nós externos

Se vale para n então uma árvores com n+1 nós

 foi substituído um nó externo por um interno e 2 externos

 o número de nós externos é então:
n+1-1+2 = (n+1) +1

Árvores Binárias

Definição de Árvores

“uma árvore é um único nó ou um nó raiz conectado a um conjunto de árvores”

Definição de Árvores Binárias

“uma árvore binária é um nó externo ou um nó raiz (interno) conectado a esquerda e a direita a árvores binárias”

Representação de Árvores Binárias

Representação de Árvores Binárias

Typedef struct tipo_no {

char conteudo;

struct tipo_no * filho_esquerda;

struct tipo_no * filho_direita;

} tipo_no;

A

B

C

Representação de Árvores Binárias

Typedef struct {

char conteudo;

tipo_no * filho_esquerda;

tipo_no * filho_direita;

tipo_no * pai;

} tipo_no

A

B

C

Representação de Árvores Binárias

Na representação nós externos podem ser

NULL

ponteiro para o próprio nó

A

B

C

Representando árvores binárias

Representando Florestas

árvores binárias possuem dois ponteiros em cada nó interno, um para cada filho, e portanto sua representação é imediata

o que fazer para árvores gerais ou florestas, com um número arbitrário de filhos por nó, que requerem um número arbitrário de ponteiros

Representação depende da Aplicação

Representando Florestas

se não é necessário caminhar para os níveis de baixo da árvore mas só para os de cima

percorre-se a ávores dos nós terminais para os não terminais e por último a raiz

B

A

C

Representando Florestas

Typedef struct {

char conteudo;

tipo_no * para_filho;

tipo_no * para irmão;

} tipo_no

A

B

C

D

E

Representando Florestas

se é necessário caminhar para os níveis mais altos

empregar uma lista encadeada conectando o nó com seus irmãos e outra com seus filhos

ao invés de empregar um nó dummy para terminar cada lista pode-se apontar de volta para seu pai permitindo mover para cima ou para baixo

esses ponteiros para pai tem que estar marcados para poder ser distinguidos dos ponteiros para irmãos

alternativamente pode-se armazenar o nome do pai de forma que a busca pára quando o nó for revisitado

Representando Florestas

Essa representação cada nó possui exatamente dois ponteiros

1 para filho e

1 para um irmão

Onde está a diferença entre essa estrutura e uma árvore binária??

não existe

Operações em Árvores Binárias

Operações em Árvores Binárias

Aplicações com Árvores Binárias

É uma estrutura útil quando uma de duas decisões devem ser tomadas no decorrer do processo.

Exemplo:

Encontrar todas as duplicatas em uma lista de números

Uma forma de fazer isso é comparar o número com todos os que o precedem

isto não é uma solução eficiente

Aplicações com Árvores Binárias

Solução:

Vamos empregar uma árvore binária

Armazenam-se os números na árvore de forma a:

o 1º número é armazenado na raiz de uma árvore com apenas um nó interno

cada um dos próximos números na lista é comparado com a raiz:

caso seja igual é uma duplicata

caso seja menor, é armazenado na sub-árvore da esquerda seguindo-se recursivamente o mesmo procedimento

caso seja maior, é armazenado na sub-árvore da direita seguindo-se recursivamente o mesmo procedimento

Aplicações com Árvores Binárias

Aplicações com Árvores Binárias

Outra aplicação comum é atravessar a árvore binária, visitando cada nó

como sistematicamente visitaremos cada nó ?

essa operação é trivial para listas lineares pela sua definição

para árvores, existem várias formas de proceder

os métodos diferem conforme a ordem em que se visitam os nós

Atravessando Árvores Binárias

Métodos

pré-ordem:visite a raiz, então visite a subárvore da esquerda, depois a subárvore da direita

em-ordem ou ordem simétrica: visite a subárvore da esquerda, então visite a raiz, depois a subárvore da direita

pós-ordem: visite a subárvore da esquerda, então visite a subárvore da direita, depois a raiz

pré-ordem:

- * a b * + f g e

em-ordem:

a*b - f+g * e

pós-ordem:

a b * f g + e * -

Atravessando Árvores Binárias

Atravessando Árvores: Pré-ordem

a implementação mais simples desse método - recursiva

como se visita uma subárvore de cada vez, seguindo-se a regra recursiva , cada subárvore é visitada começando pela raiz

void pre_ordem(tipo_no * raiz)

{ if (raiz == NULL) return;

Visite(raiz);

pre_ordem (raiz->filho_esquerda);

pre_ordem (raiz->filho_direita); }

Atravessando Árvores: Em-ordem

a implementação mais simples desse método - recursiva

void em_ordem(tipo_no * raiz)

{ if (raiz == NULL) return;

em_ordem (raiz->filho_esquerda);

Visite(raiz);

em_ordem (raiz->filho_direita); }

Atravessando Árvores: Pós-ordem

a implementação mais simples desse método - recursiva

void pos_ordem(tipo_no * raiz)

{ if (raiz == NULL) return;

pos_ordem (raiz->filho_esquerda);

pos_ordem (raiz->filho_direita);

Visite(raiz); }

Atravessando Árvores

quarta estratégia não é recursiva

visito os nós como aparecem na página lendo de cima para baixo e da esquerda para a direita

Exercícios

Retirar a recursão das rotinas que atravessam a árvore em pré-ordem, em-ordem, pós-ordem.

Para retirar a recursão é necessário o uso de pilha - pop e push

Pré-ordem

void pre_ordem(tipo_no * raiz) {

p = raiz;

do { /* segue pelo ramo da esq. até encontrar NULL */

while (p != NULL) {

push(p);

p=p->filho_esquerda ;

}

if (!empty) { /* verifica se já processou toda árvore */

p = pop;

visite(p);

p = p->filho direita;

}

} while(!empty || p != NULL );

}

1 - A B D H

2 - A B D

3 - A B

4 - A B I

Árvore Binária de Busca

É uma algoritmo simples e eficiente

a árvore tem que estar construída de forma a que:

todos os registros com chaves menores estão na sub-arvore da esquerda

todos com chaves maiores ou iguais na sub-arvore da direita

a inserção dos nós da árvore deve satisfazer a essa propriedade

Árvore Binária de Busca

A busca binária imediatamente sugere a estrutura da função de busca

para achar um registro com chave v, primeiro compare contra a raiz, se menor vá para a sub-árvore da esquerda , se maior para a sub-árvore da direita

aplique o método recursivamente

Árvore Binária de Busca

Z

9

Árvore Binária de Busca

a cada passo, garante-se que nenhuma outra parte da árvore contém a chave sendo buscada

a procedure pára quando um nó com v é encontrado

encontra-se sempre

nós terminais apontam para Z, um único nó “dummy”

se encontrar em nó cujo endereço = Z, “não encontrou”caso contrário, encontrou

Árvore Binária de Busca

Typedef struct

{ int chave;

int info;

tipo_nó * e, * d;

} tipo_nó;

tipo_nó * t,

* raiz,* z;

tipo_nó * Busca_arvore(int v; tipo_nó * x){

z->chave = v;

while (v != x->chave) {

if (v < x->chave)

x = x -> e;

else x = x -> d;

}

return(x);

}

Árvore Binária de Busca

É conveniente usar um header para a árvore cujo ponteiro da direita aponta para a raiz atual da árvore e com chave menor que qualquer outra chave

o ponteiro da esquerda do header não será usado

sua necessidade aparecerá quando discutirmos inserção

árvore vazia

{ z=malloc (sizeof(tipo_nó));z->e = z; z->d = z;

header=malloc (sizeof(tipo_nó)); header->chave = menor;

header->e = z; header->d = z ; }

Árvore Binária de Busca
Inserção de um nó

Para inserir um nó na árvore, temos que:

fazer uma busca com insucesso

colocá-lo no lugar de z no ponto que a busca terminar

é necessário saber por que nó se chegou a Z (pai), conforme caminha-se para baixo na árvore

quando Z for alcançado, pai aponta para o nó cujo ponteiro tem que ser mudado

isto é, o ponto de substituição de um nó externo por um interno para o novo nó sendo inserido

Árvore Binária de Busca
Inserção de um nó

Z

Árvore Binária de Busca
Inserção de um nó

Z

Árvore Binária de Busca
Inserção de um nó

tipo_nó * Insere_árvore (int v, tipo_nó * x)

{ tipo_nó * pai;

z->chave = v;

do

{ pai = x ;

if (v < x->chave)

x = x->e;

else

x = x->d;

} while(x != z);

x = malloc (sizeof(tipo_nó));

x ->chave = v;

x->e = z;

x->d = z;

if (v < pai->chave)

pai->e = x;

else

pai->d = x;

return(x); }

Árvore Binária de Busca
Inserção de um nó

a árvore está classificada se percorrida da forma correta

as chaves aparecem em ordem se lidas da esquerda para a direita

basta atravessar a árvore em-ordem

o método de sort vem direto da arrumação da árvore

o programa tem apenas os ponteiros para se preocupar

similar ao quicksort com o nó raiz fazendo o lugar do elemento de particionamento

a diferença entre ele e o quicksort é a memória extra usada para ponteiros

Árvore Binária de Busca
Remoção de um nó

As implementações fornecidas acima para busca, inserção e sort em árvore binária são simples.

A remoção de um nó é um tanto difícil

remoção de um nó terminal

ponha o ponteiro correspondente do pai apontando para Z (ou NULL)

se possui apenas um filho mova o ponteiro do filho para o ponteiro apropriado do pai

se o nó possui dois filhos mas um desses dois filhos não possui filhos, use esse nó para substituir o nó removido

Árvore Binária de Busca
Remoção de um nó

O que acontece com nós mais altos na árvore

substitua este com o nó com a próxima chave mais alta - nó substituto

este nó pode ter, no máximo, um filho

se é o menor dos maiores, seu ponteiro esquerdo deve ser nulo e, portanto, é facilmente removido.

faça o ponteiro para esquerda do pai de nó substituto apontar para o seu ponteiro da direita

copiar os ponteiros do nó sendo removido para os do nó substituto

fazer o ponteiro do pai do nó sendo removido apontar para o nó substituto

Árvore Binária de Busca
Remoção de um nó

Removendo 5:

basta que o ponteiro a direita de 4 aponte para Z
ou assuma o valor NULL

Árvore Binária de Busca
Remoção de um nó

Removendo 3:

basta que substituir o nó 3 pelo nó 2

continua valendo a regra de formação da árvore

Árvore Binária de Busca
Remoção de um nó

Removendo 4:

basta que o substituir 4 pelo 5

continua valendo a regra de formação da árvore

Árvore Binária de Busca
Remoção de um nó

Removendo 6 - raiz:

substituir o nó 6 pelo nó 6 abaixo de 8

o menor dos maiores

Árvore Binária de Busca
Remoção de um nó

Removendo 7 - raiz:

6 fica como raiz

8 aponta para o filho a direita de 6

Árvore Binária de Busca
Remoção de um nó

Deleta_nó ( tipo_nó * x)

{ tipo_nó *pai, *t, *aux;

do { pai = x;

if (z->chave < x->chave)

x = x->e;

else

x = x->d;

}

while (x->chave != z->chave);

t=x;

/* x e t apontam para o nó a ser deletado. Pai tem o pai do nó a ser deletado */

/* se nó terminal */

if (t->d == z)

x = x->e;

else

if (t->d->e ==Z)

/* filho da direita não tem filhos a esquerda. Um de seus filhos só tem um filho */

{x = x->d;

x->e = t->e; }

else

/*nós mais altos da árvore*/

Árvore Binária de Busca
Remoção de um nó

{ aux =x->d;

while (aux->e->e != Z)

aux=aux->e;

/*acha o menor dos maiores */

x = aux->e;

/* em x o menor dos maiores. Em aux está seu pai */

aux->e = x->d;

/* ponteiro da esq. do pai aponta para o da direita do menor dos maiores*/

x-> e = t->e;

x-> d = t->d;

}

/*substitui o nó removido */

if ( t->chave < pai->chave) pai->e= x;

else

pai->d = x;

}

free(t);

Árvore Binária de Busca

A árvore obtida depende da seqüência de inserção de nós

Para que a árvore binária de busca seja completa

completa tem altura mínima

o conjunto das chaves deve ser reordenado

árvore comum - O (n)

árvore completa - O (log n)

Árvore Binária de Busca

Para que a árvore binária de busca seja completa

o conjunto das chaves deve ser reordenado

Sejam so e s n+1 duas chaves fictícias e já inseridas

a cada passo inserir em T uma nova chave que seja de índice médio entre i e j - duas chaves já inseridas

Árvore Binária de Busca

1 2 3 4 5 6 7 8 9

Árvore Binária de Busca

A árvore completa é ótima para o problema de busca, quando a freqüência de acesso aos nós é igual

Normalmente estas freqüências são diferentes

É interessante construir uma árvore binária que seja a melhor possível no que diz respeito à busca para freqüências conhecidas

Árvore Binária de Busca

A busca binária - corresponde a busca em uma árvore completa

A raiz r da árvore corresponde à chave que ocupa a posição central

as raízes das subárvores da esquerda e da direita são as centrais dos subarrays

Hash

Um método para diretamente referenciar registros através de transformações aritméticas nas chaves em uma tabela de endereços

Acesso “direto” a cada registro

se as chaves são inteiros distintos de 1 a N

armazenar cada registro em uma posição i correspondente a sua chave

acesso imediato com o valor da chave

Hash

Hashing é uma generalização desse método trivial para aplicações típicas de busca quando não se tem um conhecimento tão especializado sobre as chaves

Hash

Identificar uma função hash que

transforma chaves de busca em endereços de uma tabela

idealmente chaves diferentes devem cair em endereços diferentes

isto não é sempre verdade

chave, info

Hash

Duas ou mais chaves diferentes podem cair no mesmo endereço - COLISÃO

a segunda parte da busca por hash é a solução de colisão que trata as chaves que caem no mesmo endereço

Hash

Solução de Colisão

lista encadeada:

apropriado em situações altamente dinâmicas

o número de chaves de busca não pode ser predito

busca seqüencial

Função Hash

Função que transforma chaves em endereços

Tem propriedades similares a um gerador de números aleatórios

as chaves são normalmente pequenos strings de caracteres

devem ser transformados em números de 0 a M-1 onde M é o nº de registros que cabem na memória disponível

a função ideal é aquela fácil de computar e que se aproxima de números aleatórios

Função Hash

1º passo: transforma chaves (strings) em números

pode-se usar a representação binária das chaves se permitido

para chaves grandes tem que remover bits das chaves e compactá-los em uma palavra de máquina

Transformada a chave em um inteiro temos:

um inteiro grande que corresponde a chave: provavelmente um dos métodos comuns de hash é escolher M primo e fazer h(k) = mod( k, M )

Função Hash

Transformação de chave alfanumérica em inteiro

para a chave AKEY

se a codificação é i -ésima letra do alfabeto igual ao o número inteiro i

para AKEY a codificação é

000101010110010111001

equivalente a 44217 em decimal aplicando

se M = 80 então AKEY endereça a posição 80 na tabela

por exemplo BARH também endereça para 80

Função Hash

Na essência estamos tratando nossa chave como um número de 32-bits

suponha que façamos a escolha infeliz de M = 32

k mod de 32 não é afetado por somar 32;

o valor da função hash é simplesmente o valor da última letra (representando letras com 5 digitos)

Função Hash

M é escolhido primo para reduzir as colisões

cada bit deve contribuir na formação do endereço

Uma boa função hash tem que levar em consideração todos os caracteres da chave

Função Hash

A situação mais comum são chaves longas de não inteiros

Problema: uma função hash com chaves grandes, difíceis para se representar em funções aritméticas

Função Hash

Pode-se aplicar uma hash transformando pedaço a pedaço da chave

chave ----- char chave[50]

endereço = 0

for (i=0; i<50; i++)

endereço =mod((endereço + código (chave[i])), M)

garante não ocorrência de overflow

Função Hash

Existe um conjunto de funções possíveis, sua eficiência depende do conjunto de chaves sendo mapeado

Os métodos não preservam a ordem das chaves

não é possível atravessar a tabela hash na ordem das chaves

um exemplo que preserva a ordem é chave/c

origina várias colisões

Tabela Hash

Ocorrência das Colisões

a função hash traduz chave em endereço de tabela

como tratar o caso em que duas chaves possuem o mesmo endereço

Tratamento de Colisões

Cadeias Separadas (Listas Encadeadas)

Linear Probing

armazenamento na própria tabela Hash

Cadeias Separadas

Cadeias separadas

dois registros endereçam uma mesma posição na tabela

cada posição na tabela aponta para uma lista de registros com o mesmo endereço

a tabela pode ser só de endereços ou também conter o 1o. elemento da lista

como o tamanho desta lista é variável - Lista Encadeada

Cadeias Separadas

Armazenamento de um registro:

calcula-se o endereço

se não existe ninguém naquela posição, armazena o registro na tabela (1o. da lista)

se existe, armazena o registro na lista

a lista em princípio é não ordenada e os registros são recuperados através de busca seqüencial

calcula-se M tal que as listas sejam pequenas (por exemplo, em média 10 elementos)

na inserção, armazena-se no início, operação mais simples

Cadeias Separadas

Busca de um registro:

calcula-se o endereço

se não existe ninguém naquela posição, retorna busca com insucesso

se existe, compara chave com o 1o. Registro da lista

se igual retorna o registro

senão, continua a busca seqüencial na lista

Métodos híbridos: usam árvore binária de busca ao invés de listas

Linear Probing

Linear Probing: armazenamento das colisões na própria tabela

o número de elementos pode ser estimado com antecedência

memória contígua suficiente pode ser alocada

pode-se trabalhar sem ponteiros

Muitos métodos existem que armazenam N registros em uma tabela onde M >N usando espaço em branco na tabela para armazenar colisões

Linear Probing

Linear probing: o mais simples

quando existir uma colisão, vá para a próxima posição na tabela.

para cada posição pesquisada é possível:

1. a chave combina;

2. não combina;

3. posição vaga

para 1 e 3 termina busca com sucesso/insucesso

para 2, vai para o próximo endereço e repete o processo

Linear Probing

Inserção:

após uma busca com insucesso, recheia-se a posição vaga com o registro a ser inserido

Busca

termina ao encontrar o registro - uma busca com sucesso

ou ao encontrar uma posição vaga - uma busca com insucesso

Linear Probing

Remoção de um elemento

retirar um elemento deixa uma posição vaga, o que pode impedir a recuperação de um registro

requer um sinal para marcar posição vaga

Índices da Tabela

tabela circular

Linear Probing

Tamanho da Tabela

tabela maior do que quando usa lista encadeada

tenho que ter M>N

Memória total usada menor devido a não existência de ponteiros

Outras formas: Double Hashing

O código a seguir mostra uma implementação das funções básicas usando essa organização simples e ilustra algumas convenções que serão usadas nos métodos de busca

propriedade: nunca gasta mais de lg N+1 comparações : não vou demonstrar vide livro

É importante notar que o tempo de inserção de novos termos é alto para busca binária: o array tem que ser mantido ordenado Þ alguns registros tem que ser movimentados para fazer lugar para o novo registro

uma inserção de chaves randômica requer que N/2 registros sejam movimentados em média Þ esse método não pode ser usado para aplicações envolvendo muitas inserções

É bom para aplicações em que a tabela pode ser contruida antes no tempo, passa por um sort (como Quicksort) e então usa um número grande de buscas

Acrescentar transparências com a solução dos exercícios.

1. pilhas serão mais encontradas do que listas => sua relação com a recursão

2. existem algoritmos para os quais filas é a estrutura natural

no_aux = malloc(sizeof(tipo_no)) /* deve testar se !=de NULL -

estouro de memória*/

if (no_aux != NULL) /* tudo ok */

Vale o mesmo para filas

No exemplo do caderno de telefones o arquivo consiste de todas as entradas. Cada entrada é um registro, a chave na qual está ordenado é o nome do dono do telefone

No exemplo do caderno de telefones o arquivo consiste de todas as entradas. Cada entrada é um registro, a chave na qual está ordenado é o nome do dono do telefone

Esse método é chamado de sort de seleção porque funciona selecionando repetidamente o menor elemento remanescente - ver exemplo da fig 8.1

o programa abaixo é a implementação desse processo:

este é um dos métodos de sort mais simples e funciona bem para peq. arquivos

pq cada registro é movido pelo menos uma vez, => é o método escolhido para classificar arquivos com registros muito grandes e chaves pequenas => será discutido a seguir em detalhe

cab => 3 para 1, ==> abc ==> pgm acima deveria ter contador reinicializado a cada passada e um exit caso contador ficasse 0

Características de Performance dos 3 algoritmos

seleção: gasta a maior parte do tempo para achar o mínimo na parte desordenada do array

bubble sort: remaneja o máximo possível de objetos em cada estágio: gasta muito tempo impondo alguma ordem a parte restante do array.

Vamos estudar agora um algoritmo de sort inventado em 1960 por C.A.R.Hoare, e tem sido muito estudaddo desde então.

Quicksort é popular por ser um bom algoritmo de sort (funciona bem em uma grande variedade de situações), fácil de implementar e consome menos recurso do que qq outro método de sort.

Quicksort é feito no próprio local, usa apenas uma memória auxiliar pequena, uma pilha, requer em torno de N logN operações para em média classificar N itens e tem um loop interno muito pequeno

usa N2 no pior caso - é sensível, um pequeno erro de implementação pode causar grandes estragos em arquivos

o desempenho desse algoritmo é bem conhecido por extenso estudo matemático e po experiências que comprovam, e está em uma grande variedade de aplicações

versões do quicksort foram desenvolvidas para melhorar performance - vamos estudar essas variações

o maior problema desse algoritmo é que é extremamente ineficiente em arquivo simples

Por exemplo, se for chamado com um arq. que já está classificado, as partições serão degeneradas e o pgm vai chamar a si mesmo N vezes, somente fixando um elemento em cada chamada. (sub-arquivo da direita de tam 1)

o algoritmo não é estável

qdo existem chaves iguais:

deve fazer ambos os ponteiros parar em chaves iguais ao elemento sedo particionado, um andar e outro parar, nenhum parar

essa questão foi estudada matematicamente em detalhe e chegou-se a conclusão que o melhor é parar os dois ponteiros => isso tende a balancear a partição no caso de chaves iguais

outra questão é o tratamento do cruzamento dos ponteiros na presença de chaves iguais.
o pgm acima está terminando a varredura qdo j < i e, então usa quicksort (l,j) para o primeiro call recursivo => qdo j = i => pode-se colocar dois elementos na posição se deixar o loop funcionar mais uma vez

se não fizer isso, o sub-arquivo da direita vai ter sua chave mais a direita a menor, pode fazer o arq. degenerar

Mudanças devem ser feitas no algoritmo apresentado para arq. com grande número de chaves repetidas

o maior problema desse algoritmo é que é extremamente ineficiente em arquivo simples

Por exemplo, se for chamado com um arq. que já está classificado, as partições serão degeneradas e o pgm vai chamar a si mesmo N vezes, somente fixando um elemento em cada chamada. (sub-arquivo da direita de tam 1)

o algoritmo não é estável

qdo existem chaves iguais:

deve fazer ambos os ponteiros parar em chaves iguais ao elemento sedo particionado, um andar e outro parar, nenhum parar

essa questão foi estudada matematicamente em detalhe e chegou-se a conclusão que o melhor é parar os dois ponteiros => isso tende a balancear a partição no caso de chaves iguais

outra questão é o tratamento do cruzamento dos ponteiros na presença de chaves iguais.
o pgm acima está terminando a varredura qdo j < i e, então usa quicksort (l,j) para o primeiro call recursivo => qdo j = i => pode-se colocar dois elementos na posição se deixar o loop funcionar mais uma vez

se não fizer isso, o sub-arquivo da direita vai ter sua chave mais a direita a menor, pode fazer o arq. degenerar

Mudanças devem ser feitas no algoritmo apresentado para arq. com grande número de chaves repetidas

seleção tem muitas aplicações no processamento de dados: normalmente uma peq. parte do arquivo é processada : o sort por seleção já visto, se adaptaria muito bem para a seleção dos menores elementos

Um método interessante que adapta o Quicksort e executa legal para qq valor de k (em tempo de exec. médio linear) é formulado a partir do quicksort

relembre que o método de particionamento do quicksort rearruma um array a[1..n] e retorna um inteiro i tal que a[1], ...a[i-1] são menores ou iguais a [i] e a[i+1] ..a[n] são maiores ou iguias a a[i]

seleção tem muitas aplicações no processamento de dados: normalmente uma peq. parte do arquivo é processada : o sort por seleção já visto, se adaptaria muito bem para a seleção dos menores elementos

Um método interessante que adapta o Quicksort e executa legal para qq valor de k (em tempo de exec. médio linear) é formulado a partir do quicksort

relembre que o método de particionamento do quicksort rearruma um array a[1..n] e retorna um inteiro i tal que a[1], ...a[i-1] são menores ou iguais a [i] e a[i+1] ..a[n] são maiores ou iguias a a[i]

Ordenação: isso fica significativo quando representamos árvores no computador, desde que existe menos flexibilidade em como representar árvores ordenadas- dependente da aplicação para a

árvore

árvores estão diretamente ligadas a recursão (veremos a seguir)a forma mais simples de definir árvores é recursivamente como se segue: "uma árvore é um único nó ou um nó raiz conectado a um conjunto de árvores"

árvores estão diretamente ligadas a recursão (veremos a seguir)a forma mais simples de definir árvores é recursivamente como se segue: "uma árvore é um único nó ou um nó raiz conectado a um conjunto de árvores"

A representação mais comum de árvores binárias ;é a que usa registros com dois links por nó normalmente serão usados os links l (left) e r (right) para indicar a ordem escolhida de representação correspondente a cada caminho da árvore desenhada em uma página

para algumas aplicações é apropriado ter dois tipos diferentes de records, um para nós internos e outro para nós externos OU ter os mesmos tipos de nós e links nos nós externos para outros propósitos

para representar uma floresta com processamento de cima para baixo, necessita-se de uma forma de tratar filhos de cada nó sem prealocar um número específico de nós

esse é exatamente a restrição das listas encadeadasjá estudadas. Pode-se usar uma lista encadeada para os filhos de um dado nó.

uma lista conectando o nó com seus irmãos e outra com seus filhos (ver fig 4.7)

ao invés de um nó dummy para terminar cada lista, fazemos ela apontar de volta para seu pai para poder se mover para cima ou para baixo (esses links para pai tem que estar marcados para poder ser distiguidos dos links para irmãos) Reconhecer fim da lista de irmãos

alternativamente pode-se armazenar o nome do pai de forma que a busca pára quando o nó for revisitado

outra forma de visitar é inorder traversal (serve para escrever as exp. de forma infixa) => de forma

similar a preorder a inorder é definida recursivamente: "visite a subárvore da esquerda, visite a raiz e depos a subárvore da direita"

também é chamada de ordem simétrica

a implementação baseada em pilha é quase idêntica ao acima (guardo link para a raiz , isso

se a implementação de árvore não fornecer)

na busca binária nós usamos uma árvore binária para descrever a seq. de comparações feitas buscando em um array ==/== aqui nós construimos uma estrutura de dados de registros, conectados com ponteiros e usamos isso para a busca

tempo de execução dos algoritmos Þ dependente da forma da árvore em média para chaves inseridas de forma randômica em torno de 2 lnN comparações e no pior caso N comparações

Considere a árvore mostrada do lado esquerdo da figura 14.12 Þ deletar um nó é fácil se:

terminalÞ ponha o link correspondente do pai com null

ou se possui apenas um filho como A, H ou R Þ mova o link na criança para o link do pai apropriado

ou mesmo se o nó possui dois filhos mas um desses dois filhos não possui filhos como N Þ use esse nó para substituir o pai.

a procedure a seguir deleta um nó apontado por t de uma árvore cuja raiz é x

um nó com chave v pode ser deletado com a chamada treedelete(treesearch(v,head) ,head))

a variável p é usada para manter o pai de x e a variável c é usada para achar o sucessor do nó a ser deletado

após a deleção x é o filho de p

o dispose de t foi deixado para fora da rotina atual : o nó pode bir a ser adicionado em outra estrutura

o programa primeiro busca a árvore na maneira normal para encontrar a localização de t na árvore

o propósito dessa busca inicial é achar p que pode ser ligado a outro após t ter sido deletado

a seguir o pgm testa três casos:

se t não tem filho a direita Þ o filho de p após a deleção é o flho da esquerda de t

se t tem filho da direita e esse filho não tem filho da esquerda Þ o filho da direita será filho p depois da deleção e esse filho teró como filho da esquerda o link copiado de t

de outra forma, x é setado com o nó com o menor valor da dubárvore da direita penderada em t Þ o link da direita desse nó é copiado para o link da esquerda do seu pai e ambos seus links são setados iguais aos de t e o pai de t aponta para esse link.

novamente tira-se vantagem das propriedades aritméticas da função mod e um truque simples de computação (Horner’s method)

novamente tira-se vantagem das propriedades aritméticas da função mod e um truque simples de computação (Horner’s method)

Esse método se baseia em outra forma de escrever a chave ver código pag 233

h valor computado, key[i] contém j se o i-ésimo caracter é a letra j do alfabeto

mod no meio não deixa dar overflow durante a computação

baseado nisso assumimos chaves inteiras e a função hash mod (chaves reais usam a função acima)

esse método é tradicionalmente chamado separaçao de cadeias obviamente o tempo para uma busca depende do tamanho da lista a lista pode ser mantida desordenada (considerando-se que deve ficar peq. se não for grande o número de colisões)

reduz o numero de comparações para busca seq. por um fator de M

Uma alternativa de manutenção das cabeças das listas é fazer o array de M cabeças e cada um aponta para o 1º da lista - 1ª chave

outra implementação: 1ª chave na tabela

M nessas implementações é escolhido relativamente peq. para não usar uma área grande de memória contígua.

pode-se usar M grande para ter listas peq. e o search seq. ser o melhor método dntro das coincidências

métodos híbridos: usam árvore binária de busca ao invés de listas

M pode ser escolhido 1/10 do número de chaves esperadas Þ listas de 10 elem em média

M nessas implementações é escolhido relativamente peq. para não usar uma área grande de memória contígua.

pode-se usar M grande para ter listas peq. e o search seq. ser o melhor método dntro das coincidências

M pode ser escolhido 1/10 do número de chaves esperadas Þ listas de 10 elem em média

examina-se chaves que não mapeiam no mesmo endereço na busca qdo linear

para parar muitas buscas qdo isso ocorre

ao invés de colocar ou examinar a seguir, usa-se uma outra função hash para fornecer um incremento fixo

implementado por u = h2(v) no começo da proc e trocando x=x+1mod M por x+u

h2 tem que se ter o mesmo cuidado de escolha

1º u tem que ser <> 0

M e u tem que ser primos entre siÞ M primo e u<M

h2 tem que ser diferente de hh2(k) = M-2-kmod(M-2) aumenta muito o custo

Þ h2 = 8-kmod8 : valores de 8 a 1

resultado na fig 16,6

esses métodos são inconvenientes em sit. onde um número não predito de inserçoões e deleções podem ser processados

deleção Þ cautela

na inserção um a colisão colocou a depois de b e se b deletado Þ buraco e não acho a

uma sol. é outro flag que marca o lugar para busca e libera para inserção

examina-se chaves que não mapeiam no mesmo endereço na busca qdo linear

para parar muitas buscas qdo isso ocorre

ao invés de colocar ou examinar a seguir, usa-se uma outra função hash para fornecer um incremento fixo

implementado por u = h2(v) no começo da proc e trocando x=x+1mod M por x+u

h2 tem que se ter o mesmo cuidado de escolha

1º u tem que ser <> 0

M e u tem que ser primos entre siÞ M primo e u<M

h2 tem que ser diferente de hh2(k) = M-2-kmod(M-2) aumenta muito o custo

Þ h2 = 8-kmod8 : valores de 8 a 1

resultado na fig 16,6

esses métodos são inconvenientes em sit. onde um número não predito de inserçoões e deleções podem ser processados

deleção Þ cautela

na inserção um a colisão colocou a depois de b e se b deletado Þ buraco e não acho a

uma sol. é outro flag que marca o lugar para busca e libera para inserção

Algoritmos e Estruturas de Dados Programa do Curso

uso geral

2000-03-20T14:42:54