Projeto de Algoritmos

Algumas ferramentas
presentes em todos os sistema Unix e GNU/Linux

Para consultar o manual sobre uma ferramenta, "utilitário" ou comando xxx no sistema GNU/Linux, diga

   man xxx

od

O programa od (de "octal dump") exibe os códigos dos caracteres de um arquivo, digamos xxx. Diga

od -t u1 -A d xxx

para exibir os códigos em notação decimal.  Diga

od -t o1 -A d xxx

para exibir os códigos em notação octal.  Diga

od -t c -A d xxx

para exibir os símbolos gráficos dos caracteres que têm tais símbolos.

wc

O programa wc (de "word count") conta o número de linhas, de palavras e de caracteres de um arquivo dado.  Se o seu arquivo é xxx, basta dizer

wc xxx

Veja a versão do programa wc escrito por Donald Knuth e Silvio Levi. Eis o documento original, antes de sua conversão automática em código C. Isso foi escrito por Knuth e Levi para ilustrar o sistema CWEB de "programação letrada".

sort

sort file

Ordena lexicograficamente as linhas do arquivo file. Tem muitas opções (por exemplo, ignorar espaços em branco no início da linha, ignorar caracteres que não sejam letras, usar como chave a string que começa no k-ésimo caracter da linha, etc.)

diff

diff -b -B -y

cmp

cmp file1 file2

indent

Faz uma endentação (ou denteação, como querem alguns) correta de um programa C.  Se o seu programa está no arquivo xxx.c, diga

indent -br -brs -nut -l65 -lc65 -fca -fc1 -T bool -T string  xxx.c

Veja  man indent.

pr

pr -3 -t

tr

tr

ispell

ispell -t files

enscript

Converte arquivos-texto em HTML, PostScript, etc.  Exemplo:

enscript --highlight=c --color --language=html --output=isort.html isort.c
converte o arquivo  isort.c no arquivo isort.html.

fmt

Um formatador de texto simples.
fmt -w65 <nome_do arquivo>

col

col -b -x <file

gdb

GNU debugger (depurador de programas)

gprof

GNU profiler: dá estatísticas sobre a execução de um programa (quantas vezes cada função foi chamada, a quantidade de tempo que cada função consumiu, etc.)

bc

Arbitrary precision calculator language

bc 

 


Algumas funções úteis

(Essas funções devem ser invocadas de dentro de um programa.)

qsort

A função qsort rearranja o vetor  base[0..nmemb-1]  em ordem crescente.  (O endereço do primeiro elemento do vetor é  base  e o vetor tem  nmemb  elementos.)  A natureza dos elementos do vetor não importa, mas  qsort  precisa saber que cada elemento ocupa  size  bytes.  Eis o protótipo da função:

qsort(void *base, 
      size_t nmemb, 
      size_t size, 
      int (*compar)(const void *, const void *));

Esse protótipo está no arquivo-interface stdlib.h.   O último argumento de  qsort  é uma função  compar,  que recebe os endereços (moldados por void *) de dois elementos do vetor e devolve um inteiro

A função qsort é, essencialmente, uma implementação do algoritmo QuickSort.

EXEMPLO 1:  Suponha que a[0..n] é um vetor de inteiros. Se cmp é a função definida por

int cmp (const void *x, const void *y) {
   return (*(int *)x - *(int *)y); 
}

então o comando

qsort(a, n+1, sizeof (int), cmp);

rearranja o vetor a[0..n] em ordem crescente.

EXEMPLO 2:  Suponha que str[0..n] é um vetor de strings (declarado por "char *str[99]", por exemplo).  Se cmp é a função definida por

int cmp (const void *x, const void *y) {
   return strcmp(*(char **)x, *(char **)y); 
}

então o comando

qsort(str, n+1, sizeof (char*), cmp);

rearranja o vetor str[0..n] em ordem lexicográfica.

EXEMPLO 3:  Suponha que  a  é um vetor de structs do tipo aluno:

struct al {
   char nome[81];
   int nota;
};
typedef struct al aluno;
aluno a[1000];

A seguinte função compara os alunos apontados por x e y com base nas suas notas:

int cmp (const void *x, const void *y) {
   int notax, notay;
   notax = ((aluno *)x)->nota;
   notay = ((aluno *)y)->nota;
   return notax - notay;
}

Para rearranjar o vetor a[0..n-1] em ordem crescente de notas, basta dizer

qsort(a, n, sizeof (aluno), cmp);

 


URL of this site: www.ime.usp.br/~pf/algoritmos/