COS-121
Estrutura de Dados e Algoritmos
2º Semestre de 2014
Professor Ricardo Farias
Aula 10
Tópicos desta aula.
Linguagem C
Listas Lineares
Lista linear é uma estrutura de dados na qual elementos de um mesmo tipo de dado estão organizados de maneira sequencial. Não necessariamente, estes elementos estão fisicamente em sequência, mas a idéia é que exista uma ordem lógica entre eles. Um exemplo disto seria um consultório médico: as pessoas na sala de espera estão sentadas em qualquer lugar, porém sabe-se quem é o próximo a ser atendido, e o seguinte, e assim por diante. Assim, é importante ressaltar que uma lista linear permite representar um conjunto de dados afins (de um mesmo tipo) de forma a preservar a relação de ordem entre seus elementos.
Cada elemento da lista é chamado de nó, ou nodo.
Definição:
Conjunto de N nós, onde N ≥ 0, x1, x2, ..., xn, organizados de forma a refletir a posição relativa dos mesmos.
Se N ≥ 0, então x1 é o primeiro nó. Para 1 < k < n, o nó xk é precedido pelo nó xk-1 e seguido pelo nó xk+1 e xn é o último nó.
Quando N = 0, diz-se que a lista está vazia.
Exemplos de listas lineares:
- Pessoas na fila de um banco;
- Letras em uma palavra;
- Relação de notas dos alunos de uma turma;
- Itens em estoque em uma empresa;
- Dias da semana;
- Vagões de um trem;
- Pilha de pratos;
- Cartas de baralho.
Alocação de uma lista
Quanto a forma de alocar memória para armazenamento de seu elementos, uma lista pode ser:
- Sequencial ou Contígua
Numa lista linear contígua, os nós além de estarem em uma sequência lógica, estão também fisicamente em sequência. A maneira mais simples de acomodar uma lista linear em um computador é através da utilização de um vetor.
A representação por vetor explora a sequencialidade da memória de tal forma que os nós de uma lista sejam armazenados em endereços contíguos.
- Encadeada
Os elementos não estão necessariamente armazenados sequencialmente na memória, porém a ordem lógica entre os elementos que compõem a lista deve ser mantida. Listas lineares encadeadas são discutida na aula 11.
Operações com Listas
As operações comumente realizadas com listas são:
- Criação de uma lista
- Remoção de uma lista
- Inserção de um elemento da lista
- Remoção de um elemento da lista
- Acesso de um elemento da lista
- Alteração de um elemento da lista
- Combinação de duas ou mais listas
- Classificação da lista
- Cópia da lista
- Localizar nodo através de info
Tipos de Listas Lineares
Os tipos mais comuns de listas lineares são as:
- pilhas
Uma pilha é uma lista linear do tipo LIFO - Last In First Out, o último elemento que entrou, é o primeiro a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e saem dela. Exemplos de pilhas são: pilha de pratos, pilha de livros, pilha de alocação de variáveis da memória, etc.
- filas
Uma fila é uma lista linear do tipo FIFO - First In First Out, o primeiro elemento a entrar será o primeiro a sair. Na fila os elementos entram por um lado (“por trás”) e saem por outro (“pela frente”). Exemplos de filas são: a fila de caixa de banco, a fila do INSS, etc.
- deques
Um deque - Double-Ended QUEue) é uma lista linear na qual os elementos entram e saem tanto pela “pela frente” quanto“por trás”. Pode ser considerada uma generalização da fila.
Assim o que vai distinguir os diferentes tipos de listas são as operações que se podem realizar sobre as mesmas, podendo tanto serem implementadas com alocação sequencial quanto com alocação encadeada (próxima aula).