Estruturas de dados simples

1. Lista x Vetor

Vetor: Contínuos na memória.
<Desenho da memoria, subsecao de memoria>
Lista: Não contínua.
<Desenho, setinhas p la e p ca na memoria>
Lista Vetor
inserir 1 n
acessar n 1
buscar n n/logn se ordenado
remover 1 n
ordenar nlogn (merge)<link> nlogn (quick, etc)<links>

bubble, quick, merge sort
quick sort eh melhor com pivot aleatorio

Vetor: dinamico vs estatico

Estatico é rápido para alocar.<motivos> operacoes "rapido e rasteiro".

Na maratona a unica situação em q usamos dinamico eh qnd fazemos lista de adjacencia em grafo.<explicacao>
Nunca iremos usar malloc nem implementar lista na mão <usaremos a STL><destaque>
alocar dinamicamente é demorado pq depende do humor do SO.

2. Fila e Pilha

Fila é como fila de banco, o primeiro que entra é o primeiro que sai e furar fila é feio.
Pilha é como uma pilha de livros, você só poe ou tira livro do topo, senão tudo cai.

É bastante intuitivo então vou só botar o link da wikipédia para não ficar muito vazio.

Fila: http://pt.wikipedia.org/wiki/FIFO
Pilha: http://pt.wikipedia.org/wiki/LIFO

Usos bonitos de fila: BFS, Escalonador de Processos.
Usos bonitos de pilha: Parser XML, RPN ( http://en.wikipedia.org/wiki/Reverse_Polish_notation )

3. Árvores: BST, Heap

Árvore em estruturas discretas são: grafos conexos sem ciclos.<link p grafos>
<desenho de um grafo bobao>

Em estruturas de dados é a mesma coisa mais o conceito de raiz, que nesse ponto é um nó arbitrário.
Com isso vem uma hierarquia o conceito de pai e filho.
<desenho de arvore binaria>

Árvores Binárias são Arvores (de EDA) em que um nó pode ter no máximo 2 filhos.

Árvores Binárias de Busca (BST) são arvores binarias em q a ordenação dos nós é especial.
O valor dos nós a esquerda de um nó X é sempre menor que o valor dos nós da direita do mesmo.(geralmente, pode ser ao contrario…)

Busca na BST:
busca binaria intuitiva
A busca numa BST tem complexidade O(k), sendo k a altura da BST.<explicar>
<desenho da bst com o k do lado>

<inserção, remoção, rotação bla bla bla e complexidades>

rb tree -> stl usa em map e set <explicacao de set e map>
avl tree

Heap

p cada nó N, todos os filhos sao menores q N -> riz eh o maior de todos
(pode ser o contrário também, a raiz eh o menor e os filhos sao maiores)
argumento do ruan que tanto faz: multiplica tudo por -1.

inserir/(remover o maior/menor) logn
olhar o maior O(1)

no vetor:
qnd a raiz = 1
filho1 e filho2 do vertice v = 2*v e 2*v + 1, respectivamente
analogamente, como C arredonda p baixo, v=(f1 ou f2)/2

qnd a raiz = 1
filho1 e filho2 do vertice v = 2*v + 1 e 2*v + 2, respectivamente
analogamente, como C arredonda p baixo, v=((f1 ou f2)-1)/2

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License