Estruturas de Dados

Estruturas de Dados

1. dados

   • homogêneos
     • Só possuem um tipo básico de dados (Ex: inteiros)
       • Existem estruturas de dados que tratam de dados homogêneos. Ex: vetores
   • heterogêneos
     • Possuem mais de um tipo básico de dados (Ex: inteiros + caracteres)
       • Existem estruturas de dados que tratam de dados heterogêneos. Ex: Listas

2. Vetores

   • Estrutura de dados linear que necessita de somente um índice para que seus elementos sejam indexados
   • 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

3. Matrizes

   • Arranjo bidimensional ou multidimensional de alocação estática e sequencial
   • É 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

4. Listas Encadeadas

   • Estrutura de dados dinâmica formada por uma sequência de elementos chamados nós
     • Nó
       • Campo de informação
         • Armazena o real elemento da lista
       • Campo de endereço
         • 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
       • A lista sem nós é chamada lista vazia ou nula
   • Cinco operações básicas
     • Criação
     • Busca
     • Inclusão
     • Remoção
     • Destruição
   • Pilhas
     • Conjunto ordenado de Itens, no qual novos itens podem ser inseridos e eliminados em uma extremidade chamada Topo
     • Lista LIFO (Last In First Out)
     • Três operações básicas
       • Push
         • Insere elemento no topo da pilha
       • Pop
         • Remove elemento do topo da pilha
       • Top
         • ou Check - acessa e consulta o elemento do topo da pilha
     • Podem ser implementadas por meio de vetores (alocação estática) ou listas(alocação dinâmica de memória)
   • Filas
     • 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)
     • Lista FIFO (First In First Out)
     • Operações Básicas
       • Enqueue (Enfileirar)
       • Dequeue (Desenfileirar)
     • Deque (Double Ended Queue) - Filas duplamente encadeadas
       • Permite eliminação e inserção de itens em ambas as extremidades. Permitem priorização. É comum em sistemas distribuídos

5. Tipos

   • Lista Encadeada Linear; Lista ligada linear; Linked list
     • O campo próximo do último nó da lista contém o valor NULL
       • é usado para indicar o final de uma lista
   • Lista Circular (ou fechada)
     • O campo próximo do último nó contém um ponteiro para o primeiro nó
     • A partir de qualquer ponto é possível atingir qualquer outro ponto da lista
     • É preciso estabelecer um primeiro e um último nó por convenção, pois não possui primeiro e último nó natural
   • Lista Duplamente Encadeada
     • Cada nó contém dois ponteiros, um para seu predecessor outro para seu sucessor
     • Cada nó possui três campos: Campo "Info" (contém as informações armazenadas no nó), e os campos "Left" e "Right"),

6. Fragmentação (Desperdício de espaço disponível de memória)

   • Interna
     • O espaço é desperdiçado dentro dos blocos alocados
   • Externa
     • Vários blocos disponíveis pequenos e não contíguos. O espaço disponível é desperdiçado fora dos blocos alocados
     • Uma lista encadeada elimina o problema da fragmentação externa
       • O tamanho do arquivo não precisa ser conhecido antes de sua criação

7. Árvore

   • 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
     • Grau - quantidade de filhos de um nó
     • A raiz tem nível 0
     • Altura - Equivale ao nível máximo de seus nós
   • Árvore Binária - todos os nós tem grau 0, 1 ou 2
   • Árvore Estritamente Binária - os nós tem grau 0 ou 2
   • Árvore Binária completa - Todas as folhas estão no mesmo nível
     • Árvore binária completa com X folhas conterá (2x - 1) nós

Imagens e arquivos do mapa