Estrutura de Dados Dinâmica em C (Struct)

Prévia do material em texto

Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Estrutura de dados dinâmica
Prof. DSc. Newton Spolaôr
Disciplina Computação I
Bacharelado em Ciência da Computação
Universidade Estadual do Oeste do Paraná (UNIOESTE)
Brasil
29/11/2016
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Sumário
1 Considerações iniciais
2 Lista encadeada
3 Exercícios
4 Considerações finais
Newton Spolaôr Estrutura de dados dinâmica 2
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Aula anterior em um olhar
A alocação dinâmica de memória usando ponteiros é um
tema relacionado a diferentes tópicos da disciplina
A ideia é que o espaço para variáveis seja alocado e
liberado dinamicamente, i.e., em tempo de execução, por
meio de comandos específicos inseridos pelo
programador
Vantagens da alocação dinâmica incluem flexibilidade e
eficiência
Na aula de hoje, será destacada a relação entre alocação
dinâmica de memória e tipos estruturados de dados para
compor uma estrutura denominada lista encadeada
Newton Spolaôr Estrutura de dados dinâmica 3
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Aula anterior em um olhar
A alocação dinâmica de memória usando ponteiros é um
tema relacionado a diferentes tópicos da disciplina
A ideia é que o espaço para variáveis seja alocado e
liberado dinamicamente, i.e., em tempo de execução, por
meio de comandos específicos inseridos pelo
programador
Vantagens da alocação dinâmica incluem flexibilidade e
eficiência
Na aula de hoje, será destacada a relação entre alocação
dinâmica de memória e tipos estruturados de dados para
compor uma estrutura denominada lista encadeada
Newton Spolaôr Estrutura de dados dinâmica 3
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Ideia de uma lista [1]
Modo simples e flexível de organizar elementos em uma
sequência, obtendo uma espécie de “vetor dinâmico”
Uma lista pode crescer ou diminuir de tamanho durante a
execução de um programa, de acordo com a demanda
Apresenta diferentes vantagens
Gerenciamento de uma quantidade imprevisível de
elementos
Gerenciamento de elementos de um mesmo tipo de dados,
o qual pode ser desde um inteiro até um struct
Newton Spolaôr Estrutura de dados dinâmica 4
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Algumas aplicações de lista [2]
Lista telefônica
Lista de tarefas (“to do” list)
Lista de voos
Representação de código e de dados, como ilustrado na
linguagem LISP
Newton Spolaôr Estrutura de dados dinâmica 5
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Algumas aplicações de lista [2]
Lista telefônica
Lista de tarefas (“to do” list)
Lista de voos
Representação de código e de dados, como ilustrado na
linguagem LISP
Newton Spolaôr Estrutura de dados dinâmica 5
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Algumas aplicações de lista [2]
Lista telefônica
Lista de tarefas (“to do” list)
Lista de voos
Representação de código e de dados, como ilustrado na
linguagem LISP
Newton Spolaôr Estrutura de dados dinâmica 5
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Algumas aplicações de lista [2]
Lista telefônica
Lista de tarefas (“to do” list)
Lista de voos
Representação de código e de dados, como ilustrado na
linguagem LISP
Newton Spolaôr Estrutura de dados dinâmica 5
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Definição [3]
Uma lista é definida como uma coleção de dados de um
mesmo tipo
É possível ver uma lista como uma seqüência de zero ou
mais itens x1, x2, . . . , xn, na qual todos os itens são de um
determinado tipo e n representa o tamanho da lista
Propriedades da lista quando se assume que n ≥ 1, x1 é o
primeiro item da lista e xn é o último item da lista
xi precede xi+1 para i = 1, 2, . . . , n − 1
xi sucede xi−1 para i = 2, 3, . . . , n
O elemento xi é dito estar na iésima posição da lista
As propriedades não implicam que os elementos estejam
ordenados, mas apenas indicam a posição deles na lista
Newton Spolaôr Estrutura de dados dinâmica 6
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Definição [3]
Uma lista é definida como uma coleção de dados de um
mesmo tipo
É possível ver uma lista como uma seqüência de zero ou
mais itens x1, x2, . . . , xn, na qual todos os itens são de um
determinado tipo e n representa o tamanho da lista
Propriedades da lista quando se assume que n ≥ 1, x1 é o
primeiro item da lista e xn é o último item da lista
xi precede xi+1 para i = 1, 2, . . . , n − 1
xi sucede xi−1 para i = 2, 3, . . . , n
O elemento xi é dito estar na iésima posição da lista
As propriedades não implicam que os elementos estejam
ordenados, mas apenas indicam a posição deles na lista
Newton Spolaôr Estrutura de dados dinâmica 6
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Definição [3]
Uma lista é definida como uma coleção de dados de um
mesmo tipo
É possível ver uma lista como uma seqüência de zero ou
mais itens x1, x2, . . . , xn, na qual todos os itens são de um
determinado tipo e n representa o tamanho da lista
Propriedades da lista quando se assume que n ≥ 1, x1 é o
primeiro item da lista e xn é o último item da lista
xi precede xi+1 para i = 1, 2, . . . , n − 1
xi sucede xi−1 para i = 2, 3, . . . , n
O elemento xi é dito estar na iésima posição da lista
As propriedades não implicam que os elementos estejam
ordenados, mas apenas indicam a posição deles na lista
Newton Spolaôr Estrutura de dados dinâmica 6
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Definição [3]
A partir da definição, é possível obter diferentes
implementações, como ilustrado a seguir
Lista sequencial: lista tipicamente implementada como um
vetor em que cada elemento xi ocupa uma posição
sucessiva a xi−1
Newton Spolaôr Estrutura de dados dinâmica 7
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Definição [3]
A partir da definição, é possível obter diferentes
implementações, como ilustrado a seguir
Lista encadeada: lista em que a ordem dos elementos é
dada pelos ponteiros de suas conexões
Newton Spolaôr Estrutura de dados dinâmica 8
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Comparação inicial entre as duas implementações
Lista sequencial
Um vetor pode ser alocado dinamicamente com um
tamanho pré-determinado (vide última aula), sendo
realocado, se necessário, para ocupar um tamanho fixo
maior/menor em tempode execução
Operações como a inclusão e a exclusão de elementos
nesse tipo de lista são relativamente custosas
O acesso ao iésimo elemento é barato
Lista encadeada
A partir de um ponteiro inicial, cada elemento da lista pode
ser alocado ou desalocado dinamicamente conforme a
necessidade
Geralmente, cada elemento é uma struct com um campo
ponteiro que pode apontar para outro elemento da mesma
struct
Operações como a inclusão e a exclusão de elementos
nesse tipo de lista são baratas e envolvem a atualização de
ponteiros
Newton Spolaôr Estrutura de dados dinâmica 9
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Comparação inicial entre as duas implementações
Lista sequencial
Um vetor pode ser alocado dinamicamente com um
tamanho pré-determinado (vide última aula), sendo
realocado, se necessário, para ocupar um tamanho fixo
maior/menor em tempo de execução
Operações como a inclusão e a exclusão de elementos
nesse tipo de lista são relativamente custosas
O acesso ao iésimo elemento é barato
Lista encadeada
A partir de um ponteiro inicial, cada elemento da lista pode
ser alocado ou desalocado dinamicamente conforme a
necessidade
Geralmente, cada elemento é uma struct com um campo
ponteiro que pode apontar para outro elemento da mesma
struct
Operações como a inclusão e a exclusão de elementos
nesse tipo de lista são baratas e envolvem a atualização de
ponteiros
Newton Spolaôr Estrutura de dados dinâmica 9
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Operações típicas em uma lista [3]
Operações tipicamente associadas a listas incluem
Inserção
Remoção
Busca
Restrições sobre algumas dessas operações determinam
variações de listas, como pilhas e filas, análogas a
conceitos do mundo real
Ao encapsular (agrupar) estruturas de dados, como uma
lista encadeada, e operações sobre essas estruturas, é
obtido um tipo abstrato de dados
Newton Spolaôr Estrutura de dados dinâmica 10
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Aula anterior em um olhar
Considerações iniciais
Objetivo geral desta aula
Objetivo geral desta aula
Apresentar definição e diferentes representações para a
estrutura de dados dinâmica lista encadeada
Newton Spolaôr Estrutura de dados dinâmica 11
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Sumário
1 Considerações iniciais
2 Lista encadeada
3 Exercícios
4 Considerações finais
Newton Spolaôr Estrutura de dados dinâmica 12
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Lista encadeada [1]
Características básicas
Tamanho da lista não é pré-definido
Cada elemento aponta para o próximo
Elementos não estão contíguos na memória e a alocação é
dinâmica
Newton Spolaôr Estrutura de dados dinâmica 13
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Lista encadeada [1]
Elemento da lista
Armazena as informações sobre cada elemento
Aponta para o próximo elemento
Assim, é definido como uma estrutura que possui
Campos representando as informações do elemento
Ponteiro para o próximo elemento
Newton Spolaôr Estrutura de dados dinâmica 14
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Implementação de lista encadeada [1]
Uma lista pode ser implementada a partir de uma cabeça
(variável ponteiro para uma estrutura)
Nessa cabeça, podem ser incluídos 3 campos
Ponteiro para o primeiro elemento
Ponteiro para o último elemento
Tamanho da lista (quantidade de elementos alocados)
Newton Spolaôr Estrutura de dados dinâmica 15
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Estruturas da lista encadeada [1]
struct Item{
char info;
/* outros campos podem ser incluídos*/
};
typedef struct Item TItem;
struct Celula{
TItem item;
struct Celula * pProx;
};
typedef struct Celula TCelula;
Newton Spolaôr Estrutura de dados dinâmica 16
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Estruturas da lista encadeada [1]
struct Lista{
TCelula * pPrimeiro;
TCelula * pUltimo;
int tamanho; //campo opcional
};
typedef struct Lista TLista;
Newton Spolaôr Estrutura de dados dinâmica 17
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Considerações sobre primeiras funções [1]
Inicialmente, serão implementadas as seguintes
operações como funções C
Iniciação (alocação da cabeça) da lista
Verificação se lista está vazia
Inserção de elemento no final da lista
Remoção de elemento do início da lista
Remoção de elemento do início da lista
Cada função terá no mínimo um parâmetro: um ponteiro
para TLista (cabeça) passado por referência
Vide código escrito no Dev C++ e figuras que serão
desenhadas no quadro
Newton Spolaôr Estrutura de dados dinâmica 18
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Outras implementações de lista encadeada [1]
Lista duplamente encadeada
Se diferencia das anteriores pelo fato de que cada
elemento aponta para os elementos anterior e posterior a
ele
Muito útil quando ocorrem muitas inserções e remoções,
principalmente de elementos intermediários
Newton Spolaôr Estrutura de dados dinâmica 19
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Outras implementações de lista encadeada [4]
Lista com descritores
Cria um nó especial para guardar um “resumo” de uma lista
Exemplo de informações do resumo: número de elementos
da lista e média/moda da lista, entre outros
Newton Spolaôr Estrutura de dados dinâmica 20
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Lista encadeada simples
Outras implementações de lista encadeada
Outras implementações de lista encadeada [1]
Lista circular
Primeiro elemento aponta para o último e vice-versa,
formando assim um círculo lógico
Pode ser implementado com descritor ou não
Newton Spolaôr Estrutura de dados dinâmica 21
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Sumário
1 Considerações iniciais
2 Lista encadeada
3 Exercícios
4 Considerações finais
Newton Spolaôr Estrutura de dados dinâmica 22
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Exercício 1
A partir do exemplo dado em aula, represente uma string
como uma lista encadeada
Antes de ir ao código, indique qual é a principal mudança
que se deve realizar em relação ao código exibido em aula
Após, indique uma vantagem e uma desvantagem em
relação ao uso de um vetor para trabalhar com essa
cadeia de caracteres
Newton Spolaôr Estrutura de dados dinâmica 23
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Exercício 2
Modifique as funções apresentadas em aula para ser
capaz de
Inserir um elemento em qualquer posição da lista
Remover um elemento em qualquer posição da listaConsultar (buscar por) um elemento na lista
Newton Spolaôr Estrutura de dados dinâmica 24
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Exercício 3
Implementar uma lista encadeada sem cabeça
A única diferença entre essa variação de lista e a lista
encadeada com cabeça é o fato de que a primeira não
possui a célula cabeça, mas apenas um ponteiro para o
primeiro elemento
Newton Spolaôr Estrutura de dados dinâmica 25
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Considerações finais
1 Considerações iniciais
2 Lista encadeada
3 Exercícios
4 Considerações finais
Newton Spolaôr Estrutura de dados dinâmica 26
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Considerações finais
Nesta aula foram apresentadas a definição e
representações para uma lista encadeada alocada
dinamicamente
Esse conteúdo é base para outros que seguirão em
diferentes disciplinas do curso
Newton Spolaôr Estrutura de dados dinâmica 27
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Contato
newtonsp.unioeste@gmail.com
Newton Spolaôr Estrutura de dados dinâmica 28
Considerações iniciais
Lista encadeada
Exercícios
Considerações finais
Referências bibliográficas
[1] Reinaldo Fortes.
Recursividade.
http://www.decom.ufop.br/reinaldo/disciplinas/bcc202-2014-
01/plano-de-aulas/, 2014.
Notas didáticas.
[2] Fernando V. Paulovich.
Listas estáticas.
http://wiki.icmc.usp.br/index.php/Scc-202(paulovich)_2014, 2014.
Notas didáticas.
[3] Huei Diana Lee.
Introdução e conceitos: Tipos de dados, estruturas de dados e
tipos abstratos de dados.
Disciplina Algoritmos e Estruturas de Dados - UNIOESTE, 2011.
Notas didáticas.
[4] Bruno B. Boniati.
Listas com descritor.
http://www.cafw.ufsm.br/b˜runo/disciplinas/estrutura_dados/slides/aula9_10_listasHet_e_listasDesc.pdf,
2013.
Notas didáticas.
Newton Spolaôr Estrutura de dados dinâmica 29
	Considerações iniciais
	Aula anterior em um olhar
	Considerações iniciais
	Objetivo geral desta aula
	Lista encadeada
	Lista encadeada simples
	Outras implementações de lista encadeada
	Exercícios
	Considerações finais