✅ 10 Melhores Estruturas de Dados e Algoritmos C ++

Estruturas de dados e algoritmos C ++

Estruturas de dados e algoritmos C ++

Estruturas de dados e algoritmos C ++ - significa organizar ou organizar os elementos de uma maneira específica. Quando dizemos que precisamos organizar elementos, esses elementos podem ser organizados de diferentes formas. Por exemplo, as meias podem ser organizadas de várias maneiras diferentes. Você pode simplesmente mantê-lo em seu armário todo bagunçado. Ou você pode mantê-lo bem dobrado. A melhor maneira é dobrar e organizá-las com cores. Portanto, para procurar um par de meias específico, o terceiro arranjo é perfeito.

De maneira semelhante à organização de meias, os Dados também podem ser organizados de diferentes maneiras ou formas. Essas diferentes maneiras de organizar dados são chamadas de Estrutura de dados. Vamos ver uma definição formal de uma estrutura de dados e o básico sobre estruturas e algoritmos de dados.

Estruturas de dados e algoritmos C ++:

O modelo lógico ou matemático de uma organização específica de dados.

É uma maneira específica de organizar dados em um computador para que possam ser usados.

Da mesma forma que as meias; organização diferente das estruturas de dados da lista e algoritmos C ++ disponíveis é -

Matriz
Lista vinculada
Pilha
Fila
Árvore
Gráfico
Tabela de hash
Montão
Registros
Tabelas

Essas estruturas de dados e algoritmos C ++ são muito importantes durante a programação. Um bom programador sempre enfatiza a estrutura de dados e não o código. Cada linguagem de programação funciona em várias estruturas de dados e algoritmos em C ++. As estruturas de dados disponíveis em C ++ são as seguintes.

Matriz
Lista vinculada
Pilha
Fila
Árvore
Gráfico
Tabela de hash
Montão

Vamos discutir este um por um:

Matriz # 1

Matriz é um tipo mais simples de estruturas de dados e algoritmos C ++. A matriz é definida como uma coleção seqüencial de tamanho fixo de elementos de dados do mesmo tipo de dados. Por exemplo, a0 = 12, a1 = 21, a2 = 14, a3 = 15… .Podemos representar uma matriz unidimensional como mostrado na figura:

Onde

0, 1, 2, 3… ..n é chamado subscrito ou índice

a (1), a (2), … a (n) é chamado de variável subscrita

Pode ser unidimensional, bidimensional, tridimensional e assim por diante multidimensional.

Na matriz de memória armazena em locais de memória contíguos.

O endereço mais baixo corresponde ao primeiro elemento

O endereço mais alto corresponde ao último elemento

Podemos declarar uma matriz 1-D (1-Dimensional) em C ++ da seguinte maneira

dataType arrayName (arraySize);

Por exemplo, int num (5);

Inicializando matriz em C ++

num = (23, 10, 12, 3, 6);

Podemos combinar declaração e inicialização em uma única declaração da seguinte maneira.

int num = (23, 10, 12, 3, 6);

Quando queremos alocar dinamicamente o tamanho de uma matriz, devemos novo operador da seguinte maneira

int * a = novo int (tamanho);

A desvantagem da matriz é a inserção e exclusão de elementos é lenta, como na matriz ordenada e seu armazenamento de tamanho fixo.

# 2 Lista vinculada

Lista refere-se a uma coleção linear de itens. Uma lista vinculada é uma série de nós conectados (elemento de dados), como mostrado na figura 3. O nó do cabeçalho aponta para o primeiro nó da lista e o último nó aponta para o NULL indicado por Æ. Como cada nó contém pelo menos.

Uma parte dos dados (qualquer tipo)
Ponteiro para o próximo nó na lista

A lista vinculada é representada na memória usando duas matrizes. Uma matriz armazena as informações chamadas informações que são dados a serem armazenados e outras armazenam o campo do próximo ponteiro chamado LINK, que é o endereço do próximo nó.

Uma vantagem de uma lista vinculada sobre uma matriz:

Uma matriz e uma lista vinculada são representações de uma lista de itens na memória. A diferença importante é a maneira como os itens são vinculados. A principal limitação da matriz é a inserção do elemento na matriz e a exclusão do elemento da matriz ordenada é difícil, pois é necessário mover os elementos de descanso. A inserção e exclusão de elementos de uma lista vinculada são muito simples.

Nota: Torne - se um desenvolvedor C ++
Aprenda a projetar e personalizar programas para várias plataformas. Codifique, teste, depure e implemente aplicativos de software. Desenvolva habilidades para garantir que os aplicativos funcionem sem problemas.

Os tipos de lista vinculada são:

1. Lista vinculada simples : contém apenas um campo vinculado que contém o endereço do próximo nó na lista e as informações arquivadas que contêm as informações a serem armazenadas.

2. Lista vinculada circular única é apenas uma lista, mas o último nó da lista contém o endereço do primeiro nó em vez de nulo. Esse é o conteúdo do cabeçalho e o próximo campo do último nó é o mesmo.

3. A lista duplamente vinculada contém dois campos vinculados, anterior e seguinte. Um campo vinculado anteriormente que contém um endereço do nó anterior na lista e o próximo campo vinculado contém o endereço do próximo nó na lista e as informações arquivadas mantêm as informações como uma loja.

4. Lista vinculada circular dupla é uma lista duplamente vinculada, mas o próximo campo do último nó contém o endereço do primeiro nó em vez de nulo.

Cursos recomendados

Curso sobre VB.NET
Treinamento em programação de ciência de dados
Curso Online ISTQB
Curso de Treinamento Kali Linux

A implementação da lista vinculada no C ++ envolve a criação de um nó, a exclusão de um nó da lista, a inserção de um nó recém-criado na lista e a pesquisa de um nó com uma chave específica.

O código para criação do nó é fornecido da seguinte maneira:

Inserir um nó na lista envolve três casos

1. Inserir um nó no início significa inserir o nó recém-criado como nó inicial. Para inserir um nó no início, primeiro crie um novo nó e faça com que o novo aponte para o início antigo e atualize start para apontar para o novo nó, conforme mostrado na figura abaixo:

Código para inserir um nó no início:

2. Inserir um nó na cauda significa inserir o nó recém-criado como o último nó. Para inserir o nó como um nó final, é necessário criar um novo nó e fazer com que o último nó antigo aponte para o novo nó e atualize o final para apontar para o novo nó.

3. Inserir um nó em uma determinada posição envolve a criação de um novo nó temporário. Em seguida, é necessário encontrar a posição de inserção do nó recém-criado.

Código para inserção do nó em uma determinada posição:

A exclusão de um nó da lista envolve a remoção de um nó da lista existente. A exclusão do nó da lista de links é simples do que inserir um nó na lista. No código C ++, a exclusão do nó é fornecida da seguinte maneira:

Atravessar um nó com uma chave (valor) específica de uma lista pesquisará um nó da lista cujas informações corresponderão à chave de um determinado nó. O código C ++ a seguir percorrerá uma lista. estruturas de dados e algoritmos C ++

# 3 Pilha

Uma pilha é uma lista de elementos nos quais um elemento pode ser inserido ou excluído apenas em uma extremidade, chamada de topo da pilha. Considere o exemplo de uma torre de Hanói. Aqui, quando temos que inserir um disco, temos que inseri-lo somente a partir do topo e, da mesma forma, a remoção do disco ocorre somente a partir do topo.

A pilha usa o princípio LIFO significa que funciona na ordem Last in First Out. Esse é o último elemento adicionado à pilha é o primeiro elemento de remoção. Portanto, existem quatro operações básicas que podem ser executadas na pilha:

Isempty: Esta operação verifica se a pilha está vazia.
Push : Esta operação adiciona um novo item à pilha.
Pop: Esta operação remove um item do item de pilha adicionado mais recentemente.
Superior: Esta operação retorna o item que foi adicionado à pilha mais recentemente.

A figura a seguir é um exemplo da pilha em que a inserção e a remoção de uma pilha do item ocorrem na parte superior da pilha e em nenhum outro lugar.

Estouro de pilha

A condição resultante da tentativa de enviar um elemento para uma pilha cheia.

Stack underflow

A condição resultante da tentativa de exibir uma pilha vazia.

Aqui mostramos algumas operações push e pop na pilha. Suponha que inicialmente a pilha esteja vazia, então adicionamos F, A, M, R, N. Em seguida, pop duas vezes e pressione N, H, B, T, K, O, P.

Implementação da pilha:

Pode ser implementado usando uma matriz ou uma lista vinculada.

O código a seguir é mostrado como a pilha é implementada em C ++ usando Class. Aqui definimos uma classe denominada pilha, na qual criamos uma matriz denominada stick, com tamanho dinâmico e duas funções principais push e pop.

Estouro de pilha: quando superior> = tamanho-1

Estouro de pilha insuficiente: quando superior a 0

10 Melhores Estruturas de Dados e Algoritmos C ++ - Fundamentos