Estruturas de Dados - Tipos Abstratos de Dados

Prévia do material em texto

Tipos abstratos de dados
Estruturas de Dados
Profa. Carla Koike ­ CIC
   
O que são vetores?
● Alocação estática e seqüencial
● Estrutura homogênea
● Inserção/Exclusão:
– realocação dos elementos
– memória não liberada
v[0] v[1] v[2] v[3] ... v[n]
   
O que são matrizes?
● Alocação estática  e seqüencial
● Estrutura homogênea
● Arranjo bi ou multidimensional
● Inserção/Exclusão:
– realocação dos elementos
– memória não liberada
v[0,0] v[0,1] v[0,2] v[1,0] ... v[n,m]
   
Alocação estática versus Alocação 
dinâmica
● Variáveis estáticas tem seu endereço fixado antes do 
início da execução do programa. A área de memória 
ocupada se mantém durante toda a execução
● Variáveis dinâmicas são criadas e eliminadas durante 
a execução do programa, ocupando memória 
somente enquanto são utilizadas
   
Alocação dinâmica de variáveis
● Posições de memória são alocadas somente quando 
são utilizadas:
– Exemplo:
 
int main(void){
int *iptr;
 iptr = (int *)malloc(10 * sizeof(int));
 if (iptr != NULL){
 int k;
 for (k = 0; k < 10; k++)
 iptr[k] = 0;
 }
...
free(iptr);
return 0;
}
   
Alocação dinâmica de variáveis
● Posições de memória são alocadas somente quando 
são utilizadas:
– Exemplo:
 
int main(void){
int *iptr;
 iptr = (int *)malloc(10 * sizeof(int));
 if (iptr != NULL){
 int k;
 for (k = 0; k < 10; k++)
 iptr[k] = 0;
 }
...
free(iptr);
return 0;
}
Vetor de tamanho fixo!
   
É possível criar vetores de tamanho 
variável usando alocação dinâmica?
v[0]
v[1]
v[2]
...
...
● Elementos do vetor são 
criados somente quando 
necessários
● Portanto, estão 
espaçados na memória
● Como saber onde está o 
próximo elemento do 
vetor?
   
É possível criar vetores de tamanho 
variável usando alocação dinâmica?
v[0]
v[1]
v[2]
...
...
● Cada elemento do vetor 
guarda a posição do 
próximo elemento
● Cada elemento é na 
verdade uma estrutura:
– typedef struct 
{ 
 int valor; 
 int *proximo; 
 }elemento;
   
É possível criar vetores de tamanho 
variável usando alocação dinâmica?
● Um ponteiro indica o 
primeiro elemento
● Um ponteiro indica o 
último elemento
● Cada elemento possui 
uma ligação para o 
próximo elemento
v[0]
proximo
v[1]
proximo
   
Estrutura de dados do vetor 
dinâmico
typedef int TipoChave;
typedef struct {
 TipoChave Chave;
 /* outros componentes */
} TipoItem;
typedef struct Celula_str *Apontador;
typedef struct Celula_str {
 TipoItem Item;
 Apontador Prox;
} Celula;
typedef struct {
 Apontador Primeiro, Ultimo;
} TipoLista;
   
Operações sobre o vetor dinâmico
void FLVazia(TipoLista *Lista)
{
 Lista->Primeiro = (Apontador) malloc(sizeof(Celula));
 Lista->Ultimo = Lista->Primeiro;
 Lista->Primeiro->Prox = NULL;
}
Criação
void Insere(TipoItem x, TipoLista *Lista)
{
 Lista->Ultimo->Prox = (Apontador) malloc(sizeof(Celula));
 Lista->Ultimo = Lista->Ultimo->Prox;
 Lista->Ultimo->Item = x;
 Lista->Ultimo->Prox = NULL;
}
Insere elemento no final
   
Análise de complexidade: estático 
versus dinâmico
● Considere um vetor estático e um vetor com alocação 
dinâmica conforme definido anteriormente:
– qual a complexidade de inserção de um ítem novo no 
início do vetor?
   
Vetor Estático
/*MAX e' uma constante que delimita o tamanho
 alocado da Lista */
void InsereInicioVetor(Item x, Item *Lista, int *n)
{
 int i;
 if (*n<MAX) {
 /*Desloca os itens do final da lista*/
 for (i=*n;i>0;i--)
 Lista[i]=Lista[i-1];
 /*Insere novo item no inicio*/
 Lista[0]=x;
 /*Atualiza tamanho do vetor*/
 (*n)++;
 } else printf(� Nao eh possivel inserir item� );
}
Insere elemento no inicio 
Complexidade O(n)
   
Vetor Dinâmico
void InsereInicio(TipoItem x, TipoLista *Lista)
{
 Apontador *temp = (Apontador) malloc(sizeof(Celula));
 temp->Item = x;
 temp->Prox = Lista->Primeiro; 
 Lista->primeiro = temp;
}
Insere elemento no inicio
Complexidade O(1)
Não depende do tamanho da lista!
   
Vetor com alocação dinâmica = 
Lista encadeada
● Diferentemente de um vetor estático, uma lista 
encadeada permite várias operações, entre as quais:
– Criar uma lista vazia
– Inserir um item novo em qualquer posição
– remover um item
– localizar um item
– copiar a lista
– combinar duas ou mais listas
– dividir uma lista em duas ou mais listas, ...
   
Tipo abstrato de dados (TAD)
● Na verdade, mostramos duas maneiras de 
implementar um TAD lista:
– por meio de um vetor estático
– por meio de ponteiros com alocação dinâmica
● Tipo abstrato de dados:
– conceito e operações
– implementação de um TAD
   
TAD Lista
● Conceito
– Uma seqüência ordenada de elementos do mesmo tipo 
● Operações
– criação, inserção, remoção, pesquisa, destruição,...
● Uma lista pode ser implementada de várias maneiras: 
arranjo (vetor estático) ou lista encadeada (vetor 
dinâmico)
● A escolha da implementação deve ser guiada pela 
eficiência na execução das operações
   
Lista Encadeada
● Cada elemento da lista é um registro que contém, 
entre outros campos, um campo do tipo ponteiro, que 
aponta para outro elemento da lista.
Inicio
   
Estrutura de Dados Lista 
Encadeada
typedef int TipoChave;
typedef struct {
 TipoChave Chave;
 /* outros componentes */
} TipoItem;
typedef struct Celula_str *Apontador;
typedef struct Celula_str {
 TipoItem Item;
 Apontador Prox;
} Celula;
typedef struct {
 Apontador Primeiro, Ultimo;
} TipoLista;
   
Remoção do último item Lista 
Encadeada
void RetiraUltimo(TipoLista *Lista)
{
 if (Vazia(*Lista)){
 printf(" Erro: Lista vazia\n");
 return;
 }
 Apontador temp;
 for(temp=Lista->Primeiro;temp->prox = Ultimo;temp++);
 free(Ultimo);
 Ultimo = temp;
}
Complexidade O(n), já que não é 
possível andar para trás na lista!!!
   
Tipos de listas encadeadas
Inicio
Lista aberta com encadeamento simples
Inicio
Lista aberta com encadeamento duplo
   
Estrutura de Dados Lista Aberta 
Duplamente Encadeada
typedef int TipoChave;
typedef struct {
 TipoChave Chave;
 /* outros componentes */
} TipoItem;
typedef struct Celula_str_dupla *ApontadorDupla;
typedef struct Celula_str_dupla {
 TipoItem Item;
 ApontadorDupla Ant;
 ApontadorDupla Prox;
} CelulaDupla;
typedef struct {
 ApontadorDupla Primeiro, Ultimo;
} TipoListaDupla;
   
Operações Lista Aberta Duplamente 
Encadeadas
void FLVaziaD(TipoListaDupla *Lista)
{
 Lista->Primeiro = (ApontadorDupla) malloc(sizeof(CelulaDupla));
 Lista->Ultimo = Lista->Primeiro;
 Lista->Primeiro->Ant = NULL;
 Lista->Primeiro->Prox = NULL;
}
Criação
void InsereD(TipoItem x, TipoListaDupla *Lista)
{
 ApontadorDupla temp;
 Lista->Ultimo->Prox = (ApontadorDupla) malloc(sizeof(CelulaDupla));
 temp = Lista->Ultimo;
 Lista->Ultimo = Lista->Ultimo->Prox;
 Lista->Ultimo->Item = x;
 Lista->Ultimo_Ant = temp;
 Lista->Ultimo->Prox = NULL;
}
Insere elemento no final
   
Listas com cabeçalhos (headers)
● Início da lista é armazenado pelo primeiro elemento 
da lista (também chamada célula ou elemento 
cabeça), em vez de uma variável adicional.
● Este primeiro elemento não tem informação: somente 
o ponteiro próximo é útil indicando o início da lista.
   
Exemplo
● Programa livro C Completo e Total, Herbert Schildt
– lista postal, duplamente encadeada.