Estruturas de dados mais populares

O que é uma estrutura de dados?
Simplificando, uma estrutura de dados é um contêiner no qual os dados são armazenados em um layout específico (formato ou forma como são organizados na memória). Esse "layout" permite que a estrutura de dados seja eficaz em algumas operações e ineficaz em outras. Seu objetivo é entender as estruturas de dados para que você possa escolher a melhor estrutura de dados para o problema em questão.

Por que precisamos de estruturas de dados?
Como as estruturas de dados são usadas para armazenar dados de maneira organizada e, como os dados são o elemento mais importante da ciência da computação, o verdadeiro valor das estruturas de dados é óbvio.
Independentemente do problema que você resolva, você precisa lidar com os dados de uma maneira ou de outra - seja o salário de um funcionário, preços de ações, lista de compras ou mesmo uma lista telefônica simples.
Com base em diferentes cenários, os dados devem ser armazenados em um formato específico. Temos várias estruturas de dados que cobrem a necessidade de armazenar dados em diferentes formatos.


Estruturas de dados usadas com frequência
Vamos primeiro listar as estruturas de dados mais usadas e, em seguida, examiná-las uma a uma:
  • Matrizes - matrizes
  • Pilhas - Pilhas
  • Filas - Filas
  • Listas vinculadas - Listas relacionadas
  • Árvores - Árvores
  • Gráficos - gráficos
  • Tenta (são essencialmente árvores, mas ainda é bom nomeá-las separadamente). - prioridade
  • Tabelas Hash - tabelas de hash


Matrizes - matrizes
Uma matriz é a estrutura de dados mais simples e mais usada. Outras estruturas de dados, como pilhas e filas, são derivadas de matrizes.
Aqui está uma imagem de uma matriz simples de tamanho 4 contendo elementos (1, 2, 3 e 4).

imagem

Cada item de dados recebe um valor numérico positivo chamado índice, que corresponde à posição desse item na matriz. A maioria dos idiomas define o índice inicial de uma matriz como 0.

A seguir, dois tipos de matrizes:
  • Matrizes unidimensionais (como mostrado acima)
  • Matrizes multidimensionais (matrizes dentro de matrizes) Matrizes multidimensionais


. Operações básicas sobre matrizes
Inserir - insere um
. Elemento em um índice especificado
Apagar (Delete) - remove um elemento em um índice especificado.
Size - obter o número total de elementos em uma matriz.

Para auto-estudo:
1 Encontre o segundo elemento mínimo da matriz.
2. Os primeiros números inteiros não repetitivos na matriz.
3. Mesclar duas matrizes classificadas.
4. Reordene os valores positivos e negativos na matriz.

Pilhas
Todos conhecemos a famosa opção Desfazer (Cancelar), presente em quase todas as aplicações. Já se perguntou como isso funciona? A essência do mecanismo é que você salve os estados anteriores do seu trabalho (que são limitados por um determinado número) na memória, de modo que a última ação apareça primeiro. Isso não pode ser feito apenas com matrizes. É aí que a pilha é útil!

Um exemplo real de uma pilha é uma pilha de livros organizados verticalmente. Para obter um livro em algum lugar no meio, você precisa excluir todos os livros colocados em cima dele. Veja como o método LIFO (Last In First Out) funciona .
Aqui está uma imagem de uma pilha contendo três elementos de dados (1, 2 e 3), onde 3 está no topo e será excluído primeiro:



As operações básicas com pilhas:
Push - insere um elemento em cima de outros.
Pull (Pop) - retorna o elemento superior após a remoção da pilha.
Esvaziar? (IsEmpty) - retorna true (true) se a pilha estiver vazia.
Superior (Superior) - retorna o elemento superior sem excluir da pilha.

Para estudo independente:
1. Avalie a expressão do postfix usando a pilha.
2. Classifique os valores na pilha.
3. Verifique os colchetes balanceados na expressão.

Filas
Como uma pilha, uma fila é outra estrutura de dados linear na qual os itens são armazenados sequencialmente. A única diferença significativa entre a pilha e a fila é que, em vez de usar o método LIFO, a fila implementa um métodoFIFO, abreviação de First in First Out .
Um ótimo exemplo de linha da vida real: várias pessoas esperando na bilheteria. Se uma nova pessoa chegar, ela entrará na fila do final, e não do começo - e a pessoa em frente será a primeira a receber um ingresso e, portanto, sairá da fila.
Aqui está uma imagem de uma fila contendo quatro elementos de dados (1, 2, 3 e 4), onde 1 está no topo e será excluído primeiro:



Operações básicas com a fila:
Enfileirar - insere um elemento no final da fila.
Retirar da fila - exclui um item do início da fila.
Esvaziar? (IsEmpty) - retorna true (true) se a fila estiver vazia.
Superior (Superior) - retorna o primeiro elemento da fila.

Para estudo independente:
1. Implementação da pilha usando a fila.
2. Os primeiros k elementos inversos da fila.
3. Geração de números binários de 1 a n usando a fila.

Lista vinculada
Uma lista vinculada é outra importante estrutura de dados linear que, à primeira vista, pode parecer semelhante a matrizes, mas difere na alocação de memória, estrutura interna e como as operações básicas de inserção e exclusão são executadas.

Uma lista vinculada é como uma cadeia de nós, em que cada nó contém informações como dados e um ponteiro para o próximo nó da cadeia. Há um ponteiro de cabeçalho que aponta para o primeiro elemento da lista vinculada e, se a lista estiver vazia, simplesmente aponta para zero ou nada.

Listas vinculadas são usadas para implementar sistemas de arquivos, tabelas de hash e listas de adjacências.

Aqui está uma representação visual da estrutura interna de uma lista vinculada:



A seguir estão os tipos de lista vinculada:
  • Lista de links únicos (unidirecional)
  • Lista duplamente vinculada (bidirecional)


Operações básicas em uma lista vinculada
InsertAtEnd - Insere um item no final de uma lista vinculada.
InsertB Start (InsertAtHead) - Insere um item no início de uma lista vinculada.
Excluir - remove este item da lista vinculada.
DeleteBeginning (DeleteAtHead) - exclui o primeiro elemento da lista vinculada.
Pesquisar - retorna o item encontrado da lista vinculada.
Esvaziar? (IsEmpty) - retorna true (true) se a lista vinculada estiver vazia.

Para estudo independente:
1. Vire a lista vinculada (inverter, inverter, exibir para trás).
2. Defina um loop em uma lista vinculada.
3. Retorne o Nésimo nó do final na lista vinculada.
4. Remova duplicatas da lista vinculada.

Gráficos Os
gráficos são uma coleção de nós conectados entre si na forma de uma rede. Nós também são chamados vértices. O par (x, y) é chamado de aresta, o que indica que o vértice x está conectado ao vértice y. Uma aresta pode conter peso / custo, mostrando quanto custa para mover do topo x para y.



Tipos de gráficos:
  • Gráfico não direcionado
  • Gráfico direcionado


Nas linguagens de programação, os gráficos são representados de duas formas:


A seguir, é apresentado um exemplo de uma lista de adjacências adjacentes (gráfico não direcionado).



Exemplos conhecidos de mover algoritmos ao longo de gráficos:


Para estudo independente:
1. Implementação da largura e profundidade Primeira pesquisa
2. Verifique se o gráfico é uma árvore ou não.
3. Contando o número de arestas no gráfico.
4. Encontre o caminho mais curto entre os picos.

Árvores
Uma árvore é uma estrutura hierárquica de dados que consiste em vértices (nós) e arestas que os conectam. As árvores parecem gráficos, mas o ponto principal que distingue uma árvore de um gráfico é que um loop não pode existir em uma árvore. Uma árvore é um gráfico rasgado.

As árvores são amplamente usadas em inteligência artificial e algoritmos complexos para fornecer um mecanismo de armazenamento eficiente para algoritmos de solução de problemas.

Aqui está uma imagem de uma árvore simples e os termos básicos usados ​​na estrutura de dados da árvore:



Existem tipos de árvore:

  • N-
  • (Balanced Tree)
  • (Binary Tree)
  • (Binary Search Tree)
  • AVL
  • - (Red Black Tree)
  • 2–3


Pelo exposto, a Árvore Binária e a Árvore de Pesquisa Binária são as árvores mais usadas.

Para estudo independente:
1. Encontre a altura da árvore binária.
2. Encontre o k-ésimo valor máximo na árvore de pesquisa binária.
3. Encontre os nós a uma distância de "k" da raiz.
4. Encontre os ancestrais do nó especificado na árvore binária.

Exemplos práticos:

1. Facebook: cada usuário é um vértice e duas pessoas são amigas quando há uma borda entre dois vértices. Também recomendações para amigos são calculadas com base na teoria dos grafos.

2. Google Maps: locais diferentes são representados por picos e estradas são representadas por arestas; a teoria dos grafos é usada para encontrar o caminho mais curto entre dois picos.

3. Redes de transporte: neles os picos são os cruzamentos de estradas e nervuras - esses são os segmentos de estradas entre seus cruzamentos.

4. Representação de estruturas moleculares onde os vértices são moléculas e as bordas são as ligações entre as moléculas.

5. Processos de sinalização discretos em gráficos. ( e há um bom artigo aqui também, e este ao mesmo tempo )

6. Observações empíricas mostram que a maioria dos genes é regulada por um pequeno número de outros genes, geralmente menos de dez. Portanto, uma rede genética pode ser considerada como um gráfico esparso, ou seja, um gráfico no qual um nó está conectado a vários outros nós. Se gráficos orientados (acíclicos) ou não direcionados estiverem saturados com probabilidades, o resultado será modelos gráficos orientados probabilisticamente e modelos gráficos não direcionados probabilísticos, respectivamente.

7. Teoria da expansão de cluster da Mayer da função de volatilidadeO gás (Z) na termodinâmica requer o cálculo de duas, três, quatro condições e assim por diante. Existe uma maneira sistemática de fazer isso combinatoriamente com gráficos, e isso ajuda a descobrir a conectividade desses gráficos. Conhecer a teoria dos grafos pode ser útil quando você deseja resumir um subconjunto desses diagramas.

8. Coloração de mapa: o famoso teorema de quatro cores declara que você sempre pode colorir corretamente as regiões do mapa, para que duas regiões adjacentes não sejam atribuídas à mesma cor usando no máximo quatro cores diferentes. Nesse modelo, regiões com cores são nós e adjacências são arestas do gráfico.

9. A tarefa com três chalés é um conhecido quebra-cabeça matemático. Ele pode ser formulado da seguinte forma: Três chalés em um avião (ou esfera), cada um dos quais deve estar conectado a empresas de gás, água e eletricidade. O problema é resolvido usando um gráfico no avião .

10. Procure o centro do gráfico: para cada vértice, encontre o comprimento do caminho mais curto para o vértice mais distante. O centro do gráfico é o vértice para o qual esse valor é mínimo. Isso é importante para o planejamento arquitetônico de assentamentos nos quais um hospital, corpo de bombeiros ou esquadra de polícia deve estar localizado, de modo que o ponto mais distante seja o mais próximo possível.

Para os amantes de C #, como eu, um link com exemplos de código C # graficamente é aqui. Para a biblioteca mais avançada com a implementação de gráficos em C ++ aqui . Para os fãs de IA e Skynet, pise aqui .

Sequências (Trie)
Sequências, também conhecidas como árvores com prefixos (Prefix Trees), são uma estrutura de dados semelhante a uma árvore que é eficaz o suficiente para resolver problemas associados a seqüências de caracteres. Eles fornecem uma pesquisa rápida e são usados ​​principalmente para pesquisar palavras em um dicionário, frases automáticas em um mecanismo de pesquisa e até mesmo para roteamento IP.

Aqui está uma ilustração de como as três palavras "top", "assim" e "deles" são armazenadas em Prioridade:



As palavras são armazenadas de cima para baixo, onde os nós verdes "p", "s" e "r" apontam para o final de "top", " assim ”e“ deles ”, respectivamente.

Para estudo independente:
1. Conte o número total de palavras na Prioridade.
2. Imprima todas as palavras armazenadas na Prioridade.
3. Classificando elementos da matriz usando Prioridade.
4. Gere palavras do dicionário usando Filas.
5. Crie o dicionário T9.

Exemplos práticos de uso:
1. Seleção do dicionário ou conclusão ao digitar uma palavra.
2. Pesquise contatos no telefone ou no dicionário telefônico.

Tabela de hash
Hashing é um processo usado para identificar objetos com exclusividade e armazenar cada objeto por um índice exclusivo pré-calculado chamado de "chave". Assim, o objeto é armazenado na forma de um par de valores-chave e uma coleção desses elementos é chamada de dicionário. Cada objeto pode ser encontrado usando essa chave.

Existem diferentes estruturas de dados baseadas em hash, mas a tabela de hash é a estrutura de dados mais usada. Uma tabela de hash é usada quando você precisa acessar elementos com uma chave e pode determinar o valor útil da chave.

As tabelas de hash geralmente são implementadas usando matrizes.

O desempenho do hash de uma estrutura de dados depende desses três fatores:
  • Função hash
  • Tamanho da tabela de hash
  • Método de processamento de colisão


Aqui está uma ilustração de como um hash é exibido em uma matriz. O índice dessa matriz é calculado usando uma função hash.



Para estudo independente:
1. Encontre pares simétricos na matriz.
2. Siga o caminho completo da viagem.
3. Descubra se a matriz é um subconjunto de outra matriz.
4. Verifique se as matrizes fornecidas são disjuntas.

Abaixo está um exemplo de código de uso da tabela de hash em .Net

static void Main(string[] args)
        {
            Hashtable ht = new Hashtable
            {
                { "001", "Zara Ali" },
                { "002", "Abida Rehman" },
                { "003", "Joe Holzner" },
                { "004", "Mausam Benazir Nur" },
                { "005", "M. Amlan" },
                { "006", "M. Arif" },
                { "007", "Ritesh Saikia" }
            };

            if (ht.ContainsValue("Nuha Ali"))
            {
                Console.WriteLine("    !");
            }
            else
            {
                ht.Add("008", "Nuha Ali");
            }

            //   .
            ICollection key = ht.Keys;

            foreach (string k in key)
            {
                Console.WriteLine(k + ": " + ht[k]);
            }
            Console.ReadKey();
        }


Exemplos práticos:

1. O jogo "Life". Nele, um hash é um conjunto de coordenadas de cada célula viva.

2. Uma versão primitiva do mecanismo de pesquisa do Google pode mapear todas as palavras existentes em um conjunto de URLs onde elas ocorrem. Nesse caso, as tabelas de hash são usadas duas vezes: na primeira vez para mapear palavras para conjuntos de URLs e, na segunda vez, para salvar cada conjunto de URLs.

3. Ao implementar uma estrutura / algoritmo de árvore de múltiplas vias, tabelas de hash podem ser usadas para acesso rápido a qualquer elemento filho do nó interno.

4. Ao escrever um programa para jogar xadrez, é muito importante acompanhar as posições que foram avaliadas anteriormente, para que você possa voltar quando precisar delas novamente, se necessário.

5. Qualquer linguagem de programação precisa mapear o nome da variável para seu endereço na memória. De fato, em linguagens de script como Javascript e Perl, os campos podem ser adicionados ao objeto dinamicamente, o que significa que os próprios objetos são como mapas de hash.

All Articles