Uma estrutura de dados (ED) é uma implementação de um tipo abstrato de dado. Na definição de um tipo abstrato de dado são definidos a natureza do dados e as operações que podem ser realizadas sobre eles, enquanto que numa estrutura de dados são definidas:
- qual o mapeamento entre este dado e uma memória, ou seja, como este dado é armazenado na memória de um computador (codificação);
- quais os algoritmos que vão implementar as operações definidas sobre estes dados.
Uma sequência ou um conjunto de dados são implementados com diferentes estruturas. As diferentes formas de implementar estes tipos abstratos de dados devem ser avaliadas. Para tal, as diretrizes de estudo são:
- diferenciar as diferentes implementações;
- definir quais são as formas de avaliar as qualidades de uma ou da outra;
- entender quais as diferentes situações em que cada implementação possa ser mais adequada para a resolução de um problema.
Existem duas formas principais de mapear uma sequência em uma memória, são elas: o vetor e a lista ligada.
Vetor
Um vetor se utiliza de um bloco de memória sequencial onde os dados são armazenados diretamente sobre ele. Este bloco é alocado como uma sequência de endereços na pilha (alocação estática de memória) ou uma sequência de endereços na heap (alocação dinâmica de memória), ou seja, um vetor é um conjunto de endereços com mapeamento direto aos elementos de uma sequência em cada uma de suas posições.
Tabela 01 – Sequência de um conjunto de alguns números pares alocada na memória e estruturada como um vetor.
| Posição | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Elemento | 6 | 4 | 5 | 8 | 10 |
Fonte: Autor.
Exemplo de um vetor alocado estaticamente em C:
Exemplo de um vetor alocado dinamicamente em C:
Em um vetor, é de interesse do programador que seja possível executar as operações de uma sequência. Algumas operações sobre vetores são:
- Inserção;
- Remoção;
- Acesso;
- Busca;
- Ordenação.
Referências
- PIVA JÚNIOR, Dilermando (et al). Estrutura de dados e técnicas de programação. 1. ed. Rio de Janeiro, RJ: Campus, 2014. 399 p. ISBN: 9788535274370.
- CORMEN, Thomas H et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 926 p. ISBN: 9788535236996.
- TOSCANI, Laira Vieira; VELOSO, Paulo A. S. Complexidade de algoritmos: análise, projeto e métodos. 3. ed. Porto Alegre: Bookman, 2012. 261 p. (Série livros didáticos informática UFRGS, 13) ISBN: 9788540701380.
- ASCENCIO, Ana Fernanda Gomes. Estruturas de dados: algoritmos, análise da complexidade e implementações em Java e C/C++. São Paulo: Pearson, c2010. 432 p. ISBN: 9788576052216, 978857605816.
- BRASSARD, Gilles; BRATLEY, Paul. Fundamentals of algorithmics. Englewood Cliffs: Prentice Hall, c1996. xx, 524 p. ISBN: 0133350681.
Livraria
