Estruturas de Dados

dados
1. homogêneos
  1. Só possuem um tipo básico de dados (Ex: inteiros)
    1. Existem estruturas de dados que tratam de dados homogêneos. Ex: vetores
2. heterogêneos
  1. Possuem mais de um tipo básico de dados (Ex: inteiros + caracteres)
    1. Existem estruturas de dados que tratam de dados heterogêneos. Ex: Listas
Vetores
1. Estrutura de dados linear que necessita de somente um índice para que seus elementos sejam indexados
2. Possui alocação estática, com dados armazenados em posições contíguas na memória e permite acesso direto ou aleatório a seus elementos
Matrizes
1. Arranjo bidimensional ou multidimensional de alocação estática e sequencial
2. É definida com um tamanho fixo, todos os elementos são do mesmo tipo, cada célula contém somente um valor e os tamanhos dos valores são os mesmos
Listas Encadeadas
1. Estrutura de dados dinâmica formada por uma sequência de elementos chamados nós
  1. Nó
    1. Campo de informação
      1. Armazena o real elemento da lista
    2. Campo de endereço
      1. Contém o endereço do próximo nó da lista
        Também conhecido como ponteiro
        A lista ligada inteira é acessada a partir de um ponteiro externo que aponta para o primeiro nó na lista, i.e., contém o endereço do primeiro nó
        ponteiro externo é aquele que não está incluído dentro de nenhum nó. Em vez disso seu valor pode ser acessado diretamente, por referência a uma veriável
    3. A lista sem nós é chamada lista vazia ou nula
2. Cinco operações básicas
  1. Criação
  2. Busca
  3. Inclusão
  4. Remoção
  5. Destruição
3. Pilhas
  1. Conjunto ordenado de Itens, no qual novos itens podem ser inseridos e eliminados em uma extremidade chamada Topo
  2. Lista LIFO (Last In First Out)
  3. Três operações básicas
    1. Push
      1. Insere elemento no topo da pilha
    2. Pop
      1. Remove elemento do topo da pilha
    3. Top
      1. ou Check - acessa e consulta o elemento do topo da pilha
  4. Podem ser implementadas por meio de vetores (alocação estática) ou listas(alocação dinâmica de memória)
4. Filas
  1. Conjunto ordenado de itens a partir do qual podem se eliminar itens numa extremidade (início da fila), e inserir itens na outra extremidade (final da fila)
  2. Lista FIFO (First In First Out)
  3. Operações Básicas
    1. Enqueue (Enfileirar)
    2. Dequeue (Desenfileirar)
  4. Deque (Double Ended Queue) - Filas duplamente encadeadas
    1. Permite eliminação e inserção de itens em ambas as extremidades. Permitem priorização. É comum em sistemas distribuídos
Tipos
1. Lista Encadeada Linear; Lista ligada linear; Linked list
  1. O campo próximo do último nó da lista contém o valor NULL
    1. é usado para indicar o final de uma lista
2. Lista Circular (ou fechada)
  1. O campo próximo do último nó contém um ponteiro para o primeiro nó
  2. A partir de qualquer ponto é possível atingir qualquer outro ponto da lista
  3. É preciso estabelecer um primeiro e um último nó por convenção, pois não possui primeiro e último nó natural
3. Lista Duplamente Encadeada
  1. Cada nó contém dois ponteiros, um para seu predecessor outro para seu sucessor
  2. Cada nó possui três campos: Campo "Info" (contém as informações armazenadas no nó), e os campos "Left" e "Right"),
Fragmentação (Desperdício de espaço disponível de memória)
1. Interna
  1. O espaço é desperdiçado dentro dos blocos alocados
2. Externa
  1. Vários blocos disponíveis pequenos e não contíguos. O espaço disponível é desperdiçado fora dos blocos alocados
  2. Uma lista encadeada elimina o problema da fragmentação externa
    1. O tamanho do arquivo não precisa ser conhecido antes de sua criação
Árvore
1. Estrutura de dados hierárquica composta por um conjunto finito de elementos com um únicos elemento raiz, com zero ou mais sub-árvores ligadas a esse elemento raiz
  1. Grau - quantidade de filhos de um nó
  2. A raiz tem nível 0
  3. Altura - Equivale ao nível máximo de seus nós
2. Árvore Binária - todos os nós tem grau 0, 1 ou 2
3. Árvore Estritamente Binária - os nós tem grau 0 ou 2
4. Árvore Binária completa - Todas as folhas estão no mesmo nível
  1. Árvore binária completa com X folhas conterá (2x - 1) nós

Next up

Estruturas de Dados

Description

Resource summary

Media attachments

Similar

	Created by Caio de Freitas over 9 years ago