Árvore de Dados

Laços

A idéia do comando if é verificar se uma dada condição é verdadeira ou falsa, por exemplo, se para uma determinada conta a utilização fosse somente para números menores que zero de uma lista de vários números, assim poderia ser utilizado o comando if para filtrar os números menores que zero.

O comando do while é um comando de laço (looping) que lembra a mistura do comando do e if. O comando do while é muito útil e a função dele é fazer um laço até que uma condição seja satisfeita, ou seja, faça algo até onde eu mandei. A sintaxe é do while (condição).

O comando for permite que um certo trecho de programa seja executado um determinado número de vezes. 

A forma do comando for é a seguinte:

for (comandos de inicialização;condição de teste;incremento/decremento)

{

// comandos a serem repetidos

// comandos a serem repetidos

}

// comandos após o 'for'

O funcionamento é o seguinte:

1.     Executa os comandos de inicialização;

2.     Testa a condição;

3.     Se a condição for falsa então executa o comando que está logo após o bloco subordinado ao for .

4.     Se condição for verdadeira então executa os comandos que estão subordinados ao for;

5.     Executa os comandos de incremento/decremento;

6.     Volta ao passo 2.

O comando for deve ser usado sempre que:

• soubermos exatamente quantas vezes o laço deve ser repetido;
• o teste deva ser feito antes da execução de um bloco de comandos;
• houver casos em que o laço não deva ser repetido nenhuma vez.

int contador; for (contador = 0; contador < 10; contador = contador+1) { printf("Contador : %d\n",contador); } printf("Valor do Contador após o laço: %d\n",contador)

int contador; for (contador = 10; contador > 0; contador = contador-1) { printf("Valor do Contador após o laço: %d\n",contador); } printf("Valor do Contador após o laço: %d\n",contador);

http://www.fisica.ufjf.br/~sjfsato/fiscomp1/node15.html

http://www.inf.pucrs.br/~pinho/LaproI/ComandosDeRepeticao/Repeticao.html

Matrizes

Matrizes são arranjos ordenados que ao contrário dos vetores podem ter n dimensões, sendo que estas dimensões lhes dão o nome n-dimensional . Uma matriz de duas dimensões será chamada bi-dimensional, uma de três dimensões tri-dimensional e assim consecutivamente. Funciona praticamente da mesma forma que um vetor exceto que utilizaremos o número n de índices para acessar um dado que queremos. Para efeitos de estudo por enquanto nos limitaremos somente às matrizes bidimensionais (duas dimensões linha X colunas). Assim se possuimos uma matriz bidimensional de duas linhas e duas colunas:

3 | 4

5 | 6

Consideramos que para acessarmos o valor 3, localizamos o índice por sua linha (1) e coluna (1) , deste modo seu índice é (1,1). O valor quatro por exemplo será (1, 2).

Declaração e inicialização de um matriz

A declaração de uma matriz em português estruturado pode ser da seguinte forma:

tipo Nome_Matriz [tamanho_linha][tamanho_coluna]

Assim temos como exemplo de declarações:

inteiro matriz [10][10]

real media [3][3]

Em uma matriz como o inteiro matriz que criamos acima é criado espaço para 100 elementos (10x10).Criaremos abaixo um algoritmo em que o usuário digita 100 elementos e estes aparecem na tela.

inteiro matriz [10][10]

inteiro i , j (i será o índice linha e j o índice coluna)

para (início: i=0 fim i<10 alteraçãoi+1 )

para (início: j=0 fim j<10 alteraçãoj+1 )

exibe Escreva um número

recebe matriz [i][j]

fecha_para

fecha_para

para (início: i=0 fim i<10 alteraçãoi+1 )

para (início: j=0 fim j<10 alteraçãoj+1 )

exibe Estes são os números digitados:

exibe matriz [i][j]

fecha_para

fecha_para

Operações com matrizes

Soma e subtração entre matrizes

inteiro matriz_A [1,,2,1,,[2]

inteiro matriz_B [2][2]

inteiro matriz_soma [2][2]

para (início: i=0 fim i<2 alteraçãoi+1 )

para (início: j=0 fim j<10 alteraçãoj+1 )

matriz_soma[i][j]= matriz_A [i][j]+ matriz_B [i][j]

fim_para

fim_para

Multiplicação por um escalar

inteiro escalar

inteiro matriz_A [2][2]

inteiro matriz_multiplicação [2][2]

para (início: i=0 fim i<2 alteraçãoi+1 )

para (início: j=0 fim j<2 alteraçãoj+1 )

matriz_multiplicação[i][j]= escalar * matriz_A [i][j]

fim_para

fim_para

Multiplicação entre matrizes

inteiro matriz_A [2][2]

inteiro matriz_B [2][2]

inteiro matriz_multiplicacao [2][2]

para (início: i=0 fim i<2 alteraçãoi+1 )

para (início: j=0 fim j<2 alteraçãoj+1 )

para (início: k=0 fim k<2 alteraçãok+1 )

matriz_multiplicacao[i][j]= matriz_multiplicacao [i][j]+ matriz_A [i][k]*matriz_B[k][j]

fim_para

fim_para

Calcular a diagonal e a transposta

inteiro matriz_A [2][2]

inteiro diagonal=0

para (início: i=0 fim i<2 alteraçãoi+1 )

para (início: j=0 fim j<10 alteraçãoj+1 )

se (i=j)

diagonal= diagonal+ matriz_A [i][j]

fim_se

fim_para

fim_para

inteiro matriz_A [2][2]

inteiro inversa=0

inteiro maximo=2

para (início: i=0 fim i<2 alteraçãoi+1 )

para (início: j=0 fim j<2 alteraçãoj+1 )

se (i+j=(maximo*2)-1)

inversa= inversa + matriz_A [i][j]

fim_se

fim_para

fim_para

http://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/Vetores_e_Matrizes

Vetor

Em computação um Vetor (Array) ou Arranjo é o nome de uma matriz unidimensional considerada a mais simples das estruturas de dados. Geralmente é constituída por dados do mesmo tipo (homogêneos)e tamanho que são agrupados continuamente na memória e acessados por sua posição (indíce - geralmente um número inteiro) dentro do vetor. Na sua inicialização determina-se o seu tamanho que geralmente não se modifica mesmo que utilizemos menos elementos.

Abaixo temos o exemplo de um vetor. Os valores internos seriam os dados alocados no vetor, enquanto seu tamanho é dado pelo número de casas disponíveis (no caso 8) e o índice representa a posição do dado no vetor ( por exemplo podemos definir que 0 tem o índice 1, 2 tem índice 2, 8 tem índice 3 e assim sucessivamente).

0

2

8

9

10

11

15

18

Declaração e inicialização de um vetor

A declaração de um vetor em português estruturado pode ser da seguinte forma:

Nome_Vetor:vetor[tamanho]tipo

Assim temos como exemplo de declarações:

VECTOR:vetor [10] numérico

MEDIA: vetor [3] numérico

Tomemos o primeiro exemplo (inteiro vector [10]) onde declaramos que estamos criando um vetor para números chamado de VECTOR com dez posições. Desta forma o computador entende que deve alocar 10 espaços para 10 números inteiros no computador que serão inseridos conforme especificado pelo programa . Por exemplo, vamos construir dois laços de repetição:

VECTOR:vetor [10] numérico

INDICE:numérico

INDICE<-0

para INDICE de 0 até VECTOR<9 passo 1 faça

exibe Escreva um número

recebe VECTOR [INDICE]

fecha_para

para INDICE de 0 até VECTOR<9 passo 1 faça

exibeVECTOR [INDICE]

recebe VECTOR [INDICE]

fecha_para

Conforme vimos, o primeiro laço para vai entender que ao entrar índice<-0 , quando o usuário digitar o primeiro valor será alocado este valor em vector[índice].Quando chegar ao final do para ele fará o teste. Se o índice continuar menor do que 10 ele entra no laço e recebe o segundo valor, chegando ao final do laço e fazendo novamente o processo até obter os dez valores quando sai do laço.

No segundo laço acessamos estes dados e exibimos na tela aplicando o mesmo príncipio do primeiro laço.

Operações com Vetores

Podemos trabalhar com vetores numéricos, executando operações sobre eles da mesma forma como executaríamos com variáveis numéricas comuns. Devemos assumir que ao declararmos um determinado vetor[índice], com um índice específico, estamos fazendo referência a um número.

http://pt.wikibooks.org/wiki/Algoritmos_e_Estruturas_de_Dados/Vetores_e_Matrizes

A diferença entre pilha e fila

Pilha:
Uma estrutura de pilha (stack), estabelece uma política LIFO -- last in, first out. Uma estrutura de pilha também oferece basicamente duas operações de manipulação, PUSH, para inserção no topo da pilha, e POP, para retirada do topo da pilha.
Embora também fosse possível implementar uma pilha através de lista usando os procedimentos que acrescentam e removem os nós no final da lista, por razões óbvias de desempenho uma pilha é usualmente implementada usando os procedimentos INSERT e REMOVEFIRST, que não requerem a varredura da lista para estabelecer essa política de manipulação de dados.

Fila:
Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos.  Mais especificamente, uma  fila (= queue)  é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.
Em outras palavras, o primeiro objeto inserido na fila é também o primeiro a ser removido
. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).

http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node30.html


http://www.ime.usp.br/~pf/algoritmos/aulas/fila.html

Estrutura de Dados

Árvores binárias

Uma árvore binária é uma estrutura de dados mais geral que uma lista encadeada.  Este capítulo introduz as operações mais simples sobre árvores binárias. O capítulo seguinte trata de uma aplicação básica.

Nós e filhos

Uma árvore binária (= binary tree) é um conjunto de registros que satisfaz certas condições.  (As condições não serão dadas explicitamente, mas elas ficarão implicitamente claras no contexto.)  Os registros serão chamados nós (poderiam também ser chamados células).  Cada nó tem um endereço.  Suporemos por enquanto que cada nó tem três campos:  um número inteiro e dois ponteiros para nós.  Os nós podem, então, ser definidos assim:

O campo conteudo é a "carga útil" do nó;  os outros dois campos servem apenas para dar estrutura à árvore.  O campo esq de todo nó contém o endereço de outro nó ou NULL.  A mesma hipótese vale para o campo dir.  Se o campo esq de um nó X é o endereço de um nó Y, diremos que Y é o filho esquerdo de X.  Analogamente, se X.dir é igual a &Y então Y é o filho direito de X.

Se um nó Y é filho (esquerdo ou direito) de X, diremos que X é o pai de Y.  Uma folha (= leaf) é um nó que não tem filho algum.

É muito conveniente confundir cada nó com seu endereço.  Assim, se x é um ponteiro para um nó (ou seja, se x é do tipo *no), dizemos simplesmente  "considere o nó x"  em lugar de  "considere o nó cujo endereço é x".

http://www.ime.usp.br/~pf/algoritmos/aulas/bint.html