Matéria Estrutura de Dados - 3º Sistemas de Informação.
Estrutura de dados
Prof : Daniel.
e-mail: dannybor@gmail.com
Conceito
Estrutura de dados e algoritmos estão
intimamente ligados, não se pode estudar estrutura de dados sem considerar o
algoritmo associado, a elas assim como a escolha de algoritmos em geral depende
da representação e da estrutura dos dados.
Para resolver um problema é necessário escolher uma abstração da
realidade, em geral mediante a definição de um conjunto que representa a
situação real. A segunda a ser escolhida
é a forma de representar esse dado.
A escolha da representação do dado é
determinada entre outras, pelas operações a serem realizadas sobre os
dados. Considere a operação de
adição. Para pequenos números, uma boa
representação é por meio de barras verticais caso em que a operação de adição é
bastante simples. Já a representação por
dígitos decimais requer regras relativamente
complicadas, as quais devem ser memorizadas. Entretanto a situação se inverte quando
consideramos a adição de grandes números, sendo mais fácil a representação por
dígitos decimais, devido ao princípio baseado no peso relativo da posição de
cada dígito. Programar é basicamente
estruturar dados e construir algoritmos.
De acordo com wuth (1976, XII), programar são formulações concretas de
algoritmos abstratos, baseada em representações e estruturas específicas de
dados. Em outras palavras, programas
representam classe especial de algoritmos
capazes de serem seguidos por computadores.
Entretanto um computador só é capaz de
seguir um programa em linguagem de máquina, que correspondem a uma seqüência de
instruções obscuras e desconfortáveis.
Para contornar tal problema é necessário construir linguagens mais
adequadas, que facilitam a tarefa de programar um computador. Segundo Dijkstra (1976), uma linguagem de
programação é uma técnica de notações para programar, com a intenção de servir
de veículo tanto para a expressão do raciocínio algorítmico quanto para a
execução automática de um algoritmo por um computador.
ESTRUTURA
BÁSICA DE DADOS
·
Listas lineares
-
Implementações de listas por meios de arranjos.
-
Implementações de listas por meios de ponteiros.
·
Pilhas
-
Implementações de pilhas por meios de arranjos.
-
Implementações de pilhas por meios de ponteiros.
·
Filas.
- Implementações de Filas por meios de arranjos.
- Implementações de Filas por meios de arranjos.
- Implementações de Filas por meios de ponteiros.
Listas lineares.
Uma das formas mais simples de
interligar os elementos de um conjunto é por meio de lista. Lista é uma estrutura em que as operações
inserir retirar e localizar são definidas.
Listas são estruturas muito flexíveis, porque podem crescer sem diminuir
de tamanho durante a execução de um programa, de acordo com a demanda. Itens podem ser acenados, inseridos ou
retirados de uma lista. Duas listas
podem ser concatenadas para formar uma lista única, assim como uma lista pode
ser parte de duas ou mais listas.
Listas são adequadas para aplicações nas
quais não é possível prever a demanda de memória, permitindo a manipulação de
quantidades imprevisíveis de dados, de formato também imprevisível.
Listas são úteis em aplicações tais como manipulação simbólica, gerencia de
memória, simulação e compiladores. Na
manipulação simbólica, as temos de uma
fórmula podem crescer sem limites .
Em simulação dirigida por relógios, pode
ser criado um número imprevisível de processos, os quais tende ser escalonado
para execução de acordo com alguma ordem predefinida.
Uma lista linear é uma sequencia de zero
ou mais itens X1, X2, na qual X1 é de um determinado tipo e N representa o
tamanho da lista linear. Sua principal
prioridade estrutural envolve as posições relativas doa itens e uma dimensão
assumindo n>=1, X1 é o primeiro item da lista e Xn é o último item da
lista. Em geral geral, Xi precede Xi+1
para i=1,2..., n1, o Xi sucede xi-1 para i=2,3...n, e o elemento Xi é dito na i
- ésima posição da lista.
Pilhas
Existem aplicações para listas lineares
nas quais inserções, retiradas e acessos a itens ocorrem sempre em um das
extremos da lista. Uma pilha é uma lista
linear em que todas as inserções, retirada e, geralmente todos os acessos são
feitos em apenas um extremo da lista.
Os itens em uma pilha são colocados um
sobre o outro com um item inserido mais recentemente no topo e o item inserido
menos recentemente no fundo. O modelo
intuitivo de uma pilha é o de um monte de pratos em um prateleira, sendo
conveniente retirar pratos ou adicionar novos na parte superior esta imagem
está frequentemente associada com uma teoria de autômato , na qual o topo de
uma pilha é considerado como o receptáculo de uma cabeça da leitura/gravação
que pode empilhar e desempilhar itens a pilha (“ choft e Ulman, 1969”).
As pilhas possuem a seguinte
propriedade: o último item inserido é o primeiro item que pode ser retirado da
lista. Por esta razão, as pilhas são
chamadas de lista LIFO, termo formado a partir de “ last-in, first-out”. “Existe uma ordem linear para pilhas, que é a
ordem do mais recente para o menos recente”.
Esta propriedade torna a pilha uma ferramenta ideal para o processamento
de estruturas aninhadas de profundidade imprevisível, situação em que é
necessário garantir que subestruturas mais internas sejam processadas antes da
estrutura que as contenham. A qualquer
instante, uma pilha contém uma seqüência de obrigações adiadas, cuja ordem de
remoção da pilha garante que as estruturas mais internas serão processadas
antes da estrutura mais externa.
FILAS
Uma fila é uma lista em que todas as
inserções são realizadas em um extremo da lista e, geralmente os acessos são
realizados no outro extremo da lista. O
modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no
início da fila são servidas primeiro e as pessoas que chegam entram no fim da
fila.por esta razão, as filas são chamadas de lista FIFO, termo formado a
partir de “ first-in”, ‘first-out”.
existe uma ordem linear para filas que é a ordem de chegada, filas sãi
utilizadas quando precisamos processar itens de acordo com a ordem “primeiro-que-
chega, primeiro-atendido”. Sistemas
operacionais utilizam filas para regular a ordem na qual tarefas devem receber
processamento e recurso devem ser alocados a processos.
Nenhum comentário:
Postar um comentário