Pular para o conteúdo principal

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.

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.

Comentários

+ Vistas

Existe uma fórmula padrão de Calculo de Estoque Mínimo e Máximo?

  Na verdade, não existe uma fórmula única e universal para calcular o estoque mínimo e máximo ideal para uma empresa de varejo, pois diversos fatores influenciam esses valores. No entanto, existem algumas fórmulas e métodos básicos que podem te ajudar a estimar esses níveis de forma eficiente, considerando as características específicas do seu negócio. Fórmula básica para o estoque mínimo: Estoque mínimo = Consumo médio diário x Tempo de reposição Essa fórmula leva em conta a quantidade média de produtos que você vende por dia e o tempo que leva para receber novos produtos do seu fornecedor. O objetivo é garantir que você tenha estoque suficiente para atender à demanda durante esse período de reposição, mesmo que haja imprevistos. Fórmula básica para o estoque máximo: Estoque máximo = Estoque médio + Lote de compra Essa fórmula considera o seu estoque médio, que é a quantidade média de produtos que você costuma ter em estoque, e o tamanho do lote de compra que você costuma fazer. ...

Mais uma inovação da Google.

Sabe aqueles filmes em que um cientista possui um laboratório secreto onde faz seus experimentos mais malucos? O Google tem algo parecido, chamado "Google X". A operação foi descoberta e mostrada ao mundo neste domingo (13/11) em uma matéria do New York Times. E é de lá que podem sair duas tecnologias com potencial de mudar a forma como conhecemos os carros atualmente. De acordo com o site Electronista, uma fonte que não quis se identificar afirmou que a empresa planeja construir carros que dispensam a necessidade de motoristas. O Google os fabricaria nos EUA e os venderia para empresas locais que queiram eliminar a figura do condutor de seu quadro de funcionários. A outra invenção do Google X é relacionada à robótica. Máquinas poderiam, por exemplo, substituir os motoristas do Google Street View, encarregados de dirigir pelas cidades enquanto o sistema fotografa as ruas. Na equipe do Google X estão Sebastian Thrun, um dos maiores experts em robótica e inteligência a...

Instalando o novo Gnome 3 no Debian 6

Instalando o novo Gnome 3 no Debian 6 (Atualizado) Vi essa dica em um comentário no site  Br-Linux , e como eu testei e deu muito certo, decidi repassar a dica... Atenção: Faça por sua conta e risco, comigo a instalação ocorreu muito bem, mais isso não impede que em outras situações a instalação não ocorra como esperado.  Para instalar o Gnome 3 no Debian 6, vamos usar os repositórios  unstable e experimental, para isso abra um terminal e como root digite: #nano /etc/apt/sources.list  Adicione as linhas a seguir: #Instavel deb http://sft.if.usp.br/debian/ sid main non-free contrib deb-src http://sft.if.usp.br/debian/ sid main non-free contrib #Experimental deb http://sft.if.usp.br/debian/ experimental main non-free contrib deb-src http://sft.if.usp.br/debian/ experimental main non-free contrib  Agora digite ctrl+o e enter para salvar a configuração, e depois digite: #apt-get update    e para instalar: #apt-get install -t ...