Estruturas de Dados

Listas

Revisão: Ponteiros

Ponteiro é uma variável usada para armazenar o endereço de outras variáveis, permitindo assim a referência indireta de valores. Os endereços contidos em uma variável do tipo ponteiro podem ser alterados diretamente através de operações aritméticas.

Exemplo 1

#include "stdio.h"

struct SPonto3D
{
    int x;
    int y;
    int z;
};

int main()
{
   int VMax, k;
   char Letra;
   int * pVMax;
   int * pk;
   SPonto3D p1;
   SPonto3D * p;

      VMax = 456;
       k = 50;
       p1.x = 10;
       p1.y = 60;
       p1.z = 800;

       pVMax = &VMax;
       pk = &k;
       p = &p1;
       *pVMax = 100;
       *pk = 200;
       (*p).x = 300;
       p->y = 400;
       pVMax = &(p1.z);
       *pVMax = 500;

printf("Max: %i k: %i x:%i y:%i z:%i",VMax,k,p1.x,p1.y,p1.z);
}

Exemplo 2: Passagem de parâmetros por valor e por referência

#include "stdio.h"

void fValor(int var);
void fRef(int * var);

int main()
{
    int x;
    x = 60;
    fRef(&x);
    fValor(x);
    printf("x : %i",x);
}

void fValor(int var)
{
var = 30;
}

void fRef(int * var)
{
*var = 40;
}

Exemplo 3: Alocação dinâmica de memória

struct SPonto3D
{ int x,y,z; };

int main()
{
    int * x; SPonto3D * p;
    x = new int;
    p = new SPonto3D;
    *x = 10;
    p->x = 100;
    p->y = 200;
    p->z = 300;
    delete x;
    delete p;
}

Exemplo4: arquivo.cpp

Ponteiros e Linguagem Java

Java não permite manipulação explícita de endereços de memória através de ponteiros. No entanto, a grande maioria dos efeitos desejados quando utiliza-se ponteiros em linguagem C, podem ser obtidos, em Java, através da utilização apropriada de objetos.

A passagem de parâmetros em Java é por referência, para objetos, e por valor, para os tipos simples. Para alguns tipos simples, Java oferece um objeto equivalente, que pode ser utilizado, no lugar do tipo simples, quando for necessária a manipulação de valores por referência indireta (e.g. int e Integer)

Ponteiros representam a maior causa de 'bugs' em programas escritos em linguagem C.

Uso de ponteiros pode prejudicar a legibilidade do código.

Utilização explícita de ponteiros, no entanto, é um exercício fundamental para a compreensão de aspectos de mais baixo nível da programação de computadores.

Definições (informais)

Um nó é um conjunto de campos, definidos normalmente por um tipo de dado primitivo (int,char,bool,string,..)
Cada nó possui, geralmente, um identificador, denominado chave .
Um nó pode possuir um único campo.
Uma lista linear é um conjunto de nós, organizados `sequencialmente'.
Os termos sucessor, antecessor, primeiro, último , inicio (antes do primeiro) e final (depois do último) são normalmente usados para se fazer referência aos elementos da lista.
Usamos também "nó x" para nos referenciarmos a um nó cujo conteúdo da chave é x.

Exemplos:

Lista com CIC, Nome e Telefone de professores.

Lista de Pontos.

Pilhas

Inserções e remoções ocorrem sempre no mesmo extremo da lista (chamado de topo da pilha).
Política de acesso LIFO: último a entrar, primeiro a sair (last in, first out. )
Overflow - Estouro da pilha por `falta de espaço' no topo. (Inserção)
Underflow - Tentativa de retirar elementos de uma pilha vazia (Remoção).

Alocação Estática (Vetores)

Alocação Dinâmica (Lista Ligada)

#include "stdio.h"
#define MAX 100

void Insere(int chave);
int Remove(void);

int Pilha[MAX];
int Topo = 0;

int main()
{
int x;

Insere(4);
Insere(8);

   x = Remove();
   printf("x : %i\n" , x);
   x = Remove();
   printf("x : %i\n" , x);

/* Ao final desta página apresentamos o
     código-fonte de um 'menu' simples
     (modo texto), que permite ao usuário
      interagir com o programa (fornecendo
      as chaves a serem inseridas ou removidas) */
}

void Insere(int chave)
{
   if(Topo>MAX)
   {
    printf("Overflow");
   }
   else
   {
    Pilha[Topo] = chave;
    ++Topo;
   }
}

int Remove(void)
{
   if(Topo==0)
   {
    printf("Underflow");
   }
   else
   {
    --Topo;
    return(Pilha[Topo]);
   }
}

#include "stdio.h"

void Insere(int chave);
int Remove(void);

struct SNo
{
int chave;
SNo * prox;
};

SNo * Topo = NULL; /* Topo aponta para nada */

int main()
{
... Repete Estática ...
}

void Insere(int chave)
{
SNo * No;

No = new SNo;

   if(No==NULL)
   {
    printf("Overflow");
   }
   else
   {
      No->chave = chave;
      No->prox = Topo;
      Topo = No;
   }
}

int Remove(void)
{
int chave;
SNo * temp;

   if(Topo==NULL)
   {
    printf("Underflow");
   }
   else
   {
      chave = Topo->chave;
      temp = Topo->prox;
      delete Topo;
      Topo = temp;
      return(chave);
   }
}

Problemas:
- O que deve ser feito quando precisarmos de mais de uma pilha para resolver um determinado problema ? (Sera' que a implementação acima e' adequada para essa situação).
- Como melhorar as implementações acima para facilitar o reaproveitamento do código (mais de uma pilha, pilha para tipos diferentes de dados, ...) ?

Outros exemplos de implementação de pilhas:
- pilha_pd.cpp Utilizando ponteiro duplo e passagem de parâmetros.
- pilha_poo.cpp Utilizando programação orientada a objetos em C++.
- pilhaEmJava.zip Utilizando programação orientada a objetos em Java (notar a utilização implícita de ponteiros).

OBS: No final desta página disponibilizamos um arquivo compactado com todos os programas-fonte, em linguagem C, apresentados.

Filas

Inserções e Remoções ocorrem em extremos opostos .
Política de acesso FIFO: primeiro a entrar, primeiro a sair (first in, first out)
Precisa um ponteiro para o inicio e outro para o final da fila.

/* Mesma estrutura SNo da Fila */

SNo * Inicio = NULL;
SNo * Fim = NULL;

void Insere(int chave)
{
SNo * No;

No = new SNo;

   if(No==NULL) printf("Memoria Insuficiente");
   else
   {
      No->chave = chave;
      No->prox = NULL;

      if(Inicio == NULL)
      {
         Inicio = Fim = No;
      }
      else
      {
         Fim->prox = No;
         Fim = No;
      }
   }
}

int Remove(void)
{
int chave;
SNo * temp;

   if(Inicio==NULL)
   {
    printf("Fila Vazia");
   }
   else
   {
      chave = Inicio->chave;
      temp = Inicio;
      Inicio = Inicio->prox;
      delete temp;

return(chave);
}
}

Listas Encadeadas

Inserções e Remoções podem acontecer em qualquer ponto.

Classificações:

Simplesmente ou Duplamente encadeada.

Ordenada ou Não Ordenada

Circular ou Não Circular.

Operações Usuais

SNo * Busca(k) - Devolve local onde chave (no) deve ser inserido.
bool Contido(k) - Responde se uma chave está contida na lista.
Insere(k) - Insere chave (dentro de um no) na lista.
Insere(SNo * pno) - Insere no na lista.
Remove(k) - Remove no contendo k da lista.
Remove(SNo * pno) - Remove no apontado por pno.
SNo * Sucessor(SNo * pno) - No sucessor do no apontado por pno.
SNo * Predecessor(SNo * pno) - Predecessor
int Minimo() - Menor elemento da lista (int é só um exemplo)
int Maximo() - Maior elemento da Lista (int é só um exemplo)
Percorre() - Percorre a lista, no á no.

Lista Simplesmente Encadeada (Não Ordenada)

void Percorre()
{
SNo * no;

no = Inicio;
while(no!=NULL)
{
printf("%i ",no->chave);
no = no->prox;
}
printf("\n");
}

/* A Busca não está sendo
   usada em Remove porque
   precisamos de um ponteiro
   para o nó anterior ao que
   será removido */

/* Para inserção utilize o
algorítmo da Fila */

SNo * Busca(int k)
{
SNo * no;
bool achou=false;

   no = Inicio;
   while(no!=NULL && achou==false)
   {
      if(no->chave == k) achou = true;
      else no = no->prox;
   }
   return(no);
}

bool Contido(int k)
{
if(Busca(k)==NULL) return(false);
else return(true);
}

void Remove(int k)
{
SNo * no, * predec;
bool achou=false;

   no = Inicio;
   predec = NULL;
   while(no!=NULL && achou==false)
   {
      if(no->chave == k)
      {
         achou = true;
         break;
      }
      predec = no;
      no = no->prox;
   }
   if(achou == true)
   {
      if(Inicio==no) Inicio = no->prox;
      if(Fim==no) Fim = predec;
      if(predec!=NULL) predec->prox = no->prox;
      delete no;
   }
}

Lista Duplamente Encadeada (Não Ordenada)

struct SNo
{
   int chave;
   SNo * prox;
   SNo * ant;
};

SNo * Inicio = NULL;
SNo * Fim = NULL;

void Insere(int chave)
{
SNo * No;
No = new SNo;

   if(No==NULL) printf("Memoria Insuficiente");
   else
   {
      No->chave = chave;
      No->prox = NULL;
      No->ant = NULL;

      if(Inicio == NULL) Inicio = Fim = No;
      else
      {
         Fim->prox = No;
         No->ant = Fim;
         Fim = No;
      }
   }
}

void Remove(int k)
{
SNo * no;

no = Busca(k);

   if(no != NULL)
   {
      if(Inicio==no) Inicio = no->prox;
      if(Fim==no) Fim = no->ant;
      if(no->ant!=NULL) no->ant->prox = no->prox;
      if(no->prox!=NULL) no->prox->ant = no->ant;
      delete no;
   }
}

void PercorreI()
{
SNo * no;

no = Fim;
while(no!=NULL)
{
printf("%i ",no->chave);
no = no->ant;
}
printf("\n");

}

Lista Duplamente Encadeada (Ordenada)

void Insere(int k)
{
SNo * No;
SNo * Lugar;

No = new SNo;

   if(No==NULL) printf("Memoria Insuficiente");
   else
   {

      No->chave = k;
      No->prox = NULL;
      No->ant = NULL;

Lugar = BuscaPontoInsercao(k);

      if(Inicio == NULL)
      {
         Inicio = Fim = No;
      }
      else
      {
         if(Lugar == NULL) /* Inicio da Fila */
         {
            Inicio->ant = No;
            No->prox = Inicio;
            Inicio = No;
         }
         else
         {
            No->prox = Lugar->prox;
            No->ant = Lugar;
            if(Lugar->prox != NULL)
            {
               Lugar->prox->ant = No;
            }
            Lugar->prox = No;
            if(Fim==Lugar)
            {
               Fim = No;
            }
         }
      }
   }
}

SNo * BuscaPontoInsercao(int k)
{
SNo * no;
bool achou=false;

   no = Inicio;
   while(no!=NULL && achou==false)
   {
      if(no->chave > k)
      {
         achou = true;
      }
      else no = no->prox;
   }
   if(achou==false) return(Fim);
   else return(no->ant);
}

Listas Circulares

O ponteiro 'proximo' do 'último' nó da lista aponta para o primeiro. Desta forma, cada nó sempre tem um sucessor. (O sucessor do último é o primeiro).

Fontes

Todos os fontes mostrados nesta seção, prontos para compilar, linkar e executar.

Exemplo de um MENU SIMPLES, em modo texto

Obs: Estes fontes utilizam recursos de c++ (new,delete,...) e foram testados utilizando o GCC para Linux. Não esqueça de ajustar o seu compilar para que ele trabalhe no modo C++ (e não no modo C puro).

Exercícios:

1 - Execute manualmente e mostre a saída de cada um dos programas abaixo (compile e execute os programas para conferir sua resposta):

- ponte-1. cpp

- ponte-2. cpp

- ponte-3. cpp

- ponte-4. cpp

- ponte-5. cpp

- ponte-6. cpp

- ponte-7. cpp

2 - Exercícios de programação:

- Com base no ponte-6.cpp criar programa que lê números inteiros e "separa" esses inteiros em três listas: lista de pares, lista de ímpares e lista de múltiplos de três . Assim que o usuario terminar de digitar os números, teclando -1, o programa deve mostrar cada uma das três listas.

Resposta: ed1-res1.cpp

- Ler palavras digitadas pelo usuário, até que ele digite a palavra "fim" e armazenar estas palavras em uma Lista duplamente encadeada ordenada. Depois que o usuário digitar "fim", o programa deve mostra a lista em ordem alfabética, e na ordem inversa.

Resposta: ed1-res2.cpp

Programas Auxiliares:

manipulaStrings.cpp Exemplo de como ler, imprimir e comparar cadeias de caracteres

listaDePalavras.cpp Exemplo de operações sobre uma lista de palavras

Listas

Revisão: Ponteiros

Definições (informais)

Pilhas

Filas

Listas Encadeadas

Lista Simplesmente Encadeada (Não Ordenada)

Lista Duplamente Encadeada (Não Ordenada)

Lista Duplamente Encadeada (Ordenada)

Listas Circulares

Fontes

Exercícios:

Outros Links