2013/2:AED-2013.10.17: TAD Fila Laboratório

Applets:
http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html
http://www.cosc.canterbury.ac.nz/mukundan/dsal/QueueAppl.html
http://www.cosc.canterbury.ac.nz/mukundan/dsal/appldsal.html

// especificação da TAD fila

// definicao da chave da fila
typedef int TipoChave;
// definicao do registro para o item
struct T_Item{
  TipoChave chave;
};
// definicao do tipo TipoItem
typedef struct T_Item TipoItem;
// definição do apontador para celula
typedef struct T_Celula * TipoApontador;
// definição do registro T_Celula
struct T_Celula{
  TipoItem Item; // item
  TipoApontador Prox; // apontador para prox. celula
};
// definicao do TipoCelula
typedef struct T_Celula TipoCelula;
// definicao do registro T_Fila
struct T_Fila{
  int Tamanho;
  int Capacidade;
  TipoApontador Frente, Tras;
};
// definicao do TipoFila
typedef struct T_Fila TipoFila;

// operacoes da TAD FILA

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item);
// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item);
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade);
// verificar se estah cheia
int FilaCheia(TipoFila Fila);
// verificar se estah vazia
int FilaVazia(TipoFila Fila);
// obter frente
void FilaFrente(TipoFila Fila, TipoItem * item);
// imprimir o conteudo da fila
void ImprimirFila(TipoFila Fila);

// IMPLEMENTACOES DAS OPERACOES
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade)
{
     // 1) criar a celula cabeca
     Fila->Frente = (TipoApontador) 
       malloc(sizeof(TipoCelula));
     // 2) fazer frente e tras apontar para a nova celula
     Fila->Tras = Fila->Frente;
     // 3) inicializar o tras (prox = NULL)
     Fila->Tras->Prox = NULL;     
     // 4) inicializar o tamanho e a capacidade
     Fila->Tamanho = 0;
     Fila->Capacidade = capacidade;
}

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item)
{
     // 1) verificar se a FILA está cheia
     if (FilaCheia(*Fila) == 1){
       printf("ERRO: Fila está cheia!");
       return;
     }
     // 2) criar uma nova celula a partir do TRAS
     Fila->Tras->Prox = (TipoApontador)
       malloc(sizeof(TipoCelula));
     // 3) Adicionar o item na nova celula
     Fila->Tras->Prox->Item = Item;
     // 4) inicializar o PROX da nova celula
     // 5) atualizar o TRAS
     // 6) Atualizar o tamanho da FILA
}

// verificar se estah cheia
int FilaCheia(TipoFila Fila)
{   if (Fila.Capacidade == Fila.Tamanho)
    { return 1;
    } else {
      return 0;
    }
}

// verificar se estah vazia
int FilaVazia(TipoFila Fila)
{   if (Fila.Frente == Fila.Tras)
    { return 1;
    } else {
      return 0;
    }    
}











// especificação da TAD fila

// definicao da chave da fila
typedef int TipoChave;
// definicao do registro para o item
struct T_Item{
  TipoChave chave;
};
// definicao do tipo TipoItem
typedef struct T_Item TipoItem;
// definição do apontador para celula
typedef struct T_Celula * TipoApontador;
// definição do registro T_Celula
struct T_Celula{
  TipoItem Item; // item
  TipoApontador Prox; // apontador para prox. celula
};
// definicao do TipoCelula
typedef struct T_Celula TipoCelula;
// definicao do registro T_Fila
struct T_Fila{
  int Tamanho;
  int Capacidade;
  TipoApontador Frente, Tras;
};
// definicao do TipoFila
typedef struct T_Fila TipoFila;

// operacoes da TAD FILA

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item);
// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item);
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade);
// verificar se estah cheia
int FilaCheia(TipoFila Fila);
// verificar se estah vazia
int FilaVazia(TipoFila Fila);
// obter frente
void FilaFrente(TipoFila Fila, TipoItem * item);
// imprimir o conteudo da fila
void ImprimirFila(TipoFila Fila);

// IMPLEMENTACOES DAS OPERACOES
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade)
{
     // 1) criar a celula cabeca
     Fila->Frente = (TipoApontador) 
       malloc(sizeof(TipoCelula));
     // 2) fazer frente e tras apontar para a nova celula
     Fila->Tras = Fila->Frente;
     // 3) inicializar o tras (prox = NULL)
     Fila->Tras->Prox = NULL;     
     // 4) inicializar o tamanho e a capacidade
     Fila->Tamanho = 0;
     Fila->Capacidade = capacidade;
}

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item)
{
     // 1) verificar se a FILA está cheia
     if (FilaCheia(*Fila) == 1){
       printf("ERRO: Fila está cheia!");
       return;
     }
     // 2) criar uma nova celula a partir do TRAS
     Fila->Tras->Prox = (TipoApontador)
       malloc(sizeof(TipoCelula));
     // 3) Adicionar o item na nova celula
     Fila->Tras->Prox->Item = item;
     // 4) atualizar o TRAS
     Fila->Tras = Fila->Tras->Prox;
     // 5) inicializar o PROX da nova celula
     Fila->Tras->Prox = NULL;
     // 6) Atualizar o tamanho da FILA
     Fila->Tamanho++;
}

// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item)
{    TipoApontador aux; // auxiliar
     // 1) se a FILA estiver vazia
     if (FilaVazia(*Fila) == 1){
       // 1.1) mostrar mensagem de erro e sair
       printf("ERRO: Fila estah vazia!\n");
       return;
     }
     // 2) Guardar a celula que está na frente
     aux = Fila->Frente->Prox;
     // 3) Atualizar a FRENTE (PROX)
     Fila->Frente->Prox = Fila->Frente->Prox->Prox;
     // 4) Decrementar o tamanho
     Fila->Tamanho--;
     // 5) Obter o item removido
     *item = aux->Item;
     // 6) liberar a celula da memoria
     free(aux);
     // 7) Atualizar TRAS se fila estiver vazia
     if (FilaVazia(*Fila) == 1)
     {  Fila->Tras = Fila->Frente;
     }
}
// imprime a fila
void ImprimirFila(TipoFila Fila)
{  printf("Fila %d/%d\n", 
     Fila.Tamanho, Fila.Capacidade);
   // 1) pegando o elemento da frente
   TipoApontador aux = Fila.Frente;
   // 2) Enquanto houver itens para navegar
   while (aux->Prox != NULL)
   { // exibir o item atual
     printf ("%d -> ", aux->Prox->Item.chave);      
     // ir para o próximo elemento
     aux = aux->Prox;
   } printf("\n");   
}
// imprime o elemento na frente da fila
void FilaFrente(TipoFila Fila, TipoItem * item)
{  if (FilaVazia(Fila) == 0){ // se FILA NAO for vazia
     *item = Fila.Frente->Prox->Item;  
   }
}
// verificar se estah cheia
int FilaCheia(TipoFila Fila)
{   if (Fila.Capacidade == Fila.Tamanho)
    { return 1;
    } else {
      return 0;
    }
}

// verificar se estah vazia
int FilaVazia(TipoFila Fila)
{   if (Fila.Frente == Fila.Tras)
    { return 1;
    } else {
      return 0;
    }    
}









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

int main(int argc, char *argv[])
{
  TipoFila fila;
  TipoItem item;
  
  // 1) Criar fila nova
  CriarFila(&fila, 10);
  ImprimirFila(fila);
  // 2) enfileirar itens
  item.chave = 2;
  Enfileirar(&fila, item);
  item.chave = 3;
  Enfileirar(&fila, item);
  // 3) imprimir fila
  ImprimirFila(fila);
  // 4) desenfileirar itens
  Desenfileirar(&fila, &item);
  printf("Desenfileirou: %d\n", item.chave);
  // 5) imprimir fila
  ImprimirFila(fila);
  
  system("PAUSE");
  return 0;
}

2013/2-PA-20130.10.11: Algoritmos de ordenação interna

void imprimeVetor(int *a, int tam) {
  int i;
  for (i = 0; i < tam; i++) {
    printf("%5d   ", a[i]);
  }
  printf("\n\n");

}

int gerarNumeroAleatorio(int max) {
  return rand() % max;
}

void trocarValores(int *a, int i, int j) {
  int aux;
  aux = a[i];
  a[i] = a[j];
  a[j] = aux;
}

void exibirPorcentagem(int i, int tam) {
  if (i % (tam / 100) == 0)
    printf("%d %\n", i);
}

void merge(int pivot, int low, int length, int high, int* a) {
  int merge1, merge2, i, *working;

  merge1 = 0;
  merge2 = pivot - low + 1;
  working = (int*) malloc(length * sizeof(int));

  for (i = 0; i < length; i++){
    working[i] = a[low + i];
  }

  for (i = 0; i < length; i++) {
    // iterando dentro de cada subvetor
    if (merge2 <= high - low) {
      if (merge1 <= pivot - low) {
        if (working[merge1] > working[merge2]) {
          a[i + low] = working[merge2++];
        } else {
          a[i + low] = working[merge1++];
        }
      } else {
        a[i + low] = working[merge2++];
      }
    } else {
      a[i + low] = working[merge1++];
    }
  }
}

void mergesort(int *a, int low, int high) {
  int i = 0;
  int length = high - low + 1;
  int pivot = 0;
  int * working;

  if (low == high) // caso base: vetor de tamanho 1
    return;
  pivot = (low + high) / 2; // cálculo do ponto médio

  mergesort(a, low, pivot); // dividir a esquerda
  mergesort(a, pivot + 1, high); // dividir a direita

  merge(pivot, low, length, high, trocas, a); // junção das soluções
}

void quicksort(int *a, int tam, int left, int right) {
  int i, j, p;
  i = left;
  j = right;

  p = a[(left + right) / 2]; // Elemento intermediário como “pivo” 
  do {
    while (a[i] < p && i < right)
      i++;
    while (a[j] > p && j > left)
      j--;
    if (i <= j) {
      trocarValores(a, i, j);
      trocas++;
      i++;
      j--;
    }
    exibirPorcentagem(i, tam);
  } while (i <= j);
  if (left < j)
    quicksort(a, tam, left, j);
  if (i < right)
    quicksort(a, tam, i, right);
}

void bubbleSort(int *a, int tam) {
  int i, j;
  unsigned long trocas = 0;

  for (i = 0; i < tam; i++) {
    for (j = 0; j < tam - 1; j++) {
      if (a[j] > a[j + 1]) {
        trocarValores(a, j, j + 1);
        trocas++;
      }
    }
  }
}

void insertionSort(int *a, int tam) {
  int i, iHole, item;

  for (i = 1; i < tam; i++) {
    // A[ i ] is added in the sorted sequence A[0, .. i-1]
    // save A[i] to make a hole at index iHole
    item = a[i];
    iHole = i;
    // keep moving the hole to next smaller index until A[iHole - 1] is <= item
    while (iHole > 0 && a[iHole - 1] > item) {
      // move hole to next smaller index
      a[iHole] = a[iHole - 1];
      iHole = iHole - 1;
    }
    // put item in the hole
    a[iHole] = item;
    exibirPorcentagem(i, tam);
  }
}

void selectionSort(int * a, int tam) {
  int i, j, menor; // declaração de variáveis

  // percorrer todas as posições do vetor, um a um
  for (i = 0; i < tam; i++) {
    menor = i; // assumir que o primeiro no intervalo é menor
    // percorrer o vetor para buscar alguem menor, caso exista
    for (j = i + 1; j < tam; j++) { // se for menor que o menor encontrado
      if (a[j] < a[menor]) {   // anote-o
        menor = j;
      }
    }   // se alguem menor que o menor for encontrado
    if (menor != i) {   // trocar as posições dos dois
      trocarValores(a, menor, i);
    }
    exibirPorcentagem(i, tam);
  }
}

void copy(int *b, int *a, int tam) {
  int i = 0;
  for (i = 0; i < tam; i++) {
    a[i] = b[i];
  }

}

/*

 ============================================================================

 Name        : Projeto-pa-ordenacao2.c

 Author      : 

 Version     :

 Copyright   : Your copyright notice

 Description : Hello World in C, Ansi-style

 ============================================================================

 */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include "ordenacao.h"

int main(void) {

int *a, *b, tam, i, num, lim;

time_t seconds, start, end;

double duration;

unsigned long trocas = 0;

tam = 1000000000;

lim = 100000;

time(&seconds);

srand((unsigned int) seconds);

//printf("Digite o tamanho do vetor:");

//scanf("\n%d", &tam);

a = (int*) malloc(tam*sizeof(int));

b = (int*) malloc(tam*sizeof(int));

for (i = 0; i < tam; i++)

{

num = gerarNumeroAleatorio(lim);

a[i] = num;

b[i] = num;

}

// time(&start);

// trocas = selectionSort(a, tam);

// time(&end);

// duration = difftime(end, start);

// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);

// system("PAUSE");

// copy(b, a, tam);

// time(&start);

// trocas = insertionSort(a, tam);

// time(&end);

// duration = difftime(end, start);

// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);

// system("PAUSE");

// copy(b, a, tam);

// time(&start);

// trocas = bubbleSort(a, tam);

// time(&end);

// duration = difftime(end, start);

// printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);

// system("PAUSE");

// copy(b, a, tam);

time(&start);

trocas = quicksort(a, tam, 0, tam-1);

time(&end);

duration = difftime(end, start);

printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);

system("PAUSE");

copy(b, a, tam);

time(&start);

trocas = mergesort(a, 0, tam-1);

time(&end);

duration = difftime(end, start);

printf("\nDuration: %f seconds \tTrocas: %u\n", duration, trocas);

system("PAUSE");

return EXIT_SUCCESS;

}

2013/2-AED-2013.10.10: TAD Fila (Implementação Parcial)

// especificação da TAD fila

// definicao da chave da fila
typedef int TipoChave;
// definicao do registro para o item
struct T_Item{
  TipoChave chave;
};
// definicao do tipo TipoItem
typedef struct T_Item TipoItem;
// definição do apontador para celula
typedef struct T_Celula * TipoApontador;
// definição do registro T_Celula
struct T_Celula{
  TipoItem Item; // item
  TipoApontador Prox; // apontador para prox. celula
};
// definicao do TipoCelula
typedef struct T_Celula TipoCelula;
// definicao do registro T_Fila
struct T_Fila{
  int Tamanho;
  int Capacidade;
  TipoApontador Frente, Tras;
};
// definicao do TipoFila
typedef struct T_Fila TipoFila;

// operacoes da TAD FILA

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item);
// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item);
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade);
// verificar se estah cheia
int FilaCheia(TipoFila Fila);
// verificar se estah vazia
int FilaVazia(TipoFila Fila);
// obter frente
void FilaFrente(TipoFila Fila, TipoItem * item);
// imprimir o conteudo da fila
void ImprimirFila(TipoFila Fila);

// IMPLEMENTACOES DAS OPERACOES
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade)
{
     // 1) criar a celula cabeca
     Fila->Frente = (TipoApontador) 
       malloc(sizeof(TipoCelula));
     // 2) fazer frente e tras apontar para a nova celula
     Fila->Tras = Fila->Frente;
     // 3) inicializar o tras (prox = NULL)
     Fila->Tras->Prox = NULL;     
     // 4) inicializar o tamanho e a capacidade
     Fila->Tamanho = 0;
     Fila->Capacidade = capacidade;
}

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item)
{
     // 1) verificar se a FILA está cheia
     if (FilaCheia(*Fila) == 1){
       printf("ERRO: Fila está cheia!");
       return;
     }
     // 2) criar uma nova celula a partir do TRAS
     Fila->Tras->Prox = (TipoApontador)
       malloc(sizeof(TipoCelula));
     // 3) Adicionar o item na nova celula
     Fila->Tras->Prox->Item = Item;
     // 4) inicializar o PROX da nova celula
     // 5) atualizar o TRAS
     // 6) Atualizar o tamanho da FILA
}

// verificar se estah cheia
int FilaCheia(TipoFila Fila)
{   if (Fila.Capacidade == Fila.Tamanho)
    { return 1;
    } else {
      return 0;
    }
}

// verificar se estah vazia
int FilaVazia(TipoFila Fila)
{   if (Fila.Frente == Fila.Tras)
    { return 1;
    } else {
      return 0;
    }    
}

2013/2-AED-2013.10.03: TAD Fila

#include <stdio.h>

// TAD Fila

// TAD Fila

#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 fila

typedef struct{

  TipoApontador Frente, Tras;

  int Tamanho;

} TipoFila;

// função que inicializa a fila

void FFVazia(TipoFila *Fila);

// função que verifica se a fila está vazia

int VaziaFila(TipoFila Fila);

// função que enfileira um item na fila (TRÁS)

void Enfileira(TipoItem x, TipoFila *Fila);

// função que desenfileira um item da fila (FRENTE)

void Desenfileira(TipoFila *Fila,  TipoItem *Item);

// função que retorna o tamanho da fila

int TamanhoFila(TipoFila Fila);

// função que informa o elemento na frente da fila

TipoItem FrenteFila(TipoFila *Fila);

// função que informa o elemento atrás na fila

TipoItem TrasFila(TipoFila *Fila);

// função que imprime o estado atual da fila

void ImprimirFila(TipoFila Fila);

// função que cria uma nova fila

void FFVazia(TipoFila *Fila)

{ // cria a célula cabeça

  Fila->Frente = (TipoApontador)

    malloc(sizeof(TipoCelula));

  // inicializa a frente e trás

  Fila->Tras = Fila->Frente;

  Fila->Frente->Prox = NULL;

  Fila->Tamanho = 0;

}

// função que verifica se a

//fila está vazia

int VaziaFila(TipoFila Fila)

{ // se a célula na frente for igual

  // a célula atrás, ela está

  // vazia

  return (Fila.Frente == Fila.Tras);

}

// função que Enfileira um item na fila

void Enfileira(TipoItem x, TipoFila *Fila)

{ Fila->Tras->Prox = (TipoApontador)

    malloc(sizeof(TipoCelula));

  Fila->Tras = Fila->Tras->Prox;

  Fila->Tras->Item = x;

  Fila->Tras->Prox = NULL;

  Fila->Tamanho++;

}

// função que desenfileira o item na

// frente da fila

void Desenfileira(TipoFila *Fila,

  TipoItem *Item)

{ TipoApontador q;

  if (VaziaFila(*Fila)) {

    printf("Erro fila esta vazia\n"); return; }

  q = Fila->Frente;

  Fila->Frente = Fila->Frente->Prox;

  *Item = Fila->Frente->Item;

  Fila->Tamanho--;

  free(q);

}

// função para obter Tamanho da fila

int TamanhoFila(TipoFila Fila)

{ return (Fila.Tamanho); }

// função para obter o elemento na frente da fila

TipoItem FrenteFila(TipoFila *Fila)

{  TipoItem item; item.Chave = -1;

  if (VaziaFila(*Fila) == 0){

    item = Fila->Frente->Prox->Item;

  } return (item);

}

// função para obter o elemento atrás na fila

TipoItem TrasFila(TipoFila *Fila)

{  TipoItem item; item.Chave = -1;

  if (VaziaFila(*Fila) == 0){

    item = Fila->Tras->Item;

  } return (item);

}

void ImprimeFila(TipoFila Fila)

{ TipoApontador Aux;

  Aux = Fila.Frente->Prox;

  printf("FRENTE: ");

  while (Aux != NULL)

  { printf("%d | ", Aux->Item.Chave);

    Aux = Aux->Prox;

  }  printf("TRAS \n");

}

/*

 ============================================================================

 Name        : projeto-aed-tad-fila.c

 Author      : waldir

 Version     :

 Copyright   : Your copyright notice

 Description : Hello World in C, Ansi-style

 ============================================================================

 */

#include <stdio.h>

#include <stdlib.h>

#include "tad-fila.h"

int main(void) {

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

  FFVazia(&fila); // Inicializa a fila

  printf("Fila vazia?: %d\n", VaziaFila(fila)); // fila vazia?

  item = FrenteFila(&fila); // elemento na frente da fila

  printf("Elemento na frente da fila: %d\n", item.Chave);

  for (i = 0; i < 5; i++){ /*Enfileira cada chave */

    item.Chave = chaves[i]; Enfileira(item, &fila);

    printf("Enfileirou: %3d \n", item.Chave);

    ImprimeFila(fila);

  }

  int tam = TamanhoFila(fila); // tamanho da fila

  printf("Tamanho da fila: %d \n", tam);

  printf("Fila vazia?: %d\n", VaziaFila(fila)); // fila vazia?

  item = FrenteFila(&fila); // elemento na frente da fila

  printf("Elemento na frente da fila: %d\n", item.Chave);

  for (i = 0; i < tam; i++) { /*Desenfileira cada chave */

    Desenfileira(&fila, &item);

    printf("Desenfileirou: %3d \n", item.Chave);

    ImprimeFila(fila);

  }

  printf("Tamanho da fila: %d\n", TamanhoFila(fila)); // tamanho da pilha

  printf("Fila vazia?: %d\n", VaziaFila(fila)); // fila vazia?

  system("PAUSE");

  return EXIT_SUCCESS;

}

2013/2-2013.09.19-AED: Notas Aula Revisão Prova 1

Problema 1
Apresentar em forma de desenho o estado final da pilha após a inserção dos elementos:
2 3 5 2 6 71 10

Apresente o desempilhamento de 4 itens e o estado final da pilha

Entrada: vetor de tamanho n (origem)
Saída: um novo vetor de tamanho n invertido (destino)

- 
1) Para cada elemento no vetor (do ultimo ao primeiro)
1.1) Ler o valor do vetor de origem
1.2) 

E A S * Y * Q U E * * * S T * * * I O * N * * *

Problema

Entrada: uma frase digitada pelo usuario
Saída: informar o número de consoantes na frase

T H E  B O O K  I S  O N  T H E  T A B L E

int main(){
  int numCons, i, tam;
  char frase[100];
  numCons = 0;
  gets(frase); // ler a frase do teclado
  
  tam = strlen(frase);
  for (i = 0; i < tam; i++)
  {
    if (frase[i] != 'A' && frase[i] != 'E' &&
   frase[i] != 'I' && frase[i] != 'O' &&
frase[i] != 'U' ){
numCons++;
}
  } 
  printf("Numero de consoantes: %d\n", numCons);
  return 0;
}

int main(){
  int numCons, i, tam;
  char frase[100];
  numCons = 0;
  gets(frase); // ler a frase do teclado
  
  tam = strlen(frase);
  for (i = 0; i < tam; i++)
  {
    if (frase[i] >= 'A' && frase[i] <= 'Z'){ // se o caractere for uma letra
printf("%c ", frase[i]);
}
  } 
  printf("Numero de consoantes: %d\n", numCons);
  return 0;
}




void subtrair(int *a, int *b, int *r){
  *r = *a - *b;  
}

2013/2-2013.09.19-AED: TAD Livro (TP1)

# tad biblioteca de livros

typedef char[5] TipoCodigo;

typedef char[30] TipoTituloLivro;

typedef char[15] TipoCategoria;

typedef char[30] TipoAutor;

typedef float TipoValor;

struct T_Livro {
  TipoCodigo codigo;
  TipoTituloLivro titulo;
  TipoCategoria categoria;
  TipoAutor autor;
  TipoValor valorPago;
};

typedef struct T_Livro TipoLivro;

struct T_Biblioteca{
  int tamanho;
  int capacidade;
  TipoLivro[100] livros;
}

typedef struct T_Biblioteca TipoBiblioteca;

//assinatura das funções void adicionarLivro(TipoBiblioteca * b, 
                    TipoLivro l);

// implementação das funções
void adicionarLivro(TipoBiblioteca * b, 
                    TipoLivro l)
{
  // se a biblioteca estiver cheia
  if (b->capacidade == b->tamanho)
  {
    printf("ERRO: Biblioteca cheia!\n");
return;
  }
  int pos = b->tamanho;
  b->livros[pos] = l;
  b->tamanho++;
}

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;
}