• Estruturas de Dados é a disciplina que estuda as técnicas computacionais para a organização e manipulação eficiente de quaisquer quantidades de informação.

• Em um projeto de software, 2 aspectos devem ser considerados para sua implementação:
• De que forma estão organizados os dados, qual a sua estrutura.
• Quais procedimentos atuam sobre estes dados, que operações podem ser realizadas sobre eles.

• Ao estudar estruturas de dados teremos sempre este par:
• Um conjunto estruturado de informações
• Uma classe de objetos ou um tipo de dados.
• Um conjunto definido de operações sobre estes dados:
• Um conjunto de métodos ou funções.

• Vetores possuem um espaço limitado para armazenamento de dados.
• Necessitamos definir um espaço grande o suficiente para a nossa pilha.
• Necessitamos de um indicador de qual elemento do vetor é o atual topo da pilha.

• Implementaremos a Estrutura de Dados Pilha utilizando a técnica da Programação Estruturada.
• Progr. Estr.: Inventada por Niklaus Wirth (década 70) Também chamada de "Programação sem GoTo"
• Procedimento Didático:
• Revisão/introdução da Programação Estruturada
• Modelagem da Pilha e de seus algoritmos usando esta técnica.

• Baseada na expressão de algoritmos única e exclusivamente através de 4 grupos de estruturas de controle:
• Bloco: Comando ou conjunto de comandos sempre executados em seqüência.

Ex (pascal): begin ? end;
• Estrutura condicional: SE-ENTÃO-SENÃO

Ex (pascal): if (cond) then bloco1 else bloco2;
• Estrutura de repetição: ENQUANTO COND FAÇA BLOCO

Ex (pascal): while (cond) do bloco;
• Estrutura de abstração: Procedimento ou Função.

Agrupamento de comandos com um nome e eventualmente também parâmetros nomeados.

• Para nós parece um retrocesso.
• Na época:
• Fazia-se programas completamente ininteligíveis,
• Foi um grande avanço no sentido de:
• se produzir código mais fácil de se manter e entender e
• com mais qualidade.
• A Programação Estruturada definiu:
• Uma nova disciplina na programação
• Um novo grupo de linguagens de programaçao, a 3ª Geração.
• Exemplos: Pascal, Algol, C, PL/1
• Ainda utilizadíssima hoje em dia:
• Sistemas Operacionais
• Análise Numérica/Computação Gráfica
• Redes de Computadores

Na Programação Estruturada:

• Não existem objetos:
• Dados e seu comportamento são considerados em separado.
• Unificar uma estrutura de dados com as operações definidas sobre a mesma é função do programador.
• Existem variáveis e tipos (dados):
• Variáveis podem ser globais ou locais (escopo).
• Tipos podem ser primitivos, derivados ou estruturados.
• Existem procedimentos e funções (comportamento):
• Conjunto de comandos referenciados por um nome.
• Um procedimento é especial e se chama Programa Principal.

• Modelamos as estruturas de dados propriamente ditas como um tipo estruturado:
• Estrutura é uma coleção de variáveis referenciada por um mesmo nome.
• Imagine um objeto sem métodos.
• Chamamos a cada elemento dessa coleção de campo.
• Algoritmicamente:

• Modelamos as operações sobre uma estrutura de dados como procedimentos ou funções
• Variáveis globais valem dentro de qualquer função (escopo global).
• Antes de vermos alocação dinâmica de memória e ponteiros vamos trabalhar com funções sem alguns parâmetros.
• Algoritmicamente:

• Aspecto Estrutural:
• Necessitamos de um vetor para armazenar as informações.
• Necessitamos de um indicador da posição atual do topo da pilha.
• Necessitamos de uma constante que nos diga quando a pilha está cheia e duas outras para codificar erros.
• Pseudo-código:

• Aspecto Funcional:

1. Colocar e retirar dados da pilha.
2. Testar se a pilha está vazia ou cheia.
3. Inicializar

• Colocar e retirar dados da pilha:
• Empilha(dado)
• Desempilha(dado)
• Topo
• Testar se a pilha está vazia ou cheia:
• PilhaCheia
• PilhaVazia
• Inicializar ou limpar:
• InicializaPilha

FUNÇÃO inicializaPilha()
início

aPilha.topo <- -1;

• bservação: Este e os próximos algoritmos pressupõem que foi definida uma variável global tipo Pilha denominada aPilha.

Booleano FUNÇÃO pilhaCheia()

início

SE (aPilha.topo = Maxpilha - 1) ENTÃO

RETORNE(Verdade)

SENÃO

RETORNE(Falso);

fim;

Booleano FUNÇÃO pilhaVazia()

início

SE (aPilha.topo = -1) ENTÃO

RETORNE(Verdade)

SENÃO

RETORNE(Falso);

Algoritmo Empilha

Constantes

ErroPilhaCheia = -1;
ErroPilhaVazia = -2;

SE (pilhaCheia) ENTÃO

RETORNE(ErroPilhaCheia);

SENÃO

aPilha.topo <- aPilha.topo + 1.
aPilha.dados[aPilha.topo] <- dado;
RETORNE(aPilha.topo);

FIM SE

Algoritmo Desempilha

Inteiro FUNÇÃO desempilha()
início

SE (pilhaVazia) ENTÃO

RETORNE(ErroPilhaVazia);

SENÃO

aPilha.topo <- aPilha.topo - 1;
RETORNE(aPilha.topo);

FIM SE

Algoritmo Desempilha - Variante

Inteiro FUNÇÃO desempilha()
início

SE (pilhaVazia) ENTÃO

ESCREVA("ERRO: Pilha vazia ao tentar desempilhar!");
RETORNE(ErroPilhaVazia);

SENÃO

aPilha.topo <- aPilha.topo - 1;
RETORNE(aPilha.dados[aPilha.topo]);

FIM SE

Algoritmo Topo

Inteiro FUNÇÃO topo()
início

SE (pilhaVazia) ENTÃO

ESCREVA("ERRO:Pilha vazia ao acessar!");
RETORNE(ErroPilhaVazia);

SENÃO

RETORNE(aPilha.dados[aPilha.topo]);

FIM SE

• Modelagem dos dados:

 

 
 
 
 
 

#define Maxpilha 100
#define ErroPilhaCheia -1
#define ErroPilhaVazia -2

/* define estrutura de um tipo pilha */
struct estruturaDaPilha {
    int dados[Maxpilha];
    int topo;
};

/* declara o tipo Pilha com a estrutura dada */
typedef struct estruturaDaPilha Pilha;

• Codificação:
• Código de definição de tipos e constantes são sempre colocados em arquivos cabeçalho (headerfiles).
• Estes arquivos têm sempre o sufixo .h
• Exemplo: pilha.h

• Para carregar as definições utilizamos a diretiva de compilação #include no programa que for utilizar aquele tipo:

• Modelagem das operações:

 

 
 
 
 
 

/* Função que empilha dados em Pilha de Inteiros */
/* Parametros:                                   */
/* dado: o dado que vai ser empilhado.           */
int empilha(int dado)
{
    IF ( pilhaCheia() )
        { RETURN(ErroPilhaCheia); }
    ELSE
      {
        aPilha.topo = aPilha.topo + 1;
        aPilha.dados[aPilha.topo] = dado;
        RETURN(aPilha.topo);
      }
}

Pilha - Exemplo de Programa Principal em "C"

/* Aplicacao: Leitura de Dados Int. do Usuário e */
/* Armazenamento em uma Pilha. */
/* PROGRAMA PRINCIPAL */
main()
{
    char tecla = ´a´;
    int dado;

    WHILE ( tecla != ´f´ )
    {
        printf("\nDigite E p/empilhar, D p/desempilhar \n");
        printf("Digite M para mostra pilha e F p/fim \n");
        tecla = getchar();
        getchar(); /* Ler o [enter] */
        SWITCH (tecla) {
          ´E´: {  printf("Digite o vaor p/empilhar: ");
                    scanf("%d%", &dado); /* Não esqueça do & */
                    if (empilha(dado) < 0)
                        { printf("Erro: Pilha cheia! \n"); }
                  }
            - - - -
        } /* fim switch */
    } /* fim while */
}

Pilha - Forma geral de um programa "C":
 

#include <cabeçalhos-padrão>
#include "cabeçalhos específicos"

função1()
- - -
- - -
- - -

funçãoN()
- - -
- - -
- - -

main()
{
- - -
- - -
- - -
}
 

Headerfiles nunca possuem comandos, somente definições

Headerfiles sempre são incluídos.

Contém todas as definições.

Arquivos de programa (comandos):

Nunca são incluídos

Nunca possuem diretivas #define

Arquivos de programa sempre têm sufixo .c

Mais tarde veremos:

Como utilizar mais de um arquivo .c (módulos)

Como garantir que definições não sejam repetidas com as diretivas #ifndef e #ifdef

• Chamada do compilador:

• Parâmetros:
• -g indica ao compilador para gerar código debugável
• -o nome do arquivo executável que será gerado

• Revisão da Modelagem e Implementação.
• Utilização do Unix
• Diretórios, donos de diretórios, startx
• Manpages. Exemplos com getchar() e scanf(?)
• Xman
• FTP:
• Como transferir arquivos de e para a rede inf.
• Edição de Programas usando Xemacs
• Como eu chamo
• Como editar
• Como compilar
• Como debugar