Estrutura De Dados

ALGORITMOS E ESTRUTURAS DE DADOS

Trabalho Prático

Indice Remissivo [Ziviani, 2004; Exerc´ıcio 5.16]

Comentários Gerais

O objetivo deste trabalho é o de projetar e implementar um sistema de programas, incluindo as estruturas de dados e os algoritmos. Neste trabalho, o aluno terá a oportunidade de exercitar parcialmente o conceito de independência de implementação, através da utilização de duas estruturas de dados distintas para implementar o mesmo problema. Neste caso, o módulo que implementa cada uma das estruturas de dados deverá permitir o intercâmbio entre uma estrutura e outra, causando o menor impacto possível em outras partes do programa.

O que deve ser apresentado:

1. Listagem do programa em Java.

2. Listagem dos testes executados.

3. Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.

4. Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).

Problema: Criação de índice remissivo

Várias aplicações necessitam de um relatório de referências cruzadas. Por exemplo, a maioria dos livros apresentam um índice remissivo que corresponde a uma lista alfabética de palavras chave ou palavras relevantes do texto com a indicação dos locais no texto onde cada palavra chave ocorre.

Como exemplo, suponha um arquivo contendo um texto constituído como abaixo:

Linha 1: Good programming is not learned from

Linha 2: generalities, but by seeing how significant

Linha 3: programs can be made clean, easy to

Linha 4: read, easy to maintain and modify,

Linha 5: human-engineered, efficient, and reliable,

Linha 6: by the application of common sense and

Linha 7: by the use of good programming practices.

Assumindo que o índice remissivo seja constituído das palavras chave:

programming, programs, easy, by, human-engineered, and, be, to,

o programa para criação do índice deve produzir a seguinte saída:

and 4 5 6

be 3

by 2 6 7

easy 3 4

human-engineered 5

programming 1 7

programs 3

to 3 4

Note que a lista de palavras chave está em ordem alfabética. Adjacente a cada palavra está uma lista de números de linhas, um para cada vez que