Estrutura de Dadoswiki.cbatista.net/lib/exe/fetch.php/ed-aula07-pilhas_e... · 2013. 11. 11. · Estrutura de dados onde a inserção e remoção de elementos ocorre a partir de uma

Estrutura de DadosEstrutura de DadosEstrutura de DadosEstrutura de DadosCarlos Eduardo Batista

Centro de Informática - [email protected]

� Pilhas e listas

Estruturas de DadosEstruturas de Dados2

� Ordenação (Classificação)◦ Rearranjar um conjunto de objetos

� Ordem ascendente ou descendente

◦ Ordenação interna� Tudo na memória principal� Seleção� Inserção� QuickSort� MergeSort

Pesquisa e classificação de dadosPesquisa e classificação de dados

� MergeSort

◦ Ordenação externa� QuickSort externo� Intercalação balanceada

3

� Ordenação interna� Complexidade

◦ Número de comparação entre chaves◦ Número de movimentações entre itens

� Usar memória com parcimônia sempre� Métodos simples

◦ Pequeno volume de informações◦ O(n2)


◦ O(n )

� Métodos eficientes◦ Menos comparações◦ O(n log n)

4

� Ordenação por seleção◦ Algoritmo simples

� Seleciona-se o menor item do vetor

� Troca-se com o item da primeira posição do vetor

� Repetir com n-1 restantes, depois n-2...◦ Até que reste apenas um elemento


◦ Até que reste apenas um elemento

� (n2/2) – (n/2) comparações

� 3(n-1) movimentações de registro

5

Ordenação por seleção

Pesquisa e classificação de dadosPesquisa e classificação de dados6

� Ordenação por inserção

� Em cada passo a partir do 2º (i=2), faça◦ Selecione o i-ésimo item da sequência fonte

◦ Coloque-o no lugar correto (de acordo com o critério de ordenação) na sequência destino

� O processo de ordenação termina quando◦ Um item com chave menor que o item em

consideração é encontrado


consideração é encontrado

◦ O final da sequência destino é atingido ‘a esquerda

� Usa-se um sentinela na posição 0 do vetor

7


� Quicksort

� Mais rápido para um grande leque de possibilidades

� Dividir para conquistar◦ Problemas menores são ordenados separadamente,

resultado é combinado

� Vetor é rearranjado a partir de um pivô


� Processo de partição◦ A parte esquerda com chaves menores ou iguais

◦ ao pivô.

◦ A parte direita com chaves maiores ou iguais ao pivô.

9

� Particionamento◦ Escolha do pivô (x)

◦ Percorre-se o vetor a partir da esquerda até que o valor seja maior ou igual ao pivô � V[i] >= x

◦ Percorre-se o vetor a partir da direita até que o valor seja menor igual ao pivô

V[j] <= x


� V[j] <= x

◦ Troca-se V[i] e V[j]

◦ Continuar o processo até que i e j se cruzem

10

� Particionamento

� Vetor V estará particionado de forma que◦ V[esq], V[esq+1]..., V[j] são menores ou iguais ao pivô (x)

◦ V[i], V[i+1],..., V[dir] são maiores ou iguais ao pivô (x)



typedef struct {Indice Esq, Dir;

} TipoItem;void QuickSort_NaoRec(Item *A, Indice *n) {

TipoPilha Pilha;Indice Esq, Dir, i, j;TipoItem Item;FPvazia(Pilha);Esq = 1;Dir = *n;Item.Dir = Dir;Item.Esq = Esq;Empilha(Item, Pilha);do {

if (Dir > Esq) {Particao(Esq, Dir, &i, &j, A);


Particao(Esq, Dir, &i, &j, A);Item.Dir = Dir; Item.Esq = i;Empilha(Item, Pilha);Dir = j;

} else {Desempilha(Pilha, Item);Dir = Item.Dir;Esq = Item.Esq;

}} while (!Vazia(Pilha));

}

void particao(Indice Esq, Indice Dir, Indice *i, Indice*j, Item *A) {

Item x, w;*i = Esq;*j = Dir;x = A[(*i + *j) / 2]; /* obtem o pivo x */do {

while (x.Chave > A[*i].Chave)(*i)++;

while (x.Chave < A[*j].Chave)(*j)--;


(*j)--;if ((*i) <= (*j)){ w = A[*i]; A[*i] = A[*j]; A[*j] = w;

(*i)++; (*j)--;}

}while (*i <= *j);}

void qordena(Indice Esq, Indice Dir, Item *A) {particao(Esq, Dir, &i, &j, A);if (Esq < j)

qordena(Esq, j, A);if (i < Dir)

qordena(i, Dir, A);}

void quicksort(Item *A, Indice *n) {


void quicksort(Item *A, Indice *n) {qordena(1, *n, A);

}


EstrututurasEstrututuras de dados de dados lineareslineareslineareslineares

� Pilhas (stack)

� Estrutura de dados onde a inserção e remoção de elementos ocorre a partir de uma único ponto de interação – o topo da pilha

� LIFO◦ Last In First Out

PilhasPilhas

◦ Last In First Out

� Exemplos◦ Pilha de pratos a lavar

◦ Pilha de execução na linguagem C� Variáveis locais são empilhadas em uma pilha

� Ao término da função, as variáveis são desempilhadas

18

Topo

PilhasPilhas19

Base

� Operações◦ Empilhar (push)� Insere um novo elemento no topo da pilha

◦ Desempilhar (pop) � Recupera e remove um elemento do topo da pilha

PilhasPilhas20

� Notação para expressões aritméticas:◦ Infixa� operador entre os operandos.

� (1 – 2) * (4 + 5)

◦ Posfixa� operador após os operandos.

� 1 2 – 4 5 + *

◦ Prefixa

PilhasPilhas

◦ Prefixa� operador antes dos operandos.

� * - 1 2 + 4 5

� Avaliação de expressões aritméticas

21

PilhasPilhas22

� Implementando pilhas◦ Um vetor de elementos� Armazenamento sequencial

◦ Uma variável para controlar o topo

PilhasPilhas23

�Operações�Criar uma pilha;

�Testar se a pilha está vazia;

�Testar se a pilha está cheia;

�Obter o elemento do topo (sem desempilhar);

�Empilhar um novo elemento (push);

�Desempilhar (e obter) o elemento do topo (pop).

PilhasPilhas

�Desempilhar (e obter) o elemento do topo (pop).

�Exibir os elementos da pilha

24

// Tipo base dos elementos da listatypedef struct elementos {

char nome[50];int num;

} t_elemento;

// Estrutura da pilhatypedef struct pilha {

PilhasPilhas25

typedef struct pilha {t_elemento vetor[MAX];int topo;

} t_pilha;

t_pilha criar() {t_pilha pilha;

pilha.topo = -1;

return pilha;}

int isVazia(t_pilha * pilha) {return (pilha->topo == -1);

}

PilhasPilhas26

}

int isCheia(t_pilha * pilha) {return (pilha->topo == MAX-1);

}

t_elemento getElementoTopo(t_pilha * pilha){

t_elemento vazio = { "" } ;

if (isVazia(pilha))return vazio; // erro

elsereturn pilha->vetor[pilha->topo];

}

t_elemento pop(t_pilha * pilha){

PilhasPilhas27

{t_elemento vazio = { "" };

if (isVazia(pilha))return vazio; // erro

elsereturn pilha->vetor[pilha->topo--];

}

int push(t_pilha *pilha, t_elemento valor){

if (isCheia(pilha))return 0; // erro

pilha->vetor[++pilha->topo] = valor;

PilhasPilhas28

return 1; // sucesso}

� ED formada por um conjunto de dados onde há uma relação de ordem linear

� Os dados são representados por nós, que podem conter dados primitivos ou compostos

� Exemplos◦ Lista telefônica, lista de setores de um disco

ListasListas

◦ Lista telefônica, lista de setores de um disco rígido, lista de resultados de uma busca na web...

29

Valores 0 1 2 3 4 5

...

N

� Operações◦ Criação de lista (vazia)

◦ Verificação de lista vazia

◦ Obtenção do tamanho da lista

◦ Obtenção/modificação de valor de uma posição

◦ Obter posição(ões) para um valor

◦ Inserir elemento antes ou depois de uma

ListasListas

◦ Inserir elemento antes ou depois de uma posição

◦ Remover um elemento de uma posição

◦ Exibir elementos de uma lista

◦ Concatenar listas

30

Lista sequencial

Lista encadeada

31

Lista encadeada

� Operações em tempo constante◦ Sequencial� Verificação de lista vazia

� Verificação de lista cheia (quantidade)

� Verificação por elemento em posição

◦ Encadeada� Verificação de lista vazia

ListasListas32

� Lista sequencial◦ Acesso a qualquer elemento em tempo constante

◦ Movimentação e inserção custosa

◦ Tamanho máximo definido

◦ Ideal para:� Listas de tamanho conhecido (pequenas), inserção remoção no fim

ListasListas

inserção remoção no fim

33

� Lista encadeada◦ Não precisa deslocar elementos nas operações de inserção e remoção

◦ Crescimento em tempo de execução

◦ Limite é a memória disponível

◦ Acesso a elementos, porém, requer busca prévia

ListasListas

◦ Ideal para:� Listas grandes, inserção/remoção no meio, sem tamanho máximo definido

34

// Tipo base dos elementos da listatypedef struct elementos {

char nome[50];// Outros elementos

} t_elemento;

// Estrutura da listatypedef struct lista {

t_elemento vetor[MAX];//vet que armazena elem. da pilhaint n; // posicao (indice) do ultimo elemento da lista

Lista sequencialLista sequencial35

int n; // posicao (indice) do ultimo elemento da lista} t_lista; // tipo lista

t_lista criar() {t_lista lista;

lista.n = -1;

return lista;}

int isVazia(t_lista * lista) {return (lista->n == -1);


return (lista->n == -1);}

int isCheia(t_lista * lista) {return (lista->n == MAX-1);

}

int getTamanho(t_lista * lista) {return lista->n + 1;

}

t_elemento * getElemento(t_lista * lista, int pos) {// verifica se pos eh validaif ( (pos > lista->n) || (pos < 0) )

return 0;


return &(lista->vetor[pos]);}

int getPosicao(t_lista * lista, t_elemento dado) {int i;for (i=0; i<=lista->n; i++)

if (compara(lista->vetor[i], dado)==0)return i;

return -1;}


}

int compara(t_elemento dado1, t_elemento dado2) {return strcmp(dado1.nome, dado2.nome);

}

int inserir (t_lista * lista, int pos, t_elemento dado) {if ( isCheia(lista) || (pos > lista->n + 1) || (pos < 0) )

return 0;

deslocaDireita(lista, pos);lista->vetor[pos] = dado;(lista->n)++;return 1;

}int deslocaDireita(t_lista * lista, int pos) {

int i;


for (i=lista->n; i < pos; i--)lista->vetor[i] = lista->vetor[i-1];

return 1;}

int remover (t_lista *lista, int pos) {if ( (pos >= lista->n) || (pos < 0) )

return 0;

deslocaEsquerda(lista, pos);

(lista->n)--;return 1;

}

int deslocaEsquerda(t_lista * lista, int pos) {int i;


int i;

for (i=pos; i<=(lista->n)-1; i++)lista->vetor[i] = lista->vetor[i+1];

return 1;}

� Estruturas de dados lineares

� Pilhas, Listas e Filas (continuação)

Próximas aulasPróximas aulas41

� Notas de Aula do Prof. Bruno B. Boniati

� Notas de Aula do Prof. João Luís Garcia Rosa

� Notas de Aula do Prof. Derzu Omaia

ReferênciasReferências42

Estrutura de DadosEstrutura de DadosEstrutura de DadosEstrutura de DadosCarlos Eduardo Batista

Centro de Informática - [email protected]

Documents

Estrutura de Dadoswiki.cbatista.net/lib/exe/fetch.php/ed-aula07-pilhas_e... · 2013. 11. 11. · Estrutura de dados onde a inserção e remoção de elementos ocorre a partir de uma