ATIVIDADE DISCURSIVA ESTRUTURA DE DADOS

Prévia do material em texto

Questão A
Uma FILA é uma estrutura de dados “linear” na qual os elementos são inseridos por uma de suas extremidades e são removidos pela outra. Normalmente os elementos entram pelo fim da fila e são removidos pelo começo dela, mas este processo pode ser invertido também.
Temos muitos exemplos de filas no mundo real, como no caixa de um supermercado, no banco, na entrada de uma escola.
Questões:
Esta questão visa verificar sua habilidade de fazer um teste de mesa para filas:
Faça uma sequencia de 15 operações de inserção e remoção de elementos, aleatoriamente. Mostre o estado da fila a cada passo. Se a fila ficar vazia, não tem problema; apenas deixe isto indicado.
Por exemplo:
Se a sua fila for de clientes
Operação 1: insert(“Ademir”);
Fila == Inicio: Ademir :Fim
Operação 2: insert(“Janaína”);
Fila == Inicio: Ademir, Janaína :Fim
Operação 3: remove();
Fila == Inicio: Janaína :Fim
            ...
Dicas:
•   Você deve escolher o tipo de elemento e a sequência de operações.
•   Procure deixar sua fila com pelo menos 4 elementos em algum momento.
•   O exercício pode terminar com a fila contendo diversos elementos.
 
Questão B
Uma LISTA é uma estrutura de dados “linear” na qual os elementos são inseridos e removidos em qualquer lugar da mesma.
Questões:
Vamos testar na prática algo similar ao realizado no exercício anterior, mas com as listas.
Aqui você deve fazer um programa em linguagem C ou C++ que contenha as seguintes estruturas:
 
a)  Escolha uma STRUCT de sua preferência para compor os dados de sua lista. Esta struct deve conter pelo menos 2 campos diferentes. Crie um vetor desta struct para ser sua lista, ou use nós com alocação dinâmica.
b)  Faça 2 rotinas; uma que permita inserir um novo elemento apenas no início da lista; outra apenas no fim. Passe o novo elemento por parâmetro.
c)  De forma similar, faça mais 2 rotinas: uma que permita remover um elemento do início da lista; outra apenas do final.
d)  Crie uma função para mostrar toda a sua lista num determinado momento.
e)  Faça uma sequência de 15 operações de inserção e/ou remoção no main. Vá mostrando a sua lista após cada operação, da mesma forma que foi feito na questão A.
 
Dicas:
•   Suas rotinas devem trabalhar com parâmetros sempre que possível.
•   Você pode escolher os campos de sua estrutura e a sequência de operações a ser realizada no main.
•   Procure deixar sua fila com pelo menos 4 elementos em algum momento.
•   O exercício pode terminar com a lista contendo diversos elementos.
•          Procure testar sua lista como “vazia” em algum momento.
QUESTÃO A
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
 
typedef enum {FALSE, TRUE} bool;
 
 
#define DuracaoDaSimulacao       200
#define ProbabilidadeDeEntrada     0.2
#define TempoMinAtendimento        5
#define TempoMaxAtendimento       20
 
 
typedef struct {
   int numeroCliente;
   int instanteEntrada;
   int tempoDeAtendimento;
} clienteT;
 
 
typedef struct {
   queueT   *fila;
   clienteT *clienteAtivo;
   int       tempo;
   int       numeroDeClientes;
   int       numeroDeAtendidos;
   int       somaTemposDeEspera;
   int       somaComprimentos;
} dadosDaSimulacaoT;
 
 
void   ExecutaSimulacao( dadosDaSimulacaoT *sim);
void   ColocaClienteNaFila( dadosDaSimulacaoT *sim);
void   ProcessaFila( dadosDaSimulacaoT *sim);
void   AtendeCliente( dadosDaSimulacaoT *sim);
void   DispensaCliente( dadosDaSimulacaoT *sim);
void   Randomize( void);
int    RandomInteger( int low, int high);
double RandomReal( double low, double high);
bool   RandomChance( double p);
 
bool traceFlag;
 
 
int main( int argc, char *argv[]) {
   dadosDaSimulacaoT dados;
 
   if (argc >= 2 && strcmp( argv[1], "-t") == 0) traceFlag = TRUE;
   else traceFlag = FALSE;
 
   Randomize();
   ExecutaSimulacao( &dados);
 
   printf( "\n");
   printf( "Resultados da simulação, dados os seguintes parâmetros:\n");
   printf( "   DuracaoDaSimulacao:     %4d\n",     
          (int) DuracaoDaSimulacao);
   printf( "   ProbabilidadeDeEntrada: %7.2f\n",
          (double) ProbabilidadeDeEntrada);
   printf( "   TempoMinAtendimento:    %4d\n",     
          (int) TempoMinAtendimento);
   printf( "   TempoMaxAtendimento:    %4d\n",
          (int) TempoMaxAtendimento);
   printf( "\n");
   printf( "Clientes atendidos:        %4d\n",
          dados.numeroDeAtendidos);
   printf( "Tempo médio de espera:     %7.2f\n",
          (double) dados.somaTemposDeEspera / dados.numeroDeAtendidos);
   printf( "Comprimento médio da fila: %7.2f\n",
          (double) dados.somaComprimentos / DuracaoDaSimulacao);
   return 0;
}
 
 
void ExecutaSimulacao( dadosDaSimulacaoT *sim) {
   sim->fila = NewQueue();
   sim->clienteAtivo = NULL;
   sim->numeroDeClientes = 0;
   sim->numeroDeAtendidos = 0;
   sim->somaTemposDeEspera = 0;
   sim->somaComprimentos = 0;
   for (sim->tempo = 0; sim->tempo < DuracaoDaSimulacao; sim->tempo++) {
      if (RandomChance( ProbabilidadeDeEntrada))
         ColocaClienteNaFila( sim);
      ProcessaFila( sim);
   }
   FreeQueue( sim->fila);
}
 
 
void ColocaClienteNaFila( dadosDaSimulacaoT *sim) {
   clienteT *c;
   sim->numeroDeClientes++;
   c = malloc( sizeof (clienteT));
   c->numeroCliente = sim->numeroDeClientes;
   c->instanteEntrada = sim->tempo;
   c->tempoDeAtendimento =
      RandomInteger( TempoMinAtendimento, TempoMaxAtendimento);
   Enqueue( sim->fila, c);
   if (traceFlag)
      printf( "%4d: Cliente %d entra na fila\n",
             sim->tempo, sim->numeroDeClientes);
}
 
 
void ProcessaFila( dadosDaSimulacaoT *sim) {
   if (sim->clienteAtivo == NULL) {
      if (!QueueIsEmpty( sim->fila))
         AtendeCliente( sim);
   } else {
      if (sim->clienteAtivo->tempoDeAtendimento == 0)
         DispensaCliente( sim);
      else
         sim->clienteAtivo->tempoDeAtendimento--;
   }
   sim->somaComprimentos += QueueLength( sim->fila);
}
 
 
void AtendeCliente( dadosDaSimulacaoT *sim) {
   clienteT *cli;
   cli = Dequeue( sim->fila);
   sim->clienteAtivo = cli;
   sim->numeroDeAtendidos++;
   sim->somaTemposDeEspera += (sim->tempo - cli->instanteEntrada);
   if (traceFlag)
      printf( "%4d: Cliente %d chega ao caixa\n",
             sim->tempo, cli->numeroCliente);
}
 
 
void DispensaCliente( dadosDaSimulacaoT *sim) {
   if (traceFlag)
      printf( "%4d: Cliente %d deixa o caixa\n",
             sim->tempo, sim->clienteAtivo->numeroCliente);
   free( sim->clienteAtivo);
   sim->clienteAtivo = NULL;
}
 
 
void Randomize( void) {
    srand( (int) time( NULL));
}
 
 
double RandomReal( double low, double high) {
    double d;
    d = (double) rand() / ((double) RAND_MAX + 1);
    return low + d * (high - low);
}
 
int RandomInteger( int low, int high) {
    int k;
    double d;
    d = (double) rand() / ((double) RAND_MAX + 1);
    k = d * (high - low + 1);
    return low + k;
}
 
 
bool RandomChance( double p) {
    return RandomReal( 0, 1) < p;
}
 
Resultados de um teste:
	   5: Cliente 1 entra na fila
   5: Cliente 1 chega ao caixa
  16: Cliente 1 deixa o caixa
  17: Cliente 2 entra na fila
  17: Cliente 2 chega ao caixa
  18: Cliente 3 entra na fila
  19: Cliente 4 entra na fila
  20: Cliente 5 entra na fila
  21: Cliente 6 entra na fila
  32: Cliente 2 deixa o caixa
   .
   .
   .
 180: Cliente 13 deixa o caixa
 181: Cliente 14 chega ao caixa
 185: Cliente 34 entra na fila
 191: Cliente 14 deixa o caixa
 192: Cliente 15 chega ao caixa
 193: Cliente 35 entra na fila
                                                             
Resultados da simulação, dados os seguintes parâmetros:          
   DuracaoDaSimulacao:      200
   ProbabilidadeDeEntrada:    0.20
   TempoMinAtendimento:       5
   TempoMaxAtendimento:      20
 
Clientes atendidos:          15
Tempo médio de espera:       50.60
Comprimento médio da fila:    9.53QUESTÃO B
#include <stdio.h>
#include <stdlib.h>
struct Node{
            int num;
            struct Node *prox;
};
typedef struct Node node;
 
int tam;
 
void inicia(node *LISTA);
int menu(void);
void opcao(node *LISTA, int op);
node *criaNo();
void insereFim(node *LISTA);
void insereInicio(node *LISTA);
void exibe(node *LISTA);
void libera(node *LISTA);
void insere (node *LISTA);
node *retiraInicio(node *LISTA);
node *retiraFim(node *LISTA);
node *retira(node *LISTA);
 
 
int main(void)
{
            node *LISTA = (node *) malloc(sizeof(node));
            if(!LISTA){
                        printf("Sem memoria disponivel!\n");
                        exit(1);
            }else{
            inicia(LISTA);
            int opt;
           
            do{
                        opt=menu();
                        opcao(LISTA,opt);
            }while(opt);
 
            free(LISTA);
            return 0;
            }
}
 
void inicia(node *LISTA)
{
            LISTA->prox = NULL;
            tam=0;
}
 
int menu(void)
{
            int opt;
           
            printf("Escolha a opcao\n");
            printf("0. Sair\n");
            printf("1. Zerar lista\n");
            printf("2. Exibir lista\n");
            printf("3. Adicionar node no inicio\n");
            printf("4. Adicionar node no final\n");
            printf("5. Escolher onde inserir\n");
            printf("6. Retirar do inicio\n");
            printf("7. Retirar do fim\n");
            printf("8. Escolher de onde tirar\n");
            printf("Opcao: "); scanf("%d", &opt);
           
            return opt;
}
 
void opcao(node *LISTA, int op)
{
            node *tmp;
            switch(op){
                        case 0:
                                   libera(LISTA);
                                   break;
                                  
                        case 1:
                                   libera(LISTA);
                                   inicia(LISTA);
                                   break;
                       
                        case 2:
                                   exibe(LISTA);
                                   break;
                       
                        case 3:
                                   insereInicio(LISTA);
                                   break;            
                                  
                        case 4:
                                   insereFim(LISTA);
                                   break;
                                  
                        case 5:
                                   insere(LISTA);
                                   break;
                       
                        case 6:
                                   tmp= retiraInicio(LISTA);
                                   printf("Retirado: %3d\n\n", tmp->num);
                                   break;
                                  
                        case 7:
                                   tmp= retiraFim(LISTA);
                                   printf("Retirado: %3d\n\n", tmp->num);
                                   break;
                       
                        case 8:
                                   tmp= retira(LISTA);
                                   printf("Retirado: %3d\n\n", tmp->num);
                                   break;
                       
                        default:
                                   printf("Comando invalido\n\n");
            }
}
 
int vazia(node *LISTA)
{
            if(LISTA->prox == NULL)
                        return 1;
            else
                        return 0;
}
 
node *aloca()
{
            node *novo=(node *) malloc(sizeof(node));
            if(!novo){
                        printf("Sem memoria disponivel!\n");
                        exit(1);
            }else{
                        printf("Novo elemento: "); scanf("%d", &novo->num);
                        return novo;
            }
}
 
 
void insereFim(node *LISTA)
{
            node *novo=aloca();
            novo->prox = NULL;
           
            if(vazia(LISTA))
                        LISTA->prox=novo;
            else{
                        node *tmp = LISTA->prox;
                       
                        while(tmp->prox != NULL)
                                   tmp = tmp->prox;
                       
                        tmp->prox = novo;
            }
            tam++;
}
 
void insereInicio(node *LISTA)
{
            node *novo=aloca();          
            node *oldHead = LISTA->prox;
           
            LISTA->prox = novo;
            novo->prox = oldHead;
           
            tam++;
}
 
void exibe(node *LISTA)
{
            system("clear");
            if(vazia(LISTA)){
                        printf("Lista vazia!\n\n");
                        return ;
            }
           
            node *tmp;
            tmp = LISTA->prox;
            printf("Lista:");
            while( tmp != NULL){
                        printf("%5d", tmp->num);
                        tmp = tmp->prox;
            }
            printf("\n        ");
            int count;
            for(count=0 ; count < tam ; count++)
                        printf("  ^  ");
            printf("\nOrdem:");
            for(count=0 ; count < tam ; count++)
                        printf("%5d", count+1);
           
                       
            printf("\n\n");
}
 
void libera(node *LISTA)
{
            if(!vazia(LISTA)){
                        node *proxNode,
                                     *atual;
                       
                        atual = LISTA->prox;
                        while(atual != NULL){
                                   proxNode = atual->prox;
                                   free(atual);
                                   atual = proxNode;
                        }
            }
}
 
void insere(node *LISTA)
{
            int pos,
                        count;
            printf("Em que posicao, [de 1 ate %d] voce deseja inserir: ", tam);
            scanf("%d", &pos);
           
            if(pos>0 && pos <= tam){
                        if(pos==1)
                                   insereInicio(LISTA);
                        else{
                                   node *atual = LISTA->prox,
                                                *anterior=LISTA;
                                   node *novo=aloca();
                                                
                                   for(count=1 ; count < pos ; count++){
                                                           anterior=atual;
                                                           atual=atual->prox;
                                   }
                                   anterior->prox=novo;
                                   novo->prox = atual;
                                   tam++;
                        }
                                  
            }else
                        printf("Elemento invalido\n\n");              
}
 
node *retiraInicio(node *LISTA)
{
            if(LISTA->prox == NULL){
                        printf("Lista ja esta vazia\n");
                        return NULL;
            }else{
                        node *tmp = LISTA->prox;
                        LISTA->prox = tmp->prox;
                        tam--;
                        return tmp;
            }
                                              
}
 
node *retiraFim(node *LISTA)
{
            if(LISTA->prox == NULL){
                        printf("Lista ja vazia\n\n");
                        return NULL;
            }else{
                        node *ultimo = LISTA->prox,
                                    *penultimo = LISTA;while(ultimo->prox != NULL){
                                   penultimo = ultimo;
                                   ultimo = ultimo->prox;
                        }
                                    
                        penultimo->prox = NULL;
                        tam--;
                        return ultimo;                      
            }
}
 
node *retira(node *LISTA)
{
            int opt,
                        count;
            printf("Que posicao, [de 1 ate %d] voce deseja retirar: ", tam);
            scanf("%d", &opt);
           
            if(opt>0 && opt <= tam){
                        if(opt==1)
                                   return retiraInicio(LISTA);
                        else{
                                   node *atual = LISTA->prox,
                                                *anterior=LISTA;
                                                
                                   for(count=1 ; count < opt ; count++){
                                               anterior=atual;
                                               atual=atual->prox;
                                   }
                                  
                        anterior->prox=atual->prox;
                        tam--;
                        return atual;
                        }
                                  
            }else{
                        printf("Elemento invalido\n\n");
                        return NULL;
            }
}
Comentários
Comentário:
Questão A - vale 1,5
Sua resposta atende ao que foi pedido na questão.
Nota: 1,5