Trabalho Interdiciplinar Individula 3 Semestre
Exames: Trabalho Interdiciplinar Individula 3 Semestre. Pesquise 862.000+ trabalhos acadêmicosPor: Extreme • 9/6/2012 • 1.487 Palavras (6 Páginas) • 1.819 Visualizações
SISTEMA DE ENSINO PRESENCIAL CONECTADO
TECNOLOGIA EM Análise e desenvolvimento de sistemas
GERALDO DOS SANTOS
Produção textual
Pirapora
2011
GERALDO DOS SANTOS
produção textual
Trabalho apresentado ao Curso Análise e Desenvolvimento de Sistemas da UNOPAR - Universidade Norte do Paraná, para as disciplinas:
Banco de Dados II
Analise de Sistemas II
Desenvolvimento Orientado a Objetos I
Algoritmos e Estrutura de Dados
Seminarios II
Prof.ª Polyanna
Prof. Roberto
Prof. Marcio
Prof. Merris
Pirapora
2011
Listas Lineares
Lista é uma das formas mais comuns de agrupar dados.
Uma lista linear é uma estrutura que permite representar um conjunto de elementos de forma a preservar a relação de ordem linear entre eles.
Pode-se definir uma lista como um conjunto de n elementos (n>=0) organizados de tal forma que a sua estrutura reflete diretamente as posições relativas dos elementos que compõem a lista.
Seja L uma lista linear tal que L:[a1, a2, a3,...,an], para n>=0
então:
a1 é o primeiro elemento de L;
an é o último elemento de L;
para cada i, 1 < i < n, o elemento ai é precedido por ai-1 e sucedido por ai+1;
para n=0, dizemos que a lista é vazia
Muitas operações podem ser executadas sobre uma lista linear:
a) criação de uma lista linear vazia
b) acesso ao i-ésimo elemento de uma lista para examiná-lo ou modificá-lo
c) inserção de um elemento na lista
d) remoção de um elemento da lista
e) cópia de uma lista
f) concatenação de duas listas
g) determinação do tamanho da lista
h) exclusão de um lista
i) entre muitas outras.
Listas Lineares com disciplina de acesso
Disciplina de acesso refere-se à forma como os elementos de uma lista linear são acessados, inseridos e removidos.
Se os elementos de uma lista linear só podem ser inseridos, acessados ou removidos da última posição, chamamos esta lista linear de pilha (LIFO - Last In First Out);
Se os elementos de uma lista linear só podem ser inseridos na última posição e acessados ou removidos da primeira posição, chamamos esta lista linear de fila (FIFO - First In First Out);
Considerações sobre alocação de memória
Ao desenvolver uma implementação para listas lineares, o primeiro problema que surge é: como armazenar os elementos da lista???
A alocação de memória para executar um programa pode ser estática ou dinâmica.
Na alocação estática, o espaço de memória ocupado pelas variáveis é determinado no momento da compilação, já na alocação dinâmica o espaço de memória é alocado em tempo de execução. Um exemplo pode ser visto na Figura 2.1.
Um lista com alocação estática de memória exige uma definição do número máximo de elementos e como consequencia pode haver um super ou sub dimensionamento do tamanho da lista. A lista com alocação dinâmica por outro lado resolve esta limitação uma vez que crescem à medida que novos elementos precisam ser armazenados (e diminui à medida que elementos anteriormente armazenados são retirados da lista).
memória usada pelo memória livre
programa
10000 i == 4200
10002 ptr ==19000
19000 5800
main()
{
int i, *ptr;
ptr = (int*) malloc (sizeof(int));
*ptr = 5800;
i = 4200;
}
(a) (b)
Figura 2.1 – (a) com alocação de memória estática; (b) com alocação dinâmica de memória
Considerações sobre acesso aos elementos de um lista linear
O acesso aos elementos de uma lista pode se dar de forma sequencial ou encadeada.
* Acesso sequencial
No acesso sequencial assume-se que os elementos de uma lista são armazenados de forma consecutiva na memória.
Considere que cada elemento da lista tenha tamanho k, veja Figura 2.2.
... | ei-1 | e | ei+1 | ... |
t t+k t+2k t+3k
Figura 2.2 – Lista linear com acesso sequencial
Uma vantagem do acesso sequencial que podemos ressaltar é a facilidade para calcular o endereço de memória de um certo índice i. Para isso, basta saber o endereço inicial t da lista, o tamanho do elemento da lista em bytes, e o índice do elemento cujo endereço se deseja obter.
Uma
...