Introdução às matrizes na estrutura de dados

Matriz é um tipo de estrutura de dados usada para armazenar dados homogêneos em locais de memória contíguos. Isso implementa a ideia de armazenar os vários itens para que possam ser recuperados ou acessados ​​de uma só vez.

Aqui, o índice refere-se à localização de um elemento na matriz. Vamos imaginar se P (L) é o nome da matriz onde 'P' é o nome da variável e 'L' é o comprimento da matriz, ou seja, o número de elementos presentes na matriz. Então P (i) representa o elemento nessa posição 'i + 1' na posição na matriz.

Por exemplo:

P (6) = 72 significa elemento no local 6 + 1 da matriz.

Necessidade de matriz: ajuda a representar um grande número de elementos usando uma única variável. Também facilita o acesso ao elemento mais rápido, fácil de armazenar na localização da memória, usando o índice da matriz que representa a localização do elemento na matriz.

Como matrizes funcionam na estrutura de dados?

Matriz armazena as variáveis ​​em locais contíguos e fornece um índice específico. Quando alguém deseja buscar os dados, a pessoa usa esse índice. Na matriz acima 'P', diga o endereço base para a matriz = 100, os elementos são armazenados como abaixo:


A memória alocada para uma matriz pode ser calculada como:

  • Matriz unidimensional: memória total alocada para uma matriz = número de elementos * tamanho de um elemento.Por exemplo: no caso acima, memória = 7 * (tamanho de int)
  • Ordem principal da linha: memória total alocada para a matriz 2D = número de elementos * tamanho de um elemento
    = Número de linhas * Número de colunas * Tamanho de um elemento
  • Ordem principal da coluna: memória total alocada para a matriz 2D = número de elementos * tamanho de um elemento
    = Número de linhas * Número de colunas * Tamanho de um elemento

Como definir matrizes?

Assim, a matriz pode ser definida como uma estrutura de dados derivada para armazenar dados homogêneos do tipo de dados primitivo em locais de memória contíguos. Abaixo estão as operações que podem ser executadas em matrizes:

1. Inserção: refere-se à inserção de um elemento na matriz em um índice específico. Isso pode ser realizado com O (n) complexidade.

2. Exclusão: refere-se à exclusão de um item em um índice específico. Esta operação requer a troca de elementos após a exclusão, portanto, exige O (n) complexidade.

3. Pesquisando: refere-se ao acesso a um item em um índice específico de uma matriz.

4. Transversal: refere-se à impressão de todos os elementos de uma matriz, um após o outro.

Propriedades de matrizes na estrutura de dados

Abaixo estão as propriedades das matrizes na estrutura de dados:

  • É um tipo de dados derivado, composto de uma coleção de vários tipos de dados primitivos, como int, char, float etc.
  • Os elementos de uma matriz são armazenados em blocos contíguos na memória primária.
  • O nome da matriz armazena o endereço base da matriz. Ele atua como um ponteiro para o bloco de memória onde o primeiro elemento foi armazenado.
  • Os índices da matriz começam de 0 a N-1 no caso de uma matriz de dimensão única, em que n representa o número de elementos em uma matriz.
  • Os elementos da matriz podem ser compostos apenas de constantes e valores literais.

Como criar matrizes?

Podemos criar matrizes usando a sintaxe abaixo:

1. Matriz dimensional: var = (c1, c2, c3, …… .cn)

Aqui, var refere-se à variável da matriz que armazena a localização base da matriz. E c1, c2… são elementos da matriz.

Exemplo: int a = (4, 6, 7, 8, 9)

Comprimento da matriz = n

2. Matriz multidimensional: var = ((r 01, … r 0n ), (r 10, … ..r 1n )… .. (r m0 … .r mn ))

Aqui, var refere-se ao nome da matriz de m linhas e n colunas.

Como acessar o elemento Arrays?

Os índices de uma matriz começam de 0 a -1, 0, que indica o primeiro elemento da matriz e -1, o último elemento da matriz. Da mesma forma, -2 indica o último, mas um elemento da matriz. Digamos, existe uma matriz 'A' com 10 elementos. Então aqui Uma variável armazena a referência da primeira variável da matriz e isso é chamado de 'Endereço Base' de uma matriz. Depois disso, se alguém quiser acessar o elemento da matriz, o endereço desse elemento será calculado usando a fórmula abaixo.

Endereço do i-ésimo elemento = Endereço base + i * tamanho de cada elemento

Aqui, o tamanho de cada elemento refere-se à memória obtida por vários tipos de dados primitivos que o array está mantendo. Por exemplo, int ocupa 2 bytes de espaço e float ocupa 4 bytes de espaço em C.

Acessando matriz multidimensional

Digamos que A (r l, ……, r u ) (c u, ……, c l ) é uma matriz multidimensional e rl, r u, c u, c l são limites inferior e superior para linhas e colunas. Além do Número de linhas em A, diga NR = r u - r l +1 e Número de colunas em A, diga NC = c l - c u +1.

Agora, para encontrar o endereço de um elemento na matriz, existem 2 métodos:

  1. Linha principal: onde atravessamos linha por linha.

Endereço A (i) (j) = Endereço base + ((i - r l ) * NC + (j - c l )) * tamanho de cada elemento.

  1. Maior da coluna: onde percorremos coluna por coluna.

Endereço A (i) (j) = Endereço base + ((i - r l ) + (j - c l ) * NR) * tamanho de cada elemento.

Complexidade: acessar qualquer elemento da matriz é muito mais fácil e pode ser feito com a complexidade O (1).

Conclusão

As matrizes são uma maneira muito exclusiva de estruturar os dados armazenados, de forma que possam ser acessados ​​com facilidade e consultados para buscar o valor em um número específico usando o valor do índice. Embora a inserção de um elemento em uma matriz leve muito tempo, ela precisa de um rearranjo e deslocamento completos dos elementos existentes de uma matriz. Ainda, é usado para implementar várias outras estruturas de dados complexas, como árvore, fila ou pilha, e também é usado em vários algoritmos.

Artigo recomendado

Este é um guia para matrizes na estrutura de dados. Aqui discutimos como criar e acessar elementos de matriz na estrutura de dados, juntamente com propriedades. Você também pode consultar nossos outros artigos relacionados para saber mais -

  1. Como criar matrizes em PHP?
  2. Matrizes em Java Programming Vantagens e Desvantagens
  3. Matrizes na programação C (exemplos)
  4. As 10 principais perguntas da entrevista sobre estrutura de dados

Categoria:

Desenvolvimento de software