O que são estruturas de dados em C e como usá-las?

Introdução

Para começar, uma estrutura de dados é uma coleção de itens de dados que são mantidos juntos sob um nome ou título e é uma maneira específica de armazenar e reunir os dados para que os dados possam ser usados ​​com eficiência.

Tipos

Estruturas de dados são predominantes e usadas em quase todos os sistemas de software. Alguns dos exemplos mais comuns de Estruturas de Dados são matrizes, filas, pilhas, listas vinculadas e árvores.

Formulários

No projeto de compiladores, sistemas operacionais, criação de bancos de dados, aplicativos de Inteligência Artificial e muito mais.

Classificação

As estruturas de dados são classificadas em duas categorias: estruturas de dados primitivas e estruturas de dados não primitivas.

1. Primitivo: São os tipos de dados básicos que são suportados por uma linguagem de programação. Um exemplo comum dessa classificação são números inteiros, caracteres e booleanos.

2. Não Primitivo: Essas categorias de estruturas de dados são criadas usando estruturas de dados primitivas. Os exemplos incluem pilhas vinculadas, listas vinculadas, gráficos e árvores.

Matrizes

Uma matriz é uma coleção simples de elementos de dados que possuem o mesmo tipo de dados. Isso significa que uma matriz de inteiros do tipo só pode armazenar valores inteiros. Um array do tipo de dados float pode armazenar valores que correspondem ao tipo de dados float e nada mais.

Os elementos armazenados em uma matriz são acessíveis linearmente e estão presentes em blocos contíguos de memória que podem ser referenciados usando um índice.

Declarando uma matriz

Em C, um array pode ser declarado como:

data_type nome[comprimento];

Por exemplo,

ordens int[10];

A linha de código acima cria um array de 10 blocos de memória nos quais um valor inteiro pode ser armazenado. Em C, o valor do índice do array começa em 0. Portanto, os valores do índice variam de 0 a 9. Se quisermos acessar qualquer valor específico nesse array, simplesmente temos que digitar:

printf(pedido[número_índice]);

Outra maneira de declarar um array é a seguinte:

data_type array_name[size]={lista de valores};

Por exemplo,

int marcas[5]={9, 8, 7, 9, 8};

A linha de comando acima cria um array com 5 blocos de memória com valores fixos em cada um dos blocos. Em um compilador de 32 bits, a memória de 32 bits ocupada pelo tipo de dados int é de 4 bytes. Assim, 5 blocos de memória ocupariam 20 bytes de memória.

Outra maneira legítima de inicializar arrays é:

marcas int [5] = {9 , 45};

Este comando irá criar um array de 5 blocos, com os últimos 3 blocos tendo 0 como valor.

Outra maneira legítima é:

int marcas [] = {9 , 5, 2, 1, 3,4};

O compilador C entende que apenas 5 blocos são necessários para ajustar esses dados em um array. Portanto, inicializará uma matriz de marcas de nome de tamanho 5.

Da mesma forma, um array 2-D pode ser inicializado da seguinte maneira

int marcas[2][3]={{9,7,7},{6, 2, 1}};

O comando acima criará uma matriz 2D com 2 linhas e 3 colunas.

Leia: Ideias e tópicos de projetos de estrutura de dados

Operações

Existem algumas operações que podem ser executadas em arrays. Por exemplo:

1. percorrendo uma matriz
2. Inserindo um elemento no array
3. Procurando por um elemento específico na matriz
4. Excluindo um elemento específico do array
5. Mesclando as duas matrizes e,
6. Classificando a matriz — em ordem crescente ou decrescente.

Desvantagens

A memória alocada para a matriz é fixa. Isso realmente é um problema. Digamos, criamos um array de tamanho 50 e acessamos apenas 30 blocos de memória. Os 20 blocos restantes ocupam memória sem nenhum uso. Portanto, para resolver esse problema, temos uma lista vinculada.

Lista vinculada

Linked List, muito parecido com arrays, armazena dados em série. A principal diferença é que ele não armazena tudo de uma vez. Em vez disso, armazena os dados ou disponibiliza um bloco de memória conforme e quando necessário. Em uma lista encadeada, os blocos são divididos em duas partes. A primeira parte contém os dados reais.

A segunda parte é um ponteiro que aponta para o próximo bloco em uma lista encadeada. O ponteiro armazena o endereço do próximo bloco que contém os dados. Há mais um ponteiro conhecido como ponteiro de cabeça. head aponta para o primeiro bloco de memória na lista vinculada. Segue a representação da lista encadeada. Esses blocos também são chamados de 'nós'.

fonte

Inicializando listas vinculadas

Para inicializar a lista de links, criamos um nó de nomes de estrutura. A estrutura tem duas coisas. 1. Os dados que ele contém e 2. O ponteiro que aponta para o próximo nó. O tipo de dados do ponteiro será o da estrutura, pois está apontando para o nó da estrutura.

nó de estrutura

{

dados int;

nó de estrutura *próximo;

};

Em uma lista encadeada, o ponteiro do último nó não apontará para nada, ou simplesmente, apontará para null.

Leia também: Gráficos na estrutura de dados

Percurso de lista vinculada

Em uma lista encadeada, o ponteiro do último nó não apontará para nada, ou simplesmente, apontará para null. Então, para percorrer uma lista encadeada inteira, criamos um ponteiro fictício que aponta inicialmente para a cabeça. E, para o comprimento da lista encadeada, o ponteiro continua a avançar até apontar para nulo ou atingir o último nó da lista encadeada.

Adicionando um nó

O algoritmo para adicionar um nó antes de um nó específico seria o seguinte:

1. defina dois ponteiros fictícios (ptr e preptr) que apontam para o cabeçalho inicialmente
2. mova o ptr até que ptr.data seja igual aos dados antes de pretendermos inserir o nó. preptr será 1 nó atrás de ptr.
3. Criar um nó
4. O nó para o qual o preptr fictício estava apontando, o próximo nó apontará para este novo nó
5. O próximo nó do novo apontará para o ptr.

O algoritmo para adicionar um nó após um dado específico seria feito de maneira semelhante.

Vantagens da lista vinculada

1. Tamanho dinâmico diferente de uma matriz
2. A execução de inserção e exclusão é mais fácil na lista vinculada do que em uma matriz.

Fila

A fila segue um tipo de sistema First In First Out ou FIFO. Em uma implementação de array, teremos dois ponteiros para demonstrar o caso de uso de Queue.

Fonte

FIFO basicamente significa que o valor que entra na pilha primeiro, sai primeiro do array. No diagrama de fila acima, a frente do ponteiro aponta para o valor 7. Se excluirmos o primeiro bloco (dequeue), a frente agora apontará para o valor 2. Da mesma forma, se inserirmos um número (enqueue), digamos, 3 em posição 5. Em seguida, o ponteiro traseiro apontará para a posição 5.

Condições de overflow e underflow

No entanto, antes de inserir um valor de dados na fila, devemos verificar as condições de estouro. Um estouro ocorrerá quando houver uma tentativa de inserir um elemento em uma fila que já está cheia. Uma fila ficará cheia quando traseira = max_size–1.

Da mesma forma, antes de excluir dados da fila, devemos verificar as condições de underflow. Um underflow ocorrerá quando houver uma tentativa de deletar um elemento de uma fila que já está vazia, ou seja, se front = null e traseiro = null, então a fila está vazia.

Pilha

Uma pilha é uma estrutura de dados na qual inserimos e excluímos elementos apenas em uma extremidade, também conhecida como topo da pilha. A implementação de pilha é, portanto, chamada de implementação de último a entrar, primeiro a sair (LIFO). Ao contrário da fila, para a pilha, exigimos apenas um ponteiro superior.

Se quisermos inserir (push) elementos em um array, o ponteiro superior move-se para cima ou incrementa em 1. Se queremos excluir (pop) um elemento, o ponteiro superior diminui em 1 ou diminui em 1 unidade. Uma pilha suporta três operações básicas: push, pop e peep. A operação Peep é simplesmente exibir o elemento mais alto da pilha.

Fonte

Aprenda cursos de software online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Conclusão

Neste artigo, falamos sobre 4 tipos de estruturas de dados, ou seja, arrays, listas vinculadas, filas e pilhas. Espero que tenham gostado deste artigo e fiquem ligados para mais leituras interessantes. Até a próxima vez.

Se você estiver interessado em aprender mais sobre Javascript, desenvolvimento full-stack, confira o Programa PG Executivo do upGrad & IIIT-B em Desenvolvimento de Software Full-stack, projetado para profissionais que trabalham e oferece mais de 500 horas de treinamento rigoroso, mais de 9 projetos , e atribuições, status de ex-alunos do IIIT-B, projetos práticos práticos e assistência de trabalho com as principais empresas.