MC102MN

Na aula passada vimos alocação dinâmica de memória, um jeito de o programa poder usar uma quantidade de memória que só vai ser definida em tempo de execução. Para pedir um lugar de memória novo usamos malloc e para liberar esse lugar de memória usamos free.

Na aula de hoje vamos ver com mais calma vários usos diferentes de alocação de memória dinâmica. Alguns dos mais óbvios ficaram para exercício, como por exemplo alocar um tabuleiro de tamanho indeterminado para um dos nossos jogos.

O tipo de exemplo que veremos na aula de hoje pode ser encarado como uma mini introdução a estruturas de dados básicas.

A primeira coisa que veremos, que será usada como base para as outras, é o vetor que cresce. É só uma struct que guarda um vetor que pode crescer sempre que você precisar. Vou escrever aqui como um vetor de inteiros, mas é trivial adaptar para guardar estruturas arbitrárias.

struct vetor {
  int *v;
  int nalocados;
  int nusados;
};

struct vetor cria_vetor() {
  struct vetor v;
  v.v = NULL;
  v.nalocados = v.nusados = 0;
  return v;
}

void aumenta(struct vetor *v, int tamanho_novo) {
  int *novo_vetor = malloc(tamanho_novo*sizeof(int));
  memcpy(novo_vetor, v->v, v->nusados*sizeof(int));
  v->nalocados = tamanho_novo;
  free(v->v);
  v->v = novo_vetor;
}

A estrutura de dados mais básica que se usa em computação é uma pilha. A metáfora para entendê-la é que você tem uma pilha de inteiros, e a qualquer momento você pode ou jogar algum outro em cima da pilha ou tirar o último que você colocou na pilha. Esse tipo de ferramenta é útil nas mais variadas situações, e inclusive algo parecido está por trás da recursão.

A pilha é manipulada por duas funções: empilha, que coloca um inteiro no topo da pilha e desempilha, que tira e retorna o inteiro que estava no topo da pilha.

void empilha(struct vetor *pilha, int n) {
  if (pilha->nalocados == pilha->nusados) {
    aumenta(pilha, 2*pilha->nalocados);
  }
  pilha->v[pilha->nusados] = n;
  pilha->nusados += 1;
}

int desempilha(struct vetor *pilha) {
  if (pilha->nusados == 0) return 0;
  pilha->nusados -= 1;
  return pilha->v[pilha->nusados];
}

Vamos implementar aqui uma fila burra, que gasta muita memória, mas é fácil de entender. Uma fila é como uma pilha só que ao desempilhar você pega o elemento mais antigo na fila, em vez do mais novo.

struct fila {
  struct vetor v;
  int inicio, fim;
};

struct fila nova_fila() {
  struct fila f;
  f.v = cria_vetor();
  f.inicio = f.fim = 0;
}

void aumenta_fila(struct fila *v, int n) {
  int i;
  struct vetor v = cria_vetor()
  aumenta(&v, 2*f->v.nalocados);
  for (i = 0; i < f->fim - f->inicio; ++i)
     v.v[i] = f->v.v[inicio+i];
  free(f->v.v);
  f->v = v;
  f->inicio = 0;
  f->fim = i;
}

void enfileira(struct fila *f, int n) {
  if (f->fim == f->v.nalocados) aumenta_fila(f, 2*f->fim);
  f->v.v[f->fim] = n;
  f->fim += 1;
}

int desenfila(struct fila *f) {
  if (f->fim == f->inicio) return 0;
  f->inicio += 1;
  return f->v.v[f->inicio-1];
}

A lista ligada é a outra estrutura de dados básica. Ela é uma struct que contém um ponteiro para outra struct igual a ela. Com esses ponteiros você consegue formar uma cadeia de structs, cada uma apontando pra próxima, como se fosse uma corrente. Inserindo e removendo nós nessa corrente de forma sincronizada você consegue resolver vários problemas importantes. Uma lista ligada é assim:

struct no_lista {
  struct no_lista *prox;
  int n;
}

struct no_lista *cria_no(struct no_lista *prox, int n) {
  struct no_lista *no = malloc(sizeof(struct no_lista));
  no->prox = prox;
  no->n = n;
  return no;
}

Com a lista ligada podemos construir uma pilha:

struct pilha {
  struct no_lista *p;
}

struct pilha cria_pilha() {
  struct pilha p;
  p.p = NULL;
  return p;
}

void empilha(struct pilha *p, int n) {
  p->p = cria_no(p->p, n);
}

int desempilha(struct pilha *p) {
  int n;
  struct no_lista *pp;
  if (p->p == NULL) return 0;
  n = p->p->n;
  pp = p->p->prox;
  free(p->p);
  p->p = pp;
  return n;
}

E podemos construir uma fila de forma muito parecida

struct fila {
 struct no_lista *prim, *ult;
};

struct fila cria_fila() {
 struct fila f;
 f.prim = f.ult = NULL;
 return f;
}

void enfileira(struct fila *f, int n) {
  struct no_lista *no = cria_no(NULL, n);
  if (f->prim == NULL) {
    p->prim = f->ult = no;
  } else {
    f->ult->prox = no;
    f->ult = no;
  }
}

int desenfileira(struct fila *f) {
  int n;
  struct no_lista *p;
  if (f->prim == NULL) return 0;
  n = f->prim->n;
  p = f->prim;
  f->prim = f->prim->prox;
  free(p);
  return n;
}