Nos dias 30/03 e 01/04, substitui o prof. Thomas W. Rauber na disciplina de Estruturas de Dados para o período 2015/1. Neste post estou disponibilizando o material produzido para estas aulas.

30/03: Listas Lineares em Alocação Sequencial e Estática

Nesta aula foram apresentados os slides da Aula 09 do Thomas. Como exercício, pediu-se aos alunos que:

1 – Implementassem um TAD (Tipo Abstrato de Dados) para “Lista Estática” em C, com funções básicas do tipo (criar, inserir, remover, acessar, etc.);

2 – Implementassem algumas funções extras para este mesmo TAD:

• Dada uma lista, verificar se ela está ordenada (crescente ou decrescente);
• Dada uma lista, criar e retornar uma cópia da mesma;
• Dadas duas listas, L1 e L2, criar uma terceira lista que contenha os elementos de L1 e L2 intercalados em ordem crescente, assumindo que L1 e L2 estão também em ordem crescente.

As duas questões acima foram implementadas em um só TAD, que é dividido em 2 arquivos: [cci]ListaEstatica.h[/cci] e [cci]ListaEstatica.c[/cci]. Começamos com o código do arquivo cabeçalho (header):

[cc_c]
#ifndef __ListaEstatica_h
#define __ListaEstatica_h

/*** Declaração dos tipos. ***/
typedef struct TItemListaEstatica *ItemListaEstatica;
typedef struct TListaEstatica *ListaEstatica;

/*** Declaração das funções da lista. ***/

/* Cria uma lista estática, dada sua capacidade máxima. */
ListaEstatica criarListaEstatica(int);

/* Verifica se a lista está vazia. */
int vaziaListaEstatica(ListaEstatica);

/* Retorna o tamanho da lista estática. */
int tamanhoListaEstatica(ListaEstatica);

/* Insere um item no final da lista. */
void inserirNoFinalListaEstatica(ListaEstatica, ItemListaEstatica);

/* Insere um item na posição específica. */
void inserirNaPosicaoListaEstatica(ListaEstatica, ItemListaEstatica, int);

/* Remove um item de uma posição específica. */
ItemListaEstatica removerDaPosicaoListaEstatica(ListaEstatica, int);

/* Retorna o item de uma posição específica. */
ItemListaEstatica acessarItemListaEstatica(ListaEstatica, int);

/* Imprime a lista. */
void imprimirListaEstatica(ListaEstatica);

/* Destrói a lista. */
void destruirListaEstatica(ListaEstatica);

/*** Declaração das funções do item de lista. ***/

/* Cria um item de lista, dado seu valor. */
ItemListaEstatica criarItemListaEstatica(int);

/* Atribui um valor a um item de lista. */
void atribuirValorItemListaEstatica(ItemListaEstatica, int);

/* Retorna o valor de um item de lista. */
int obterValorItemListaEstatica(ItemListaEstatica);

/* Imprime um item de lista. */
void imprimirItemListaEstatica(ItemListaEstatica);

/* Destrói um item de lista. */
void destruirItemListaEstatica(ItemListaEstatica);

/*** Declaração das funções do exercício 2 passado em sala. ***/

/* Verifica se uma lista está ordenada. */
int ordenadaListaEstatica(ListaEstatica);

/* Cria uma cópia da lista. */
ListaEstatica criarCopiaListaEstatica(ListaEstatica);

/* Intercala duas listas estáticas, produzindo uma terceira lista. */
ListaEstatica intercalarListaEstatica(ListaEstatica, ListaEstatica);

#endif
[/cc_c]

O arquivo cabeçalho declara os tipos [cci_c]ItemListaEstatica[/cci_c] e [cci_c]ListaEstatica[/cci_c] como ponteiros para estruturas que serão definidas no arquivos de implementação. Desta forma, utilizamos tipos opacos e não permitimos que usuários do TAD manipulem diretamente sua estrutura interna. Esta característica dos TADs promove a abstração e o encapsulamento, permitindo construção de software em camadas e uma manutenção de menor custo em sistemas de grande porte.

Em seguida, o TAD declara as funções que um programa “cliente” pode usar para manipular estes dois tipos opacos. As funções são divididas em três partes:

• Funções básicas da lista: criar, verificar se está vazia, retornar o tamanho atual, inserir no final, inserir na posição, remover da posição, acessar item na posição, imprimir e destruir;
• Funções do item de lista: criar, atribuir valor, obter valor, imprimir e destruir;
• Funções do exercício 2: verificar se está ordenada, criar cópia e intercalar duas listas.

Por fim, é interessante observar que o arquivo possui uma condição de guarda ([cci_c]#ifndef __ListaEstatica_h[/cci_c]) para prevenir inclusão dupla caso esse TAD seja usado por outro TAD no futuro e que todas as funções possuem o nome do tipo como sufixo ([cci_c]vaziaListaEstatica()[/cci_c], [cci_c]tamanhoListaEstatica()[/cci_c], etc.) para que não haja colisão de nomes com outros TADs que venham a ser utilizados pelo mesmo programa.

Feito o cabeçalho, partimos para a implementação: [cci]ListaEstatica.c[/cci].

[cc_c]
#include
#include
#include “ListaEstatica.h”

/* Estrutura de um item da lista. */
struct TItemListaEstatica {
int valor;
};

/* Estrutura da lista. */
struct TListaEstatica {
ItemListaEstatica *vetor; // Vetor que armazena os itens.
int capacidade; // Capacidade máxima da lista.
int proximo; // Próxima posição vazia.
};

/* Cria uma lista estática, dada sua capacidade máxima. */
ListaEstatica criarListaEstatica(int capacidade) {
ListaEstatica lista = (ListaEstatica)malloc(sizeof(struct TListaEstatica));
lista->vetor = (ItemListaEstatica *)malloc(capacidade * sizeof(struct TItemListaEstatica *));
lista->capacidade = capacidade;
lista->proximo = 0;
return lista;
}

/* Verifica se a lista está vazia. */
int vaziaListaEstatica(ListaEstatica lista) {
return (lista->proximo == 0);
}

/* Retorna o tamanho da lista estática. */
int tamanhoListaEstatica(ListaEstatica lista) {
return lista->proximo;
}

/* Insere um item no final da lista. */
void inserirNoFinalListaEstatica(ListaEstatica lista, ItemListaEstatica item) {
// Verifica se a lista está cheia. Se estiver, não continua.
if (lista->proximo >= lista->capacidade) {
printf(“A lista está cheia!\n”);
return;
}

// Insere o elemento ao final da lista.
lista->vetor[lista->proximo] = item;
lista->proximo++;
}

/* Insere um item na posição específica. */
void inserirNaPosicaoListaEstatica(ListaEstatica lista, ItemListaEstatica item, int posicao) {
// Verifica se a lista está cheia. Se estiver, não continua.
if (lista->proximo >= lista->capacidade) {
printf(“A lista está cheia!\n”);
return;
}

// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->proximo)
printf(“Posição inválida: %d. A lista tem tamanho %d e capacidade %d.\n”, posicao, lista->proximo, lista->capacidade);

// Joga os itens posteriores à posição escolhida uma posição para a frente.
int idx;
for (idx = lista->proximo; idx > posicao; idx–) lista->vetor[idx] = lista->vetor[idx – 1];

// Aumenta o tamanho da lista.
lista->proximo++;

// Armazena o novo item na lista.
lista->vetor[posicao] = item;
}

/* Remove um item de uma posição específica. */
ItemListaEstatica removerDaPosicaoListaEstatica(ListaEstatica lista, int posicao) {
// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->proximo) {
printf(“Posição inválida: %d. A lista tem tamanho %d e capacidade %d.\n”, posicao, lista->proximo, lista->capacidade);
return NULL;
}

// Guarda o item da posição para poder retorná-lo.
ItemListaEstatica item = lista->vetor[posicao];

// Reduz o tamanho da lista.
lista->proximo–;

// Joga os itens posteriores à posição escolhida uma posição para trás.
int idx;
for (idx = posicao; idx < lista->proximo; idx++) lista->vetor[idx] = lista->vetor[idx + 1];
return item;
}

/* Retorna o item de uma posição específica. */
ItemListaEstatica acessarItemListaEstatica(ListaEstatica lista, int posicao) {
// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->proximo) {
printf(“Posição inválida: %d. A lista tem tamanho %d e capacidade %d.\n”, posicao, lista->proximo, lista->capacidade);
return NULL;
}

return lista->vetor[posicao];
}

/* Imprime a lista. */
void imprimirListaEstatica(ListaEstatica lista) {
int idx;
for (idx = 0; idx < lista->proximo; idx++) imprimirItemListaEstatica(lista->vetor[idx]);
}

/* Destrói a lista. */
void destruirListaEstatica(ListaEstatica lista) {
// Destrói os itens de lista.
int idx;
for (idx = 0; idx < lista->proximo; idx++) destruirItemListaEstatica(lista->vetor[idx]);

// Libera a memória ocupada pelo vetor e pela lista em si.
free(lista->vetor);
free(lista);
}

/* Cria um item de lista, dado seu valor. */
ItemListaEstatica criarItemListaEstatica(int valor) {
ItemListaEstatica item = (ItemListaEstatica)malloc(sizeof(struct TItemListaEstatica));
item->valor = valor;
return item;
}

ItemListaEstatica criarCopiaItemListaEstatica(ItemListaEstatica item) {
ItemListaEstatica copia = (ItemListaEstatica)malloc(sizeof(struct TItemListaEstatica));
copia->valor = item->valor;
return copia;
}

/* Atribui um valor a um item de lista. */
void atribuirValorItemListaEstatica(ItemListaEstatica item, int valor) {
item->valor = valor;
}

/* Retorna o valor de um item de lista. */
int obterValorItemListaEstatica(ItemListaEstatica item) {
return item->valor;
}

/* Imprime um item de lista. */
void imprimirItemListaEstatica(ItemListaEstatica item) {
printf(“%d\n”, item->valor);
}

/* Destrói um item de lista. */
void destruirItemListaEstatica(ItemListaEstatica item) {
free(item);
}

/* Verifica se uma lista está ordenada. */
int ordenadaListaEstatica(ListaEstatica lista) {
// Assume-se que a lista está ordenada.
int crescente = 1, decrescente = 1;

// Verifica se está ordenada.
int idx;
for (idx = 1; idx < lista->proximo; idx++) {
if (lista->vetor[idx] < lista->vetor[idx – 1]) crescente = 0;
if (lista->vetor[idx] > lista->vetor[idx – 1]) decrescente = 0;
}

// A lista está ordenada se crescente ou decrescente forem verdade.
return crescente | decrescente;
}

/* Cria uma cópia da lista. */
ListaEstatica criarCopiaListaEstatica(ListaEstatica lista) {
// Cria a lista cópia com a mesma capacidade da original.
ListaEstatica copia = (ListaEstatica)malloc(sizeof(struct TListaEstatica));
copia->vetor = (ItemListaEstatica *)malloc(lista->capacidade * sizeof(struct TItemListaEstatica *));
copia->capacidade = lista->capacidade;

// Copia o vetor.
int idx;
copia->proximo = lista->proximo;
for (idx = 0; idx < lista->proximo; idx++) copia->vetor[idx] = criarCopiaItemListaEstatica(lista->vetor[idx]);
return copia;
}

/* Intercala duas listas estáticas, produzindo uma terceira lista. */
ListaEstatica intercalarListaEstatica(ListaEstatica l1, ListaEstatica l2) {
// Cria uma lista com a capacidade das duas listas somadas.
int capacidade = l1->capacidade + l2->capacidade;
ListaEstatica lista = (ListaEstatica)malloc(sizeof(struct TListaEstatica));
lista->vetor = (ItemListaEstatica *)malloc(capacidade * sizeof(struct TItemListaEstatica *));
lista->capacidade = capacidade;

// Intercala os elementos das listas, assumindo que estão em ordem crescente.
int idx, idx1, idx2;
for (idx = 0, idx1 = 0, idx2 = 0; idx1 < l1->proximo && idx2 < l2->proximo; idx++) {
int valor1 = obterValorItemListaEstatica(l1->vetor[idx1]);
int valor2 = obterValorItemListaEstatica(l2->vetor[idx2]);
if (valor1 <= valor2) lista->vetor[idx] = criarCopiaItemListaEstatica(l1->vetor[idx1++]);
else lista->vetor[idx] = criarCopiaItemListaEstatica(l2->vetor[idx2++]);
}

// Um dos vetores vai acabar primeiro. Completa com o outro vetor.
while (idx1 < l1->proximo) lista->vetor[idx++] = criarCopiaItemListaEstatica(l1->vetor[idx1++]);
while (idx2 < l2->proximo) lista->vetor[idx++] = criarCopiaItemListaEstatica(l2->vetor[idx2++]);

// Indica a próxima posição da lista resultante.
lista->proximo = idx;
return lista;
}
[/cc_c]

A implementação define as estruturas de dados e as funções declaradas no arquivo cabeçalho. A estrutura do item da lista é bem simples, contém apenas um valor inteiro, porém poderia ser substituída por estruturas mais complexas (com várias variáveis internas) na medida da necessidade. Se você precisasse, por exemplo, de uma lista de alunos e suas notas, poderia criar um tipo item de lista com uma string ([cci_c]char *[/cci_c]) armazenando o nome do aluno e alguns floats representando as notas do aluno no semestre, por exemplo. Neste caso, outras funções parecidas com [cci_c]obterValorItemListaEstatica()[/cci_c] deveriam existir para poder manipular a estrutura interna do tipo item de lista. Caso esse tipo acabe ficando mais complexo, talvez seja interessante representá-lo como um TAD separado e a lista poderia ser genérica declarando [cci_c]ItemListaEstatica[/cci_c] como um ponteiro para void.

A estrutura da lista consiste em um ponteiro para [cci_c]ItemListaEstatica[/cci_c] para que um vetor de elementos deste tipo possa ser alocado dinamicamente na criação da lista. Como o tipo [cci_c]ItemListaEstatica[/cci_c] foi definido no arquivo cabeçalho como ponteiro para a estrutura [cci_c]struct TItemListaEstatica[/cci_c], na prática esta variável [cci_c]vetor[/cci_c] é um vetor de ponteiros para um tipo opaco, que tem suas operações definidas também neste TAD. Além do vetor, a estrutura da lista registra também a capacidade máxima da lista (tamanho do vetor) e a posição do próximo item da lista (a próxima posição vazia no vetor).

Cada função está comentada no código acima, então dispensa explicações aqui no texto. Basta que o aluno analise o código e os comentários para entender como cada função faz seu papel. É importante apenas considerar que ao se trabalhar sempre com ponteiros, é preciso ficar atento às alocações ([cci_c]malloc()[/cci_c]) e desalocações ([cci_c]free()[/cci_c]) de memória e às cópias dos elementos do vetor que devem sempre passar por uma nova alocação de memória, do contrário se estaria copiando um ponteiro e duas listas poderiam estar apontando para o mesmo item de lista na memória. Isso pode causar uma série de problemas.

Estando com o TAD pronto, é interessante criar um programinha que faça alguns testes com ele. Segue abaixo o arquivo [cci]prog.c[/cci]:

[cc_c]
#include
#include “ListaEstatica.h”

int main() {
// Cria uma lista com capacidade 10.
ListaEstatica lista = criarListaEstatica(10);

// Insere 4 itens ao final da lista.
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(10));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(20));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(40));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(50));

// Tenta obter um item de uma posição inválida.
ItemListaEstatica item = acessarItemListaEstatica(lista, 9);
printf(“\n”);

// Insere mais 4 itens ao final da lista.
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(70));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(80));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(90));
inserirNoFinalListaEstatica(lista, criarItemListaEstatica(100));

// Verifica se a lista está vazia.
if (vaziaListaEstatica(lista)) printf(“A lista está vazia.\n\n”);
else printf(“A lista não está vazia.\n\n”);

// Insere outros 2 itens no meio da lista.
inserirNaPosicaoListaEstatica(lista, criarItemListaEstatica(30), 2);
inserirNaPosicaoListaEstatica(lista, criarItemListaEstatica(60), 5);

// Tenta adicionar mais um elemento, mas a lista está cheia!
item = criarItemListaEstatica(999);
inserirNoFinalListaEstatica(lista, item);
destruirItemListaEstatica(item);

// Remove itens da lista.
item = removerDaPosicaoListaEstatica(lista, 4);
destruirItemListaEstatica(item);
item = removerDaPosicaoListaEstatica(lista, 6);
destruirItemListaEstatica(item);

// Imprime a lista.
printf(“\nLista depois das operações:\n”);
imprimirListaEstatica(lista);

// Cria uma cópia da lista, apaga a original.
ListaEstatica l1 = criarCopiaListaEstatica(lista);
destruirListaEstatica(lista);
printf(“\nL1 (cópia da anterior):\n”);
imprimirListaEstatica(l1);

// Verifica se L1 está ordenada.
if (ordenadaListaEstatica(l1)) printf(“\nL1 está ordenada.\n”);
else printf(“\nL1 não está ordenada.\n”);

// Cria uma lista L2.
ListaEstatica l2 = criarListaEstatica(5);
inserirNoFinalListaEstatica(l2, criarItemListaEstatica(50));
inserirNoFinalListaEstatica(l2, criarItemListaEstatica(80));
inserirNoFinalListaEstatica(l2, criarItemListaEstatica(110));
printf(“\nL2:\n”);
imprimirListaEstatica(l2);

// Intercala L1 com L2.
lista = intercalarListaEstatica(l1, l2);
printf(“\nL1 intercalada com L2:\n”);
imprimirListaEstatica(lista);

// Destrói as listas.
destruirListaEstatica(l1);
destruirListaEstatica(l2);
destruirListaEstatica(lista);
}
[/cc_c]

O programa de testes também é auto-explicativo dados os comentários ao longo do código. Para compilar o TAD, conforme visto na aula sobre este assunto, executamos o comando:

[cc]gcc -c ListaEstatica.c[/cc]

O comando acima produz o arquivo objeto [cci]ListaEstatica.o[/cci], com o código do TAD compilado porém ainda sem efetuar a ligação, que é feita só quando da compilação do executável. Esta compilação final para o programa de testes pode ser feita com:

[cc]gcc -o prog prog.c ListaEstatica.o[/cc]

O que cria (no Linux e no Mac) o arquivo [cci]prog[/cci], que pode ser executado com [cci]./prog[/cci]. O processo de compilação acima pode ser automatizado com o programa GNU make. Não sei se os alunos já aprenderam a fazer Makefile, mas ele é bem simples para esse exemplo da lista estática. Crie um arquivo com o nome [cci]Makefile[/cci] no mesmo diretório dos outros arquivos e com o conteúdo seguinte:

[cc]
all: prog

prog: prog.c ListaEstatica.o
gcc -o prog prog.c ListaEstatica.o

ListaEstatica.o: ListaEstatica.c ListaEstatica.h
gcc -c ListaEstatica.c

clean:
@rm -rf *.o prog
[/cc]

Com esse arquivo no diretório, você pode compilar tudo de uma vez apenas com o comando [cci]make[/cci] e limpar o diretório (excluindo o executável e arquivos objetos) com o comando [cci]make clean[/cci]. O comando [cci]make[/cci] efetua compilação sob demanda, recompilando apenas arquivos que são necessários. Ou seja, caso ele detecte que não houve mudanças num determinado código-fonte, ele não recompila aquele código.

Segue abaixo o resultado da compilação e da execução do programa de testes em meu computador ([cci]$[/cci] representa o prompt de comando no terminal):

[cc]
$ make
gcc -c ListaEstatica.c
gcc -o prog prog.c ListaEstatica.o

$ ./prog
Posição inválida: 9. A lista tem tamanho 4 e capacidade 10.

A lista não está vazia.

A lista está cheia!

Lista depois das operações:
10
20
30
40
60
70
90
100

L1 (cópia da anterior):
10
20
30
40
60
70
90
100

L1 está ordenada.

L2:
50
80
110

L1 intercalada com L2:
10
20
30
40
50
60
70
80
90
100
110
[/cc]

 

01/04: Listas com Alocação Não Sequencial e Dinâmica

Nesta aula foram apresentados os slides da Aula 10 e Aula 10_2 do Thomas. Pediu-se aos alunos que implementassem o mesmo exercício da aula anterior (lista estática), porém utilizando lista dinâmica.

Novamente, tanto as funções básicas quanto as funções extras (verificar se está ordenada, criar cópia, intercalar) foram implementadas em um só TAD, dividido nos arquivos [cci]ListaDinamica.h[/cci] e [cci]ListaDinamica.c[/cci]. Começamos com o código do arquivo cabeçalho (header):

[cc_c]
#ifndef __ListaDinamica_h
#define __ListaDinamica_h

/*** Declaração dos tipos. ***/
typedef void *ItemListaDinamica; // Lista genérica!
typedef struct TListaDinamica *ListaDinamica;

/*** Declaração das funções da lista. ***/

/* Cria uma lista dinâmica. */
ListaDinamica criarListaDinamica();

/* Verifica se a lista está vazia. */
int vaziaListaDinamica(ListaDinamica);

/* Retorna o tamanho da lista dinâmica. */
int tamanhoListaDinamica(ListaDinamica);

/* Insere um item no final da lista. */
void inserirNoFinalListaDinamica(ListaDinamica, ItemListaDinamica);

/* Insere um item na posição específica. */
void inserirNaPosicaoListaDinamica(ListaDinamica, ItemListaDinamica, int);

/* Remove um item de uma posição específica. */
ItemListaDinamica removerDaPosicaoListaDinamica(ListaDinamica, int);

/* Retorna o item de uma posição específica. */
ItemListaDinamica acessarItemListaDinamica(ListaDinamica, int);

/* Imprime a lista, dada uma função impressora. */
void imprimirListaDinamica(ListaDinamica, void (*)(ItemListaDinamica));

/* Destrói a lista. */
void destruirListaDinamica(ListaDinamica);

/*** Declaração das funções do exercício 2 passado em sala. ***/

/* Verifica se uma lista está ordenada, dada uma função de comparação. */
int ordenadaListaDinamica(ListaDinamica, int (*)(ItemListaDinamica, ItemListaDinamica));

/* Cria uma cópia da lista. */
ListaDinamica criarCopiaListaDinamica(ListaDinamica);

/* Intercala duas listas dinâmicas, produzindo uma terceira lista, dada uma função de comparação. */
ListaDinamica intercalarListaDinamica(ListaDinamica, ListaDinamica, int (*)(ItemListaDinamica, ItemListaDinamica));

#endif
[/cc_c]

Pode-se notar a semelhança do arquivo de cabeçalho da lista dinâmica com aquele da lista estática apresentada na aula anterior. No entanto, aproveitamos esse novo exercício para demonstrar a criação de uma estrutura de dados genérica. Enquanto na lista estática declaramos o tipo do elemento da lista como [cci_c]typedef struct TItemListaEstatica *ItemListaEstatica;[/cci_c], agora este tipo foi declarado como [cci_c]typedef void *ItemListaDinamica;[/cci_c], permitindo que qualquer ponteiro (ponteiro para inteiro, para float, para uma estrutura que representa um aluno, um livro, um produto de uma loja, etc.) possa ser colocado na lista.

Por um lado, essa alteração simplifica o TAD pois todas as funções que operavam sobre o elemento da lista ([cci_c]criarItemListaEstatica()[/cci_c], [cci_c]atribuirValorItemListaEstatica[/cci_c], etc.) não pertencem mais ao TAD, ficando sob responsabilidade do código que usa a lista dinâmica. Por outro lado, o uso de [cci_c]void *[/cci_c] deixa algumas das funções do TAD mais complexas, a saber:

• [cci_c]void imprimirListaDinamica(ListaDinamica, void (*)(ItemListaDinamica))[/cci_c]: como o TAD é genérico, não sabemos que informação exatamente será colocada dentro da lista. Desta maneira, não temos como imprimir os elementos da lista: se forem, por exemplo, inteiros, se imprime usando [cci_c]printf()[/cci_c] e o código [cci_c]%d[/cci_c], mas se for um número real se deve usar [cci_c]%f[/cci_c] e se for uma estrutura complexa não tem nem como saber! A solução é exigir que seja passado como parâmetro uma função que realiza a impressão. O 2º parâmetro [cci_c]void (*)(ItemListaDinamica)[/cci_c] representa um ponteiro para uma função que recebe um argumento do tipo [cci_c]ItemListaDinamica[/cci_c] e retorna [cci_c]void[/cci_c]. Na hora de imprimir o item, essa função será chamada e cabe ao usuário do TAD passar uma função apropriada (veremos uma no programa principal, mais adiante);
   
• [cci_c]int ordenadaListaDinamica(ListaDinamica, int (*)(ItemListaDinamica, ItemListaDinamica))[/cci_c]: aqui ocorre algo similar, porém com uma função que recebe dois argumentos do tipo [cci_c]ItemListaDinamica[/cci_c] e retorna um inteiro. Essa deve ser uma função de comparação com funcionamento similar à função strcmp: retornar um número negativo se o primeiro argumento for menor que o segundo, um número positivo se for maior e zero se forem iguais. Tendo uma função de comparação, é possível verificar se os elementos da lista — quaisquer que sejam eles — estão ordenados. Novamente, cabe ao usuário do TAD passar uma função apropriada;
   
• [cci_c]ListaDinamica intercalarListaDinamica(ListaDinamica, ListaDinamica, int (*)(ItemListaDinamica, ItemListaDinamica))[/cci_c]: a situação aqui é idêntica à da função anterior, na qual o terceiro parâmetro é uma função de comparação. Ela é usada para verificar de qual lista obter o próximo elemento de modo a intercalar duas listas ordenadas e obter como resultado uma lista também ordenada.

Entendidas as novidades descritas acima, vejamos agora o arquivo de implementação:

[cc_c]
#include
#include
#include “ListaDinamica.h”

/* Estrutura de um nó da lista. */
typedef struct TNoListaDinamica {
ItemListaDinamica item;
struct TNoListaDinamica* anterior;
struct TNoListaDinamica* posterior;
} *NoListaDinamica;

/* Estrutura da lista. */
struct TListaDinamica {
NoListaDinamica primeiro;
NoListaDinamica ultimo;
int tamanho;
};

/* Cria uma lista dinâmica. */
ListaDinamica criarListaDinamica() {
ListaDinamica lista = (ListaDinamica)malloc(sizeof(struct TListaDinamica));
lista->primeiro = lista->ultimo = NULL;
lista->tamanho = 0;
return lista;
}

/* Verifica se a lista está vazia. */
int vaziaListaDinamica(ListaDinamica lista) {
return (lista->tamanho == 0);
}

/* Retorna o tamanho da lista dinâmica. */
int tamanhoListaDinamica(ListaDinamica lista) {
return lista->tamanho;
}

/* Insere um item no final da lista. */
void inserirNoFinalListaDinamica(ListaDinamica lista, ItemListaDinamica item) {
// Cria um novo nó para inserir o item na lista.
NoListaDinamica no = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica));
no->item = item;
no->posterior = NULL;

// Verifica se a lista não está vazia, integrando o nó à lista.
if (lista->ultimo) {
no->anterior = lista->ultimo;
lista->ultimo = lista->ultimo->posterior = no;
}

// Se a lista está vazia, coloca o nó como primeiro e último elemento.
else {
lista->primeiro = lista->ultimo = no;
no->anterior = NULL;
}

// Aumenta o tamanho da lista.
lista->tamanho++;
}

/* Insere um item na posição específica. */
void inserirNaPosicaoListaDinamica(ListaDinamica lista, ItemListaDinamica item, int posicao) {
// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->tamanho) {
printf(“Posição inválida: %d. A lista tem tamanho %d.\n”, posicao, lista->tamanho);
return;
}

// Se a posição escolhida é igual ao tamanho da lista, o elemento será adicionado no final (já implementado acima).
if (posicao == lista->tamanho) {
inserirNoFinalListaDinamica(lista, item);
return;
}

// Cria um novo nó para inserir o item na lista.
NoListaDinamica no = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica));
no->item = item;

// Se a posição escolhida é o início da lista, trata essa situação separadamente.
if (posicao == 0) {
no->anterior = NULL;
no->posterior = lista->primeiro;
lista->primeiro = no;
return;
}

// Encontra o nó anterior ao da posição escolhida.
int idx;
NoListaDinamica noAnterior = lista->primeiro;
for (idx = 1; idx < posicao; idx++) noAnterior = noAnterior->posterior;

// Insere o elemento entre o nó anterior e o nó que se encontra atualmente na posição escolhida.
no->anterior = noAnterior;
no->posterior = noAnterior->posterior;
no->anterior->posterior = no;
no->posterior->anterior = no;

// Aumenta o tamanho da lista.
lista->tamanho++;
}

/* Remove um item de uma posição específica. */
ItemListaDinamica removerDaPosicaoListaDinamica(ListaDinamica lista, int posicao) {
// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->tamanho – 1) {
printf(“Posição inválida: %d. A lista tem tamanho %d.\n”, posicao, lista->tamanho);
return NULL;
}

// Encontra o nó da posição escolhida.
int idx;
NoListaDinamica no = lista->primeiro;
for (idx = 0; idx < posicao; idx++) no = no->posterior;

// Se há um nó anterior, faz ele “saltar” este nó.
if (no->anterior) no->anterior->posterior = no->posterior;

// Se não há um nó anterior, então era o primeiro. Atualiza o primeiro da lista.
else lista->primeiro = no->posterior;

// Se há um nó posterior, faz o mesmo na direção contrária.
if (no->posterior) no->posterior->anterior = no->anterior;

// Se não há um nó posterior, então era o último. Atualiza o último da lista.
else lista->ultimo = no->anterior;

// Reduz o tamanho da lista.
lista->tamanho–;

// Apaga o nó e retorna o item que havia dentro dele.
ItemListaDinamica item = no->item;
free(no);
return item;
}

/* Retorna o item de uma posição específica. */
ItemListaDinamica acessarItemListaDinamica(ListaDinamica lista, int posicao) {
// Verifica se a posição escolhida é fora dos limites da lista.
if (posicao < 0 || posicao > lista->tamanho – 1) {
printf(“Posição inválida: %d. A lista tem tamanho %d.\n”, posicao, lista->tamanho);
return NULL;
}

// Encontra o nó da posição escolhida e retorna seu item.
int idx;
NoListaDinamica no = lista->primeiro;
for (idx = 0; idx < posicao; idx++) no = no->posterior;
return no->item;
}

/* Imprime a lista. */
void imprimirListaDinamica(ListaDinamica lista, void (*funcaoImpressora)(ItemListaDinamica)) {
NoListaDinamica no = lista->primeiro;
while (no) {
funcaoImpressora(no->item);
no = no->posterior;
}
}

/* Destrói a lista. */
void destruirListaDinamica(ListaDinamica lista) {
// Destrói os nós da lista.
NoListaDinamica no = lista->primeiro;
while (no) {
NoListaDinamica proximo = no->posterior;
free(no);
no = proximo;
}

// Libera a memória ocupada pela lista em si.
free(lista);
}

/* Verifica se uma lista está ordenada, dada uma função de comparação. */
int ordenadaListaDinamica(ListaDinamica lista, int (*cmp)(ItemListaDinamica, ItemListaDinamica)) {
// Assume-se que a lista está ordenada.
int crescente = 1, decrescente = 1;

// Para a iteração, precisamos sempre de pares de nós.
NoListaDinamica no = lista->primeiro;
NoListaDinamica prox = NULL;
if (no) prox = no->posterior;

// Verifica se está ordenada.
while (no && prox) {
if (cmp(no->item, prox->item) > 0) crescente = 0;
if (cmp(no->item, prox->item) < 0) decrescente = 0; no = no->posterior;
prox = prox->posterior;
}

// A lista está ordenada se crescente ou decrescente forem verdade.
return crescente | decrescente;
}

/* Cria uma cópia da lista. */
ListaDinamica criarCopiaListaDinamica(ListaDinamica lista) {
// Cria a lista cópia com o mesmo tamanho da original.
ListaDinamica copia = (ListaDinamica)malloc(sizeof(struct TListaDinamica));
copia->tamanho = lista->tamanho;

// Copia o primeiro nó, se houver.
NoListaDinamica noCopia;
if (lista->primeiro) {
noCopia = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica));
noCopia->item = lista->primeiro->item;
noCopia->anterior = NULL;
copia->primeiro = noCopia;

// Copia os demais nós da lista.
NoListaDinamica no = lista->primeiro->posterior;
while (no) {
NoListaDinamica novoNo = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica));
novoNo->item = no->item;
noCopia->posterior = novoNo;
novoNo->anterior = noCopia;

// Passa para o próximo.
noCopia = novoNo;
no = no->posterior;
}

// Finaliza com o último.
copia->ultimo = noCopia;
noCopia->posterior = NULL;
}

// Se não houver primeiro nó, retorna uma cópia de lista vazia.
else copia->primeiro = copia->ultimo = NULL;

return copia;
}

/* Intercala duas listas dinâmicas, produzindo uma terceira lista. */
ListaDinamica intercalarListaDinamica(ListaDinamica l1, ListaDinamica l2, int (*cmp)(ItemListaDinamica, ItemListaDinamica)) {
// Cria uma lista com o tamanho das duas listas somadas.
int tamanho = l1->tamanho + l2->tamanho;
ListaDinamica lista = (ListaDinamica)malloc(sizeof(struct TListaDinamica));
lista->tamanho = tamanho;

// Se o tamanho somado é zero, retorna uma lista vazia.
if (tamanho == 0) {
lista->primeiro = lista->ultimo = NULL;
return lista;
}

// Cria referências a nós para poder navegar nas três listas.
NoListaDinamica no1 = l1->primeiro;
NoListaDinamica no2 = l2->primeiro;
NoListaDinamica no = NULL;

// Cria os nós da terceira lista, por enquanto sem itens.
NoListaDinamica novoNo = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica));
lista->primeiro = no = novoNo;
int idx;
for (idx = 1; idx < tamanho; idx++) { novoNo = (NoListaDinamica)malloc(sizeof(struct TNoListaDinamica)); no->posterior = novoNo;
novoNo->anterior = no;

// Passa para o próximo.
no = novoNo;
}
lista->ultimo = no;
no->posterior = NULL;

// Intercala os elementos das listas, assumindo que estão em ordem crescente.
no = lista->primeiro;
while (no1 && no2) {
if (cmp(no1->item, no2->item) <= 0) { no->item = no1->item;
no1 = no1->posterior;
}
else {
no->item = no2->item;
no2 = no2->posterior;
}
no = no->posterior;
}

// Uma das listas vai acabar primeiro. Completa com a outra lista.
while (no1) {
no->item = no1->item;
no1 = no1->posterior;
no = no->posterior;
}
while (no2) {
no->item = no2->item;
no2 = no2->posterior;
no = no->posterior;
}

return lista;
}
[/cc_c]

Cada função está comentada no código acima, então dispensa explicações aqui no texto. Basta que o aluno analise o código e os comentários para entender como cada função faz seu papel. É importante observar, no entanto, que o uso de estruturas encadeadas com ponteiros como a lista dinâmica exige um cuidado muito grande para não se perder nas diversas operações que envolvem alocação/desalocação de memória e cópias de ponteiros de um lado para o outro. Note, por exemplo, como a função [cci_c]intercalarListaDinamica()[/cci_c] ficou mais extensa e complexa do que sua equivalente para a lista estática.

Com o TAD pronto, vamos ao programinha de testes, [cci]prog.c[/cci]:

[cc_c]
#include
#include “ListaDinamica.h”

// Elementos a serem usados na lista.
int elems[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110};

/* Função impressora para ponteiros para inteiros. */
void imprimeInteiro(ItemListaDinamica item) {
// Converte pra ponteiro pra inteiro e imprime.
int* p = (int*)item;
printf(“%d\n”, *p);
}

/* Função de comparação para ponteiros para inteiros. */
int comparaInteiros(ItemListaDinamica a, ItemListaDinamica b) {
// Converte para ponteiro para inteiro e retorna a diferença.
return *(int*)a – *(int*)b;
}

int main() {
// Cria uma lista.
ListaDinamica lista = criarListaDinamica();

// Insere 4 itens ao final da lista.
inserirNoFinalListaDinamica(lista, &elems[1]);
inserirNoFinalListaDinamica(lista, &elems[2]);
inserirNoFinalListaDinamica(lista, &elems[4]);
inserirNoFinalListaDinamica(lista, &elems[5]);

// Imprime a lista.
printf(“\nLista [10, 20, 40, 50]:\n”);
imprimirListaDinamica(lista, imprimeInteiro);

// Tenta obter um item de uma posição inválida.
ItemListaDinamica item = acessarItemListaDinamica(lista, 9);
printf(“\n”);

// Insere mais 4 itens ao final da lista.
inserirNoFinalListaDinamica(lista, &elems[7]);
inserirNoFinalListaDinamica(lista, &elems[8]);
inserirNoFinalListaDinamica(lista, &elems[9]);
inserirNoFinalListaDinamica(lista, &elems[10]);

// Imprime a lista.
printf(“\nLista [10, 20, 40, 50, 70, 80, 90, 100]:\n”);
imprimirListaDinamica(lista, imprimeInteiro);

// Verifica se a lista está vazia.
if (vaziaListaDinamica(lista)) printf(“A lista está vazia.\n\n”);
else printf(“A lista não está vazia.\n\n”);

// Insere outros 2 itens no meio da lista.
inserirNaPosicaoListaDinamica(lista, &elems[3], 2);
inserirNaPosicaoListaDinamica(lista, &elems[6], 5);

// Imprime a lista.
printf(“\nLista [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]:\n”);
imprimirListaDinamica(lista, imprimeInteiro);

// Remove itens da lista.
item = removerDaPosicaoListaDinamica(lista, 4);
item = removerDaPosicaoListaDinamica(lista, 6);

// Imprime a lista.
printf(“\nLista [10, 20, 30, 40, 60, 70, 90, 100]:\n”);
imprimirListaDinamica(lista, imprimeInteiro);

// Cria uma cópia da lista, apaga a original.
ListaDinamica l1 = criarCopiaListaDinamica(lista);
destruirListaDinamica(lista);
printf(“\nL1 (cópia da anterior):\n”);
imprimirListaDinamica(l1, imprimeInteiro);

// Verifica se L1 está ordenada.
if (ordenadaListaDinamica(l1, comparaInteiros)) printf(“\nL1 está ordenada.\n”);
else printf(“\nL1 não está ordenada.\n”);

// Cria uma lista L2.
ListaDinamica l2 = criarListaDinamica();
inserirNoFinalListaDinamica(l2, &elems[5]);
inserirNoFinalListaDinamica(l2, &elems[8]);
inserirNoFinalListaDinamica(l2, &elems[11]);
printf(“\nL2 [50, 80, 110]:\n”);
imprimirListaDinamica(l2, imprimeInteiro);

// Intercala L1 com L2.
lista = intercalarListaDinamica(l1, l2, comparaInteiros);
printf(“\nL1 intercalada com L2:\n”);
imprimirListaDinamica(lista, imprimeInteiro);

// Destrói as listas.
destruirListaDinamica(l1);
destruirListaDinamica(l2);
destruirListaDinamica(lista);
}[/cc_c]

O programa de testes também é auto-explicativo dados os comentários ao longo do código. Note, no entanto, que sendo esta lista genérica, são observadas as seguintes diferenças com relação ao programa de testes da lista estática:

• Os elementos (números inteiros) que são colocados na lista não são mais criados a partir de uma função do TAD como anteriormente ([cci_c]criarItemListaEstatica()[/cci_c]). Foi declarada uma variável global [cci_c]elems[/cci_c] do tipo vetor de inteiros e para adicionar um elemento na lista bastou passar um ponteiro para um desses números, como, por exemplo, em [cci_c]inserirNoFinalListaDinamica(lista, &elems[1])[/cci_c], que adiciona o número [cci_c]10[/cci_c] à lista. Como eles não são criados por função de criação de TAD, também não precisam ser destruídos como anteriormente ([cci_c]destruirItemListaEstatica()[/cci_c]);
   
• Uma função chamada [cci_c]imprimeInteiro()[/cci_c] foi criada para ser passada como parâmetro nas chamadas de [cci_c]imprimirListaDinamica()[/cci_c]. Ela é a função impressora para o tipo de elemento que usamos nesse programa de testes no lugar de [cci_c]void *[/cci_c], ou seja, ponteiros para inteiros. A função recebe um argumento do tipo [cci_c]ItemListaDinamica[/cci_c], que nada mais é do que um ponteiro genérico, e converte-o para ponteiro para inteiro, imprimindo o conteúdo apontado pelo ponteiro em seguida;
   
• Outra função faz as vezes de função comparadora: [cci_c]comparaInteiros()[/cci_c], funcionando de forma similar à função impressora (convertendo os ponteiros genéricos em ponteiros para inteiros e usando o valor apontado por eles para a comparação). A função simplesmente faz uma subtração dos valores dos argumentos, de modo que se o primeiro for maior que o segundo o resultado será positivo, se for menor será negativo e se for igual será zero, como esperado de uma função desse tipo. [cci_c]comparaInteiros()[/cci_c] é depois passada como parâmetro nas chamadas de [cci_c]ordenadaListaDinamica()[/cci_c] e [cci_c]intercalarListaDinamica()[/cci_c].
   

Por fim, segue o Makefile que permite compilar facilmente o TAD e o program de testes:

[cc]
all: prog

prog: prog.c ListaDinamica.o
gcc -o prog prog.c ListaDinamica.o

ListaDinamica.o: ListaDinamica.c ListaDinamica.h
gcc -c ListaDinamica.c

clean:
@rm -rf *.o prog
[/cc]

E o resultado de uma execução do programa:

[cc]
Lista [10, 20, 40, 50]:
10
20
40
50
Posição inválida: 9. A lista tem tamanho 4.

Lista [10, 20, 40, 50, 70, 80, 90, 100]:
10
20
40
50
70
80
90
100
A lista não está vazia.

Lista [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]:
10
20
30
40
50
60
70
80
90
100

Lista [10, 20, 30, 40, 60, 70, 90, 100]:
10
20
30
40
60
70
90
100

L1 (cópia da anterior):
10
20
30
40
60
70
90
100

L1 está ordenada.

L2 [50, 80, 110]:
50
80
110

L1 intercalada com L2:
10
20
30
40
50
60
70
80
90
100
110
[/cc]