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// MAC122
003// 2017/09/07
004
005// Ordena vetor de palavras ("strings") usando o metodo da Bolha e trocando efetivamente as palavras de posicao
006// Le de arquivo "N\n" e a seguir N linhas com um nome cada
007// Complexidade: O(n*n * u), se u = comprimento medio das palavras
008
009// Exercicio 1: Altere o codigo para ler as linhas e deduzir numero nomes
010// Exercicio 2: Prove que o algoritmo de ordenacao implementado e' estavel
011
012#include <stdio.h> 
013#include <stdlib.h>
014#include <string.h>
015
016#define MAXCOMPLINHA    512 // maior comprimento de linha aceito
017#define MAX           10000 // maior quantidade de linhas aceitas (no arquivo de entrada)
018
019// Leia proxima linha do arquivo apontado por 'aptf', devolva no endereco da "string" que a recebeu
020char * leituraElemento (FILE *aptf, char linha[]) {
021  if (fgets(linha, MAXCOMPLINHA, aptf)==NULL || ferror(aptf) || feof(aptf) ) { // char *fgets(char *str, int n, FILE *stream)
022    printf(" - %s", linha);
023    if (linha != NULL) return linha;
024    return NULL; // final de arquivo
025    }
026  printf(" * %s", linha);
027  return linha;
028  }
029
030// Leia todas as linhas (de palavras) presentes no arquivo de entrada
031// Primeira linha deve ter um inteiro com numero de palavras no arquivo (isso pode ser alterado, experimente)
032void leituraVetor (FILE *apf, char vetStr[][MAXCOMPLINHA], int *N) {
033  int i = 0, f;
034  char *linha0;
035  fscanf(apf, "%d", N); printf(" - n=%d\n", *N);
036  f = *N;
037  // Em geral, apos ler o inteiro o apontador e' posicionado para proximo caractere que
038  // corresponderia ao final de linha ('\n'), assim precisa forcar para evitar pegar esta linha "nula".
039  linha0 = leituraElemento(apf, vetStr[i]);
040  if (linha0!=NULL && linha0[0]=='\0') f = *N+1; // ignore primeira linha
041  for (i = 0; i < f; i++)
042    if (leituraElemento(apf, vetStr[i]) == NULL)
043      break;
044  }
045
046// Auxiliar
047void imprimeVetor (char vetStr[][MAXCOMPLINHA], int n) {
048  int i;
049  for (i = 0; i < n; i++) {
050    printf("%s", vetStr[i]);
051    }
052  }
053
054// Troque de lugar as "strings" nas posicoes i e j
055void trocaEmVetor (char vetStr[][MAXCOMPLINHA], int i, int j) {
056  char aux[MAXCOMPLINHA];
057  strcpy(aux, vetStr[i]);       // aux <- vetStr[i];
058  strcpy(vetStr[i], vetStr[j]); // vetStr[i] <- vetStr[j];
059  strcpy(vetStr[j], aux);       // vetStr[j] <- aux;
060  }
061
062// Ordena comparando palavras usando o metodo da Bolha e trocando as "strings" de posicao.
063void ordenaBolha (char vetStr[][MAXCOMPLINHA], int N) {
064  int i, j;
065  for (i = 1; i < N; i++) { //D printf("\ni=%3d: ", i);
066    for (j = i; j > 0; j--) { //D printf("%d ", j);
067      if (strcmp(vetStr[j-1], vetStr[j]) > 0)
068        trocaEmVetor(vetStr, j, j-1);
069      }
070    } //D printf("\n");
071  }
072
073// Comeca aqui!
074int main (int argc, char *argv[]) {
075  FILE *apont;
076  char vetorDados[MAX][MAXCOMPLINHA];
077  int N;
078
079  if (argc < 2) {
080      printf("Necessario um nome de arquivo como parametro\n");
081      printf("Arquivo com: N seguido de N strings para ordenar\n");
082      return 1;
083      }
084  printf("Abre %s\n", argv[1]); //return 1; 
085  apont = fopen(argv[1], "r");
086
087  leituraVetor(apont, vetorDados, &N);
088
089  printf("\nInicial:\n");
090  imprimeVetor(vetorDados, N);
091
092  ordenaBolha(vetorDados, N);
093
094  printf("\nOrdenado:\n");
095  imprimeVetor(vetorDados, N);
096
097  return 0;
098
099  }