tema 4 - mod 1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

TEMA 4 – LISTAS, PILHAS, FILAS e DEQUES
MOD 1 – CONCEITOS DA MANIPULAÇÃO DE DADOS NA MEMÓRIA
-> LISTAS
__ALOCAÇÃO SEQUENCIAL
É o armazenamento de dados de forma sequencial na memória do computador, ou seja, as posições de memória ocupadas serão contíguas. 
Para a alocação sequencial que possa ser concluída, o programa precisa informar previamente todo o tamanho de memória que será necessário. Há duas estratégias que envolvem a alocação de toda a memória, diferindo apenas se esse valor é determinado em tempo de compilação ou de execução.
Em linguagens de programação de alto nível, a alocação sequencial é representada pelos arrays ou vetores:
Um vetor informa ao compilador que ele deve reservar memória suficiente para armazenar todos os elementos. Para isso, é preciso especificar o tipo de dado que o vetor conterá.
_______________________________________________________________________
1: [...]
2: int vetor [10]; //informação da reserva memória
3: int a = 50;
4: vetor [ 3 ] = a; 
5: [...]							código1
_______________________________________________________________________
Na linha 4 quer dizer saltar 6 posições de memória (3(índice do vetor)*2(número de posições de memória que cada elemento ocupa)=6). O número de posições necessárias depende do tamanho do tipo de dado e da palavra da memória.
Para alocar um vetor, o compilador calcula a quantidade de memória necessária com base no tipo de dado e no número de elementos. O acesso aos elementos ocorre por índice, que representa o deslocamento em relação ao primeiro endereço.
A alocação sequencial usa memória contígua, o que facilita o acesso rápido, mas dificulta a remoção de elementos, pois isso pode comprometer a continuidade dos dados. A alocação dinâmica, por outro lado, é mais flexível para operações como remoção. 
____CONCEITOS E OPERAÇÕES EM LISTAS LINEARES GENÉRICAS
Consideraremos que as listas lineares estão implementadas através de alocação sequencial em vetores de tamanho ilimitado. 
Listas lineares são estruturas de dados não primitiva usadas para reunir um conjunto de elementos que guardam relação entre si. Pode armazenar dados complexos, onde cada nó possui campos com diferentes características. Um desses campos, chamado “chave”, é usado para indexar e buscar os nós da lista.
Segundo Markenzon, uma lista linear é um conjunto de n ≥ 0 nós, tais que suas propriedades estruturais decorrem, unicamente, da posição relativa dos nós dentro da sequência linear.
As listas apresentam casos particulares, chamados de deque, pilha e fila. Tais casos se diferenciam pela forma como as operações de inserção e remoção podem ocorrer na lista.
--Operações de busca, inserção e remoção 
A lista é representada por “Lista” e possui “n” posições ocupadas.
Algoritmo 1 - busca
1: int buscar (chave)
2: 	se n > 0
3: 		para i = 1 até i 0 
3:			int i = busca (chave)
4: 			se i V [ 0 ], então, V [ i + 1 ] > V [ i ].