Este projeto, realizado no âmbito da cadeira de Algoritmos e Estrutura de Dados, do curso LEE, teve como objectivo a elaboração de um programa na linguagem de programação C. O programa texto percorre o ficheiro de palavras e, para cada palavra diferente encontrada, cria uma lista de ocorrências.

A saída do programa depende dos argumentos da linha de comando.

Versão elementar “f” – Indica o número de palavras diferentes no ficheiro;

          Versão simples “-s” – O programa lista todas as palavras do ficheiro por ordem alfabética e, para cada uma, o número de ocorrências;

          Versão de detalhe “-d” – O programa lista todas as palavras do ficheiro e, para cada uma, todas as linhas e colunas que esta ocorre;

          Versão ordenada direta “-o” – O programa lista todas as palavras do ficheiro por ordem crescente do número de ocorrências;

          Versão ordenada inversa “-r” – O programa lista todas as palavras do ficheiro por ordem inversa do número de ocorrências.

Escolha de estruturas

De forma a resolver o problema proposto e obter a maior eficácia, foi necessário fazer uma escolha ponderada das estruturas de dados a utilizar ao longo do projecto.

As funções já criadas numa primeira parte do projecto utilizaram como estrutura listas ligadas, filas.

Já na segunda parte, as primeiras três versões do programa requerem uma ordenação tendo como prioridade a ordem alfabética. Desta forma, foi necessário escolher um algoritmo de ordenação que fosse o mais eficaz possível. Por isso, escolheu-se usar uma “Binary Search Tree (bst)”. Desta forma conseguiu-se que a árvore fosse composta por vários nós (tantos quanto o número de palavras existente no ficheiro), em que cada nó tem a palavra, a lista de ocorrências desta palavra, entre outros elementos importantes como ponteiros para o nó à esquerda e nó à direita.

Para as últimas duas versões, o objectivo era ordenar as palavras por número de ocorrência. Para isso, a estrutura de dados escolhida foi um array. Os nós da árvore foram passados para um array que, como tal, ficou com o tamanho igual ao número de nós existente na árvore. Escolhida a estrutura para guardar os nós, foi necessário escolher um algoritmo de ordenação que fosse suficientemente rápido e eficaz, o “QuickSort”.

Assim, é possível concluir que, ainda que o programa tenha como principal base a ordenação de palavras, para diferentes fins por vezes é necessário usar diferentes estruturas de dados. Neste caso, mais precisamente, foram necessárias três importantes estruturas de dados.

Apesar de haver outras estruturas com o mesmo propósito das que foram usadas, estas provaram ser as mais apropriadas.

Todas estas escolhas estão melhor justificadas com os valores de crescimento de cada função que não serão enunciadas neste post pois tornar-se-ia algo cansativo, no entanto, é de notar a importância de uma boa análise de algoritmos.

Análise de Algoritmos

A notação Grande-O ou notação assintótica (Big-O Notation) é uma notação matemática utilizada para analisar o comportamento assintótico de funções.

Quando se está a planear escrever um determinado programa é muito importante ter em conta a ordem de crescimento de cada função utilizada, pois isso vai condicionar o programa. Escolhas menos acertadas vão, certamente, prejudicar o resultado, uma vez que as funções obtêm um nível de rapidez abaixo do esperado.