Aula 36 – Revisão Completa: listaSequencial.c

Visão Geral do Programa

Esta aula revisa o arquivo listaSequencial.c — o programa completo que implementa todos os conceitos das Aulas 29 a 35. Em vez de ver os conceitos isoladamente, aqui você lê o código como um todo e entende como cada parte se encaixa na outra.

O programa implementa as seguintes operações, nesta ordem no arquivo:

Bloco 1 — Cabeçalho, Includes e Defines

As primeiras linhas do arquivo estabelecem o contexto e as dependências do programa:

/******************************************************************************
    listaSequencial.c
  Este programa gerencia listas lineares sequenciais.
  As listas gerenciadas podem ter MAX elementos (posicoes de 0 a MAX-1 no
    arranjo A). Alocamos MAX+1 posicoes no arranjo para possibilitar a
    criacao de um elemento sentinela.
******************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#define MAX  50
#define ERRO -1

Bloco 2 — Definição dos Tipos

A fundação de tudo: os três typedefs que definem o que é uma lista neste programa.

typedef int TIPOCHAVE;

typedef struct {
  TIPOCHAVE chave;
  // outros campos...
} REGISTRO;

typedef struct {
  REGISTRO A[MAX+1];
  int nroElem;
} LISTA;

Leia de baixo para cima para entender a dependência entre os tipos:

Bloco 3 — inicializarLista

/* Inicialização da lista sequencial (a lista já está criada e é apontada
   pelo endereço em l) */
void inicializarLista(LISTA* l) {
  l->nroElem = 0;
} /* inicializarLista */

Três pontos para fixar sobre esta função:

Bloco 4 — exibirLista

/* Exibição da lista sequencial */
void exibirLista(LISTA* l) {
  int i;
  printf("Lista: \" ");
  for (i = 0; i < l->nroElem; i++)
    printf("%i ", l->A[i].chave); // só lembrando TIPOCHAVE = int
  printf("\"\n");
} /* exibirLista */

O for percorre exatamente os nroElem primeiros índices do array — de 0 até nroElem - 1. A condição i < l->nroElem garante que nunca acessamos posições além dos elementos válidos.

Bloco 5 — tamanho e tamanhoEmBytes

/* Retornar o tamanho da lista (numero de elementos "validos") */
int tamanho(LISTA* l) {
  return l->nroElem;
} /* tamanho */

/* Retornar o tamanho em bytes da lista. Neste caso, isto nao depende do numero
   de elementos que estao sendo usados, pois a alocacao de memoria eh estatica.
   A priori, nao precisariamos do ponteiro para a lista, vamos utiliza-lo apenas
   porque teremos as mesmas funcoes para listas ligadas. */
int tamanhoEmBytes(LISTA* l) {
  return sizeof(LISTA);
} /* tamanhoEmBytes */

Bloco 6 — primeiroElem, ultimoElem e enesimoElem

/* Retornar a chave do primeiro elemento (caso haja) e ERRO caso vazia */
TIPOCHAVE primeiroElem(LISTA* l) {
  if (l->nroElem > 0) return l->A[0].chave;
  else return ERRO; // lista vazia
} /* primeiroElem */

/* Retornar a chave do ultimo elemento (caso haja) e ERRO caso vazia */
TIPOCHAVE ultimoElem(LISTA* l) {
  if (l->nroElem > 0) return l->A[l->nroElem - 1].chave;
  else return ERRO; // lista vazia
} /* ultimoElem */

/* Retornar a chave do elemento na posição n (0 a MAX-1) */
TIPOCHAVE enesimoElem(LISTA* l, int n) {
  if ((n >= 0) && (n < l->nroElem)) return l->A[n].chave;
  else return ERRO;
} /* enesimoElem */

As três funções seguem o mesmo padrão de proteção: verificam se o acesso é válido antes de acessar o array. Compare os três casos de acesso:

Bloco 7 — reinicializarLista

/* Reinicializar a estrutura */
void reinicializarLista(LISTA* l) {
  l->nroElem = 0;
} /* reinicializarLista */

O código é idêntico ao de inicializarLista. A diferença está na intenção semântica: inicializarLista é chamada na primeira vez, quando a lista acaba de ser criada; reinicializarLista é chamada para esvaziar uma lista que já estava em uso.

Bloco 8 — inserirElemLista

/* Inserção "direta" na iésima posição (posicao i do arranjo A).
   Funciona da mesma maneira de um insertionSort: deve-se deslocar todos os
   elementos a partir da iesima posicao e entao se insere o novo elemento. */
bool inserirElemLista(LISTA* l, REGISTRO reg, int i) {
  int j;
  if ((l->nroElem >= MAX) || (i < 0) || (i > l->nroElem))
    return false; // lista cheia ou índice inválido
  for (j = l->nroElem; j > i; j--) l->A[j] = l->A[j-1];
  l->A[i] = reg;
  l->nroElem++;
  return true;
} /* inserirElemLista */

Esta é a função mais complexa do programa. Disseque cada parte:

Passo a passo para inserir chave 12 na posição i=2 da lista [9, 3, 4, 1] (nroElem=4):

Bloco 9 — buscaSequencial

/* Busca sequencial em lista ordenada ou não SEM SENTINELA */
int buscaSequencial(LISTA* l, TIPOCHAVE ch) {
  int i = 0;
  while (i < l->nroElem) {
    if (ch == l->A[i].chave) return i; // achou
    else i++;
  }
  return ERRO; // não achou
} /* buscaSequencial */

A lógica é direta: percorre do índice 0 ao nroElem-1, comparando a chave procurada ch com a chave de cada elemento. Dois caminhos de saída:

Bloco 10 — excluirElemLista

/* Exclusão do elemento cuja chave seja igual a ch */
bool excluirElemLista(LISTA* l, TIPOCHAVE ch) {
  int pos, j;
  pos = buscaSequencial(l, ch);
  if (pos == ERRO) return false; // não existe
  for (j = pos; j < l->nroElem - 1; j++) l->A[j] = l->A[j+1];
  l->nroElem--;
  return true;
} /* excluirElemLista */

A função tem três etapas encadeadas:

Visualizando a exclusão do elemento com chave 4 (posição 3) da lista [9, 3, 12, 4, 1]:

Bloco 11 — buscaSentinela

/* Busca sequencial em lista COM SENTINELA (vetor criado com MAX+1 posições) */
int buscaSentinela(LISTA* l, TIPOCHAVE ch) {
  int i = 0;
  l->A[l->nroElem].chave = ch; // sentinela
  while (l->A[i].chave != ch) i++;
  if (i > l->nroElem - 1) return ERRO; // não achou
  else return i;
} /* buscaSentinela */

Compare com a buscaSequencial: o while original tinha duas condições. Esta versão tem apenas uma:

Bloco 12 — main(): o Programa em Ação

O main exercita todas as funções em sequência. Vamos percorrê-lo em seções:

Seção A — Inicialização e estado inicial

LISTA lista;
inicializarLista(&lista);
exibirLista(&lista);
printf("Numero de elementos na lista: %i.\n", tamanho(&lista));
printf("Tamanho da lista (em bytes): %i.\n",  tamanhoEmBytes(&lista));

LISTA lista; declara a struct na stack. inicializarLista(&lista) zera nroElem. A lista exibida está vazia e já ocupa 208 bytes — a memória é reservada integralmente desde a declaração.

Seção B — Inserções

REGISTRO reg;
reg.chave = 9;
inserirElemLista(&lista, reg, 0);  // lista: [9]
exibirLista(&lista);

reg.chave = 3;  inserirElemLista(&lista, reg, 1);  // [9, 3]
reg.chave = 4;  inserirElemLista(&lista, reg, 2);  // [9, 3, 4]
reg.chave = 1;  inserirElemLista(&lista, reg, 3);  // [9, 3, 4, 1]
reg.chave = 12; inserirElemLista(&lista, reg, 2);  // [9, 3, 12, 4, 1] ← inserção no meio!
exibirLista(&lista);
printf("Numero de elementos na lista: %i.\n", tamanho(&lista));
printf("Tamanho da lista (em bytes): %i.\n",  tamanhoEmBytes(&lista));

Seção C — Buscas

printf("Chave 4 encontrada na posicao: %i do arranjo A.\n", buscaSequencial(&lista, 4));
printf("Chave 4 encontrada na posicao: %i do arranjo A.\n", buscaSentinela(&lista, 4));

Ambas as funções encontram o mesmo elemento e retornam o mesmo índice (3). A lista nesse ponto é [9, 3, 12, 4, 1] — o elemento 4 está no índice 3.

Seção D — Exclusões

if (excluirElemLista(&lista, 4)) printf("Exclusao bem sucedida: 4.\n");
if (excluirElemLista(&lista, 8)) printf("Exclusao bem sucedida: 8.\n"); // 8 não existe!
if (excluirElemLista(&lista, 9)) printf("Exclusao bem sucedida: 9.\n");
exibirLista(&lista);
printf("Numero de elementos na lista: %i.\n", tamanho(&lista));
printf("Tamanho da lista (em bytes): %i.\n",  tamanhoEmBytes(&lista));

Seção E — Reinicialização

reinicializarLista(&lista);
exibirLista(&lista);
printf("Numero de elementos na lista: %i.\n", tamanho(&lista));
printf("Tamanho da lista (em bytes): %i.\n",  tamanhoEmBytes(&lista));
return 0;

A lista volta ao estado inicial. Os dados [3, 12, 1] ainda existem fisicamente no array, mas nroElem = 0 faz com que todas as funções os ignorem completamente.

Saída Completa do Programa

O comentário ao final do arquivo registra a saída real de uma execução: