Estruturas de Dados

Caio de Freitas
Mind Map by Caio de Freitas, updated more than 1 year ago
Caio de Freitas
Created by Caio de Freitas over 6 years ago
37
6

Description

Tecnológico Tecnologia da Informação Mind Map on Estruturas de Dados, created by Caio de Freitas on 09/18/2015.

Resource summary

Estruturas de Dados
  1. 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
      3. Vetores
        1. Estrutura de dados linear que necessita de somente um índice para que seus elementos sejam indexados
          1. 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
          2. Matrizes
            1. Arranjo bidimensional ou multidimensional de alocação estática e sequencial
              1. É 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
              2. Listas Encadeadas
                1. Estrutura de dados dinâmica formada por uma sequência de elementos chamados nós
                    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
                          1. Também conhecido como ponteiro
                            1. 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ó
                              1. 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
                          2. A lista sem nós é chamada lista vazia ou nula
                        2. Cinco operações básicas
                          1. Criação
                            1. Busca
                              1. Inclusão
                                1. Remoção
                                  1. Destruição
                                  2. Pilhas
                                    1. Conjunto ordenado de Itens, no qual novos itens podem ser inseridos e eliminados em uma extremidade chamada Topo
                                      1. Lista LIFO (Last In First Out)
                                        1. Três operações básicas
                                          1. Push
                                            1. Insere elemento no topo da pilha
                                            2. Pop
                                              1. Remove elemento do topo da pilha
                                              2. Top
                                                1. ou Check - acessa e consulta o elemento do topo da pilha
                                              3. 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)
                                                  1. Lista FIFO (First In First Out)
                                                    1. Operações Básicas
                                                      1. Enqueue (Enfileirar)
                                                        1. Dequeue (Desenfileirar)
                                                        2. 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
                                                      2. 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ó
                                                              1. A partir de qualquer ponto é possível atingir qualquer outro ponto da lista
                                                                1. É preciso estabelecer um primeiro e um último nó por convenção, pois não possui primeiro e último nó natural
                                                                2. Lista Duplamente Encadeada
                                                                  1. Cada nó contém dois ponteiros, um para seu predecessor outro para seu sucessor
                                                                    1. Cada nó possui três campos: Campo "Info" (contém as informações armazenadas no nó), e os campos "Left" e "Right"),
                                                                  2. 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
                                                                          1. 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
                                                                        2. Á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ó
                                                                              1. A raiz tem nível 0
                                                                                1. 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
                                                                                  1. Árvore Estritamente Binária - os nós tem grau 0 ou 2
                                                                                    1. Á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
                                                                                    Show full summary Hide full summary

                                                                                    Similar

                                                                                    Memória Computacional
                                                                                    Filipe Gabriel
                                                                                    ITIL V3 - Processos
                                                                                    Rodrigo Ferreira
                                                                                    Servidores de Web e de Aplicação
                                                                                    Raphael Luiz Fonseca
                                                                                    Tecnologias de Informação e Comunicação
                                                                                    luccianafprado
                                                                                    Planejamento de TI
                                                                                    Willian da Silva2402
                                                                                    Projeto Livraria Banco de dados
                                                                                    Nathalia Souza
                                                                                    Banco de Dados
                                                                                    talyson.milan
                                                                                    Segurança da Informação
                                                                                    Gilvan Silva
                                                                                    Banco de dados e SGBD
                                                                                    bruno de assis
                                                                                    NORMALIZAÇÃO BANCO DE DADOS
                                                                                    Cristiano Gonçalves