Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/08/16
003// 
004// Descricao:
005// 1. funcao "buscaSentinela(int vet[], int n, int x)" que devolve i se x ocorre primeiro na posicao i, -1 em caso contrario
006// 2. programa principal que
007//    * entrada dados: usuario digita valores ate que entra negativo, primeiro valor e' guardado na posicao 0 e assim por diante
008//                     o ultimo valor digitado (negado) NAO sera' armazenado!
009//    * buscas:        usando a funcao de 1, o usuario devera digitar um valor, se negativo pare (e nada imprime), senao
010//                     verifique se valor no vetor (imprimindo sua posicao ou -1 se nao estiver no vetor)
011//                     o programa para quando usuario digitar um valor negativo (neste caso o programa deve imprimir NADA).
012
013#include <stdio.h>
014
015#define MAX 50
016
017// Vetor nao ordenado: melhoria incremental (uma comparacao a menos por passo)
018// Param:   'vet[]' vetor com dados, 'int n' numero de elementos no vetor, 'int x' elemento buscado
019// Devolve: j entre 0 e n-1 se encontrou na posicao j; -1 se x nao pertence a 'vet[]'
020int buscaSentinela (int vet[], int n, int x) {
021  int j = 0;
022  vet[n] = x;            // necessario uma posicao adicional para o sentinela
023  while (vet[j]!=x) j++; // invariante: x NAO pertence a 'vet[0]' ate 'vet[j-1]'
024  if (j<n)               // parou antes do sentinela => encontrou!
025    return j;
026  return -1;
027  }
028
029int main (void) {
030  int n, vet[MAX];
031  int i, x = 0;
032  // entrada de dados - tamanho do vetor (quantos dados uteis)
033  scanf("%d", &n);
034  // entrada de dados - supor valor nao negativos
035  for (i=0; i<n; i++)
036    scanf("%d", &vet[i]);
037  printf("busca...\n");
038  // busca elementos (digitar negativo finaliza programa)
039  x = 0;
040  while (x>=0) {
041    scanf("%d", &x);
042    if (x>=0) {
043      i = buscaSentinela(vet, n, x);
044      if (i>=0)
045         printf("%d\n", i);
046      else
047         printf("-1\n"); // NAO encontrado
048      }
049    }
050  return 0;
051  }