sábado, 9 de novembro de 2013

2013/2-AED-Exercício Para Casa 8/11/2013

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

int main(int argc, char *argv[])
{
  TipoLista lista, pares, impares;
  TipoItem item;
  int i = 0;
  int a[] = {2,5,6,7,8,9,11,12,15,16,17};
  int tam = 11;
  int capacidade = 10;
 
  // 1) Criar a lista
  CriarLista(&lista, capacidade);
  CriarLista(&pares, capacidade);
  CriarLista(&impares, capacidade);
  // 2) Imprimir a lista
  ImprimirLista(lista);
  // 3) inserir os elementos
  for (i = 0; i < tam; i++)
  {   item.Chave = a[i];
      InserirLista(&lista, item);
      // 4) Imprimir a lista
      ImprimirLista(lista);
  }
  // 5) Pesquisar a lista
  item.Chave = 5;
  i = PesquisarLista(lista, item);
  printf("Resultado pesquisa %d: %d\n",
    item.Chave, i);
  item.Chave = 3;
  i = PesquisarLista(lista, item);
  printf("Resultado pesquisa %d: %d\n",
    item.Chave, i);
   
  // 6) Retirar alguns elementos da lista
  for (i = 0; i < capacidade; i++)
  {
      RetirarLista(&lista, &item);
      printf("Retirado da lista: %d\n",
         item.Chave);
     // 7) imprimir a lista
      ImprimirLista(lista);
      //8) testar se numero eh par ou impar
      if (item.Chave % 2 == 0)
      { InserirLista(&pares, item);
      } else {
        InserirLista(&impares, item);
      }
  }
  printf("Pares: \n");
  ImprimirLista(pares);
  printf("Impares: \n");
  ImprimirLista(impares);
 
  system("PAUSE");   
  return 0;
}
Postado por às Nenhum comentário:

2013/2-AED-TAD Lista Programa Principal E TAD Lista H

// TAD LISTA

// Tipos de dados
typedef int TipoChave;

struct T_Item{
  TipoChave Chave;
};

typedef struct T_Item TipoItem;

typedef struct T_Celula * TipoApontador;

struct T_Celula{
  TipoItem Item;
  TipoApontador Prox;
};

typedef struct T_Celula TipoCelula;

struct T_Lista{
  int Tamanho;
  int Capacidade;
  TipoApontador Primeiro, Ultimo;
};

typedef struct T_Lista TipoLista;

// Cabeçalho das operações

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);

// Implementação das operações

void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
  Lista->Primeiro = (TipoApontador) malloc(
                             sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
  Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
  Lista->Tamanho = 0;
  Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
  Lista->Primeiro->Prox = NULL;
}

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item)
{
  //1 ) verificar se LISTA estah cheia
  if (ListaCheia(*Lista) == 1){
    printf("ERRO: lista cheia!\n");return;
  }
  //2 ) criar nova celula a partir da ultima celula
  Lista->Ultimo->Prox = (TipoApontador)
      malloc(sizeof(TipoCelula));
  //3 ) inserir a chave na celula
  Lista->Ultimo->Prox->Item = item;
  //4 ) atualizar apontadores (prim e ult.)
  Lista->Ultimo = Lista->Ultimo->Prox;
  Lista->Ultimo->Prox = NULL;
  //5 ) atualizar tamanho
  Lista->Tamanho++;
}

// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item)
{
  TipoApontador aux, q;
  //1) verificar se LISTA estah vazia
  if(ListaVazia(*Lista) == 1){
    printf("ERRO: lista vazia");return;
  }
  //2) guardar a celula anterior (aux)
  aux = Lista->Primeiro;
  //3) guardar a celula a ser removida (q)
  q = aux->Prox;
  //4) atualizar a celula anterior
  aux->Prox = q->Prox;
  //5) obter o item removido
  *item = q->Item;
  //6) liberar o espaco de memoria de q
  free(q);
  //7) decrementar tamanho
  Lista->Tamanho--;
}

// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
  TipoApontador aux;
  int i = 0;
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL &&
     aux->Prox->Item.Chave != item.Chave){
  //3.1) se a chave que estiver na celula apos aux
  //     for igual a chave procurada
  //3.2) atualizar aux
    aux = aux->Prox;
    i++;
  }
  if (aux->Prox !=NULL){
    // achei
    printf("Elemento encontrado!\n");
  } else {
    // nao achei
    printf("Elemento NAO encontrado!\n");
    i = -1;
  }
  return i;
}

// verificar se estah cheia
int ListaCheia(TipoLista Lista){
  if (Lista.Tamanho == Lista.Capacidade)
  {  return 1; // lista cheia
  } else {
    return 0;  //lista nao cheia
  }
}
// verificar se estah vazia
int ListaVazia(TipoLista Lista)
{
  if (Lista.Primeiro == Lista.Ultimo)
  { return 1; // lista vazia
  } else {
    return 0; // lista nao vazia
  }
}
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista){
  return Lista.Tamanho;
}
// imprimir a lista
void ImprimirLista(TipoLista Lista)
{
  TipoApontador aux;
 
  printf("TAD Lista [%d/%d]\n",
     Lista.Tamanho, Lista.Capacidade);
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  printf(" [/]-> ");
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL){
  //3.2) atualizar aux
    printf("[%d]-> ", aux->Prox->Item.Chave);
    aux = aux->Prox;
  }
  printf("NULL\n\n");
}














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

int main(int argc, char *argv[])
{
  TipoLista lista;
  TipoItem item;
  int i = 0;
  int a[] = {2, 5, 6, 7, 8, 9, 11};
  int tam = 7;
  int capacidade = 10;
 
  // 1) Criar a lista
  CriarLista(&lista, capacidade);
  // 2) Imprimir a lista
  ImprimirLista(lista);
  // 3) inserir os elementos
  for (i = 0; i < tam; i++)
  {   item.Chave = a[i];
      InserirLista(&lista, item);
      // 4) Imprimir a lista
      ImprimirLista(lista);
  }
  // 5) Pesquisar a lista
  item.Chave = 5;
  i = PesquisarLista(lista, item);
  printf("Resultado pesquisa %d: %d\n",
    item.Chave, i);
  item.Chave = 3;
  i = PesquisarLista(lista, item);
  printf("Resultado pesquisa %d: %d\n",
    item.Chave, i);
   
  // 6) Retirar alguns elementos da lista
  for (i = 0; i < tam; i++)
  {
      RetirarLista(&lista, &item);
      printf("Retirado da lista: %d\n",
         item.Chave);
     // 7) imprimir a lista
      ImprimirLista(lista);
  }
 
  system("PAUSE");   
  return 0;
}
Postado por às Nenhum comentário:

2013/2-AED-TAD Lista Arquivo .H

// TAD LISTA

// Tipos de dados
typedef int TipoChave;

struct T_Item{
  TipoChave Chave;
};

typedef struct T_Item TipoItem;

typedef struct T_Celula * TipoApontador;

struct T_Celula{
  TipoItem Item;
  TipoApontador Prox;
};

typedef struct T_Celula TipoCelula;

struct T_Lista{
  int Tamanho;
  int Capacidade;
  TipoApontador Primeiro, Ultimo;
};

typedef struct T_Lista TipoLista;

// Cabeçalho das operações

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);

// Implementação das operações

void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
  Lista->Primeiro = (TipoApontador) malloc(
                             sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
  Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
  Lista->Tamanho = 0;
  Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
  Lista->Primeiro->Prox = NULL;
}

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item)
{
  //1 ) verificar se LISTA estah cheia
  if (ListaCheia(*Lista) == 1){
    printf("ERRO: lista cheia!\n");return;
  }
  //2 ) criar nova celula a partir da ultima celula
  Lista->Ultimo->Prox = (TipoApontador)
      malloc(sizeof(TipoCelula));
  //3 ) inserir a chave na celula
  Lista->Ultimo->Prox->Item = item;
  //4 ) atualizar apontadores (prim e ult.)
  Lista->Ultimo = Lista->Ultimo->Prox;
  Lista->Ultimo->Prox = NULL;
  //5 ) atualizar tamanho
  Lista->Tamanho++;
}

// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item)
{
  TipoApontador aux, q;
  //1) verificar se LISTA estah vazia
  if(ListaVazia(*Lista) == 1){
    printf("ERRO: lista vazia");return;
  }
  //2) guardar a celula anterior (aux)
  aux = Lista->Primeiro;
  //3) guardar a celula a ser removida (q)
  q = aux->Prox;
  //4) atualizar a celula anterior
  aux->Prox = q->Prox;
  //5) obter o item removido
  *item = q->Item;
  //6) liberar o espaco de memoria de q
  free(q);
  //7) decrementar tamanho
  Lista->Tamanho--;
}

// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
  TipoApontador aux;
  int i = -1;
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL &&
     aux->Prox->Item.Chave != item.Chave){
  //3.1) se a chave que estiver na celula apos aux
  //     for igual a chave procurada
  //3.2) atualizar aux
    aux = aux->Prox;
    i++;
  }
  if (aux->Prox !=NULL){
    // achei
    printf("Elemento encontrado!\n");
  } else {
    // nao achei
    printf("Elemento NAO encontrado!\n");
  }
  return i;
}

// verificar se estah cheia
int ListaCheia(TipoLista Lista){
  if (Lista.Tamanho == Lista.Capacidade)
  {  return 1; // lista cheia
  } else {
    return 0;  //lista nao cheia
  }
}
// verificar se estah vazia
int ListaVazia(TipoLista Lista)
{
  if (Lista.Primeiro == Lista.Ultimo)
  { return 1; // lista vazia
  } else {
    return 0; // lista nao vazia
  }
}
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista){
  return Lista.Tamanho;
}
// imprimir a lista
void ImprimirLista(TipoLista Lista)
{
  TipoApontador aux;
 
  printf("TAD Lista [%d/%d]\n",
     Lista.Tamanho, Lista.Capacidade);
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL){
  //3.2) atualizar aux
    printf("%d -> ", aux->Prox->Item.Chave);
    aux = aux->Prox;
  }
  printf("\n\n");
}
Postado por às Nenhum comentário:

2013/2-AED-2013.11.07: TAD Lista - Código fonte em C

// TAD LISTA

// Tipos de dados
typedef int TipoChave;

struct T_Item{
  TipoChave Chave;
};

typedef struct T_Item TipoItem;

typedef struct T_Celula * TipoApontador;

struct T_Celula{
  TipoItem Item;
  TipoApontador Prox;
};

typedef struct T_Celula TipoCelula;

struct T_Lista{
  int Tamanho;
  int Capacidade; 
  TipoApontador Primeiro, Ultimo;
};

typedef struct T_Lista TipoLista;

// Cabeçalho das operações

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);

// Implementação das operações

void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
  Lista->Primeiro = (TipoApontador) malloc(
                             sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
  Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
  Lista->Tamanho = 0;
  Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
  Lista->Primeiro->Prox = null;
}

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item)
{
  //1 ) verificar se LISTA estah cheia
  if (ListaCheia(*Lista) == 1){
    printf("ERRO: lista cheia!\n");return;
  }
  //2 ) criar nova celula a partir da ultima celula
  Lista->Ultimo->Prox = (TipoApontador)
      malloc(sizeof(TipoCelula));
  //3 ) inserir a chave na celula
  Lista->Ultimo->Prox->Item = item;
  //4 ) atualizar apontadores (prim e ult.)
  Lista->Ultimo = Lista->Ultimo->Prox;
  Lista->Ultimo->Prox = null;
  //5 ) atualizar tamanho 
  Lista->Tamanho++;
}

// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item)
{
  TipoApontador aux, q;
  //1) verificar se LISTA estah vazia
  if(ListaVazia(*Lista) == 1){
    printf("ERRO: lista vazia");return;
  }
  //2) guardar a celula anterior (aux)
  aux = Lista->Primeiro;
  //3) guardar a celula a ser removida (q)
  q = aux->Prox;
  //4) atualizar a celula anterior
  aux->Prox = q->Prox;
  //5) obter o item removido
  *item = q->Item;
  //6) liberar o espaco de memoria de q
  free(q);
  //7) decrementar tamanho 
  Lista->Tamanho--;
}

// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
  TipoApontador aux;
  int i = -1;
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != null &&
     aux->Prox->Item != item){
  //3.1) se a chave que estiver na celula apos aux
  //     for igual a chave procurada
  //3.2) atualizar aux
    aux = aux->Prox;
    i++;
  }
  if (aux->Prox !=null){
    // achei
    printf("Elemento encontrado!\n");
  } else {
    // nao achei
    printf("Elemento NAO encontrado!\n");
  }
  return i;
}

// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
 
}
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista

// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);
Postado por às Nenhum comentário:

quinta-feira, 7 de novembro de 2013

2013/2-AED-2013.11.01: TAD Lista - Código Fonte em C

// TAD LISTA

 // Tipos de dados
typedef int TipoChave;

 struct T_Item{
  TipoChave Chave;
};

 typedef struct T_Item TipoItem;

 typedef struct T_Celula * TipoApontador;

 struct T_Celula{
  TipoItem Item;
  TipoApontador Prox;
};

 typedef struct T_Celula TipoCelula;

 struct T_Lista{
  int Tamanho;
  int Capacidade;  
  TipoApontador Primeiro, Ultimo;
};

 typedef struct T_Lista TipoLista;

 // Cabeçalho das operações

 // inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);

 // Implementação das operações

 void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
  Lista->Primeiro = (TipoApontador) malloc(
                             sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
  Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
  Lista->Tamanho = 0;
  Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
  Lista->Primeiro->Prox = null;
}

Postado por às Nenhum comentário:

quinta-feira, 24 de outubro de 2013

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;
}
Postado por às Nenhum comentário:

sexta-feira, 11 de outubro de 2013

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

Postado por às Nenhum comentário:

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;
    }    
}
Postado por às Nenhum comentário:

quinta-feira, 3 de outubro de 2013

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

Postado por às Nenhum comentário:
Assinar: Comentários (Atom)