Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/10/02
003
004// Introducao ao conceito de FILA (primeiro a entrar, primeiro a sair) ou "queue" (FIFO - "first in, first out")
005// Usa conceito de apontador para apontador ("**apont")
006// Exemplo usando lista ligada (com 'typedef' e 'struct'), inserir e remover da fila
007
008// Exercicio: Fazer uma implementacao equivalente utilizando vetor no lugar de lista ligada.
009
010// gcc -fsanitize=address -g -o introducao_fila_lista_ligada_struct introducao_fila_lista_ligada_struct.c
011
012#include <stdio.h>
013#include <string.h> // para 'strcpy(...)'
014#include <stdlib.h> // para 'malloc(...)'
015
016#define TAM 10 // limite para numero de caracteres em campo do registro
017#define M 5    // limite para vetor de registros
018
019typedef struct reg {  // define estrutura 'dado'
020  int id;
021  char nome[TAM];
022  struct reg *prox; // aponta para uma estrutura 'dado'
023  } tipoRegistro;
024
025// Para depuracao: imprimir registro
026void imprimir (tipoRegistro *item) {
027  if (item == NULL) { // fila vazia
028    printf("<vazio>");
029    return;
030    }
031  printf("(%d, %s)", item->id, item->nome);
032  }
033
034// Testar: imprimir fila toda (comecando do primeiro)
035void imprimirFilaToda (tipoRegistro *primeiro) {
036  tipoRegistro *item = primeiro;
037  int i;
038  printf("Situacao da fila: ");
039  while (item!=NULL) {
040    imprimir(item);
041    printf(" ");
042    item = item->prox; //printf(" - %s\n", nomes[i]);
043    }
044  printf("\n");
045  }
046
047// Criar item de registro
048tipoRegistro *criar (int id, char *nome) {
049  tipoRegistro *item = malloc(sizeof(tipoRegistro));
050  // Nao basta apontar para "string" apontada por "nome", precisa copiar todos seus caracteres na posicao nova apontada por "item"
051  strcpy(item->nome, nome);
052  item->id   = id;
053  item->prox = NULL; // importante!
054  return item;
055  }
056
057// Inserir ao final da fila
058void inserir (tipoRegistro *item, tipoRegistro **primeiro, tipoRegistro **ultimo) {
059  if (*primeiro == NULL) { // fila vazia (apontado eh vazio)
060    *primeiro = item; // para alterar quem chama
061    *ultimo = item;
062    }
063  else {
064    (*ultimo)->prox = item;
065    *ultimo = item; // para alterar quem chama    
066    }
067  }
068
069// Remover o ultimo da fila (apos usar o dado poderia-se devolve-lo `a fila de memoria com "free(item);")
070// Tem que passar endereco do apontador para apontador de registros para poder altera-lo
071tipoRegistro *remover (tipoRegistro **primeiro, tipoRegistro **ultimo) {
072  tipoRegistro *item1, *item2 = NULL;
073  if (*primeiro == NULL) { // fila vazia
074    return NULL;
075    }
076  item1 = *primeiro;
077  while (item1->prox != NULL) {
078    item2 = item1;
079    item1 = item1->prox; // avance
080    }
081  if (item2==NULL) { // tinha apenas 1 elemento
082    *ultimo = item1; // anterior ao ultimo
083    *primeiro = item1;
084    }
085  else { 
086    item2->prox = NULL;
087    *ultimo = item2;
088    }   
089  return item1; // devolva o (anterior) ultimo
090  }
091
092int main (void) {
093  int i;
094  char nomes[][TAM] = { "aluno 1", "aluno 2", "aluno 3", "aluno 4", "aluno 5" };
095  tipoRegistro *item0, *item, *primeiro = NULL, *ultimo = NULL;
096
097  printf("Simulando operacoes:\n");
098  for (i=0; i<5; i++) { // inserir os 5 item
099    item = criar(i, nomes[i]); // imprimirFilaToda(item);
100    inserir(item, &primeiro, &ultimo); // tem que passar o local em que o apontador para primeiro esta (para altera-lo)
101    imprimirFilaToda(primeiro);
102    }
103
104  item0 = remover(&primeiro, &ultimo); // remover item "(4, aluno 5)"
105  printf("Removido item: "); imprimir(item0); printf("\n");
106
107  item = remover(&primeiro, &ultimo); // remover item "(3, aluno 4)"
108  printf("Removido item: "); imprimir(item); printf("\n");
109
110  inserir(item0, &primeiro, &ultimo); // inserir item "(4, aluno 5)"
111  printf("Inserido item: "); imprimir(item0); printf("\n");
112
113  printf("Situacao final da fila: ");
114  imprimirFilaToda(primeiro);
115  return 0;
116  }