AULA-04-ESTRUTURA-DE-DADOS-1

Text Material Preview

ESTRUTURA DE DADOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prezado (a) aluno (a), 
É comum em nosso dia a dia, elaborarmos listas relacionando alguns 
itens, seja no intuito de auxiliar nas atividades diárias ou quando vamos realizar 
compras em um supermercado. Na área de estruturas de dados, as listas 
auxiliam na automatização de processos do mundo real, conforme a 
necessidade ou intuito de cada situação, sem deixar de atender as 
características que determinam os requisitos de sua manipulação. 
Esta aula é voltada ao ensino do Tipo Abstrato de Dados, popularmente 
conhecido como TAD, neste caso, voltado ao tipo lista, além disso, você vai 
aprender a descrever e a construir listas estáticas. 
 
Bons estudos! 
 
 
 
 
 
 
 
 
 
 
 
 
AULA 04 - TIPO DE 
LISTAS 
 
 
 
4 TIPO ABSTRATO DE DADOS DO TIPO LISTA 
Um Tipo Abstrato de Dado (TAD) é uma construção que permite definir um novo 
tipo de dado baseado nos tipos primitivos oferecidos pelas linguagens de 
programação, como int, float, char, entre outros. Com um TAD, é possível criar 
estruturas que agregam elementos de diferentes tipos e tratá-los de forma conjunta 
(CELES; CERQUEIRA; RANGEL, 2016). 
Por exemplo, em linguagem C, podemos criar uma estrutura de TAD utilizando 
a instrução struct, como a estrutura Aluno apresentada a seguir: 
 
A estrutura acima é composta por três elementos distintos: nome, representado 
como uma cadeia de caracteres; nota, como um número real; e turma, como um 
número inteiro. Com essa estrutura, é possível manipular individualmente ou em 
conjunto os elementos que a compõem, como apresentado abaixo. 
 
Conforme Edelweiss e Galante (2009), uma lista é uma coleção de dados que 
são organizados em ordem linear. Cada elemento da lista é chamado de nó e pode 
conter informações de um único tipo de dado primitivo ou até mesmo de um tipo 
composto de dado, como um TAD. Os elementos contidos em uma lista são 
organizados de forma sequencial, ocupando posições consecutivas, e não há 
elementos nulos na estrutura. Quando um elemento é inserido ou removido da lista, 
os demais elementos são deslocados para acomodar as alterações e manter a ordem 
correta (MATTOS; LORENZI; CARVALHO, 2007). Na Figura 1, ilustra-se como ocorre 
a inclusão e a exclusão de um elemento na lista. 
 
 
 
 
Figura 1 - Inclusão e exclusão de item na lista 
 
Fonte: Vetorazzo, 2018. 
Na Figura 1, ao adicionar o elemento "i" entre as posições 2 e 3, os elementos 
nas posições 3 e 4 são deslocados para a direita, tornando-se as posições 4 e 5, 
respectivamente. Já na exclusão do elemento da posição 3, os elementos nas 
posições 4 e 5 são deslocados para a esquerda, tornando-se as posições 3 e 4, 
respectivamente. 
Conforme Vetorazzo (2018), uma lista estática do tipo TAD é caracterizada por 
ter uma quantidade fixa de itens, geralmente implementada através de um arranjo de 
elementos de uma estrutura abstrata. Ao ser criada, é definido um tamanho máximo 
para a lista, tornando-a estática. 
Nesse contexto, Forbellone (2005) pontua a importância de considerar as 
vantagens, desvantagens e casos indicados para o uso de listas estáticas: 
• Vantagens: estas listas permitem acesso direto aos elementos do 𝑎𝑟𝑟𝑎𝑦 
através de índices e garantem um tempo de acesso constante, 
independentemente da quantidade de itens na lista. 
• Desvantagens: a principal desvantagem destas listas é o custo de 
processamento para realizar as inserções e as exclusões, pois é necessário 
reposicionar os elementos da lista. Além disso, o tamanho máximo da lista é 
predefinido no momento de sua criação, o que pode limitar sua capacidade de 
armazenamento. 
• Indicação: este tipo de lista é direcionado às listas pequenas, quando 
precisamos limitar seu tamanho máximo, e sempre que for possível que o 
processo de inclusão e exclusão de itens seja feito preferencialmente na última 
posição. 
 
 
Uma lista estática do tipo TAD pode ser composta por dois elementos. O 
primeiro elemento é chamado de dado e representa um arranjo da estrutura desejada, 
como por exemplo, dado[MAX] , que contém informações como nome, nota e turma 
de cada aluno. O segundo elemento denominado n, é um contador que armazena o 
total de itens presentes na lista durante a execução do programa. 
 
A Figura 2 a seguir, apresenta um exemplo de elementos TAD em uma lista 
estática. 
Figura 2 - Exemplo de elementos TAD em uma lista estática 
 
Fonte: Vetorazzo, 2018. 
Após definir e declarar a estrutura da lista como um arranjo e elementos do tipo 
TAD, é imprescindível desenvolver a sua interface de acesso, que consiste nas 
funções responsáveis por permitir a manipulação da lista. Essas funções possibilitam 
realizar operações como adicionar e remover itens, verificar se a lista está vazia ou 
cheia e imprimir os elementos, entre outras ações necessárias. 
4.1 Interface de uma lista estática 
Conforme Mattos, Lorenzi e Carvalho (2007), a lista estática apresenta uma 
importante característica que consiste na separação entre sua estrutura de dados e a 
implementação dos métodos que compõem sua interface de acesso. Isso permite que 
um programador utilize os métodos da lista sem necessariamente conhecer os 
detalhes de sua implementação. 
Não há uma definição fixa dos métodos de acesso de uma lista estática, pois 
 
 
eles podem ser definidos de acordo com as funcionalidades e necessidades 
específicas da aplicação que irá utilizá-la (CELES; CERQUEIRA; RANGEL, 2016). 
Existem algumas operações comuns que são amplamente conhecidas e utilizadas, 
tais como: 
• Inicializar uma lista vazia. 
• Verificar se a lista está sem elementos. 
• Verificar se a lista atingiu sua capacidade máxima. 
• Remover um item específico da lista. 
• Acessar um item em uma posição específica da lista. 
• Inserir um novo item em uma posição determinada da lista. 
• Inserir um novo item no final da lista. 
• Modificar um item existente na lista. 
• Obter o número total de itens presentes na lista. 
• Concatenar duas listas em uma única lista. 
• Imprimir todos os elementos contidos na lista. 
• Dividir a lista em duas ou mais partes separadas. 
• Classificar os itens da lista em ordem específica. 
• Inverter a ordem dos itens presentes na lista. 
Essas são apenas algumas das operações comumente implementadas em 
uma lista estática, mas é importante destacar que a escolha e implementação dos 
métodos podem variar de acordo com as necessidades e requisitos do projeto em 
questão. 
Uma lista estática é mais abrangente em comparação com filas e pilhas que 
você conheceu na aula 02, pois não possui uma ordem definida para a inserção ou 
remoção de elementos. Isso implica que os itens podem ser inseridos ou removidos 
de qualquer posição na lista, desde que seja uma posição sequencial e não contenha 
elementos nulos (EDELWEISS; GALANTE, 2009). 
Principais funções de acesso às listas estáticas 
Criação de uma lista vazia: uma lista pode ser criada ou inicializada quando 
o seu contador de elementos é definido como zero, se apresentando vazia e pronta 
 
 
para receber itens. O pseudocódigo a seguir ilustra essa função: 
 
Identificação de uma lista vazia: uma lista é considerada vazia, quando seu 
contador de elementos for zero. A seguir, o pseudocódigo apresenta o algoritmo desta 
função. 
 
Identificação de uma lista cheia: essa é uma das tarefas cruciais, pois não é 
permitido adicionar mais elementos a uma lista além do que o máximo estabelecido. 
Para avaliar essa condição, é necessário comprar o contador de itens da lista com o 
valor constante que define o número máximo de elementos, conforme é detalhado no 
algoritmo a seguir: 
 
Identificação do número de itens da lista: a quantidade de elementos em 
uma lista é representada pelo seu contador de elementos, que é modificado sempre 
que ocorre uma inserçãoou exclusão. O pseudocódigo a seguir descreve essa 
função. 
 
Inserção de item na lista: ao incluir um novo item à uma lista, é necessário 
seguir as seguintes regras: 
• Verificar se a lista está cheia. 
• Abrir um espaço para inserir o novo item e reorganizar os elementos para evitar 
 
 
posições vazias, a menos que o novo item seja inserido no final da lista. 
• Incrementar o contador de itens da lista. 
A função de inserção de um novo elemento em uma lista recebe três 
parâmetros: a lista em que o elemento será inserido, a posição em que ele será 
inserido e o valor a ser armazenado. 
 
Exclusão de item de uma posição da lista: da mesma forma que a inserção 
de itens, a exclusão de um item segue alguns critérios: 
• Verificar se a lista está vazia. 
• Fechar o espaço deixado pelo elemento excluído e reorganizar os demais itens, 
a menos que o item seja excluído do final da lista. 
• Decrementar o contador de itens da lista. 
A função de exclusão de um elemento de uma lista recebe dois parâmetros: a 
lista da qual o item será removido e a posição do item. 
 
 
 
 
Impressão dos elementos de uma lista: para imprimir os itens de uma lista, 
o algoritmo percorre todos os elementos do arranjo, começando do início até o 
contador de itens, que indica o número total de elementos da lista. 
 
4.2 Construção de listas estáticas 
Você terá acesso à implementação em linguagem C dos principais métodos de 
acesso da lista estática com base em um TAD, os quais foram previamente 
apresentados em pseudocódigo anteriormente. Essa implementação envolve a 
criação de três arquivos: lista.h, lista.c e hello.c. 
No arquivo lista.h, você encontrará o cabeçalho que contém os protótipos das 
funções e a definição da estrutura TAD da lista. A estrutura TAD representa os dados 
de um aluno e possui três atributos: nome, nota e turma. Essa estrutura será 
armazenada em um arranjo de cinco elementos, correspondendo aos itens da lista 
utilizada. Na demonstração a seguir, vemos que este arquivo define o número máximo 
de elementos da lista, o arranjo é responsável por armazenar os dados desses alunos 
em casa posição e os protótipos das funções de acesso a ela. 
 
 
 
 
 
No arquivo lista.c, está a implementação das funções que manipulam a lista. É 
um arquivo que requer a inclusão do arquivo lista.h o qual inclui os protótipos das 
funções, assim como sua estrutura de definição. 
 
 
 
 
No arquivo hello.c, você encontrará o método 𝑚𝑎𝑖𝑛, que declara uma lista TAD 
e utiliza as funções implementadas para realizar operações nessa lista. É um tipo de 
 
 
arquivo que apresente um módulo principal, pois nele é realizada a declaração do 
arranjo da estrutura TAD Aluno (apresentado a seguir), e as chamadas das funções 
de acesso à lista. É necessário realizar a inclusão do arquivo lista.c tanto para o 
acesso aos métodos da lista, como a sua estrutura. Mas, no teste de inclusão de 
elementos na lista, deve-se criar uma função que chamamos de instancia, que prepara 
os dados de entrada, utilizando como parâmetros as informações do aluno: nome, 
nota e turma. 
Na demonstração a seguir, é possível acompanhar a criação de uma lista de 
cinco posições com armazenamento da estrutura Aluno e a realização de algumas 
operações através dos métodos, entre eles, criar, inserção e remoção de elementos, 
verificar se a lista está cheia ou vazia, entre outros. 
 
 
 
 
Assim, os três arquivos trabalham juntos para criar e manipular uma lista 
estática baseada em um TAD de alunos. O resultado da execução desse programa é 
mostrado na Figura 3. Inicialmente, uma lista é criada e é verificado se ela está vazia 
e cheia (linhas 16 a 23). Em seguida, três alunos são adicionados à lista: Pedro, Ana 
e Maria, nessa ordem, e a relação de alunos é impressa (linhas 25 a 37). 
Posteriormente, o aluno Pedro é removido da primeira posição, e a lista é 
impressa novamente para ilustrar a exclusão (linhas 39 a 42). Em seguida, Paula é 
adicionada à primeira posição, Pedro à segunda posição e João à quinta posição. A 
lista é impressa novamente para exibir as alterações (linhas 44 a 58). 
Por fim, é verificado se a lista está cheia, e a quantidade de elementos 
presentes na lista é exibida (linhas 60 a 64). 
 
 
 
 
 
 
 
 
Figura 3 - Resultado da execução do programa de exemplo. 
 
Fonte: Vetorazzo, 2018. 
 
 
 
 
 
 
 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução a estrutura de dados: com 
técnicas de programação em C. 2. ed. Rio de Janeiro: Elsevier, 2016. 
EDELWEISS, N.; GALANTE, R. Estrutura de dados. Porto Alegre: Bookman, 2009. 
FORBELLONE, A. L. Lógica de programação: a construção de algoritmos e 
estruturas de dados. 3. ed. São Paulo: Pearson, 2005. 
LORENZI, F. MATTOS, P. N.; CARVALHO, T. P. Estruturas de dados. São Paulo: 
CENGAGE Learning, 2007. 
VETORAZZO, A. S. Listas. In.: VETORAZZO, A. S. et al. Estrutura de dados. Porto 
Alegre: SAGAH, 2018.