O TAD Lista

Este trabalho visa implementar um Tipo Abstrato de dado (TAD) “lista de inteiros” usando listas encadeadas.

Você deve implementar um TAD “lista de números inteiros” usando lista encadeada dupla não-circular. Essa lista pode ser vista de forma abstrata como se fosse um vetor de N inteiros com posições de 0 a N-1.

As seguintes operações devem ser suportadas:

• cria (lista): cria uma nova lista
• destrói (lista): esvazia e destrói a lista
• insere (lista, elemento, posição): insere um novo elemento na posição indicada
• elemento = retira (lista, posição): retira o elemento da posição indicada
• elemento = consulta (lista, posição): informa o valor do elemento na posição indicada, sem retirá-lo
• posição = procura (lista, elemento): informa a posição da 1ª ocorrência do elemento informado
• vazia (lista) : informa se a lista está vazia
• tamanho (lista) : informa o número atual de elementos na lista

Os arquivos necessários para desenvolver este trabalho estão neste arquivo. Eles são:

• liblista.h: arquivo de cabeçalho com os protótipos das funções (não deve ser alterado).
• liblista.c: arquivo que implementa as operações sobre as listas (“esqueleto” a completar).
• tp4.c: código que usa a biblioteca (“esqueleto” a completar).
• makefile: arquivo do utilitário “make” para compilar seu código.

O programa de teste em tp4.c deve executar o seguinte algoritmo:

cria uma lista L vazia
imprime L
insere no final de L os valores 10, 11, 12, 13 e 14, nessa ordem
imprime L
insere no início de L o valor 32
insere no início de L o valor 64
imprime L
insere no meio de L o valor 103
insere no meio de L o valor 47
imprime L
imprime o conteúdo das posições início, 5, última e 100 de L
imprime as posições dos valores 5, 10 e 14 em L
retira de L os valores 12, 103 e 79
imprime L
enquanto L não estiver vazia
  retira o primeiro valor de L e o imprime
  retira o último valor de L e o imprime
  imprime L
fim enquanto
destrói L
encerra

A saída correspondente na tela deve ser:

LISTA: [ ] (0 elementos)
LISTA: [ 10 11 12 13 14 ] (5 elementos)
LISTA: [ 64 32 10 11 12 13 14 ] (7 elementos)
LISTA: [ 64 32 10 103 47 11 12 13 14 ] (9 elementos)

VALOR NA POSICAO 0: 64
VALOR NA POSICAO 5: 11
VALOR NA POSICAO -1: 14
VALOR NA POSICAO 100 NAO ENCONTRADO

POSICAO DO VALOR 5: NAO ENCONTRADO
POSICAO DO VALOR 10: 2
POSICAO DO VALOR 14: 8

RETIRA VALOR 12 DA POSICAO 6
RETIRA VALOR 103 DA POSICAO 3
RETIRA VALOR 79 NAO ENCONTRADO
LISTA: [ 64 32 10 47 11 13 14 ] (7 elementos)

RETIRADO PRIMEIRO: 64
RETIRADO ULTIMO: 14
LISTA: [ 32 10 47 11 13 ] (5 elementos)
RETIRADO PRIMEIRO: 32
RETIRADO ULTIMO: 13
LISTA: [ 10 47 11 ] (3 elementos)
RETIRADO PRIMEIRO: 10
RETIRADO ULTIMO: 11
LISTA: [ 47 ] (1 elementos)
RETIRADO PRIMEIRO: 47
RETIRADO ULTIMO: NAO ENCONTRADO
LISTA: [ ] (0 elementos)

Entregue um único arquivo tp4.tgz que contenha por sua vez os seguintes arquivos:

• liblista.h: o mesmo arquivo fornecido, não o modifique
• liblista.c: sua implementação das funções definidas em liblista.h
• tp4.c: implementa a função main que usa a lista
• makefile

Critérios de avaliação:

• Funcionar corretamente
• Não ter problemas de memória (testar com Valgrind)
• Respeitar o conceito de TAD
• Usar funções para evitar repetição de blocos de código
• Respeitar estilo (endentação, espaçamento, nomes de variáveis)
• Usar comentários (nem demais, nem de menos)
• … (outros que se fizerem necessários)