RESUMO_SIMPLES_SOBRE_ESTRUTURAS_DE_DADOS.txt

RESUMINHO SIMPLES SOBRE ESTRUTURAS DE DADOS

- Em programação existem "dados simples":
	- numeros inteiros: -1, 0, 1, etc.
	- numeros reais: -1.5, 0.1, 9.9, etc
	- valores booleanos: verdadeiro ou falso, que no fim das contas eh um inteiro onde 0 significa falso e qualquer outra coisa eh verdadeiro
	- strings (texto): apenas uma sequencia de caracteres, os quais por sua vez sao inteiros
- E existem "dados compostos", que sao criados pelo programador para agrupar dados simples de forma a representar coisas mais complexas. Ex.: para representar uma pessoa podemos criar um dado composto com 2 membros (campos): idade (int) e nome (string)
- Tanto dados simples e compostos podem ser agrupados de forma homogenea em arrays (vetores), que são meramente o agrupamento linear contíguo de N dados daquele mesmo tipo

- quando falamos de lista, fila, pilha, árvore e grafo, estamos falando de dados compostos. Mais que isso, estamos falando de dados compostos que tem propositos e usos práticos já bem estabelecidos na história da programação.

- lista, fila e pilha são os tipos mais faceis. Elas podem ser implementadas usando apenas arrays de dados simples, mas tambem podem ter uma implementação mais complexa.
- Uma lista eh meramente uma estrutura linear de dados onde qualquer elemento pode ser acessado, removido e inserido a qualquer instante. isso pode ser implementado tanto usando arrays quanto listas encadeadas ou duplamente encadeadas. é desnecessário explicar exatamente o que é uma lista encadeada ou duplamente encadeada, basta explicar que enquanto um array sempre tem um tamanho fixo, uma lista encadeada ou duplamente encadeada pode aumentar ou diminuir de tamanho facilmente.
- uma fila é uma lista onde voce nao deixa inserir e remover elementos em qualquer lugar. você só insere no final e só remove no começo, igual filas da vida real, fila de banco, fila de açougue etc. Os elementos são removidos exatamente na ordem que foram inseridos, quem chega primeiro sai primeiro e quem chega por ultimo sai por ultimo, sem furar fila.
- em uma pilha voce também não pode inserir e remover em qualquer ordem. voce só insere no topo e só remove do topo, igual uma pilha da vida real, uma pilha de livros em uma caixa, ou uma pilha de pratos na pia da cozinha. Os elementos são removidos na ordem inversa que são inseridos. Os últimos a serem inseridos são os primeiros a serem removidos e os primeiros a serem inseridos são os ultimos a serem removidos.

- árvore e grafo são estruturas não lineares, diferente de lista, fila e pilha que são estruturas lineares
- em estruturas lineares existe no máximo um elemento antes do atual e no máximo um elemento depois do atual
- em estruturas não lineares, podem existir N elementos (tipicamente chamados de nós) antes do atual e M elementos depois do atual.

- uma árvore é uma estrutura onde todos os nós estão conectados e existe sempre um e apenas um elemento raiz, a partir do qual podem seguir 0 ou mais novos elementos imediatmente seguintes. E dos elementos seguintes podem seguir outros 0 ou mais novos elementos seguintes e assim por diante. estruturas de árvore são representações exatas de árvores genealógicas DESDE QUE estejamos representando exclusivamente mulheres ou homens (porque se representassemos ambos os sexos os filhos de pessoas com parentesco faria a árvore virar um grafo). A característica visual marcante da representação gráfica de uma árvore é que além dela ter um único nó raiz, após qualquer nó se dividir em 2 ou mais, essas divisões jamais se encontrarão novamente, diferente de um grafo onde isso pode acontecer.
- uma outra característica da árvore é que existe uma "direção" nas relações entre os nós. Diz-se que um nó está conectado a seus filhos (os imediatamente proximos), mas não se diz que os filhos estão conectados ao pai

- um grafo é uma estrutura onde não necessariamente todos os nós estão conectados e além disso não existe um único elemento raiz. A partir de cada nó do grafo seguem-se 0 ou mais outros nós e a conexão entre esses outros nós pode ser tanto apenas "de ida" como é na árvore, ou "de volta" (do próximo pra esse), ou ainda tanto ida quanto volta. além disso é possível que existam sequencias de nós que retornem a um nó anterior da sequencia, um ciclo, algo que não existe em árvores. Grafos podem ser usados para representar uma rede de amizades: A e B se consideram mutuamente amigos, B se considera amigo de C mas C não se considera amigo de B, embora se considere amigo de A, e D é um cara recluso que não é amigo de ninguém e ninguém é amigo dele.


- além dessas estruturas clássicas (lista, fila, pilha, árvore, grafo) existem estruturas muito comuns que nem sempre são ensinadas em disciplinas de algoritmos e estrutura de dados, mas são usadas extensivamente na hora de programar de verdade. As mais comuns são mapas (maps) e conjuntos (sets)
- um set representa um conjunto de coisas que não se repetem. por exemplo um conjunto de palavras (strings) ou um conjunto de ponteiros (ints) ou um conjunto de dados complexos (structs) de pessoas, onde cada struct tem nome (string) e idade (int). as operações comuns dos sets são inserção, checagem e remoção. São úteis por exemplo quando você precisa percorrer por completo um grafo que pode ter ciclos. nesse caso a cada nó você verifica se ele está no set. se não estiver, adiciona e visita o nó. se estiver, abandona o nó e segue os outros.
- um map representa um mapeamento entre um conjunto de chaves únicas, não repetíveis, e valores não únicos, que podem ou não ser repetidos. Como dicionários da vida real, onde cada palavra do índice de palavras nunca se repete, mas palavras sinônimas tem a mesma descrição entre si embora a palavra índice seja diferente. Operações típicas de mapas são atualizacao do valor associado a uma chave, adicao de um par chave/valor e remoção de um par chave/valor. maps são úteis para criar estruturas complexas dinâmicas onde chaves e valores são definidos em tempo de execução (ao invés de durante a compilação)