Articles

Resumo de estruturas de dados

by admin

Resumo de tipos de dados

Em ciência da computação, um tipo de dados abstrato (ADT) é um modelo matemático para tipos de dados onde o tipo de dados é definido por seu comportamento (semântica) do ponto de vista de um usuário de dados, especificamente em termos de valores possíveis, operações possíveis sobre esse tipo de dados, e o comportamento dessas operações. Isto contrasta com estruturas de dados, que são representações concretas de dados, e são o ponto de vista de um implementador, não um usuário.

Formalmente, um ADT pode ser definido como uma “classe de objetos cujo comportamento lógico é definido por um conjunto de valores e um conjunto de operações”; isto é análogo ao algī ebrica de estrutura em matemática. O que se entende por “comportamento” varia de Autor para autor, com os dois principais tipos de especificações formais para comportamento sendo a especificação axiomática (algébrica) e um modelo abstrato; estes correspondem a semântica axiomática e semântica operacional de uma máquina abstrata, respectivamente. Alguns autores também incluem a complexidade computacional (“custo”), tanto em termos de tempo (para operações de computação) e espaço (para representar valores).

A razão pela qual usamos estruturas abstratas é porque elas usam eficientemente a memória baseada no design dos dados armazenados nelas. Com grandes quantidades de dados ou muito frequentemente mudando dados, a estrutura de dados pode fazer uma enorme diferença na eficiência (tempo de execução) do seu programa de computador.

em linguagem mais comum, uma estrutura de dados abstratos é apenas algum arranjo de dados que nós construímos em um arranjo ordenado.

perfeitamente linda visão geral

Alguns tipos de resumo de estruturas de dados

Avaliado por IB

  1. estática e dinâmica de estruturas de dados
  1. arrays
  2. arrays de duas dimensões
  3. stack
  4. fila
  5. lista ligada
  6. árvore
  7. árvore binária
  8. collections
  9. recursão

NÃO foi Avaliado pela IB, mas você deve conhecê-los

  1. lista
  2. dicionários
  3. define
  4. tupla

operações Básicas de estruturas de dados

eu encontrei este excelente slide de Simon Allardice.

operações básicas de matrizes.png

a Comparação de diferentes estruturas de dados

Estrutura de Dados pontos Fortes Fraquezas
arrays Inserir e eliminar elementos, iterar por uma coleção de Ordenação e pesquisa, Inserindo e excluindo – especialmente se você estiver inserindo e excluindo, no início ou no final do array
lista ligada direto de indexação, Fácil de criar e usar acesso directo, pesquisa e classificação
pilha e fila projetado para LIFO / FIFO acesso directo, pesquisa e classificação
árvore binária velocidade de inserção e exclusão, velocidade de acesso, manter a ordem de classificação alguma sobrecarga

  • estruturas Fixas são mais rápidos / menor
  • Quando você estiver considerando-se você deve usar um resumo da estrutura de dados, você deve perguntar a si mesmo: o que possui o maior número de dados e o que mantém o mais frequentemente alteradas de dados?

comparação de estruturas de dados estáticas vs dinâmicas

esta comparação é usada no nosso manual de ciência da computação.

Static estrutura de dados Dinâmica de estruturas de dados
Ineficiente como a memória é alocada, que pode não ser necessário. eficiente como a quantidade de memória varia conforme necessário.
acesso rápido a cada elemento de dados como a localização da memória é fixada quando o programa é escrito. acesso mais lento a cada elemento como a localização da memória é alocada em tempo de execução.os endereços de memória atribuídos serão contíguos tão rapidamente quanto possível.os endereços de memória atribuídos podem estar fragmentados de forma mais lenta de acesso.
as estruturas são um tamanho fixo, tornando-as mais previsíveis para trabalhar. Por exemplo, eles podem conter um cabeçalho.as estruturas variam em tamanho, por isso é necessário haver um mecanismo para conhecer o tamanho da estrutura atual.
a relação entre os diferentes elementos dos dados não se altera. a relação entre os diferentes elementos dos dados irá mudar à medida que o programa é executado.

escolhendo qual a estrutura de dados a usar

Este gráfico é usado com enorme gratidão do Departamento de Ciência da Computação da Escola de Dartford.

escolhendo um fluxograma de tipo de dados.png

padrões

  • identifique uma situação que requer o uso de pensamento recursivo.
  • identifique o pensamento recursivo numa solução de problema especificada.
  • Trace um algoritmo recursivo para expressar uma solução para um problema.
  • descrever as características de um conjunto bidimensional.
  • construir algoritmos usando matrizes bidimensionais.
  • descreva as características e aplicações de uma pilha.
  • construir algoritmos usando os métodos de acesso de uma pilha.
  • descreva as características e aplicações de uma fila.
  • construir algoritmos usando os métodos de acesso de uma fila.
  • explique a utilização de matrizes como pilhas estáticas e filas.descreva as características e características de uma estrutura de dados dinâmica.
  • descreva como as listas ligadas funcionam logicamente.
  • Sketch linked lists (single, double and circular).descreva as características e aplicações de uma colecção.
  • construir algoritmos usando os métodos de acesso de uma coleção.discuta a necessidade de subprogramas e Colecções no âmbito de soluções programadas.
  • construir algoritmos utilizando subprogramas pré-definidos, matrizes unidimensionais e / ou colecções.
  • descreve como as árvores funcionam logicamente (tanto binário como não-binário).
  • Define os Termos: pai, filho-esquerdo, filho-direito, sub-árvore, raiz e folha.
  • Declare o resultado da subordem, postorder e Preorder Tree traversal.esboçam árvores binárias.
  • Define o termo estrutura de dados dinâmicos.
  • Compare a utilização de estruturas de dados estáticas e dinâmicas.
  • sugere uma estrutura adequada para uma dada situação.