Estrutura de Dados

Árvores

Árvores são estruturas de dados organizados através da dependência de elementos sucessores ("filhos") em relação a seus antecessores ("pais"). Existe um componente (nó) especial chamado raiz, a partir do qual a árvore começa. A organização dos nós deve seguir algum critério, sem o que fica difícil empregar a estrutura de forma prática.

Ex.:
Árvore s/ critérios
(apenas conceitual)

Árvores binárias de busca (ABB)

Árvores binárias são estruturas organizadas de forma que cada nó possui zero, um ou dois filhos. Em nenhuma circunstância pode haver violação desta regra. Árvores binárias de busca (ABB) possuem uma regra de formação: geralmente, os descendentes maiores devem ser alocados à direita de seus ascendentes, enquanto os descendentes menores devem ficar à esquerda.

Ex. ABB:

Ex. 2: montagem de uma ABB dada uma certa ordem.

62 - 48 - 84 - 37 - 53 - 96 - 77 -
25 - 40 - 89 - 99 - 65 - 43 - 30 -
50 - 19 - 1

Estrutura de um nó em C

typedef struct temp
{
int dado;
struct temp *dir;
struct temp *esq;
}ABB;

Por exemplo, pode-se declarar alguns ponteiros globais:
ABB *novo, *aux, *pai, *apaga, *raiz;

main()
{
novo = aux = pai = apaga = raiz = NULL;
.
.
.

Inclusão em ABB

void incluir()

{
    int qual;
    printf("nElemento a incluir= "); scanf("%d", qual);
    novo = (ABB*) malloc (sizeof(ABB)); novo -> dado = qual;
    novo -> esq = novo -> dir = NULL;
    if (raiz == NULL) // árvore vazia!
    {
        raiz = novo;
        return;
    }

    posiciona();
    if (novo -> dado > pai -> dado) pai -> dir = novo;
    else pai -> esq = novo;

}


void posiciona()
{
­ aux = pai = raiz;
    while (aux != NULL)
    {
        pai = aux;
        if (novo -> dado > aux -> dado) aux = aux -> dir;
        else aux = aux -> esq;
    }
}

Exclusão em ABB

Pela direita do nó: pegar o menor dos maiores
· Se o sucessor imediato não tiver filhos à esquerda, então
  ele mesmo é o menor dos maiores;
· Se o sucessor imediato tem filhos à esquerda, o menor dos
  maiores é o último elemento à esquerda.

Pela esquerda do nó: pegar o maior dos maiores
  A lógica é a mesma, invertendo os sentidos.

void excluir()
{
    int qual; apaga = raiz;  if (raiz == NULL) return;
    printf("nQual elemento exclui?= "); scanf("%d", &qual);
    while (qual != apaga -> dado && apaga != NULL)
    {
        pai = apaga;
        if (qual > apaga -> dado) apaga = apaga -> dir;
        else apaga = apaga -> esq;
    }
    if (apaga == NULL) return;
    if (apaga -> dir != NULL) excluir_a_direita();
    else excluir_a_esquerda();
}

void excluir_a_direita()
{
    pai = aux = apaga = dir;
    if (aux -> esq == NULL)
    {
        apaga -> dir = aux -> dir;
        apaga -> dado = aux -> dado;
        free(aux);
    }
    while (aux -> esq != NULL)
    {
        pai = aux;
        aux = aux -> esq;
    }
    apaga -> dado = aux -> dado;
    pai -> esq = aux -> dir;
    free (aux);
}

void excluir_a_esquerda()
{
onde for dir (direita) troca por esq (esquerda)
e vice-versa
}

S. A. T. C.

Aula CVS - Part II

Para fazer no Eclipse (C:\Arquivos de Programas\Java\jdk3.1.2...\eclipse.exe)

1. Crie um novo projeto Java. Para isso clique File > New > Project... :

1.1 Na tela seguinte, escolha um Projeto Java e clique "Next" :

1.2 Dê um nome ao seu Projeto, preenchendo o campo "Project Name:" e clique "Finish" :

1.3 Crie uma Classe. Faça File > New > Class:

1.4 No campo "Name:" dê um nome a sua Classe. Marque a opção public static void main(String[] args) e clique "Finish":

2. Hora de publicar seu projeto na máquina servidora. Então clique com o botão direito no seu projeto na aba Package Explorer e selecione Team > Share Project...

2.1 Em seguida inclua os dados da conexão com o servidor e do diretório de reposição. Clique "Next":

2.2 Na tela que surge, escolha a opção Use an existing module e clique sobre o módulo existente. Em seguida, "Finish":

Agora, se vc deseja importar um Projeto do CVS...

1º) Clique em File > Import... :

2º) Na tela Import, selecione Checkout Projects from CVS e clique em "Next" :

!Hasta la vista Sñrs!

Banco de Dados II

Recuperando Dados de Várias Tabelas (JOINS)

Para que possamos recuperar informações de um banco de dados, muitas vezes temos a necessidade de acessar simultaneamente várias tabelas relacionadas entre si. Algumas dessas consultas necessitam realizar uma junção (JOIN) entre tabelas, para que dessa junção possa extrair as informações necessárias à consulta formulada.

Exemplo:

CLIENTES
codigo	nome	cidade	estado
1	João	Jundiaí	SP
2	Ana	Jundiaí	SP
3	Maria	Campinas	SP
4	José	Jundiaí	SP
5	Flávio	Jundiaí	SP
6	Renato	Campinas	SP

6 rows

VENDEDORES
identificacao	nome
10	Marcelo
20	Kátia
30	Thiago

3 rows

PEDIDOS
numero	VENDEDORES_identificacao	CLIENTES_codigo	data_hora
1	10	1	2007-05-21 00:00:00.000
2	10	2	2007-05-20 00:00:00.000
3	20	1	2007-05-19 00:00:00.000
4	30	7	2007-05-18 00:00:00.000
5	10	7	2007-05-21 00:00:00.000
6	50	1	2007-05-21 00:00:00.000
7	10	1	2007-05-17 00:00:00.000

7 rows

Inner Joins

Quando usamos INNER JOIN como tipo de join, serão incluídas somente as linhas que satisfazem a condição do join.

Exemplo:

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES INNER JOIN PEDIDOS
ON codigo = CLIENTES_codigo

nome	CLIENTES_codigo	numero
João	1	1
Ana	2	2
João	1	3
João	1	6
João	1	7

5 rows

Nesta junção são apresentados os pedidos de cada cliente, pois a condição de join restringe e qualifica a junção dos dados entre as tabelas. A equação apresentada na cláusula WHERE é chamada de equação de junção.

Cross Joins

Quando usamos CROSS JOIN, incluímos cada uma das combinações de todas as linhas entre as tabelas.


Exemplo:

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES CROSS JOIN PEDIDOS

nome	CLIENTES_codigo	numero
João	1	1
João	2	2
João	1	3
João	7	4
João	7	5
João	1	6
João	1	7
Ana	1	1
Ana	2	2
Ana	1	3
Ana	7	4
Ana	7	5
Ana	1	6
Ana	1	7
Maria	1	1
Maria	2	2
Maria	1	3
Maria	7	4
Maria	7	5
Maria	1	6
Maria	1	7
José	1	1
José	2	2
José	1	3
José	7	4
José	7	5
José	1	6
José	1	7
Flávio	1	1
Flávio	2	2
Flávio	1	3
Flávio	7	4
Flávio	7	5
Flávio	1	6
Flávio	1	7
Renato	1	1
Renato	2	2
Renato	1	3
Renato	7	4
Renato	7	5
Renato	1	6
Renato	1	7

42 rows

Podemos observar que não existe muito proveito do resultado desse tipo de join, executando-se quando queremos fazer referência cruzada entre as duas tabelas e suas linhas todas.

Outer Join

Quando usamos OUTER JOIN, incluímos as linhas que satisfazem a condição de join e as linhas restantes de uma das tabelas do join.
É a seleção em que são restritas as linhas que interessam em uma tabela, mas são consideradas todas as linhas de outra tabela.
Ou seja, queremos ver as linhas de uma tabela que estão relacionadas com as de outra tabela e quais linhas não estão.

Exemplificando no mundo real, poderíamos dizer que queremos ver quais clientes têm pedidos e quais não têm nenhum pedido.
É de muita utilidade quando queremos verificar se existem membros órfãos em um banco de dados, ou seja, chave primária e chave estrangeira sem sincronia ou simetria.

Um OUTER JOIN somente pode ser realizado entre duas tabelas, não mais que duas tabelas.

Possui três tipos de qualificador para o OUTER JOIN.

LEFT OUTER JOIN - são incluídas todas as linhas da tabela do primeiro nome de tabela (a tabela mais à esquerda da expressão)

RIGHT OUTER JOIN - são incluídas todas as linhas da tabela do segundo nome de tabela da expressão (tabela mais à direita da expressão)

FULL OUTER JOIN - são incluídas as linhas que não satisfazem a expressão tanto da primeira quanto da segunda tabelas.

Exemplos:

1. Quais os clientes que têm pedido e os que não têm pedido

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES LEFT OUTER JOIN PEDIDOS
ON codigo = CLIENTES_codigo

nome	CLIENTES_codigo	numero
João	1	1
João	1	3
João	1	6
João	1	7
Ana	2	2
Maria	NULL	NULL
José	NULL	NULL
Flávio	NULL	NULL
Renato	NULL	NULL

9 rows

2. Quais os pedidos que têm cliente e os que não têm cliente

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES RIGHT OUTER JOIN PEDIDOS
ON codigo = CLIENTES_codigo

nome	CLIENTES_codigo	numero
João	1	1
Ana	2	2
João	1	3
NULL	7	4
NULL	7	5
João	1	6
João	1	7

7 rows

3. Quais os clientes que têm pedido e os que não têm pedido e quais os pedidos que têm cliente e os que não têm cliente

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES FULL OUTER JOIN PEDIDOS
ON codigo = CLIENTES_codigo

nome	CLIENTES_codigo	numero
João	1	1
João	1	3
João	1	6
João	1	7
Ana	2	2
Maria	NULL	NULL
José	NULL	NULL
Flávio	NULL	NULL
Renato	NULL	NULL
NULL	7	4
NULL	7	5

11 rows

Podemos utilizar as cláusulas LIKE, NOT LIKE, IN, NOT IN, NULL, NOT NULL e misturá-las com os operadores AND, OR e NOT, dentro de uma cláusula WHERE na junção de tabelas.


Exemplo:

SELECT nome, CLIENTES_codigo, numero
FROM CLIENTES INNER JOIN PEDIDOS
ON codigo = CLIENTES_codigo
WHERE nome LIKE 'J%' AND DAY(data_hora) = 21

nome	CLIENTES_codigo	numero
João	1	1
João	1	6

2 rows

Estrutura de Dados

Prova 1

Sñrs.,
Esta é uma das possíveis soluções para o 1º Teste da Prova de ontem. Resolvi postar na esperança de que um dos Sñrs (diferentemente de mim...) possa ter resolvido a questão...

---

#include <stdio.h>
#include <malloc.h> // <- biblioteca p/ uso do comando malloc
main()
{
int *v, n, i;
do
{
printf("\nQual o tamanho do vetor?= ");
scanf("%d", &n);
}while(n<1);

v = (int*)malloc(n*sizeof(int));
int *x = (int*)malloc(n*2*sizeof(int)); // <- declaração e alocação do vetor x com o dobro do tamanho de y
for(i=1; i<=n; i++)
{
v[i-1]=i*5;
printf("| %d |", v[i-1]);
}

printf(" -> Vetor v\n");

for(i=0; i<n*2; i+=2)
{
x[i]=v[i/2];
x[i+1]=-1;
printf("| %d || %d |", x[i], x[i+1]);
}

printf(" -> Vetor x");
fflush(stdin); getchar();
}

---

!Hasta la vista!

Estrutura de Dados
Fila (FIFO)

Teoria:

Sequência ordenada de elementos, podendo ser adicionados novos elementos numa das extremidades (parte de trás ou cauda) e retirados na outra extremidade (parte da frente ou cabeça).
• Só os elementos que estão à frente é que podem ser retirados;
• Só se pode adicionar novos elementos na parte de trás;
• A fila de espera comporta- se como um FIFO (“First- IN, First- Out”).

Depois de muito queimar a mufa, descobri que a melhor resposta era CTRL + C, CTRL + V...
Com um código-fonte gentilmente cedido por uma pessoa que conheci hoje na faculdade, fiz umas adaptações no código anterior:

---

#include <stdio.h>
 #include <malloc.h>
 
 typedef struct temp
 {
     int dado;
     struct temp *prox;
 }pilha;
 
 pilha *chao,*topo, *novo;
 
 // colocar aqui funções de manipulação
 
 void inserir()
 {
     novo=(pilha*) malloc (sizeof(pilha));
     printf("\n\tDigite o dado p/ armazenar=
");
     scanf("%d", &novo->dado); //armazenar 1 valor em um dado
     novo -> prox = NULL;
     if (chao==NULL) //fila vazia
         chao=novo;
     else
     topo->prox = novo;
     topo = novo;
 }   
 
 
 void retirar()
 {
     if(topo==NULL)
     {
         printf("\n\tPilha vazia!");
         return;
     }
     novo = chao;
 
     chao = chao->prox;
 
     free(novo); //"desalocar", liberar memória
 }
 
 void mostrar()
 {
     if(chao==NULL)
     {
         printf("\n\tPilha vazia!");
         return;
     }
     novo = chao; //começa do chao
     while (novo != NULL)
     {
         printf("\t%d", novo->dado);
         novo = novo->prox; //vá p/ o próximo!
     }
 }                  
 
 main()
 {
     chao = topo = novo = NULL; //pilha vazia!
     int op;
     do
     {
         printf("\n\nDigite uma opcao: ");
         printf("\n\t1-Inserir\n\t2-Retirar");
         printf("\n\t3-Mostrar\n\t4-Fim\n\n->");
         scanf("%d", &op);
         switch(op)
         {
             case 1: inserir(); break;
             case 2: retirar(); break;
             case 3: mostrar(); break;
             case 4: break;
             default: printf("\n\t***Erro!");
         }
     }while (op != 4);
 }
 

---

* Os Sñrs devem ter ouvido o professor falar
que poderia ser feito sem o uso de outra referência (ponteiro), não? Pois o desafio agora é esse. Buenas suertes...

Estrutura de Dados

Pilhas (dinâmicas)

Pilhas são estruturas de dados, que podem ser alocadas dinâmica ou sequencialmente. Têm uma disciplina de acesso rígida, que deve sempre ser observada (LIFO: last in, first out; o último a entrar é o primeiro a sair).

As pilhas são úteis na construção de programas como sistemas operacionais e quaisquer outros que disciplinem acessos concorrentes, nos quais exista espera (ver sosim).

        temp{|____| -> armazenar dados (int, float,...)
       *temp{|____| -> referência, ligação (ponteiro)
    
     |3|} temp
    
     ---
     
     |_|
     
     |2|
     ---
     |_|
     
     |1|
     ---
     |_|
 

NULL -> "chão"

pilha.exe
||
SO
||
processo
(código + dados + refs)

1º passo: criar 1 unidade da pilha, na forma de estrutura (em C, struct).
struct é um dado heterogêneo, misto, ou seja, comporta vários tipos de dados, inclusive outros struct's.

/*criar 1 tipo personalizado, cujo nome*/
timedef struct temp //repete daqui
    {
        int dado;  // declarar todos os
        float num; // dados que precisar, qq tipo.
        struct temp *prox; //declarar 1 ponteiro do mesmo tipo do struct               
        //repete aqui (obrigatoriamente)
     }pilha; /* é pilha*/

FILA (FIFO)
//<- FIM
inicio -> |_| -> |_| -> |_| -> NULL //INSERIR NO FIM
//remover do começo