O TAD Lista
Este trabalho visa implementar um Tipo Abstrato de dado (TAD) “lista de inteiros” usando listas encadeadas.
Atividade
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 listadestrói (lista)
: esvazia e destrói a listainsere (lista, elemento, posição)
: insere um novo elemento na posição indicadaelemento = retira (lista, posição)
: retira o elemento da posição indicadaelemento = consulta (lista, posição)
: informa o valor do elemento na posição indicada, sem retirá-loposição = procura (lista, elemento)
: informa a posição da 1ª ocorrência do elemento informadovazia (lista)
: informa se a lista está vaziatamanho (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.
Exemplo de funcionamento
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)
Entregáveis
Entregue um único arquivo tp4.tgz
que contenha por sua vez os seguintes arquivos:
liblista.h
: o mesmo arquivo fornecido, não o modifiqueliblista.c
: sua implementação das funções definidas emliblista.h
tp4.c
: implementa a funçãomain
que usa a listamakefile
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)