Menu

Introdução às estruturas de dados em C ++

introduction data structures c

Experimente Nosso Instrumento Para Eliminar Problemas

Um tutorial introdutório sobre estruturas de dados em C ++.

“A estrutura de dados pode ser definida como uma coleção organizada de dados que ajuda um programa a acessar os dados de forma eficiente e rápida para que todo o programa possa funcionar de maneira eficiente. “

Sabemos que, no mundo da programação, os dados são o centro e tudo gira em torno dos dados. Precisamos fazer todas as operações de dados, incluindo armazenamento, pesquisa, classificação, organização e acesso a dados de forma eficiente e só então nosso programa pode ter sucesso.

=> Veja aqui para explorar a lista completa de tutoriais C ++.

Introdução às estruturas de dados em C ++ (1)

O que você aprenderá:

Visão geral

Precisamos encontrar a maneira mais eficiente de armazenar dados que possa nos ajudar a construir soluções dinâmicas. A estrutura de dados nos ajuda a construir tais soluções.

Ao organizar ou organizar os dados em estruturas, precisamos garantir que o arranjo represente quase um objeto do mundo real. Em segundo lugar, esse arranjo deve ser simples o suficiente para que qualquer pessoa possa acessá-lo facilmente e processá-lo sempre que necessário.

Nesta série, aprenderemos em detalhes sobre estruturas de dados básicas e avançadas. Também aprenderemos em detalhes sobre as várias técnicas de pesquisa e classificação que podem ser executadas em estruturas de dados.

Depois de aprender esta série de tutoriais, o leitor deve se familiarizar bem com cada estrutura de dados e sua programação.

Vejamos alguns dos termos que usamos ao lidar com estruturas de dados:

Por exemplo,pegue um aluno específico. Um aluno pode ter os seguintes detalhes representados pictoricamente.

Exemplo - Estrutura de Dados

  • Dados: É o valor elementar. Na figura acima, o nº do rolo do aluno pode ser um dado.
  • Item do grupo: Este é o item de dados que possui mais de um subitens. Na figura acima, Student_name tem o nome e o sobrenome.
  • Registro: É uma coleção de itens de dados. No exemplo acima, itens de dados como nº da lista do aluno, nome, classe, idade, série, etc. formam um registro juntos.
  • Entidade: É uma classe de registros. No diagrama acima, o aluno é uma entidade.
  • Atributo ou campo: As propriedades de uma entidade são chamadas de atributos e cada campo representa um atributo.
  • Arquivo: Um arquivo é uma coleção de registros. No exemplo acima, uma entidade de estudante pode ter milhares de registros. Assim, um arquivo conterá todos esses registros.

O leitor deve estar ciente de todos esses termos, pois os usamos de vez em quando quando usamos várias estruturas de dados.

As estruturas de dados são o principal bloco de construção do programa e, como programadores, devemos ter cuidado com a estrutura de dados a ser usada. A estrutura de dados exata a ser usada é a decisão mais difícil de tomar no que diz respeito à programação.

Vamos discutir a necessidade de estrutura de dados em Programação.

Necessidade de estrutura de dados na programação

À medida que a quantidade de dados continua a crescer, os aplicativos tornam-se cada vez mais complexos, portanto, torna-se difícil para o programador gerenciar esses dados tão bem quanto o software.

Normalmente, a qualquer momento, o aplicativo pode enfrentar os seguintes obstáculos:

# 1) Pesquisando grandes quantidades de dados: Com uma grande quantidade de dados sendo processados ​​e armazenados, a qualquer momento nosso programa pode ser solicitado a pesquisar um dado específico. Se os dados forem muito grandes e não organizados corretamente, levará muito tempo para obter os dados necessários.

Quando usamos estruturas de dados para armazenar e organizar dados, a recuperação de dados se torna mais rápida e fácil.

# 2) Velocidade de processamento: Dados desorganizados podem resultar em baixa velocidade de processamento, pois muito tempo será perdido na recuperação e acesso aos dados.

Se organizarmos os dados corretamente em uma estrutura de dados durante o armazenamento, não perderemos tempo em atividades como recuperar, organizá-los sempre. Em vez disso, podemos nos concentrar no processamento de dados para produzir a saída desejada.

# 3) Solicitações simultâneas múltiplas: Muitos aplicativos hoje em dia precisam fazer uma solicitação simultânea de dados. Essas solicitações devem ser processadas com eficiência para que os aplicativos funcionem sem problemas.

Se nossos dados forem armazenados apenas aleatoriamente, não poderemos processar todas as solicitações simultâneas simultaneamente. Portanto, é uma decisão sábia organizar os dados em uma estrutura de dados adequada de modo a minimizar o tempo de resposta das solicitações simultâneas.

Classificação da estrutura de dados

As estruturas de dados usadas em C ++ podem ser classificadas da seguinte maneira.

Classificação de estruturas de dados

Uma estrutura de dados é uma forma de organizar os dados. Portanto, podemos classificar as estruturas de dados conforme mostrado em estruturas de dados primitivas ou padrão e estruturas de dados não primitivas ou definidas pelo usuário.

Vimos todos os tipos de dados suportados em C ++. Como esta também é uma forma de organizar os dados, dizemos que é uma estrutura de dados padrão.

As outras estruturas de dados não são primitivas e o usuário deve defini-las antes de usá-las em um programa. Essas estruturas de dados definidas pelo usuário são classificadas em estruturas de dados lineares e não lineares.

Estrutura de Dados Lineares

As estruturas de dados lineares têm todos os seus elementos organizados de forma linear ou sequencial. Cada elemento em uma estrutura de dados linear tem um predecessor (elemento anterior) e um sucessor (próximo elemento)

As estruturas de dados lineares são divididas em estruturas de dados estáticas e dinâmicas. As estruturas de dados estáticas geralmente têm um tamanho fixo e, uma vez que seu tamanho é declarado no momento da compilação, não pode ser alterado. Estruturas de dados dinâmicas podem mudar seu tamanho dinamicamente e se acomodar.

O exemplo mais popular de estrutura de dados estáticos lineares é um array.

Variedade

Uma matriz é uma coleção sequencial de elementos do mesmo tipo. Cada elemento da matriz pode ser acessado usando sua posição na matriz, chamada de índice ou subscrito da matriz. O nome da matriz aponta para o primeiro elemento da matriz.

variedade

O mostrado acima é uma matriz 'a' de n elementos. Os elementos são numerados de 0 a n-1. O tamanho da matriz (n neste caso) também é chamado de dimensão da matriz. Conforme mostrado na figura acima, o nome da matriz aponta para o primeiro elemento da matriz.

A matriz é a estrutura de dados mais simples e é eficiente, pois os elementos podem ser acessados ​​usando subscritos diretamente. Se quisermos acessar o terceiro elemento do array, basta dizer a (2).

Mas adicionar ou excluir os elementos do array é difícil. Portanto, usamos arrays apenas em aplicativos simples ou em aplicativos onde a adição / exclusão de elementos não é necessária.

As estruturas de dados dinâmicos lineares populares são lista vinculada, pilha e fila.

Lista Ligada

Uma lista vinculada é uma coleção de nós. Cada nó contém o elemento de dados e um ponteiro para o próximo nó. Os nós podem ser adicionados e excluídos dinamicamente. Uma lista vinculada pode ser uma lista unida individualmente em que cada nó tem um ponteiro para o próximo elemento apenas. Para o último elemento, o próximo ponteiro é definido como nulo.

Na lista duplamente vinculada, cada nó possui dois ponteiros, um para o nó anterior e o segundo para o próximo nó. Para o primeiro nó, o ponteiro anterior é nulo e para o último nó, o próximo ponteiro é nulo.

Lista Ligada

Conforme mostrado na figura acima, o início da lista é chamado de cabeça, enquanto o final da lista encadeada é chamado de cauda. Conforme mostrado acima, cada nó possui um ponteiro para o próximo elemento. Podemos facilmente adicionar ou excluir elementos mudando o ponteiro para o próximo nó.

Pilha

Pilha é uma estrutura de dados linear na qual os elementos podem ser adicionados ou removidos apenas de uma extremidade conhecida como “Topo” da pilha. Desta forma, a pilha exibe o tipo de acesso à memória LIFO (Last In, First Out).

Pilha

Conforme mostrado acima, os elementos da pilha são sempre adicionados em uma extremidade e também removidos da mesma extremidade. Isso é chamado de “topo” da pilha. Quando um elemento é adicionado, ele é empurrado para baixo na pilha e o topo da pilha é incrementado em uma posição.

Da mesma forma, quando um elemento é removido, o topo da pilha diminui. Quando uma pilha está vazia, o topo da pilha é definido como -1. Existem duas operações principais “Empurrar” e “Pop” que são realizadas na pilha.

Fila

A fila é mais uma estrutura de dados linear na qual os elementos são adicionados em uma extremidade chamada “traseira” e excluídos de outra extremidade chamada “frontal”. Queue demonstra FIFO (First In, First Out), o tipo de metodologia de acesso à memória.

Fila

O diagrama acima mostra uma fila com extremidades traseiras e frontais. Quando a fila está vazia, os ponteiros traseiro e frontal coincidem.

Estrutura de dados não linear

Em estruturas de dados não lineares, os dados não são organizados sequencialmente, em vez disso, são organizados de forma não linear. Os elementos são conectados uns aos outros em um arranjo não linear.

Estruturas de dados não lineares são árvores e gráficos.

aplicativo grátis para agendar postagens instagram

Árvores

Árvores são estruturas de dados multinível não lineares que possuem uma relação hierárquica entre os elementos. Os elementos da árvore são chamados de nós.

O nó no topo é chamado de raiz da árvore. A raiz pode ter um ou mais nós filhos. Os nós subsequentes também podem ter um ou mais nós filhos. Os nós que não possuem nós filhos são chamados de nós folha.

Árvores

No diagrama acima, mostramos uma árvore com 6 nós. Destes três nós são os nós folha, um nó superior é a raiz e os outros são nós filhos. Dependendo do número de nós, nós filhos, etc. ou da relação entre os nós, temos diferentes tipos de árvores.

Gráficos

O gráfico é um conjunto de nós chamados vértices conectados uns aos outros por meio dos links chamados Arestas . Os gráficos podem ter um ciclo dentro dele, ou seja, o mesmo vértice pode ser um ponto inicial, bem como o ponto final de um determinado caminho. As árvores nunca podem ter um ciclo.

Gráficos

O diagrama acima é um gráfico não direcionado. Também podemos ter gráficos direcionados onde representamos as arestas usando setas direcionadas.

Operações na estrutura de dados

Todas as estruturas de dados realizam várias operações em seus elementos.

Eles são comuns a todas as estruturas de dados e estão listados a seguir:

  • Procurando: Esta operação é realizada para pesquisar um determinado elemento ou chave. Os algoritmos de pesquisa mais comuns são a pesquisa sequencial / linear e a pesquisa binária.
  • Ordenação: A operação de classificação envolve a organização dos elementos em uma estrutura de dados em uma ordem específica crescente ou decrescente. Existem vários algoritmos de classificação disponíveis para estruturas de dados. Os mais populares entre eles são Quicksort, Selection sort, Merge sort, etc.
  • Inserção: A operação de inserção trata da adição de um elemento à estrutura de dados. Esta é a operação mais importante e, como resultado da adição de um elemento, a organização muda e precisamos cuidar para que a estrutura de dados permaneça intacta.
  • Eliminação: A operação de exclusão remove um elemento da estrutura de dados. As mesmas condições que devem ser consideradas para a inserção devem ser atendidas no caso da operação de exclusão.
  • Atravessando: Dizemos que percorremos uma estrutura de dados quando visitamos cada um dos elementos da estrutura. O cruzamento é necessário para realizar certas operações específicas na estrutura de dados.

Em nossos tópicos subsequentes, aprenderemos primeiro as várias técnicas de pesquisa e classificação a serem realizadas em estruturas de dados.

Vantagens da estrutura de dados

  • Abstração: As estruturas de dados são frequentemente implementadas como tipos de dados abstratos. Os usuários apenas acessam sua interface externa sem se preocupar com a implementação subjacente. Assim, a estrutura de dados fornece uma camada de abstração.
  • Eficiência: A organização adequada dos dados resulta em acesso eficiente aos dados, tornando os programas mais eficientes. Em segundo lugar, podemos selecionar a estrutura de dados adequada, dependendo de nossos requisitos.
  • Reutilização: Podemos reutilizar as estruturas de dados que projetamos. Eles também podem ser compilados em uma biblioteca e distribuídos ao cliente.

Conclusão

Com isso, concluímos este tutorial de introdução às estruturas de dados. Apresentamos cada uma das estruturas de dados resumidamente neste tutorial.

Em nossos tutoriais subsequentes, exploraremos mais sobre as estruturas de dados junto com as várias técnicas de pesquisa e classificação.

=> Clique aqui para ver a série de treinamento Absolute C ++.

Leitura recomendada

^