2013/2-AED-2013.09.12: TAD Pilha - Laboratório em sala de aula

Arquivo .h

// tad pilha.h

typedef int TipoChave;

typedef struct {
  TipoChave Chave;
}TipoItem;

typedef struct TipoCelula * TipoApontador;

typedef struct TipoCelula{
  TipoItem Item;
  TipoApontador Prox;
}TipoCelula;

typedef struct {
  int Tamanho;
  TipoApontador Topo, Fundo;
}TipoPilha;

// criar uma nova pilha vazia
void FPVazia(TipoPilha * Pilha);
// verifica se a pilha está vazia
int VaziaPilha(TipoPilha Pilha);
// empilha um novo elemento na pilha
void Empilha(TipoItem x, TipoPilha* Pilha);
// desempilha um elemento da pilha
void Desempilha(TipoItem* x, TipoPilha* Pilha);
// informa o tamanho da pilha
int TamanhoPilha(TipoPilha Pilha);
// imprime os valores da pilha
void ImprimirPilha(TipoPilha Pilha);
// informa o elemento que está no topo da pilha
TipoItem TopoPilha(TipoPilha Pilha);

void FPVazia(TipoPilha * Pilha){
// criar a celula topo, cabeca
Pilha->Topo = (TipoApontador) 
    malloc(sizeof(TipoCelula));
// faz o fundo apontar para o mesmo lugar do topo
Pilha->Fundo = Pilha->Topo;
// inicializa o tamanho para zero
Pilha->Tamanho = 0;
}

int TamanhoPilha(TipoPilha Pilha){
return Pilha.Tamanho;
}

int VaziaPilha(TipoPilha Pilha){
return Pilha.Topo == Pilha.Fundo;
}

void Empilha(TipoItem x, TipoPilha* Pilha){
TipoApontador aux;
aux = (TipoApontador) malloc(sizeof(TipoCelula));
Pilha->Topo->Item = x;
aux->Prox = Pilha->Topo;
Pilha->Topo = aux;
Pilha->Tamanho++;
}

void Desempilha(TipoItem *x, TipoPilha* Pilha){
TipoApontador q;
if (VaziaPilha(*Pilha)){
printf("ERRO: Pilha vazia!\n");
return;
}
q = Pilha->Topo;
Pilha->Topo = q->Prox;
*x = q->Prox->Item;
free(q); // libera a celula removida da memoria
}

void ImprimirPilha(TipoPilha Pilha)
{
TipoApontador aux;
TipoItem item;
printf("Tamanho: %d\n", Pilha.Tamanho);
aux = Pilha.Topo;
printf("TOPO: \n");
while (aux->Prox != NULL){
printf("%d\n", aux->Prox->Item);
aux = aux->Prox;
}
printf("FUNDO: \n");
}

Arquivo .c

#include <stdio.h>
#include <stdlib.h>
#include "tad-pilha.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {

TipoPilha Pilha;
TipoItem item;
TipoItem a[] = {2, 5, 6, 1, 6, 3, 7};
int tam = 7, i;

FPVazia(&Pilha); // inicializando a pilha
ImprimirPilha(Pilha);

for (i = 0; i < tam; i++){ // empilhamento
item = a[i];
Empilha(item, &Pilha);
ImprimirPilha(Pilha);
}

for (i = 0; i < tam; i++){ // desempilhamento
Desempilha(&item, &Pilha);
printf("Desempilhando: %d\n", item);
ImprimirPilha(Pilha);
}




return 0;
}

2013/2-AED-2013.09.12: TAD Pilha

Arquivo .H

---

#include <stdio.h>
#include <stdlib.h>

// TAD Pilha
#define MAX 900000

// definição do tipochave
typedef int TipoChave;

// definição do registro tipo item
typedef struct {
  TipoChave Chave;
} TipoItem;

// definição do apontador para célula
typedef struct TipoCelula *TipoApontador;

// definição para o tipo célula
typedef struct TipoCelula {
  TipoItem Item;
  TipoApontador Prox;
} TipoCelula;

// definição do tipo pilha
typedef struct{
  TipoApontador Fundo, Topo;
  int Tamanho;
} TipoPilha;

// função que inicializa a pilha
void FPVazia(TipoPilha *Pilha);
// função que verifica se a pilha está vazia
int VaziaPilha(TipoPilha Pilha);
// função que empilha um item na pilha
void Empilha(TipoItem x, TipoPilha *Pilha);
// função que desempilha um item da pilha
void Desempilha(TipoPilha *Pilha,  TipoItem *Item);
// função que retorna o tamanho da pilha
int TamanhoPilha(TipoPilha Pilha);
// função que informa o elemento no topo da pilha
TipoItem TopoPilha(TipoPilha *Pilha);
// função que imprime o estado atual da pilha
void ImprimirPilha(TipoPilha Pilha);

// função que cria uma nova pilha
void FPVazia(TipoPilha *Pilha)
{ // cria a célula cabeça
  Pilha->Topo = (TipoApontador)
    malloc(sizeof(TipoCelula));
  // inicializa o topo e fundo
  Pilha->Fundo = Pilha->Topo;
  // inicializa o próximo do topo
  Pilha->Topo->Prox = NULL;
  // inicializa o tamanho
  Pilha->Tamanho = 0;
}

// função que verifica se a
//pilha está vazia
int VaziaPilha(TipoPilha Pilha)
{ // se a célula no topo for igual
  // a célula no fundo, ela está
  // vazia
  return (
    Pilha.Topo == Pilha.Fundo);
}


// função que empilha um item na pilha
void Empilha(TipoItem x, TipoPilha *Pilha)
{
  TipoApontador Aux;  // apontador auxiliar
  // aloca o apontador auxiliar
  Aux = (TipoApontador)
    malloc(sizeof(TipoCelula));
  // coloca o item no topo da pilha
  Pilha->Topo->Item = x;
  // célula auxiliar aponta para topo
  Aux->Prox = Pilha->Topo;
  // topo recebe auxiliar
  Pilha->Topo = Aux;
  // incrementar o tamanho da pilha
  Pilha->Tamanho++;
}

// função que desempilha o item no
// topo da pilha
void Desempilha(TipoPilha *Pilha,
  TipoItem *Item)
{ TipoApontador q;
  // se a pilha estiver vazia,
  // mostrar uma mensagem de erro
  if (VaziaPilha(*Pilha)) {
    printf("Erro: pilha vazia\n"); return;
  }
  q = Pilha->Topo; // obtem a célula no topo
  // altera o apontador para
  // apontar para o próximo
  Pilha->Topo = q->Prox;
  // obtem o item a ser removido do topo
  *Item = q->Prox->Item;
  // libera o espaço de memória alocado
  free(q);
  // diminuir o tamanho da pilha
  Pilha->Tamanho--;
}

// função para obter Tamanho da pilha
int TamanhoPilha(TipoPilha Pilha)
{ return (Pilha.Tamanho); }


// função para obter o elemento no topo da pilha
TipoItem TopoPilha(TipoPilha *Pilha)
{  TipoItem item; item.Chave = -1;
if (VaziaPilha(*Pilha) == 0){
item = Pilha->Topo->Prox->Item;
}
return (item);
}

void ImprimirPilha(TipoPilha Pilha)
{
  TipoApontador aux; TipoItem item;
  printf("Pilha Tamanho: %d -> ", Pilha.Tamanho);
  aux = Pilha.Topo;
  printf("Topo: ");
  while (aux->Prox != NULL){
 item = aux->Prox->Item;
 printf(" %3d | ", item.Chave);
 aux = aux->Prox;
  }
  printf(": Fundo\n");
}

---

Arquivo .C

---

#include "tad-pilha.h"

int main(void) {

  TipoPilha pilha; TipoItem item; int i;
  int chaves[] = {10, 11, 12, 45, 1};

  FPVazia(&pilha); // Inicializa a pilha
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  item = TopoPilha(&pilha); // elemento no topo da pilha
  printf("Elemento no topo da pilha: %d\n", item.Chave);
  ImprimirPilha(pilha);

  /*Empilha cada chave */
  for (i = 0; i < 5; i++){
    item.Chave = chaves[i];
    Empilha(item, &pilha);
    printf("Empilhou: %3d => ", item.Chave);
    ImprimirPilha(pilha);
  }
  int tamPilha = TamanhoPilha(pilha); // tamanho da pilha
  printf("Tamanho da pilha: %d \n", tamPilha);
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  item = TopoPilha(&pilha); // elemento no topo da pilha
  printf("Elemento no topo da pilha: %d\n", item.Chave);

  for (i = 0; i < tamPilha; i++) { /*Desempilha cada chave */
    Desempilha(&pilha, &item);
    printf("Desempilhou: %3d => ", item.Chave);
    ImprimirPilha(pilha);
  }
  printf("Tamanho da pilha: %d\n", TamanhoPilha(pilha)); // tamanho da pilha
  printf("Pilha vazia?: %d\n", VaziaPilha(pilha)); // pilha vazia?
  system("PAUSE");
  return EXIT_SUCCESS;
}

2013/2-AED-2013.08.29: TAD Matriz

// tad matriz

// definição da TAD

typedef int TipoChave;

struct t_matriz{

  int capacidade;

  int tamanho;

  int linha;

  int coluna;

  int numLinhas;

  int numColunas;

  TipoChave **a;

};

typedef struct t_matriz TipoMatriz;

// operações da TAD matriz

// criar uma nova matriz

void criarMatriz(TipoMatriz *m, int numLinhas, int numColunas);

void imprimirMatriz(TipoMatriz m);

void inserirMatriz(TipoMatriz *m, TipoChave c);

TipoChave obterElementoEm(TipoMatriz m, int linha, int coluna);

void obterPosicaoDe(TipoMatriz m, TipoChave c, 

    int *linha, int *coluna);

int cheiaMatriz(TipoMatriz m);

// implementacao

void criarMatriz(TipoMatriz *m, int numLinhas, int numColunas){

  int c = 0;

  m->numLinhas = numLinhas;

  m->numColunas = numColunas;

  m->capacidade = numLinhas * numColunas;

  m->tamanho = 0;

  m->linha = 0;

  m->coluna = 0;

  

  m->a = (int **) malloc(numLinhas * sizeof(int *));

  for (c = 0; c < numLinhas; c++){

    m->a[c] = (int *) malloc (numColunas * sizeof (int));

  }

  

}

void imprimirMatriz(TipoMatriz m){

  printf("Tamanho: %d\n", m.tamanho);

  printf("Capacidade: %d\n", m.capacidade);

  printf("Dimensao: %dx%d\n", m.numLinhas, m.numColunas);

  int i, j;

  for (i = 0; i < m.numLinhas; i++){

    for (j = 0; j < m.numColunas; j++){

 printf("%d ", m.a[i][j]);

}

  }

}