Estrutura de Dados

Baixe aqui - Estrutura de dados Usando C.

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 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.