Estrutura de dados
As estruturas de dados fornecem uma maneira de armazenar e organizar dados em um computador. A programação usa várias estruturas de dados diferentes. Dentro de um programa, uma estrutura de dados é uma coleção de elementos de dados organizados de alguma forma. Por exemplo, uma coleção de elementos pode ser organizada e numerada em sequência. Estruturas de dados comuns são arquivos, listas, arrays, pilhas, filas e árvores.
arquivos
Um arquivo de computador é usado para armazenar informações. Os programas de computador podem usar arquivos para ler as informações que precisam ser processadas e para gravar os resultados do processamento. Os dados dentro de um arquivo são normalmente organizados em pacotes menores de informações, que costumam ser chamados de 'registros' ou 'linhas'.
Por exemplo, um arquivo pode conter as informações da folha de pagamento de cada funcionário, com cada funcionário representado por uma linha. Um programa de computador pode ler essas informações linha por linha e realizar algum tipo de operação relacionada à folha de pagamento, como o cálculo de benefícios para um determinado período de pagamento. Os resultados podem ser adicionados ao arquivo existente ou gravados em um novo arquivo. Os arquivos possibilitam que diferentes programas compartilhem informações, já que um arquivo pode ser passado para o próximo.
Listas
Uma lista contém elementos de um determinado tipo de dados. Por exemplo, uma lista pode conter strings. Um exemplo seria o nome de todos os jogadores de um time de futebol. Cada nome é uma string, mas quando você organiza todos os nomes juntos, eles formam uma lista. Uma lista é a estrutura de dados mais simples.
Por exemplo, uma lista de strings pode ser assim:
('John,' 'Paul,' 'George,' 'Ringo')
Uma lista de números pode ser assim:
(67, 84, 92, 52, 81, 75)
Cada elemento em uma lista é identificado por um índice específico. Todos os elementos em uma lista são ordenados em uma sequência particular, e o índice de um elemento informa em que posição na sequência esse elemento está localizado. Normalmente, o valor do índice da primeira posição é zero (0).
Array
Um array é uma estrutura de dados onde os elementos são identificados por um ou mais índices. Uma matriz é semelhante a uma lista, mas uma matriz pode ter várias dimensões. Uma matriz unidimensional é o mesmo que uma lista: uma sequência linear de elementos que são todos do mesmo tipo.
Em uma matriz bidimensional, os elementos são organizados em duas dimensões, que você pode considerar como as linhas e colunas de uma tabela. Este tipo de array usa dois índices: um para linhas e outro para colunas. A combinação única de dois valores de índice representa uma célula única na tabela. Cada célula corresponde a um elemento, que pode ser uma string, um número ou algum outro tipo de dado.
Uma matriz bidimensional também é chamada de matriz. Uma matriz tridimensional pode ser representada por um cubo e usa três índices. Os arrays podem ter mais dimensões, mas são mais difíceis de visualizar.
Os arrays permitem organizar os dados de forma eficiente, pois os índices permitem recuperar qualquer elemento. Eles são relativamente fáceis de implementar. No entanto, todos os elementos devem ser do mesmo tipo, e pesquisar em uma grande matriz pode ser demorado se não for classificado.
Pilhas
Uma pilha é uma estrutura de dados em que os elementos são inseridos ou excluídos apenas na parte superior. Uma pilha é semelhante a uma lista, mas pode conter qualquer tipo de elemento. Ao contrário de uma lista, a ordem dos elementos é fixa e não pode ser alterada. Isso limita as operações que podem ser realizadas nele. Existem basicamente apenas duas operações: push e pop. Push adiciona um item ao topo da pilha e pop remove um item do topo da pilha.
Uma pilha é uma estrutura de dados LIFO (último a entrar, primeiro a sair). Os elementos são removidos na ordem inversa de sua adição. A maneira mais fácil de visualizar uma pilha é como uma pilha de livros, e a única coisa que você pode fazer é adicionar um livro ao topo ou remover um livro do topo. Esta não é uma estrutura de dados muito sofisticada, mas é muito eficiente. As pilhas podem ser muito grandes e, ainda assim, você pode trabalhar com uma pilha muito rapidamente, já que está preocupado apenas com o item no topo.
Fila
Uma fila é uma estrutura de dados onde os elementos são mantidos em ordem e onde os elementos são inseridos em uma extremidade e excluídos na outra. Uma fila é uma estrutura de dados primeiro a entrar, primeiro a sair (FIFO). O primeiro elemento em uma fila será o primeiro a ser removido. Você também pode continuar adicionando ou removendo elementos, e a fila pode ficar mais longa ou mais curta.
A maneira mais fácil de visualizar uma fila é uma fila de pessoas esperando no banco. Novas pessoas que entram no banco são adicionadas ao final da fila. Quando um caixa abre, a pessoa que está saindo da fila está bem na frente e é a pessoa que está há mais tempo na fila.
Uma fila é muito útil para lidar com uma etapa intermediária em um programa. Imagine dois processos executados em velocidades variáveis devido à natureza dos elementos que estão sendo processados - alguns elementos são mais complicados do que outros e levam mais tempo. Se os processos estiverem conectados em uma sequência direta, onde a saída do primeiro processo se torna a entrada do segundo processo, o programa pode não ser muito eficiente, pois os dois processos podem acabar tendo que esperar um pelo outro. Uma fila entre os dois processos permite que os programas sejam mais eficientes.
Quando o primeiro processo é executado mais rápido que o segundo, o comprimento da fila aumenta, mas o primeiro processo não precisa ficar lento. Quando o segundo processo é executado mais rápido do que o primeiro, o comprimento da fila diminui, mas o segundo processo não precisa esperar pelo primeiro. O uso de uma fila reduz o tempo de espera geral. Obviamente, se o segundo processo for consistentemente mais rápido que o primeiro, a fila ficará vazia e parte da eficiência será perdida.
Árvores
Uma árvore é uma estrutura de dados hierárquica. Parece um pouco com uma estrutura de árvore com galhos, mas normalmente é mostrado de cabeça para baixo. Uma árvore é um tipo de gráfico conectado onde cada elemento é representado como um nó em um gráfico. Os relacionamentos entre os nós são descritos em termos de pais e filhos.
Cada nó na árvore está conectado a um nó pai mais acima na estrutura, com exceção do nó no topo, que não tem um pai. No exemplo abaixo, o nó número dois não tem pai e é considerado a raiz da árvore.
 |
Cada nó da árvore pode ter qualquer número de filhos na parte inferior da estrutura, incluindo zero. No exemplo, os nós dois, seis e sete têm dois filhos cada, enquanto os nós cinco e nove têm um filho cada. Os nós três, quatro, cinco e onze não têm filhos e são considerados folhas.
Árvores são uma estrutura de dados mais complicada. Eles normalmente são usados para representar dados hierárquicos ou coleções de listas classificadas. Por exemplo, considere a estrutura de pastas e arquivos em seu computador.
A raiz é normalmente a unidade C: e seus arquivos são organizados em várias pastas. Cada pasta pode conter qualquer número de pastas ou arquivos. Isso pode ter vários níveis de profundidade, então a localização real de um arquivo pode ser algo como C: \ MeusDocumentos \ Projetos2013 \ MeuRelatório.doc . Você pode representar toda a estrutura de todos os seus arquivos e pastas como uma estrutura em árvore.
Resumo da lição
Uma estrutura de dados é uma coleção de elementos de dados organizados de alguma forma. Estruturas de dados comuns são arquivos, listas, arrays, pilhas, filas e árvores.
Resultados de Aprendizagem
Ao concluir esta lição, você será capaz de:
- Defina a estrutura de dados
- Descreva estruturas de dados comuns, como arquivos, listas, arrays, pilhas, filas e árvores