Cada vez mais, noto que as pessoas autodidatas modernas realmente não têm material. Todo mundo conhece idiomas, mas pouco básico, como tipos de dados ou algoritmos. Um pouco sobre os tipos de dados.
Em 1976, o cientista suíço
Nicklaus Wirth escreveu o livro
Algoritmos + estruturas de dados = programas.Mais de 40 anos depois, essa equação ainda é verdadeira. E se você é autodidata e repassa o artigo por um longo tempo em programação, pode fazê-lo na diagonal. Você pode codificar o café.
O artigo também terá perguntas que você poderá ouvir na entrevista.
O que é uma estrutura de dados?
Uma estrutura de dados é um contêiner que armazena dados em um layout específico. Esse "layout" permite que a estrutura de dados seja eficaz em algumas operações e ineficaz em outras.
Quais existem?
Elementos
lineares formam uma sequência ou uma lista linear, ignorando os nós é linear. Exemplos: matrizes. Lista vinculada, pilhas e filas.
Não linear , se o desvio de nós for não linear e os dados não forem seqüenciais. Exemplo: gráfico e árvores.
Estruturas de dados básicas.
- Matrizes
- Pilhas
- Filas
- Listas Relacionadas
- Conta
- Árvores
- Prefixo de árvores
- Hash da tabela
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.
Imagem de uma matriz simples de tamanho 4 contendo elementos (1, 2, 3 e 4).
Cada item de dados recebe um valor numérico positivo (índice), que corresponde à posição do item na matriz. A maioria dos idiomas define o índice inicial de uma matriz como 0.
Existem
Unidimensional , como mostrado acima.
Multidimensional , matrizes dentro de matrizes.
Operações básicas
- Inserir insere um elemento em um determinado índice
- Get-retorna um elemento em um determinado índice
- Excluir - excluir um item em um determinado índice
- Tamanho - obtenha o número total de elementos na matriz
Perguntas
- Encontre o segundo elemento mínimo da matriz
- Os primeiros números inteiros não repetitivos em uma matriz
- Mesclar duas matrizes classificadas
- Reordenando valores positivos e negativos em uma matriz
Pilhas
Uma pilha é um tipo de dados abstrato, que é uma lista de elementos organizados de acordo com o princípio LIFO (último a entrar, primeiro a sair, último a entrar, primeiro a sair).
Essas não são matrizes. Esta é a vez.
Inventado por Alan Thuring.Um exemplo de pilha seria um monte de livros organizados verticalmente. Para obter o livro, que fica em algum lugar no meio, você precisará excluir todos os livros colocados nele. É assim que o método LIFO (Last In First Out) funciona. A função "Cancelar" nos aplicativos funciona no LIFO.
A imagem da pilha, em três elementos (1, 2 e 3), onde 3 está no topo e será excluído primeiro.
Operações básicas
- Push insere um item na parte superior
- Retorna pop o elemento superior após remover da pilha
- isEmpty-retorna true se a pilha estiver vazia
- Top - retorna o elemento top sem excluir da pilha
Perguntas
- Implementar uma fila usando a pilha
- Classificar valores na pilha
- Implementando duas pilhas em uma matriz
- Inverter uma string usando uma pilha
Filas
Como as pilhas, uma fila armazena um elemento de maneira seqüencial. Uma diferença significativa da pilha é o uso de FIFO (primeiro a entrar) em vez de LIFO.
Um exemplo de linha é uma linha de pessoas. O último levou o último e você o fará, e o primeiro a deixará em primeiro lugar.
A imagem da fila, em quatro elementos (1, 2, 3 e 4), onde 1 está no topo e será excluído primeiro
Operações básicas
- Enfileirar—) - insere um elemento no final da fila
- Dequeue () - remove um elemento do início da fila
- isEmpty () - retorna true se a fila estiver vazia
- Top () - retorna o primeiro elemento da fila
Perguntas
- Implementar uma pilha usando uma fila
- Inverta os primeiros N elementos de uma fila
- Gerando números binários de 1 a N usando uma fila
Lista vinculada
Uma lista vinculada é uma matriz em que cada elemento é um objeto separado e consiste em dois elementos - dados e um link para o próximo nó.
A principal vantagem sobre a matriz é a flexibilidade estrutural: a ordem dos elementos da lista vinculada pode não coincidir com a ordem da localização dos elementos de dados na memória do computador, e a ordem de passagem da lista é sempre explicitamente determinada por seus relacionamentos internos.
Existem
Unidirecional , cada nó armazena o endereço ou link para o próximo nó na lista e o último nó tem o próximo endereço ou link como NULL.
1-> 2-> 3-> 4-> NULL
Bidirecional , dois links associados a cada nó, um dos pontos fortes para o próximo nó e um para o nó anterior.
NULL <-1 <-> 2 <-> 3-> NULL
Circular , todos os nós estão conectados para formar um círculo. No final, não há NULL. Uma lista vinculada cíclica pode ser uma lista vinculada cíclica simples ou dupla.
1-> 2-> 3-> 1
A lista unidirecional linear mais comum. Um exemplo é um sistema de arquivos.
Operações básicas
- InsertAtEnd - Insira o item especificado no final da lista.
- InsertAtHead - Insere um item no topo da lista
- Excluir - remove o item especificado da lista.
- DeleteAtHead - exclui o primeiro elemento da lista
- Pesquisa - retorna o item especificado da lista
- isEmpty - retorna True se a lista vinculada estiver vazia
Perguntas
- Reverso da lista vinculada
- Definindo um loop em uma lista vinculada
- Retornar N item do final na lista vinculada
- Remover duplicatas de uma lista vinculada
Conta
Um gráfico é um conjunto de nós (vértices) conectados entre si na forma de uma rede por arestas (arcos).
Existem
Orientadas , as nervuras são direcionais, isto é, existe apenas uma direção disponível entre dois vértices conectados.
Desorientado , para cada uma das costelas você pode ir nas duas direções.
Misto
Encontrado em formas como
- Matriz de adjacência
- Lista de adjacências
Algoritmos gerais de passagem de gráfico
- Pesquisa por largura - rastreamento no nível
- Pesquisa em profundidade - atravessando os picos
Perguntas
- Implementar pesquisa em largura e profundidade
- Verifique se o gráfico é uma árvore ou não
- Contar o número de arestas em um gráfico
- Encontre o caminho mais curto entre dois picos
Árvores
Uma árvore é uma estrutura de dados hierárquica composta por nós (vértices) e arestas (arcos). As árvores são essencialmente gráficos conectados sem loops.
Estruturas de árvores em todos os lugares. Todo mundo conhece a árvore de habilidades nos jogos.
Árvore simples
Tipos de árvore
A árvore binária é a mais comum.
“Uma árvore binária é uma estrutura hierárquica de dados na qual cada nó tem um valor (também é a chave neste caso) e faz referência aos descendentes esquerdo e direito. »- ProcsTrês maneiras de contornar uma árvore
- Em ordem direta (de cima para baixo) - o prefixo.
- Em ordem simétrica (da esquerda para a direita) - forma de infixo.
- Na ordem inversa (de baixo para cima) - formulário postfix.
Perguntas
- Encontre a altura de uma árvore binária
- Encontre o N menor item em uma árvore de pesquisa binária
- Encontre nós à distância N da raiz
- Encontre ancestrais do nó N na árvore binária
Trie (árvore de prefixo)
Uma espécie de árvore para seqüências de caracteres, pesquisa rápida. Dicionários T9
É assim que essa árvore armazena as palavras “top”, “assim” e “deles”.
As palavras são armazenadas de cima para baixo, os nós de cor verde "p", "s" e "r" apontam para o final de "topo", "assim" e "seus", respectivamente.
Perguntas
- Conte o número total de palavras
- Imprimir todas as palavras
- Classificar elementos da matriz da árvore de prefixos
- Criar dicionário T9
Hash da tabela
Hashing é um processo usado para identificar objetos de forma exclusiva e armazenar cada objeto em um índice exclusivo pré-calculado (chave).
Um objeto é armazenado como um par de valores-chave e uma coleção desses elementos é chamada de dicionário. Cada objeto pode ser encontrado usando essa chave.
Em essência, essa é uma matriz na qual a chave é representada como uma função hash.
O desempenho de hash depende de
- Funções de hash
- Tamanho da tabela de hash
- Métodos de gerenciamento de colisão
Um exemplo de correspondência de hash em uma matriz. O índice desta matriz é calculado através de uma função hash.
Perguntas
- Encontre pares simétricos em uma matriz
- Descubra se uma matriz é um subconjunto de outra matriz
- Descrever hash aberto
Lista de recursos
Em vez de uma conclusão
O material é tão interessante quanto as próprias línguas. Talvez alguém veja as estruturas básicas que lhe são familiares e se interesse.
Obrigado pela leitura. Espero que não perca tempo =)
PS: Peço desculpas, como se viu, a tradução do artigo já estava aqui e, muito recentemente, eu esqueci.
Se estiver interessado,
aqui está ela , graças
Hokum , terei mais cuidado.