Pagina anteriorIndiceProxima pagina

Algoritmos Computacionais

4.1

Capítulo 4

Estrutura de Dados

4.1 Estruturas de dados

Estruturas primitivas : inteiro, caracter, real, etc.
 A maioria dos computadores têm instruções para manipulá-las.
 

Tipos de dados não-primitivos:

Vetor - É um conjunto que contém um número fixo de elementos de um mesmo tipo. Cada elemento do vetor está associado a um índice único.
Ex.: Vetor de números inteiros [0,4,7,10,3,2,0,4]
Um vetor deve possuir um nome.
Ex.: VETOR_INTEIRO

Ex.: Algoritmo para ler as notas de 3 alunos e imprimir os nomes daqueles cujas notas forem maior que a média.
 
Algoritmo Notas {Sem Vetor}
Início
    Ler Nome1, Nota1
    Ler Nome2, Nota2
    Ler Nome3, Nota3
    Média <- (Nota1+Nota2+Nota3)/3.0
    Se Nota1 > Média
      Então Imprimir Nome1
    Fim Se
    Se Nota2 > Média
       Então Imprimir Nome2
    Fim Se
    Se Nota3 > Média
       Então Imprimir Nome3
    Fim Se
Fim de Notas.
Algoritmo Notas {Com Vetor}
Início
 Para I <- 1 Até 3 Faça
  Ler Nome[I], Nota[I]
 Fim Para
 {Cálculo da Média}
 Soma <- 0.0
 Para I <- 1 Até 3 Faça
  Soma <- Soma + Nota [I]
 Fim Para
 Média <- Soma/3.0
 Para I <- 1 Até 3 Faça
  Se Nota[I] > Média
  Então Imprimir Nome[I]
  Fim Se
 Fim Para
Fim de Notas

Ex.: Ordenar um vetor de N números inteiros em ordem crescente.
 Algoritmo
1.Repetir N vezes
2.Procurar o menor valor do vetor
3.Copiar este valor para a menor posição de um vetor alternativo
4.Mudar este valor para um valor bem alto
2.1 Índice_min <- 1
2.2 Para I <- 1 até N faça
2.3     Se VETOR[I] < VETOR[Índice_min]
          Então Índice_min <- I  
          Fim Se
3.1 Vetor_Alternativo[Posição_min] <- VETOR [Índice_min]
4.1 VETOR[Índice_min] <- 9999

Variáveis
Índice_Min: Inteira <- Posição do menor elemento
Vetor [ ]: Conjunto De N Números Inteiros ? Desordenados
Vetor_Alternativo [ ]: Ordenado
Posição_Min: Inteira <- Posição ainda não ocupada do Vetor_Al-ternativo
I: Inteira <- Controle do laço
N: Inteira <- Número de elementos
 
Algoritmo Ordena
Início
   Para Posição_Min <- 1 Até N Faça
      Índice_Min <- 1
      Para I <- 2 Até N Faça
          Se Vetor[I] < Vetor[Índice_Min]
          Então Índice_Min <- I
          Fim Se
      Fim Para
  Vetor_Alternativo[Posição_Min] <- Vetor[Índice_Min]
  Vetor[Índice_Min] <- 9999
 Fim Para
Fim de Ordena

Usando apenas um vetor, trocar o menor elemento numa passagem pelo elemento atualmente em teste.
 
Algoritmo Ordena
Aux:Inteiro
Início
 Para Posição_Min ? 1 Até N-1 Faça
  Índice_Min ? Posição_Min
  Para I <- Posição_Min + 1 Até N Faça
   Se Vetor[I] < Vetor[Índice_Min]
   Então Índice_Min <- I
   Fim Se
  Fim Para
  Se Índice_Min  ? Posição_Min
  Então Aux ? Vetor[Posição_Min]
        Vetor[Posição_Min] <- Vetor[Índice_Min]
        Vetor[Índice_Min] <- Aux
  Fim Se
 Fim Para
Fim de Ordena
1ºAlgoritmo tem complexidade     N*(N-1)
O segundo tem complexidade dada por:  
 O conceito de vetor pode ser generalizado para o conceito de matriz.
Ex.: MATRIZ_A [3,4] conjunto de inteiros
Matriz_A[1,1] = 10
Matriz_A[2,3] = 1


Pagina anteriorIndiceProxima pagina

araujo@eng.uerj.br