C# - Estrutura de dados - II
 Veremos hoje uma introdução a estrutura de dados na linguagem C#.


Continuando o artigo anterior veremos agora as demais estrutura de dados mais usadas na plataforma .NET.
 

 

 

4- Array

 

Um array é uma coleção de itens de dados armazenados em locais de memória contíguos. A ideia é armazenar vários itens do mesmo tipo juntos e isso facilita o cálculo da posição de cada elemento simplesmente adicionando um deslocamento a um valor base, ou seja, a localização de memória do primeiro elemento do array (geralmente indicado pelo nome do array).

 

 

Se você inicializar uma matriz em C# assim:

int[] array = new int[5];

O compilador alocará 5 blocos de memória contínuos para "array", cada bloco ocupará 4 bytes na memória, pois o tamanho de int é de 4 bytes. Abaixo estão os endereços de cada elemento do "array" na memória.

 

Todos os arrays são derivados implicitamente de System.Array, que é derivada de System.Object, o que significa que os arrays são um tipo de referência e são gerenciados na memória heap. No entanto, há uma pequena diferença quando você inicializa um array de tipo primitivo e de tipo de referência.

Se o array for de um tipo primitivo, na heap cada elemento é inicializado pelo valor padrão do tipo primitivo. Nosso "array" declarado no último parágrafo contém valores inteiros. portanto, na memória, cada elemento do array contém 0 no momento da inicialização.

Se array for de um tipo de referência, no momento da inicialização, cada elemento de array é inicializado com valor Null.

 

5- BinaryTree

 

 

Ao contrário de Arrays, Listas Vinculadas, Pilha e Filas, que são estruturas de dados lineares, as árvores são estruturas de dados hierárquicas. Uma árvore binária é uma estrutura de dados em árvore na qual cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho direito. É implementado principalmente usando Links.

Uma árvore binária é representada por um ponteiro para o nó mais alto da árvore. Se a árvore estiver vazia, o valor de root será NULL. Um nó de árvore binária contém as seguintes partes.

 

Podemos implementar um único nó de uma árvore binária como uma estrutura de dados e usá-lo para armazenar dados. A implementação é simples, como a implementação de uma célula de lista encadeada.

Uma árvore de pesquisa binária é uma árvore binária com propriedades de pesquisa em que os elementos na subárvore esquerda são menores que a raiz e os elementos na subárvore direita são maiores que a raiz.

 

Para encontrar um elemento em uma árvore de pesquisa binária, primeiro precisamos comparar o elemento com o nó raiz; se corresponder, temos o nó direito, caso contrário, precisamos verificar o nó esquerdo ou direito.

 

Exemplo de implementação de uma Binary Tree:

 

public class BinarySearchTree
{
    public class Node
    {
        public Node()
        { }
        public int Data;
        public Node Left;
        public Node Right;
        public void DisplayNode()
        {
            Console.Write(Data + " ");
        }
    }
    public Node root;
    public BinarySearchTree()
    {
        root = null;
    }
    public void Insert(int i)
    {
        Node newNode = new Node();
        newNode.Data = i;
        if (root == null)
            root = newNode;
        else
        {
            Node current = root;
            Node parent;
            while (true)
            {
                parent = current;
                if (i < current.Data)
                {
                    current = current.Left;
                    if (current == null)
                    {
                        parent.Left = newNode;
                        break;
                    }
                    else
                    {
                        current = current.Right;
                        if (current == null)
                        {
                            parent.Right = newNode;
                            break;
                        }
                    }
                }
            }
        }
    }
}

 

6. Hashtable

 

Uma Hashtable é uma estrutura de dados implementada na plataforma .NET de duas formas :

 

1- Hashtable simples no namespace System.Collections

2- E como estrutura de dados genérica Dictionary no namespace System.Collections.Generic,

 

Recomenda-se usar o Dictionary ao invés da classe Hashtable.

 

O princípio de funcionamento de Hashtable e Dictionary é que constroem um hash que é índice em uma matriz geralmente usando polinômios. Pesquisar em uma tabela de hash e dicionário tem a complexidade de tempo O(1).

 

Uma tabela de hash é normalmente organizada como uma matriz de listas vinculadas. As células individuais nas listas vinculadas armazenam, cada uma, uma chave e um valor. Associada a essa estrutura está uma função hash, que recebe uma chave como parâmetro e calcula a localização de um array.

 

Este local da matriz contém uma referência ao início da lista vinculada que conterá a chave fornecida se estiver na tabela de hash. Assim, para encontrar uma chave em uma tabela de hash, primeiro aplicamos a função de hash à chave e, em seguida, pesquisamos a lista vinculada no local calculado pela função de hash.

 

A figura a seguir ilustra o layout de uma tabela de hash em que as chaves são strings e os valores são ints, e a função hash é denotada por h:

 

A classe Hashtable oferece a funcionalidade de mapear de um tipo para outro tipo mantendo internamente duas matrizes de objeto, uma para as chaves a partir da qual você está mapeando, e, uma para os valores que você está mapeando.

Quando você insere um par chave/valor em um Hashtable, ela rastreia automaticamente qual chave pertence a qual valor e permite recuperar o valor que está associado com uma chave especificada rápida e facilmente.

Assim um Hashtable é como um recipiente utilizado para armazenar dados em pares de chave/valor  onde as chaves são usadas como índice e ajudam a localizar os valores rapidamente.

Dessa forma a classe Hashtable representa uma coleção de pares chave/valor que são organizados com base no código hash da chave.

No exemplo abaixo temos um exemplo que associa as idades de algumas pessoas com seus nomes e a seguir exibe a informação:

using System.Collections;

Hashtable idades = new Hashtable();

idades["Macoratti"] = 48;
idades["Miriam"] = 39;
idades["Janice"] = 21;
idades["Jefferson"] = 23;
idades["Yuri"] = 21;
idades["Bianca"] = 21;

// iterando usando a instrução foreach
// O iterador gera um objeto DictionaryEntry contendo o par key/value
foreach (DictionaryEntry element in idades)
{
    //obtém os valores da HashTable usando Key e Value
    string nome = (string)element.Key;
    int idade = (int)element.Value;
    //exibe os valores da HashTable
    Console.WriteLine("Nome: {0}, Idade: {1}", nome, idade);
}

Diferenças entre a classe HashTable e Dictionary:

HashTable
Retorna nulo se tentarmos encontrar uma chave que não existe.
É mais lento do que um Dictionary porque requer boxing e unboxing.
Todos os membros de um Hashtable são thread safe.
Não é um tipo genérico. O que significa que não podemos usá-lo com qualquer tipo de dados.

Dictionary
Retorna um erro se tentar encontrar uma chave que não existe.
É mais rápido do que um Hashtable porque não há boxing e unboxing.
Somente membros estáticos públicos são thread-safe.
É um tipo genérico, logo podemos usá-lo com qualquer tipo de dados.                                  

E estamos conversados... 

"Porque todos sois filhos de Deus pela fé em Cristo Jesus.Porque todos quantos fostes batizados em Cristo já vos revestistes de Cristo."
Gálatas 3:26,27

Referências:

José Carlos Macoratti