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 PILHA (primeiro a entrar, primeiro a sair) ou "stack" (LIFO - "last in, first out")
005// Usa conceito de apontador para apontador ("**apont")
006// Exemplo usando lista ligada (com 'typedef' e 'struct'), inserir e remover da pilha
007
008// Exercicio: Fazer uma implementacao equivalente utilizando vetor no lugar de lista ligada.
009
010// gcc -fsanitize=address -g -o introducao_pilha_lista_ligada_struct introducao_pilha_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) { // pilha vazia
028    printf("<vazio>");
029    return;
030    }
031  printf("(%d, %s)", item->id, item->nome);
032  }
033
034// Testar: imprimir pilha toda
035void imprimirPilhaToda (tipoRegistro *topo) {
036  tipoRegistro *item = topo;
037  int i;
038  printf("Situacao da pilha: ");
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 no topo da pilha: versao 1 devolvendo o topo
058tipoRegistro *inserir (tipoRegistro *item, tipoRegistro *topo) {
059  if (topo != NULL) { // pilha vazia
060    item->prox = topo;
061    return item;
062    }
063  return item;
064  }
065
066// Inserir no topo da pilha: versao 2 atualizando o topo
067void inserirV2 (tipoRegistro *item, tipoRegistro **topo) {
068  if (*topo != NULL) { // pilha vazia (apontado eh vazio)
069    item->prox = *topo;
070    }
071  *topo = item; // para alterar quem chama
072  }
073
074// Remover do topo da pilha (apos usar o dado poderia-se devolve-lo `a pilha de memoria com "free(item);")
075// Tem que passar endereco do apontador para apontador de registros para poder altera-lo
076tipoRegistro *remover (tipoRegistro **topo) {
077  tipoRegistro *item;
078  if (*topo == NULL) { // pilha vazia
079    return NULL;
080    }
081  item = *topo;
082  *topo = (*topo)->prox;
083  return item;
084  }
085
086int main (void) {
087  int i;
088  char nomes[][TAM] = { "aluno 1", "aluno 2", "aluno 3", "aluno 4", "aluno 5" };
089  tipoRegistro *item0, *item, *topo = NULL;
090
091  printf("Simulando operacoes:\n");
092  for (i=0; i<5; i++) { // inserir os 5 item
093    item = criar(i, nomes[i]); // imprimirPilhaToda(item);
094    if (i%2 == 0) // usar versao 1
095      topo = inserir(item, topo);
096    else // usar versao 2
097      inserirV2(item, &topo); // tem que passar o local em que o apontador para topo esta (para altera-lo)
098    imprimirPilhaToda(topo);
099    }
100
101  item0 = remover(&topo); // remover item "(4, aluno 5)"
102  printf("Removido item: "); imprimir(item0); printf("\n");
103
104  item = remover(&topo); // remover item "(3, aluno 4)"
105  printf("Removido item: "); imprimir(item); printf("\n");
106
107  inserirV2(item0, &topo); // inserir item "(4, aluno 5)"
108  printf("Inserido item: "); imprimir(item0); printf("\n");
109
110  printf("Situacao final da pilha: ");
111  imprimirPilhaToda(topo);
112  return 0;
113  }