Apostila De Aed Em C++

Pontifícia Universidade Católica de Minas Gerais Bacharelado em Sistemas de Informação Algoritmos e Técnicas de Programação II Professores Fabio Tirelo e Silvio Jamil

Conte´ udo 1 Qualidade de C´ odigo

1

2 Classes

6

3 Tipos Abstratos de Dados 3.1 Defini¸c˜ ao . . . . . . . . . . . . . . . 3.2 Implementa¸c˜ ao de um TAD . . . . . 3.3 Estudo de caso: TAD Vetor . . . . . 3.3.1 Exemplo de Cliente . . . . . 3.3.2 Uma primeira implementa¸c˜ao

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

11 11 11 13 13 13

4 Apontadores

16

5 Aloca¸ c˜ ao Dinˆ amica

19

6 An´ alise de complexidade 6.1 Introdu¸c˜ ao . . . . . . . . . . . . . . . . 6.2 Complexidade computacional e an´alise 6.3 Nota¸c˜ ao O . . . . . . . . . . . . . . . . 6.4 Exemplos . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

24 24 24 25 27

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

29 29 29 30 31 32

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Utilizando Vetores . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

34 34 34 34 35 36

9 Estudo de Caso: TAD Fila 9.1 Defini¸c˜ ao . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Aplica¸c˜ oes . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3 Interface da Classe Fila . . . . . . . . . . . . . . . . . . 9.3.1 Implementa¸c˜ ao do TAD Fila Utilizando Vetores . 9.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

38 38 38 38 39 42

. . . . . . . assint´otica . . . . . . . . . . . . . . .

7 Recursividade 7.1 Defini¸c˜ ao . . . . . . . . . . . . . . . . . 7.2 Ilustra¸c˜ ao de uma abordagem recursiva 7.3 Caracter´ısticas de algoritmos recursivos 7.4 Exemplos . . . . . . . . . . . . . . . . . 7.5 Anatomia de chamadas recursivas . . . . 8 Estudo de Caso: TAD Pilha 8.1 Defini¸c˜ ao . . . . . . . . . . . . . . . 8.2 Aplica¸c˜ oes . . . . . . . . . . . . . . . 8.3 Interface da Classe Pilha . . . . . . . 8.3.1 Implementa¸c˜ ao do TAD Pilha 8.4 Exemplos . . . . . . . . . . . . . . .

1

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

T´ opico 1

Qualidade de C´ odigo Para determinarmos se um programa ´e bom, diversos fatores devem ser analisados. Entre eles, alguns dos mais importantes s˜ ao: • Do ponto de vista do usu´ ario: se o programa est´a correto, se ´e eficiente e se ´e de f´acil utiliza¸c˜ ao; • Do ponto de vista da equipe de programadores: se ´e f´acil fazer altera¸c˜oes, seja para corre¸c˜ao de erros ou para atualiza¸c˜ oes. A corre¸c˜ ao do programa depende particularmente do m´etodo de desenvolvimento utilizado e dos testes que foram feitos. Em geral, este fator est´a intimamente relacionado `as t´ecnicas de programa¸c˜ ao utilizadas. Os testes devem estar centrados principalmente em determinar o comportamento do programa em casos extremos e em detectar pontos cr´ıticos do c´odigo. Um programa ´e eficiente quando faz bom uso dos recursos computacionais existentes. Quando economizamos o tempo de CPU para realizar determinado processamento, dizemos que temos eficiˆencia de tempo; quando economizamos mem´oria dispon´ıvel, dizemos que tempo eficiˆencia de espa¸co. Como veremos, nem sempre estes dois tipos de eficiˆencia s˜ao compativeis, isto ´e, em geral devemos escolher qual dos dois ser´a escolhido. Para sabermos se um programa ´e eficiente, desenvolveremos m´etricas para determinar o comportamento do algoritmo em casos cr´ıticos e formas de comparar dois algoritmos que resolvam um mesmo problema. Aqui, estamos interessados nos fatores de qualidade do ponto de vista do programador, visto que estes garantir˜ ao que o programa seja alterado com mais facilidade quando for necess´ario. Os elementos que chamam a aten¸c˜ ao quando falamos em qualidade do c´odigo s˜ao a indenta¸c˜ ao, os coment´ arios, a documenta¸c˜ ao, a escolha dos identificadores e modulariza¸c˜ ao. A indenta¸c˜ ao permite visualizar as rela¸c˜oes de dependˆencia entre as diversas constru¸c˜oes do programa. Os coment´ arios ajudam a entender algoritmos complexos e a resolver d´ uvidas que possam surgir ao ler um fragmento de c´ odigo. A documenta¸c˜ ao ´e normalmente confundida com coment´arios. A documenta¸c˜ao ´e um relat´orio que explica a l´ ogica do programa, detalhando as etapas do desenvolvimento e descrevendo os algoritmos e as estruturas de dados utilizados, sendo a primeira leitura para quem tiver que entender o programa. A escolha dos identificadores diz respeito a quais nomes dar a vari´aveis, fun¸c˜oes, classes e m´odulos do programa. Nomes de vari´ aveis como x ou a dizem muito pouco (ou quase nada) sobre a finalidade da vari´ avel no programa. Mas, dependendo das caracter´ısticas do problema a ser resolvido podem dizer muito. Por exemplo, no desenvolvimento de um programa para calcular o resultado de um polinˆ omio, o uso de uma vari´avel idenficada por x est´a correto, pois este nome est´a diretamente relacionado ao problema em quest˜ao. Suponha agora, que estamos desenvolvimento um programa para identificar se uma data esta correta, o uso de uma vari´avel identificada por x, neste caso, n˜ ao ´e recomendada, pois esta n˜ao se relaciona com o problema. 1

Notas de aulas de AED

2

A modulariza¸c˜ ao ´e a divis˜ ao do programa em fun¸c˜oes, classes e m´odulos; ao dividir o programa em partes, facilitamos sua leitura, visto que ´e poss´ıvel desenvolver m´etodos para a leitura do programa, via constru¸c˜ oes de alto n´ıvel; por exemplo, ler a fun¸c˜ao main d´a a id´eia do que o programa faz; para conhecermos os detalhes, devemos entender as fun¸c˜oes individualmente. Ainda no item modulariza¸c˜ ao, uma grande dificuldade ´e descobrir como dividir um programa em fun¸c˜oes, isto ´e, o que devem ser as fun¸c˜oes de um programa, como elas devem ser relacionadas, etc. Em geral, podemos procurar partes do programa que est˜ao duplicadas e transform´a-las em chamadas a uma nova fun¸c˜ ao, devidamente parametrizada. Tamb´em ´e interessante que partes distintas do programa fiquem em fun¸c˜ oes distintas. Tomemos por exemplo um programa que leia dois vetores de 10 n´ umeros inteiros e exiba um n´ umero que represente a distˆancia de hamming entre os dois vetores. Mesmo sem saber o que significa a distˆancia de hamming entre dois vetores, podemos escrever a seguinte fun¸c˜ ao main: void main(void) { int vetor1[10], vetor2[10], hamming; leVetor(vetor1); leVetor(vetor2); hamming = calculaDistanciaHamming(vetor1, vetor2); cout << "Distancia de hamming = " << hamming << endl; }

Observe que a leitura da fun¸c˜ ao main j´a permite ter uma id´eia do que o programa faz. A forma como as etapas do programa s˜ ao realizadas depender˜ao de cada uma das fun¸c˜oes. Quanto melhor as fun¸c˜oes estiverem escritas, mais f´ acil ser´a a compreens˜ao. Observe tamb´em que a cria¸c˜ao da fun¸c˜ao leVetor permitiu que elimin´ assemos c´odigo redundante no programa. ´ indiscut´ıvel que dividir o programa em partes facilita a compreens˜ao do programa e a locaE liza¸c˜ao de erros. Entretanto, ´e importante que esta divis˜ao siga crit´erios bem definidos. Uma t´ecnica interessante ´e a chamada Programa¸c˜ ao Defensiva, inspirada livremente na Dire¸c˜ao Defensiva. Ambas seguem a mesma id´eia de que devemos nos prevenir dos erros dos outros, de modo a evitar problemas, sejam na programa¸c˜ao ou no trˆansito. Nossa defini¸c˜ao ser´a bem semelhante `a famosa m´ axima “vocˆe deve dirigir para vocˆe e para os outros”. No caso da programa¸c˜ao, ao escrever uma fun¸c˜ ao, devemos imaginar que qualquer dado externo passado para a fun¸c˜ao deve ser testado; se o seu valor for incompat´ıvel com o esperado pela fun¸c˜ao, ent˜ao alguma coisa deve ser feita. Em outras palavras, uma fun¸c˜ ao n˜ao deve executar comandos inv´alidos devido a erros que n˜ao sejam exclusivamente de sua responsabilidade, devendo estar assim prevenida para evit´a-los. Por exemplo, considere o que aconteceria na fun¸c˜ao abaixo, se o valor zero fosse passado como segundo parˆ ametro: int divide(int x, int y) { return (x/y); }

Uma boa regra de programa¸c˜ ao a ser seguida ´e: teste todos os valores que a fun¸ c˜ ao for utilizar, sejam parˆ ametros, entradas do usu´ ario, ou vari´ aveis globais. Outro ponto importante diz respeito ao grau de dependˆencia entre as fun¸c˜oes. Isto recebe o nome de Acoplamento. Quanto maior for o grau de dependˆencia entre duas fun¸c˜oes, maior ser´a o acoplamento, e mais dif´ıcil ser´ a compreender e modificar uma das fun¸c˜oes. Isto porque altera¸c˜oes simples em uma fun¸c˜ ao podem gerar altera¸c˜oes dr´asticas na outra. V´arios fatores fazem duas fun¸c˜ oes estar relacionadas. Entre eles, destacamos: • Retorno das fun¸c˜ oes: se uma fun¸c˜ao F1 chama uma fun¸c˜ao F2 e utiliza o resultado retornado por esta, ent˜ ao estaremos estabelecendo uma rela¸c˜ao de dependˆencia. Muitas vezes, esta rela¸c˜ ao pode ser confusa, como no exemplo a seguir: suponha que a fun¸c˜ ao posicaoDe seja utilizada para verificar se um elemento x est´a presente em um vetor v contendo n elementos; se x estiver presente no vetor, ent˜ao ser´a retornada a posi¸c˜ao da primeira ocorrˆencia de x, sen˜ ao, retornaremos o valor -1. Uma implementa¸c˜ao poss´ıvel desta fun¸c˜ ao ´e a seguinte:

Todos os direitos reservados aos autores

Notas de aulas de AED

3

int posicaDe(int v[], int n, int x) { bool encontrado = false; int i = 0; while (i < n && encontrado == false) { if (v[i] == x) encontrado = true; else i++; } if (encontrado == true) return i; else return -1; }

O maior problema desta fun¸c˜ ao ´e utilizar o seu valor de retorno para duas finalidades distintas: (a) informar se o elemento foi encontrado; (b) caso o elemento tenha sido encontrado, informar a posi¸c˜ ao de sua primeira ocorrˆencia. • Parˆ ametros: se uma fun¸c˜ ao F1 chama uma fun¸c˜ao F2, ent˜ao ´e importante que ao escrever a fun¸c˜ ao F1, estejamos cientes dos parˆametros que F2 espera. Considere por exemplo que a fun¸c˜ ao extenso, receba uma data e escreva na tela esta data por extenso; esta fun¸c˜ao pode ter v´ arios cabe¸calhos poss´ıveis: – void extenso(int dia, int mes, int ano); – void extenso(int ano, int mes, int dia); – void extenso(Data d); As duas primeiras formas s˜ ao totalmente v´alidas, e ir˜ao depender do programador: no Brasil, possivelmente utilizar´ıamos a primeira forma, mas em outros locais, a segunda forma poderia ser preferida. Observe ent˜ ao que a quantidade de parˆametros utilizados pode gerar confus˜oes na utiliza¸c˜ ao da fun¸c˜ ao. Na terceira forma, estamos supondo a existˆencia de uma estrutura Data que possua campos para dia, mˆes e ano. Observe que esta forma ´e mais atraente, visto que n˜ ao haver´ a d´ uvidas com rela¸c˜ao `a ordem em que os parˆametros devem ser passados. Os parˆ ametros devem ser muito bem escolhidos, pois estes poder˜ao gerar dificuldades ao tentar entender as rela¸c˜ oes entre as fun¸c˜oes. • Vari´ aveis Globais: Dada a chamada da fun¸c˜ao F2 de dentro da fun¸c˜ao F1, um importante fator de dependˆencia entre as fun¸c˜oes ´e o uso de globais. Por exemplo, considere o fragmento de c´ odigo abaixo: int x; // Vari´ avel global F2(...) { ... x = ...; // vari´ avel x alterada ... } F1(...) { ... F2(...) ... x ... // uso do valor de x }

Veja que o valor de x dentro de F1 depende da atribui¸c˜ao feita em F2. Esta dependˆencia ´e uma das mais dif´ıceis de serem encontradas e s˜ao as que causam maiores efeitos ao tentar corrigir ou fazer altera¸c˜ oes de manuten¸c˜ao em um programa. Claro que vari´aveis globais n˜ao devem ser simplesmente desconsideradas para sempre; entretanto, ´e importante que haja crit´erios bastante rigorosos para que o seu uso n˜ao crie dependˆencias mal´eficas no programa. Considere o programa abaixo:

Todos os direitos reservados aos autores

Notas de aulas de AED

4

void main(void) { int v[10], i; for (i = 0; i < 10; i++) cin >> v[i]; for (i = 9; i >= 0; i--) cout << v[i] << " "; }

Este ´e um programa bastante simples que faz a leitura de um vetor seguida da impress˜ao dos seus elementos em ordem invertida ` a de leitura. Para facilitar altera¸c˜oes futuras neste programa, ´e aconselh´ avel o uso de fun¸c˜ oes, o que poderia alterar o programa para: int v[10]; void leVetor() { for (int i = 0; i < 10; i++) cin >> v[i]; } void imprimeInvertido() { for (int i = 9; i >= 0; i--) cout << v[i] << " "; } void main(void) { leVetor(); imprimeInvertido(); }

Problema desta implementa¸c˜ ao: o uso da vari´avel global tornou as duas fun¸c˜oes totalmente limitadas, isto ´e, se precis´ assemos ler e imprimir invertido um outro vetor, digamos u, precisar´ıamos criar novas fun¸c˜ oes, duplicando um c´ odigo j´a existente. [Observe que neste caso o problema n˜ ao ´e v ter sido declarada como global, mas as fun¸c˜ oes estarem totalmente dependentes desta vari´ avel.] Este programa poderia ser ent˜ ao rescrito da seguinte forma: int v[10]; void leVetor(int vetor[]) { for (int i = 0; i < 10; i++) cin >> vetor[i]; } void imprimeInvertido(int vetor[]) { for (int i = 9; i >= 0; i--) cout << vetor[i] << " "; } void main(void) { leVetor(v); imprimeInvertido(v); }

Um problema j´ a foi resolvido: fun¸c˜oes dependendo de vari´aveis globais. Agora, se houver a necessidade de ler um outro vetor e imprimi-lo tamb´em invertido, precisaremos somente declar´a-lo e chamar as fun¸c˜ oes com parˆ ametros apropriados, como mostra o c´odigo abaixo: int u[10], v[10]; void leVetor(int vetor[]) { for (int i = 0; i < 10; i++) cin >> vetor[i]; } void imprimeInvertido(int vetor[]) { for (int i = 9; i >= 0; i--) cout << vetor[i] << " "; } void main(void) {

Todos os direitos reservados aos autores

Notas de aulas de AED

5

leVetor(v); leVetor(u); imprimeInvertido(v); imprimeInvertido(u); }

Ainda restam outros problemas: primeiramente, estamos trabalhando somente com vetores de 10 posi¸c˜oes. Se tivermos que modificar este programa para trabalhar com vetores de 20 posi¸c˜oes, por exemplo, ter´ıamos que alterar 4 pontos no c´odigo (as duas declara¸c˜oes e os limites dos comandos ´ interessante, ent˜ao, definirmos uma constante para o tamanho do vetor. for dentro das fun¸c˜ oes). E Observe que a modifica¸c˜ ao supracitada no programa a seguir requer a altera¸c˜ao de somente um ponto do programa (a declara¸c˜ ao da constante): const int tamanho = 10; int u[tamanho], v[tamanho]; void leVetor(int vetor[]) { for (int i = 0; i < tamanho; i++) cin >> vetor[i]; } void imprimeInvertido(int vetor[]) { for (int i = tamanho - 1; i >= 0; i--) cout << vetor[i] << " "; } void main(void) { leVetor(v); leVetor(u); imprimeInvertido(v); imprimeInvertido(u); }

Todos os direitos reservados aos autores

T´ opico 2

Classes Considere um outro fator de qualidade que nos levar´a a novos conceitos na programa¸c˜ao: se dois ou mais elementos de um programa possuirem alguma rela¸c˜ ao conceitual, ent˜ ao estes elementos dever˜ ao estar agrupados no c´ odigo. Uma forma de seguir esta regra ´e sempre colocar fun¸c˜oes de uma mesma esp´ecie seguidas ao longo do programa. Por exemplo, se um programa possuir dez fun¸c˜oes, sendo que trˆes fazem opera¸c˜ oes sobre datas, ent˜ao faz sentido deixar estas fun¸c˜oes em seq¨ uˆencia ao longo do programa. Esta ´e uma t´ecnica importante, que ser´a futuramente estendida para a cria¸c˜ao de bibliotecas de fun¸c˜ oes. Por enquanto, introduziremos o conceito de Classes. Considere o programa abaixo: void imprime(int dia, int mes, int ano) { cout << dia << "/" << mes << "/" << ano << endl; } bool bissexto(int ano) { if (ano % 4 != 0) return false; else if (ano % 100 == 0 && ano % 400 != 0) return false; else return true; } bool valida(int dia, int mes, int ano) { int maiordia; if (mes > 12 || mes < 1) return false; else if (mes == 4 || mes == 6 || mes == 9 || mes == 11) maiordia = 30; else if (mes == 2) if (bissexto(ano)) maiordia = 29; else maiordia = 28; else maiordia = 31; if (dia < 1 || dia > maiordia) return false; return true; } void main(void) { int dia, mes, ano; cout << "Digite a data: "; cin >> dia >> mes >> ano; if (valida(dia, mes, ano)) imprime(dia,mes,ano); else

6

Notas de aulas de AED

7

cout << "Data inv´ alida"; }

Um problema neste programa ´e o fato de termos v´arios parˆametros nas fun¸c˜oes que s˜ao necess´arios na representa¸c˜ ao das datas. Por exemplo, se o programador que escreveu as fun¸c˜oes fosse de alguma nacionalidade em que a ordem da descri¸c˜ao da data ´e diferente da nossa, ent˜ao ter´ıamos problemas com rela¸c˜ ao a ordem correta dos parˆametros. Ent˜ao, ´e interessante criarmos uma estrutura que represente uma data e us´a-la ao longo do programa. Desta forma, ficaremos livres de saber a ordem dos parˆ ametros a serem passados, como ilustra o programa abaixo: struct Data { int dia, mes, ano; }; bool bissexto(int ano) { if (ano % 4 != 0) return false; else if (ano % 100 == 0 && ano % 400 != 0) return false; else return true; } void imprime(Data d) { cout << d.dia << "/" << d.mes << "/" << d.ano << endl; } bool valida(Data d) { int maiordia; if (d.mes > 12 || d.mes < 1) return false; else if (d.mes == 4 || d.mes == 6 || d.mes == 9 || d.mes == 11) maiordia = 30; else if (d.mes == 2) if (bissexto(d.ano)) maiordia = 29; else maiordia = 28; else maiordia = 31; if (d.dia < 1 || d.dia > maiordia) return false; return true; } void main(void) { int dia, mes, ano; cout << "Digite a data: "; cin >> d.dia >> d.mes >> d.ano; if (valida(d)) imprime(d); else cout << "Data inv´ alida"; }

At´e agora, a u ´nica vantagem que obtivemos foi n˜ao precisarmos nos preocupar com a ordem dos parˆametros. Entretanto, o n´ıvel de organiza¸c˜ao do programa foi melhorado. Observe que os dados que representam uma data foram agrupados em uma estrutura do programa, seguindo a regra definida acima. Mostraremos agora uma evolu¸c˜ ao do conceito de estrutura que nos permitir´a englobar todas as opera¸c˜ oes relacionadas em uma mesma parte do programa: uma Classe. Uma Classe ´e um tipo de dados semelhante a uma estrutura, constitu´ıdas por Atributos e M´etodos. Atributos de classe s˜ ao semelhantes a campos de estruturas; por exemplo, uma classe Data poderia conter os atributos dia, mes e ano. M´etodos de classe s˜ao fun¸c˜oes que operam sobre os atributos.

Todos os direitos reservados aos autores

Notas de aulas de AED

8

Se declararmos uma vari´ avel cujo tipo ´e uma classe, esta vari´avel ser´a composta, assim como nas estruturas. Haver´ a uma c´ opia de cada um dos atributos para cada vari´avel declarada daquela classe. Por exemplo, se Data for uma classe definida no programa, ent˜ao a declara¸c˜ao: Data d1, d2, d3;

criar´a trˆes vari´ aveis cujo tipo ´e Data; cada uma destas vari´aveis possui os campos dia, mes e ano. Uma classe ´e geralmente dividida em duas partes: a parte privativa cont´em elementos que ser˜ao de uso exclusivo da classe, isto ´e, n˜ ao poder˜ao ser acessados por entidades externas `a classe; a parte p´ ublica cont´em os elementos exportados pela classe, isto ´e, elementos que podem ser utilizados por entidades externas ` a classe. Por simplicidade, convencionaremos que todos os atributos s˜ao privativos e todos os m´etodos s˜ ao p´ ublicos. Uma classe pode possuir tamb´em m´etodos especiais denominados construtores. Um construtor ´e um m´etodo especial que possui o mesmo nome da classe e n˜ao possui tipo de retorno, tendo por finalidade iniciar os atributos do objeto. No exemplo abaixo, vemos uma classe completa com atributos e um construtor e um exemplo de utiliza¸c˜ ao da classe: class Data { private: int dia, mes, ano; public: Data(int d, int m, int a) { dia = d; mes = m; ano = a; } bool bissexto() { if (ano % 4 != 0) return false; else if (ano % 100 == 0 && ano % 400 != 0) return false; else return true; } void imprime() { cout << dia << "/" << mes << "/" << ano << endl; } bool valida() { int maiordia; if (mes > 12 || mes < 1) return false; else if (mes == 4 || mes == 6 || mes == 9 || mes == 11) maiordia = 30; else if (d.mes == 2) if (bissexto(ano)) maiordia = 29; else maiordia = 28; else maiordia = 31; if (dia < 1 || dia > maiordia) return false; return true; } }; void main(void) { Data d(10,3,2003); if (d.valida()) d.imprime(); else cout << "Data inv´ alida"; }

Neste exemplo, iniciemos com a parte privativa que inicia por private:. Observe que fizemos uma declara¸c˜ ao semelhante aos campos da estrutura Data do exemplo anterior. A partir de public:, iniciamos a parte p´ ublica da classe, que cont´em os seus m´etodos. O primeiro m´etodo ´e o construtor, que ´e respons´avel por definir os valores iniciais dos atributos do objeto. Observe que os valores dos parˆametros s˜ao atribu´ıdos aos atributos da classe no construtor. Analisando a primeira linha da fun¸c˜ao main, vemos a declara¸c˜ao Data d(10,3,2003);. Todos os direitos reservados aos autores

Notas de aulas de AED

9

Exatamente neste ponto ´e feita a chamada do construtor. Ao declararmos o objeto d, definimos quais ser˜ ao os parˆ ametros passados para o construtor. Estes valores ser˜ao ent˜ao atribu´ıdos aos ´ importante atributos dia, mes e ano, de modo que o objeto d representar´a a data 10/3/2003. E ressaltar que a ordem de atribui¸c˜ ao foi definida pela ordem dos parˆametros, n˜ao havendo rela¸c˜ao alguma com a ordem em que os atributos foram definidos. ´ um m´etodo que verifica se o ano armaO segundo m´etodo utiliza somente o atributo ano. E zenado na data ´e um ano bissexto. O m´etodo imprime ´e semelhante ` a fun¸c˜ao imprime anterior, com a diferen¸ca que os valores de dia, mes e ano s˜ ao os atributos da classe e n˜ao mais os parˆametros. Observe como o m´etodo imprime ´e chamado na terceira linha da fun¸c˜ao main. A sintaxe ´e semelhante a uma chamada de fun¸c˜ao, sendo que a utiliza¸c˜ ao do operador “ponto”define que os valores dos atributos durante a execu¸c˜ao do m´etodo ser˜ ao obtidos do objeto para o qual o m´etodo foi chamado. Neste caso, a chamada d.imprime() chama o m´etodo imprime e os valores de dia, mes e ano s˜ao os valores destes atributos armazenados em d. ´ importante ressaltar que A fun¸c˜ ao main abaixo mostra a utiliza¸c˜ao de duas datas distintas. E cada objeto possui uma c´ opia de cada um dos atributos de modo que a chamada d1.imprime() imprimir´ a os atributos de d1 e a chamada d2.imprime() imprimir´a os atributos de d2. void main(void) { Data d1(10,3,2003), d2(3,7,2002); d1.imprime(); d2.imprime(); }

Outra funcionalidade que uma classe pode oferecer ´e o chamado construtor default, que ´e um construtor sem parˆ ametros. Em outras palavras, o construtor default de uma classe ´e um m´etodo sem parˆametros e sem tipo de retorno e cujo nome ´e o mesmo da classe. Este construtor especial serve para iniciar objetos com valores padr˜ao. No exemplo completo abaixo, o objeto d1 ´e iniciado com os valores passados como parˆ ametro para o primeiro construtor e o objeto d2 ´e iniciado com o valor padr˜ ao 1/1/2003. class Data { private: int dia, mes, ano; public: Data(int d, int m, int a) { dia = d; mes = m; ano = a; } Data() { // construtor default dia = 1; mes = 1; ano = 2003; } bool bissexto() { if (ano % 4 != 0) return false; else if (ano % 100 == 0 && ano % 400 != 0) return false; else return true; } void imprime() { cout << dia << "/" << mes << "/" << ano << endl; } bool valida() { int maiordia; if (mes > 12 || mes < 1) return false; else if (mes == 4 || mes == 6 || mes == 9 || mes == 11) maiordia = 30; else if (d.mes == 2) if (bissexto()) maiordia = 29; else maiordia = 28; else maiordia = 31; if (dia < 1 || dia > maiordia) return false; return true;

Todos os direitos reservados aos autores

Notas de aulas de AED

10

} }; void main(void) { Data d1(10,3,2003), d2; d1.imprime(); d2.imprime(); }

A diferencia¸c˜ ao na chamada do construtor ´e feita pelo compilador por meio da lista de parˆametros. Ao iniciar d1, utiliza-se o primeiro construtor, pois passamos 3 parˆametros para a sua inicia¸c˜ao; ao iniciar d2, utiliza-se o segundo construtor, pois nenhum parˆametro foi passado. Se tent´assemos utilizar 1, 2 ou mais de 3 parˆ ametros, haveria um erro de compila¸c˜ao; o mesmo ocorreria se algum dos parˆametros passados para d1 fosse incompat´ıvel com o tipo int, da mesma forma que ocorre com chamadas de fun¸c˜ oes. Observe que, at´e agora, n˜ ao houve ganho algum em poder de express˜ao da linguagem, isto ´e, o que fizemos utilizando classes poderia ter sido feito corretamente utilizando estruturas e fun¸c˜oes independentes. Entretanto, melhoramos a organiza¸c˜ao do nosso c´odigo, pois deixamos todas as fun¸c˜oes em um mesmo local do programa: a classe Data, al´em de representar uma data, tamb´em agrupa as opera¸c˜ oes sobre este tipo de dado. Al´em disso, a atribui¸c˜ao de valores iniciais a atributos ficou mais simples, pois podemos pass´a-los diretamente para o construtor, sem a necessidade de iniciarmos campo a campo.

Todos os direitos reservados aos autores

T´ opico 3

Tipos Abstratos de Dados 3.1

Defini¸ c˜ ao

Um Tipo Abstrato de Dados (TAD) ´e um conjunto de dados munido de opera¸c˜oes sobre estes dados. Por exemplo, o TAD Data representa todas as datas existentes, munidas das opera¸c˜oes usuais sobre datas. Quando um programa utiliza um TAD, ent˜ao dizemos que este programa ´e um Cliente do TAD. Por exemplo, podemos definir a fun¸c˜ao main abaixo, que utiliza o TAD Data; desta forma main ´e cliente do TAD Data. void main(void) { Data d1(10,3,2003), d2; d1.imprime(); d2.imprime(); }

3.2

Implementa¸ c˜ ao de um TAD

Na Programa¸c˜ ao Orientada por Objetos, dizemos que uma Classe implementa um Tipo Abstrato de Dados. Em outras palavras, uma classe cont´em os elementos que representam o tipo, e agrupa todas as opera¸c˜ oes realizadas sobre estes elementos. Ao definirmos um TAD, devemos nos preocupar sempre em definir a interface de comunica¸c˜ao do cliente com o TAD. Na implementa¸c˜ao via classe, isto significa determinar quais ser˜ao os m´etodos, os seus cabe¸calhos e o que cada m´etodo faz. Os algoritmos que ser˜ao utilizados s˜ao irrelevantes nesta fase. No nosso exemplo de data, os cabe¸calhos e uma descri¸c˜ao dos objetivos de cada m´etodo s˜ ao suficientes para escrevermos algoritmos que utilizem datas. Na implementa¸c˜ ao de um TAD, alguns fatores elevam a qualidade do c´odigo: • Ocultamento de informa¸c˜ oes: ´e importante que o cliente conhe¸ca o menor n´ umero poss´ıvel de informa¸c˜ oes a respeito do TAD. Por exemplo, na classe Data, os atributos dia, mes e ano n˜ao podem ser alterados em qualquer cliente, visto que s˜ao privativos da classe. Se quisermos permitir que o cliente altere algum dos campos, ser´a melhor criarmos m´etodos para fazerem esta altera¸c˜ ao, como mostrado no fragmento de c´odigo abaixo: class Data { private: int dia, mes, ano; public: Data(int d, int m, int a) { // Com valida¸ c~ ao ano = a; mes = (m >= 1 && m <= 12) ? m : 1; dia = d; if (! valida()) dia = 1; }

11

Notas de aulas de AED

12

Data() { ... } bool bissexto() { ... } void imprime() { ... } bool valida() { ... } void alteraMes(int m) { if (m >= 1 && m <= 12) mes = m; } }; void main(void) { Data d(10,3,2003); // A data ´ e v´ alida d.mes = 13; // Tentativa de atribuir valor inv´ alido // ´ e impedida pelo compilador d.alteraMes(13); // Tentativa de atribuir valor inv´ alido // ´ e impedida pelo m´ etodo alteraMes d.imprime(); }

Suponha agora que, em vez de utilizarmos os trˆes campos para dia, mˆes e ano, utilizemos um u ´nico campo armazenando o n´ umero de dias de diferen¸ca entre a data desejada e uma data base qualquer (por exemplo, poder´ıamos utilizar como base 1/1/1 ou 1/1/1970 ou ent˜ ao 1/1/2000. Neste caso, se a base for o dia 01/01/2000, ent˜ao a data 03/02/2003 seria representada por um u ´nico n´ umero: 1130. Esta representa¸c˜ao possui duas vantagens: economia de espa¸co, ao utilizarmos um u ´nico n´ umero no lugar de trˆes, e facilidade para realizar opera¸c˜ oes sobre datas, como por exemplo, determinar que dia foi 456 dias antes de 10/01/2003. Se esta mudan¸ca for necess´aria, o cliente acima continua funcionando sem problemas, ao passo que se a segunda linha da fun¸c˜ao main acima fosse permitida, dever´ıamos alterar tamb´em o cliente e n˜ ao somente a classe. Isto tornaria o trabalho de alterar a representa¸c˜ ao interna da data muito mais complexo. • Interface simples e bem definida: o TAD deve ser definido de forma que seja f´acil utilizar as suas funcionalidades. Uma das conseq¨ uˆencias da boa defini¸c˜ao da interface ´e a possibilidade de alterar os algoritmos sem que isto altere a interface dos m´etodos. Por exemplo, observe que podemos alterar o algoritmo da fun¸c˜ao valida sem necessitarmos alterar a sua assinatura: bool valida() { int dias_mes[12] = {31,28,31,30,31,30,31,31,30,31,30,31}; if (mes > 12 || mes < 1) return false; int maiordia = dias_mes[mes - 1]; if (mes == 2 && bissexto()) maiordia++; return (dia >= 1 && dia <= maiordia); }

De qualquer maneira, o importante ´e que o cliente pode fazer a valida¸c˜ao da data independente do algoritmo utilizado. Isto significa que se quisermos alterar o algoritmo utilizado para valida¸c˜ ao, o cliente n˜ ao precisar´a ser alterado. Outros fatores de qualidade ser˜ ao discutidos no momento oportuno. Resumindo, chegamos a duas caracter´ısticas importantes de um Tipo Abstrato de Dados: • independˆencia da representa¸c˜ ao interna: n˜ao importa se h´a trˆes n´ umeros ou somente um para representar a data, pois isto n˜ao ir´a afetar os clientes; na verdade, os clientes est˜ao independentes desta decis˜ ao. • independˆencia dos algoritmos: n˜ao importa como a data ser´a validada, mas sim qual ´e a interface do m´etodo, isto ´e, o que s˜ao os parˆametros esperados e o que significa o valor retornado. Todos os direitos reservados aos autores

Notas de aulas de AED

3.3

13

Estudo de caso: TAD Vetor

Para exemplificar todo o conte´ udo visto at´e agora, faremos uma implementa¸c˜ao do Tipo Abstrato de Dados Vetor, que armazena n´ umeros inteiros e possui as seguintes opera¸c˜oes: • Cria¸c˜ ao: inicializa o vetor como vazio; • obtemTamanho(): Retorna o n´ umero de elementos armazenados no vetor; • insereNoFinal(x): Insere x na primeira posi¸c˜ao vazia do vetor; • alteraEm(p,x): Atribui x ao elemento da posi¸c˜ao p do vetor, caso p seja uma posi¸c˜ao v´alida; • elementoEm(p): Retorna o valor armazenado na posi¸c˜ao p, caso esta seja uma posi¸c˜ao v´alida; retorna −1 caso contr´ ario; • posicaoDe(x): Retorna a posi¸c˜ ao da primeira ocorrˆencia de x no vetor ou o valor −1 caso x n˜ ao seja encontrado; • imprime(): Imprime os elementos do vetor, separados por um espa¸co.

3.3.1

Exemplo de Cliente

Abaixo, temos um exemplo de fun¸c˜ ao que deve funcionar com a implementa¸c˜ao do TAD Vetor: void main(void) { Vetor V; V.insereNoFinal(10); V.insereNoFinal(8); V.insereNoFinal(16); V.insereNoFinal(7); V.insereNoFinal(5); V.insereNoFinal(13); V.imprime(); cout << endl; V.alteraEm(3,19); V.alteraEm(15,9); for (int i = 0; i < V.obtemTamanho(); i++) cout << "Elemento na posicao " << i << ": " << V.elementoEm(i) << endl; cout << endl; V.imprime(); }

3.3.2

Uma primeira implementa¸ c˜ ao

Podemos implementar este TAD como uma classe com a seguinte assinatura: class Vetor { public: Vetor(); int obtemTamanho(); void insereNoFinal(int novo_valor); void alteraEm(int pos, int novo_valor); int elementoEm(int pos); int posicaoDe(int elemento); void imprime(); };

Faremos inicialmente uma implementa¸c˜ao que utiliza aloca¸c˜ao est´atica e que n˜ao permite que o vetor possua mais do que 100 elementos. Se n˜ao houver possibilidade de inser¸c˜ao do elemento, exibiremos uma mensagem de erro. O mesmo ser´a feito nas opera¸c˜oes alteraEm e elementoEm. Uma implementa¸c˜ ao desta classe pode ser a seguinte:

Todos os direitos reservados aos autores

Notas de aulas de AED

14

const int TAMANHO_MAXIMO = 100; class Vetor { private: int v[TAMANHO_MAXIMO], numElementos; public: Vetor(); int obtemTamanho(); void insereNoFinal(int novo_valor); void alteraEm(int pos, int novo_valor); int elementoEm(int pos); int posicaoDe(int elemento); void imprime(); };

Observe que os atributos necess´ arios s˜ao o vetor, que est´a definido estaticamente com 100 elementos, e o n´ umero de elementos. O construtor dever´ a simplesmente inicializar o atributo numElementos com zero, indicando que n˜ao h´ a elementos armazenados. Pode-se tamb´em zerar todas as posi¸c˜oes do vetor, mas isto n˜ao ´e totalmente necess´ ario, pois os demais m´etodos utilizar˜ao o n´ umero de elementos para evitar acesso a posi¸c˜ oes inexistentes do vetor. Vetor::Vetor() { numElementos = 0; // Inicializa¸ c~ ao opcional do vetor for (int i = 0; i < TAMANHO_MAXIMO; i++) v[i] = 0; }

O m´etodo obtemTamanho dever´ a retornar o n´ umero de elementos presentes no vetor. Pode-se simplesmente retornar o valor do atributo numElementos, como abaixo: int Vetor::obtemTamanho() { return numElementos; }

A inser¸c˜ ao no final do vetor dever´a verificar se o vetor est´a cheio. Se estiver, ent˜ao n˜ao poderemos fazer a inser¸c˜ ao e uma mensagem de erro ser´a exibida. Sen˜ao, faremos a inser¸c˜ao na posi¸c˜ao numElementos e este atributo ser´a incrementado em um: void Vetor::insereNoFinal(int novo_valor) { if (numElementos == TAMANHO_MAXIMO) cout << "ERRO: O vetor est´ a cheio!" << endl; else { v[numElementos] = int novo_valor; numElementos++; } }

O m´etodo alteraEm(p,x) verifica se p ´e uma posi¸c˜ao v´alida do vetor. Se for, atribui o valor de x `a posi¸c˜ ao p; sen˜ ao, exibe uma mensagem de erro: void Vetor::alteraEm(int pos, int novo_valor) { if (pos < 0 || pos >= numElementos) cout << "ERRO: A posi¸ c~ ao " << pos << " n~ ao ´ e v´ alida!" << endl; else v[pos] = novo_valor; }

O m´etodo elementoEm(p) funciona de modo semelhante: int Vetor::elementoEm(int pos) { if (pos >= 0 && pos < numElementos) return v[pos]; cout << "ERRO: A posi¸ c~ ao " << pos << " n~ ao ´ e v´ alida!" << endl; return -1; }

Todos os direitos reservados aos autores

Notas de aulas de AED

15

O m´etodo posicaoDe(x) procura a primeira ocorrˆencia de x no vetor. Se o elemento n˜ao for encontrado, retornar´ a −1: int Vetor::posicaoDe(int elemento) { int i = 0; bool encontrado = false; while (encontrado == false && i < numElementos) if (v[i] == elemento) encontrado = true; else i++; return (encontrado) ? i : -1; }

O m´etodo imprime() simplesmente faz a impress˜ao dos elementos do vetor: void Vetor::imprime() { for (int i = 0; i < numElementos; i++) cout << v[i] << " "; cout << endl; }

Todos os direitos reservados aos autores

T´ opico 4

Apontadores Durante a execu¸c˜ ao do programa, as vari´aveis s˜ao armazenadas na mem´oria em endere¸cos especificados pelo compilador. Se imaginarmos a mem´oria como um grande vetor, podemos considerar que as vari´ aveis ocupam posi¸c˜ oes espec´ıficas neste vetor, denominadas endere¸cos de mem´ oria. At´e agora, trabalhamos somente com vari´ aveis cujos endere¸cos foram determinados pelo compilador durante o processo de compila¸c˜ ao. Quando isto ocorre, dizemos que a vari´avel ´e est´atica, ou que ela foi alocada estaticamente. Posteriormente, veremos como criar vari´aveis dinamicamente, isto ´e, durante a execu¸c˜ ao do programa. Como um endere¸co de mem´ oria ´e um n´ umero inteiro, ´e poss´ıvel armazenarmos endere¸cos de mem´oria de vari´ aveis existentes em posi¸c˜oes da mem´oria. Isto ´e o que ocorre quando armazenamos o ´ındice de um vetor em uma vari´ avel em um comando de repeti¸c˜ao que percorre o vetor. Um Apontador ´e uma vari´ avel cujo valor ´e um endere¸co de mem´ oria. Em C++, para criarmos apontadores, devemos inicialmente determinar qual o tipo da vari´avel que ter´a seu endere¸co armazenado. Mesmo sabendo que os endere¸cos de uma vari´avel do tipo char e de uma vari´ avel do tipo double s˜ ao n´ umeros inteiros, o compilador C++ utiliza esta informa¸c˜ao para ajudar a evitar erros cometidos ao confundir os tipos. Para criarmos um apontador que conter´a o endere¸co de uma vari´avel do tipo T, ou em outras palavras, um apontador para alguma informa¸c˜ao do tipo T, utilizamos a sintaxe T * var. Por exemplo, o trecho de c´ odigo a seguir declara trˆes vari´aveis do tipo char (c1, c2 e c5), dois apontadores para o tipo char (c3 e c3), uma vari´avel do tipo int (i2), trˆes apontadores para o tipo int (i1, i3 e i4), uma vari´ avel do tipo float (f2) e um apontador para o tipo float (f1). Observe que o asterisco deve preceder a declara¸c˜ao de cada apontador. char c1, c2, *c3, *c4, c5; int *i1, i2, *i3, *i4; float *f1, f2;

Para manipularmos endere¸cos de mem´oria, podemos utilizar dois operadores: endere¸co de (&) e conte´ udo de (*). O fragmento de c´ odigo abaixo declara uma vari´avel inteira (x) e um apontador para inteiros (ptr) e atribui a ptr o endere¸co de mem´oria onde x est´a armazenada: int x, *ptr; ptr = &x; // Atribui a ptr o endere¸ co de x

´ poss´ıvel alterar o valor de x via um apontador que contenha o seu endere¸co. Isto ´e feito E utilizando o operador conte´ udo de (*), como no exemplo abaixo: int x = 0, *ptr; ptr = &x; // Atribui a ptr o endere¸ co de x *ptr = 1; // Atribui 1 ` a vari´ avel cujo endere¸ co est´ a // armazenado no apontador ptr, isto ´ e, x cout << x; // Imprime 1 e n~ ao 0

16

Notas de aulas de AED

17

Considere o programa abaixo. #include int x = 10; int * ptr = &x; void mostrar() { cout << "Valor de cout << "Valor de cout << "Conte´ udo cout << "Endere¸ co cout << "Endere¸ co } void main(void) { mostrar(); *ptr = 123; mostrar(); }

x: ptr: de ptr: de x: de ptr:

" " " " "

<< << << << <<

x ptr *ptr &x &ptr

<< << << << <<

endl; endl; endl; endl; endl;

A fun¸c˜ ao mostrar est´ a exibindo na seq¨ uˆencia: • o valor de x; • o valor de ptr, que ´e o endere¸co de x; • o conte´ udo de ptr, que ´e o valor de x; • o endere¸co de x; • o endere¸co de ptr. Considerando que, no programa acima, a vari´avel a seja alocada pelo compilador no endere¸co FF50 e p seja alocada pelo compilador no endere¸co FF54, ent˜ao a sa´ıda obtida na tela ser´a: Valor de Valor de Conte´ udo Endere¸ co Endere¸ co Valor de Valor de Conte´ udo Endere¸ co Endere¸ co

x: ptr: de ptr: de x: de ptr: x: ptr: de ptr: de x: de ptr:

10 FF50 10 FF50 FF54 123 FF50 123 FF50 FF54

Considere agora o programa abaixo: #include void main(void) { char ch1, ch2, *p, *q; ch1 = ’A’; p = &ch1; q = *p = *p + 1; // comando *q = *p + 1; // comando *p = ch2 + 1; // comando cout << "Valor de ch1: " cout << "Valor de ch2: " }

&ch2; 1 2 3 << ch1 << endl; << ch2 << endl;

Lembrando que *p significa vari´ avel cujo endere¸co est´a armazenado em p, temos que o comando 1 altera o valor de ch1 para ‘B’ (lembre-se que somar 1 a uma vari´avel char que contenha uma letra ´e equivalente a obter a letra seguinte). O comando 2 altera o valor de ch2 (apontado por q) para ‘C’, que ´e exatamente o valor de ch1 mais um. O comando 2 atribui a ch1 o valor ‘D’. Observe o que acontece no programa abaixo: Todos os direitos reservados aos autores

Notas de aulas de AED

18

#include void main(void) { float x = 0.8, *apont1, *apont2; apont1 = &x; // comando 1 apont2 = apont1; // comando 2 *apont1 = *apont2 / 2; // comando 3 *apont2 = x / 2; // comando 4 cout << "Valor de x: " << x << endl; }

O comando 1 atribui o endere¸co de x a apont1. O comando 2 atribui o valor de apont1 a apont2, isto ´e, o apontador apont2 conter´a, assim como apont1, o endere¸co da vari´avel x. Isto significa que tanto *apont1 quanto *apont2 significam x. Deste modo, o comando 3 atribui 0.4 a x e o comando 4 atribui 0.2 a x.

Todos os direitos reservados aos autores

T´ opico 5

Aloca¸c˜ ao Dinˆ amica Considere que vocˆe esteja escrevendo um programa que leia um valor n indicando o n´ umero de elementos de uma seq¨ uˆencia e, em seguida, leia n n´ umeros fornecidos pelo usu´ario, armazenando-os em um vetor. Como o valor de n ´e a princ´ıpio desconhecido, podemos supor um valor m´aximo (por exemplo, 100.000 elementos) e impedirmos, no programa, que o usu´ario forne¸ca um valor de n maior que este m´aximo especificado. Entretanto, dois problemas ocorrem: pode ser que o valor m´aximo ainda seja pequeno para alguma seq¨ uˆencia de elementos; por outro lado, se a quantidade de elementos for muito pequena, teremos desperdi¸cado muito espa¸co de mem´oria ao reservarmos ´area para um vetor muito grande. Quando declaramos um vetor como mostrado a seguir, o endere¸co da primeira posi¸c˜ao do vetor e o n´ umero de bytes que este vetor ocupa s˜ao definidos pelo compilador. Esta aloca¸c˜ao ´e chamada de Aloca¸c˜ ao Est´ atica: int vetor[100]; // Vetor alocado estaticamente

O mesmo ocorre com todas as vari´aveis declaradas no programa. O compilador define onde a vari´avel estar´ a armazenada e quantos bytes ser˜ao utilizados para conter o seu valor. Um problema como o especificado acima requer que tenhamos a possibilidade de definir o tamanho de um vetor durante a execu¸c˜ao, pois, somente ap´os o usu´ario fornecer o valor de n, saberemos o n´ umero de elementos que o vetor dever´a possuir. Isto pode ser feito utilizando Aloca¸c˜ ao Dinˆ amica. Alocar dinamicamente uma vari´ avel significa definir, em tempo de execu¸c˜ao, o endere¸co e o n´ umero de bytes que esta vari´ avel ocupar´a. Para alocarmos dinamicamente um vetor de elementos, declaramos um apontador e atribu´ımos a este apontador o endere¸co retornado pelo operador new da linguagem C++. H´a duas formas de alocarmos uma vari´avel dinamicamente: 1. Aloca¸c˜ ao de uma vari´ avel simples: int * p; // p ´ e um apontador para inteiros p = new int; // aloca nova ´ area para um inteiro

2. Aloca¸c˜ ao de um vetor de elementos: int int ... p =

* p; // p ´ e um apontador para inteiros n; obten¸ c~ ao do valor de n ... new int[n]; // aloca ´ area para um vetor de n inteiros

Inicialmente, iremos nos concentrar na segunda forma. A resolu¸c˜ao do problema acima pode ser feita utilizando este recurso lingu´ıstico da seguinte maneira:

19

Notas de aulas de AED

20

#include void main(void) { int * vetor, n, i; cout << "Qual ´ e o valor de n? "; cin >> n; vetor = new int[n]; for (i = 0; i < n; i++) { cout << "Elemento na posi¸ c~ ao " << i << ": "; cin >> vetor[i]; } ... uso do vetor ... }

Observe que o vetor alocado dinamicamente ´e manipulado da mesma forma que um vetor alocado estaticamente, isto ´e, utilizando [] para indexa¸c˜ao. A diferen¸ca ´e que agora declaramos o vetor como um apontador e utilizamos o operador new para fazermos a aloca¸c˜ao. Quando uma vari´ avel ´e alocada estaticamente, a ´area de mem´oria que ela ocupa ´e liberada automaticamente durante a execu¸c˜ ao e coincide com o final do escopo da vari´avel. Por exemplo, uma vari´ avel local de fun¸c˜ ao tem a sua ´area de mem´oria liberada automaticamente quando esta fun¸c˜ao retorna; uma vari´ avel global deixa de existir quando o programa termina. Uma vari´ avel alocada dinamicamente deixa de existir quando o programador utiliza o operador delete. Este operador tem por objetivo liberar a ´area de mem´oria reservada para uma vari´avel. O programa acima fica assim, com o uso do delete: #include void main(void) { int * vetor, n, i; cout << "Qual ´ e o valor de n? "; cin >> n; vetor = new int[n]; // Aloca¸ c~ ao de vetor for (i = 0; i < n; i++) { cout << "Elemento na posi¸ c~ ao " << i << ": "; cin >> vetor[i]; } ... uso do vetor ... delete [] vetor; // Libera ´ area de mem´ oria }

O uso dos colchetes entre o delete e a vari´avel apontador ´e necess´ario quando liberamos ´area de mem´oria reservada para um vetor. Se tiv´essemos feito a aloca¸c˜ao como uma vari´avel simples, n˜ao utilizar´ıamos os colchetes. ´ importante salientar que o delete opera sobre a ´area de mem´oria cujo endere¸co est´a no E apontador, e n˜ ao sobre o apontador. Por exemplo, considere o seguinte fragmento de c´odigo: int * v1, * v2, n; cout << "Qual ´ e o valor de n? "; cin >> n; v1 = new int[n]; // Aloca¸ c~ ao de v1 v2 = v1; // v1 e v2 apontam para o mesmo local for (i = 0; i < n; i++){ cout << "Elemento na posi¸ c~ ao " << i << ": "; cin >> v2[i]; } for (i = n - 1; i >= 0; i++) cout << v1[i] << " "; cout << endl; delete [] v2;

Neste exemplo, alocamos um vetor dinamicamente e armazenamos o seu endere¸co de in´ıcio na vari´avel apontador v1. Em seguida, atribu´ımos o valor de v1 a v2; isto faz com que tenhamos Todos os direitos reservados aos autores

Notas de aulas de AED

21

´ vital percerbermos que n˜ao h´a dois dois apontadores contendo o mesmo endere¸co de mem´ oria. E vetores, mas somente um vetor, cujo endere¸co est´a armazenado em duas vari´aveis apontadores. Desta forma, ap´ os esta atribui¸c˜ ao, tanto faz se utilizarmos o vetor via vari´avel v1 ou via vari´avel v2. Al´em disso, observe que ao fazer a libera¸c˜ao de mem´oria, podemos utilizar o delete com v1 ou com v2; todos os dois apontadores contˆem o endere¸co do mesmo vetor, e esta ´area de mem´oria ´ importante salientar que, se fiz´essemos a libera¸c˜ao como: ser´a liberada. E delete [] v1; delete [] v2;

ocorreria um erro de execu¸c˜ ao: a primeira linha liberaria a ´area do vetor e ao tentarmos fazer o segundo delete, tentar´ıamos liberar uma ´area de mem´oria que n˜ao est´a mais reservada para o programa (v1 e v2 s˜ ao o mesmo vetor). Considere por exemplo que precisemos fazer uma fun¸c˜ao que aloque dinamicamente um vetor com o n´ umero de elementos especificado como parˆametro da fun¸c˜ao. O endere¸co onde o vetor foi alocado (isto ´e, um apontador) ser´a retornado pela fun¸c˜ao. O vetor, ap´os ser alocado, ser´a preenchido com zeros. Esta fun¸c˜ ao pode ser escrita como: // n ´ e o tamanho do vetor a ser alocado // retornaremos o endere¸ co de mem´ oria do vetor, que // ´ e do tipo (int *). int * alocaVetor(int n) { int * v, i; if (n <= 0) // N~ ao ´ e poss´ ıvel alocar return NULL; // Endere¸ co zero: marca erro na aloca¸ c~ ao v = new int[n]; // Aloca um vetor de n inteiros for (i = 0; i < n; i++) // Zera o vetor v[i] = 0; return v; // Retorna o endere¸ co do novo vetor }

Fa¸camos um outro exemplo: considere que precisemos ler uma seq¨ uˆencia de n´ umeros de ponto flutuante e armazenar esta seq¨ uˆencia em um vetor. Os n´ umeros que ser˜ao inseridos ser˜ao sempre n´ umeros no intervalo fechado [1, 100], de modo que poderemos utilizar um valor qualquer como sentinela no final da entrada; em outras palavras, considere que o usu´ario digitar´a diversos n´ umeros e que, ao final, ele digitar´ a algum valor inv´alido para marcar o final da entrada. Por exemplo, se o usu´ario digitar 1.2, 3.7, 41.3, 82.3, 7.42, -1, ent˜ao saberemos que a seq¨ uˆencia desejada ´e 1.2, 3.7, 41.3, 82.3, 7.42. Faremos uma fun¸c˜ ao de cabe¸calho double * leSequencia(int & n);

que ler´ a o vetor e retornar´ a dois valores: o endere¸co onde o vetor foi alocado, por meio de return, e o n´ umero de elementos lidos, por meio do parˆametro de referˆencia n. Fa¸camos uma vers˜ ao inicial desta fun¸c˜ao, lendo no m´aximo 100 elementos: const int MAXIMO_ELEMENTOS = 100; double * leSequencia(int & n) { n = 0; double * v = new double[MAXIMO_ELEMENTOS]; cout << "Qual ´ e o primeiro elemento? "; cin >> x; while (n < MAXIMO_ELEMENTOS && x >= 1.0 && x <= 100.0) { v[n] = x; n++; // Salva o valor no vetor e incrementa n cout << "Qual ´ e o pr´ oximo elemento? "; cin >> x; }

Todos os direitos reservados aos autores

Notas de aulas de AED

22

return v; }

Observe que, se o usu´ ario tentar fornecer mais elementos que o limite especificado, ent˜ao o programa cessar´ a a leitura e retornar´ a os 100 primeiros elementos no vetor. Al´em disso, o n´ umero de elementos ´e armazenado diretamente no parˆametro de referˆencia n. Um exemplo de cliente desta fun¸c˜ ao ´e: void main(void) { double * meuVetor; int numElementos, i; meuVetor = leSequencia(numElementos); cout << "N´ umeros fornecidos: " << endl; for (i = 0; i < numElementos; i++) cout << meuVetor[i] << " "; cout << endl; delete [] meuVetor; }

Neste exemplo, ´e interessante salientar os seguintes aspectos: • A chamada de leSequencia atribui a meuVetor o endere¸co do vetor alocado dentro da fun¸c˜ao e a numElementos, o n´ umero de elementos lidos; • A libera¸c˜ ao de mem´ oria ´e feita utilizando o apontador que cont´em o endere¸co de mem´oria da ´ area alocada dinamicamente; isto significa que: – Tivemos que utilizar a vari´ avel meuVetor e n˜ao a vari´avel v, pois esta ´e local da fun¸c˜ao leSequencia; – Fazer a libera¸c˜ ao de mem´ oria dentro da fun¸c˜ao leSequencia ´e um erro, pois este vetor ainda ser´ a utilizado ao longo do programa. Devemos salientar que esta fun¸c˜ ao possui ainda um grave problema: se quisermos armazenar mais do que 100 elementos, devemos alterar o valor da constante, o que trar´a os problemas j´a discutidos anteriormente. Para evitarmos tais problemas, utilizaremos uma nova abordagem. Se o n´ umero de elementos ultrapassar o tamanho especificado, ent˜ao faremos a aloca¸c˜ao de um novo vetor maior que o original, copiaremos todos os elementos para este novo vetor e utilizaremos este novo vetor no lugar do original. Uma vez que o vetor original pode ser substitu´ıdo pelo novo vetor, liberaremos a ´area de mem´ oria que continha inicialmente os elementos. Esta abordagem, denominada realoca¸c˜ ao, est´a implementada na fun¸c˜ao leSequencia abaixo: const int TAMANHO_INICIAL = 100; double * leSequencia(int & n) { int tamanho = TAMANHO_INICIAL, novo_tamanho, i; double * vetor, * novo_vetor; vetor = new double[tamanho]; n = 0; cout << "Qual ´ e o primeiro elemento? "; cin >> x; while (x >= 1.0 && x <= 100.0) { if (n == tamanho) { novo_tamanho = 2 * tamanho; novo_vetor = new double[novo_tamanho]; for (i = 0; i < tamanho; i++) novo_vetor[i] = vetor[i]; delete [] vetor; tamanho = novo_tamanho; vetor = novo_vetor;

Todos os direitos reservados aos autores

Notas de aulas de AED

23

} vetor[n] = x; n++; // Salva o valor no vetor e incrementa n cout << "Qual ´ e o pr´ oximo elemento? "; cin >> x; } return vetor; }

Nesta nova fun¸c˜ ao, fazemos um teste dentro do while, verificando se o n´ umero de elementos j´a lidos ´e igual ao tamanho do vetor; se for igual, ent˜ao o vetor est´a cheio e n˜ao ´e poss´ıvel inserir novos elementos. Se isto ocorrer, ent˜ ao fazemos a realoca¸c˜ao, cujo c´odigo est´a dentro do if, realizando as seguintes opera¸c˜ oes: • Definimos o tamanho do novo vetor: neste exemplo, criamos um novo vetor com o dobro do tamanho do vetor utilizado, isto ´e, o vetor inicia com 100 elementos e passa a 200, 400, 800 elementos, conforme a necessidade; poder´ıamos aumentar de 1 em 1 elemento, ou ent˜ao de 10 em 10, ou outra quantidade qualquer, poder´ıamos aumentar em 20% ou outra quantidade proporcional, etc. • Alocamos o novo vetor com o tamanho especificado. • Copiamos todos os elementos do vetor antigo para o novo vetor. • Liberamos ´ area de mem´ oria do vetor antigo: este vetor n˜ao ´e mais necess´ario, pois todos os elementos j´ a est˜ ao em novo vetor, que ´e um vetor maior que o original. • Atribu´ımos o valor do novo tamanho ` a vari´ avel tamanho. • Atribu´ımos o endere¸co do novo vetor ao apontador que cont´em o vetor utilizado: esta atribui¸c˜ ao faz com que a vari´ avel vetor que est´a sendo utilizada ao longo da fun¸c˜ao contenha agora o endere¸co do vetor maior, de modo que as inser¸c˜oes seguintes ser˜ao poss´ıveis. Agora, podemos fornecer qualquer quantidade de elementos, pois a fun¸c˜ao n˜ao precisa mais limitar esta quantidade. A u ´nica limita¸c˜ao que temos agora ´e de m´aquina.

Todos os direitos reservados aos autores

T´ opico 6

An´ alise de complexidade 6.1

Introdu¸ c˜ ao

Normalmente, o mesmo problema pode ter diversas solu¸c˜oes computacionais utilizando diferentes t´ecnicas de programa¸c˜ ao, assim como, diferentes l´ogicas de programa¸c˜ao. Uma pergunta surge ent˜ao: como devemos fazer para escolher qual solu¸c˜ao usar? A resposta para esta quest˜ao parece ´ claro que iremos considerar a solu¸c˜ao que seja mais r´ ´obvia. E apida. Mas como determinar qual solu¸c˜ ao ´e mais r´ apida? Para isto, ser´a necess´ario implementar programas que resolvam este problema, seguido de uma verifica¸c˜ao de tempo para cada solu¸c˜ao. Essa metodologia para a determina¸c˜ ao do programa mais r´ apido ´e bastante custosa pois devemos ter um computador, um compilador, conhecer alguma linguagem de programa¸c˜ao, assim como, tempo sobrando para o seu desenvolvimento. Ainda, essa metodologia ´e altamente dependente das configura¸c˜oes do computador usado. Para diminuir o custo deste processo, tentaremos desenvolver uma metodologia que determinar´ a o custo computacional de um algoritmo, com rela¸c˜ao ao tempo mas tamb´em ao espa¸co utilizado.

6.2

Complexidade computacional e an´ alise assint´ otica

Dentre os objetivos de ATP2, estamos interessados em resolver problemas da melhor forma poss´ıvel, isto ´e, desenvolver algoritmo cujo custo computacional seja o menor poss´ıvel (dentro das limita¸c˜ oes e possibilidades oferecidas at´e o momento) para um dado problema. Em outras palavras, buscamos programas eficientes. Por exemplo, fa¸ca uma fun¸c˜ ao de cabe¸calho int posicaoDe(int x, int * v, int tam); que retorne a posi¸c˜ ao da ocorrˆencia do elemento x no vetor v contendo tam elementos distintos. Caso n˜ao exista este elemento, retorne -1. A primeira solu¸c˜ ao para essa fun¸c˜ ao seria: int posicaoDe(int x, int * v, int tam){ int pos = -1; for (int i = 0; i < tam; i++) if (v[i] == x) pos = i; return pos; } Nessa solu¸c˜ ao podemos observar que todos os elementos ser˜ao sempre pesquisados e verificados, logo podemos afirmar que ser˜ ao feitas tam compara¸c˜oes para determinar a posi¸c˜ao do elemento. Mas se o elemento estiver na primeira posi¸c˜ao, ser´a necess´ario comparar todos os elementos com o elemento a ser pesquisado? Veja a segunda solu¸c˜ao 24

Notas de aulas de AED

25

int posicaoDe(int x, int * v, int tam){ int pos = -1; for (int i = 0; i < tam; i++) if (v[i] == x) return i; return pos; } nessa solu¸c˜ ao, podemos ter 3 situa¸c˜ oes cr´ıticas: (i) o elemento est´a na primeira posi¸c˜ao do vetor; (ii) o elemento est´ a na u ´ltima posi¸c˜ ao do vetor; e (iii) o elemento n˜ao est´a no vetor. Para a situa¸c˜ao (i) teremos somente uma compara¸c˜ ao, j´ a para as outras situa¸c˜oes teremos tam compara¸c˜oes. Ainda ´e poss´ıvel melhorar a solu¸c˜ ao deste problema? A resposta ficar´a como exerc´ıcio, assim como, poss´ıveis solu¸c˜ oes, caso existam. Como podemos observar, existem diferentes formas para se resolver o problema de localiza¸c˜ao de um elemento em um vetor, entretanto nenhuma compara¸c˜ao entre as abordagens foi realizada. Para compararmos diferentes programas, relativo a sua eficiˆencia, definimos uma medida de grau de dificuldade de um algoritmo, denominada complexidade computacional. A complexidade computacional indica quanto esfor¸co ´e necess´ario para se aplicar um algoritmo, ou qu˜ao custoso este algoritmo ´e. Dois diferentes crit´erios de eficiˆencia podem ser considerados: tempo e espa¸co. Aqui, consideraremos somente o tempo. Quando consideramos tempo, a primeira id´eia que temos ´e: quantos minutos (ou segundos) s˜ao necess´ arios para a execu¸c˜ ao de um programa? Esta abordagem ´e muito custosa, visto que todos os programa devem ser implementados, na mesma linguagem, e executados em m´aquinas com as mesmas configura¸c˜ oes, e ainda nas mesmas condi¸c˜oes de teste. Contrariamente ao uso de tempo real, a avalia¸c˜ ao de eficiˆencia de um algoritmo, d´a-se pela utiliza¸c˜ao de unidades l´ogicas, que expressam a rela¸c˜ ao entre o tamanho n da entrada e a quantidade de tempo f (n) necess´aria para processar os dados. A defini¸c˜ ao de uma unidade l´ogica est´a associada a(s) opera¸c˜ao(˜oes) que se deseja considerar para comparar algoritmos, por exemplo, quantas compara¸c˜oes s˜ao realizadas para localizar um elemento dentro de um vetor? Neste caso, a unidade l´ogica a ser considerada ´e a compara¸c˜ ao. Normalmente, a fun¸c˜ ao para expressar a eficiˆencia de um algoritmo ´e complexa e cheia de termos. Quando consideramos grandes quantidades de dados, termos que n˜ao modifiquem a grandeza da express˜ ao devem ser eliminados de forma a simplificar a compara¸c˜ao entre diferentes fun¸c˜oes. Essa medida de eficiˆencia ´e denominada complexidade assint´ otica. Veja um exemplo, considere um algoritmo com a seguinte complexidade computacional f (n) = n3 + 100n + 10000

(6.1)

onde n ´e o tamanho da entrada do algoritmo (por exemplo, o n´ umero de elementos de um vetor). Nesta fun¸c˜ ao, observamos que para valores de n pequenos, o terceito termo ´e o mais importante, mas para valores de n muito grandes, o segundo e o terceiro termos s˜ao quase irris´orios no c´alculo da fun¸c˜ao. Com isto, podemos concluir que a complexidade assint´otica desse algoritmos est´a em fun¸c˜ao do termo n3 . Vale ressaltar que a avalia¸c˜ ao de eficiˆencia de um algoritmo faz sentido quando consideramos entradas de tamanho muito grande, pois para pequenas entrada, normalmente todos os algoritmos s˜ao r´apidos. Por isto, a necessidade do estudo da complexidade assint´otica, que ficar´a mais clara na pr´oxima se¸c˜ ao.

6.3

Nota¸ c˜ ao O

Uma abordagem para o estudo da eficiˆencia de um algoritmo ´e a an´alise do pior caso, tentando determinar a dependˆencia funcional do tempo de execu¸c˜ao com o tamanho da entrada. O primeiro

Todos os direitos reservados aos autores

Notas de aulas de AED

26

passo no processo ´e definir a no¸c˜ ao de “proporcional a”de forma precisa matematicamente, separando ainda, a an´ alise do algoritmo de uma implementa¸c˜ao em particular. A id´eia ´e ignorar fatores constantes na an´ alise, como vista na complexidade assint´otica. Por exemplo, na maioria dos casos, n´ os desejamos saber se o algoritmo ´e proporcional a n ou a n log n, independentemente se ser´a executado em um micro-computador ou em um super-computador. O artefato matem´atico para tornar esta defini¸c˜ ao precisa ´e chamada de nota¸ c˜ ao O (ou nota¸c˜ao grande O), que ´e usada para especificar a complexidade assint´ otica. Defini¸ c˜ ao 6.3.1 (Nota¸ c˜ ao O) f (n) ´e O(g(n)) se existem n´ umeros positivos c e n0 tais que f (n) ≤ c g(n) para todo n ≥ no Essa defini¸c˜ ao ´e lida da seguinte forma: f ´e O de g se existe um n´ umero positivo c tal que f n˜ao seja maior do c g para n suficientemente grande, isto ´e, para todo n maior que algum n´ umero n0 . Informalmente, essa defini¸c˜ao encapsula a no¸c˜ao de “´e proporcional a”e libera a an´alise dos detalhes de m´ aquinas particular. Al´em disso, a declara¸c˜ao que o tempo de execu¸c˜ao de um algoritmo ´e O(g(n)) ´e independente da entrada do algoritmo. Uma vez que n´os estamos interessados em estudar um algoritmo e n˜ao a entrada nem sua implementa¸c˜ao, a nota¸c˜ao O ´e a maneira u ´til de definir limites superiores sobre o tempo de execu¸c˜ao. A nota¸c˜ ao O tem sido extremamente u ´til e tem ajudado bastante os analistas a classificar os algoritmos pelo desempenho e a guiar os projetistas de algoritmos na pesquisa para o melhor algoritmo para problemas importantes. Entretanto, devemos ser extremamente cuidadosos na interpreta¸c˜ ao dos resultados expressos na nota¸c˜ao O, dentre as raz˜oes para este cuidado podemos citar: (i) por ser um limite superior, o tamanho da entrada poderia ser muito menor que a identificada pela defini¸c˜ ao; (ii) a entrada que provoca o pior caso, pode dificilmente ocorrer na pr´atica; (iii) a constante c ´e desconhecida e n˜ao precisa ser pequena; e (iv) a constante n0 ´e desconhecida e n˜ ao precisa ser pequena. A seguir iremos considerar cada um destes itens em detalhe. A afirma¸c˜ ao que o tempo de execu¸c˜ao de um algoritmo ´e O(g(n)) n˜ao implica que o algoritmo sempre ser´ a t˜ ao longo, esta afirma¸c˜ ao diz somente que a an´alise foi capaz de mostrar que ele nunca tomar´a um tempo maior que g(n). Mesmo se a entrada do pior caso ´e conhecida, pode ser o caso que as entrada na pr´atica conduzam a tempos de execu¸c˜ ao muito inferiores. Por exemplo, um algoritmo de ordena¸c˜ao (ser´a estudado posteriormente) chamada Quicksort possui o tempo de execu¸c˜ao no pior caso O(n2 ), mas ´e possible arranjar a entrada de forma que o tempo de execu¸c˜ao seja proporcional a n log n. As constantes c e n0 impl´ıcitas na nota¸c˜ao O frequentemente escondem detalhes de implementa¸c˜ao que s˜ ao importantes na pr´ atica. Obviamente, dizer que um algoritmo tem um tempo de execu¸c˜ ao O(g(n)) n˜ ao considera nada sobre o tempo de execu¸c˜ao se n for menor que n0 , e c poderia esconder um grande overhead projetado para evitar que o pior caso seja muito ruim. Obviamente, ´e prefer´ıvel um algoritmo que executa em n2 nano-segundos que um algoritmo que executa em log n s´eculos, mas infelizmente, n´os n˜ao poder´ıamos fazer esta escolha com base na nota¸c˜ao O. De forma geral, os algoritmos podem ser classificados de acordo com o seu custo computacional crescente segundo a nota¸c˜ ao O, como veremos a seguir:

Todos os direitos reservados aos autores

Notas de aulas de AED

27

O(1) A maioria das instru¸c˜oes da maioria dos programas s˜ao executados uma u ´nica vez, ou no m´aximo, poucas vezes. Se todas as instru¸c˜oes de um programa tivessem esta propriedade, n´os dir´ıamos que seu tempo de execu¸c˜ ao ´e constante. Essa ´e a situa¸c˜ao que todos os programadores e/ou projetistas de software devem se esfor¸car para conseguir. O(log n) Este tempo de execu¸c˜ao normalmente ocorre em algoritmos quando particionamos um problema grande em peda¸cos menores de interesse. Quando isto ocorre n´ os dizemos que o algoritmo possui tempo de execu¸c˜ao logar´ıtmico. O(n) Quando o tempo de execu¸c˜ao ´e linear, a soma de processamento normalmente ´e pequena para cada elemento da entrada. O(n log n) Este tempo de execu¸c˜ao ´e computado para algoritmos que resolvem um problema atrav´es da sua quebra em subproblemas menores, resolve cada um destes subproblemas independentemente, e ent˜ao combina as solu¸c˜oes. O(n2 ) Este tempo de execu¸c˜ao normalmente ´e computado quando todos os pares de itens de dados s˜ao processados. Quando isto ocorre dizemos que o tempo de execu¸c˜ao ´e quadr´atico. Normalmente, algoritmos quadr´aticos devem ser usados para problemas relativamente pequenos. O(n3 ) Similarmente ao anterior, um algoritmo que processa triplas de itens de dados possui um tempo de execu¸c˜ao c´ ubico. O(2n ) Poucos algoritmos com tempo de execu¸c˜ao exponenciais s˜ao apropriados para usos pr´ aticos. Estes algoritmos s˜ao chamados de for¸ca bruta pois, geralmente, processam n-uplas itens de dados.

6.4

Exemplos

Calcular a ordem de complexidade do seguinte algoritmo : void Ordena(int A[ ], int n) { int i, j, min, x; for (i = 1; i < n; i ++) { min = i; for (j = i + 1; j <= n; j ++) if (A[j − 1] < A[min − 1]) min = j; if (min != i) { x = A[i − 1]; A[i − 1] = A[min − 1]; A[min − 1] = x; } } } O c´alculo da ordem de complexidade deve ser efeito, ent˜ao, da seguinte forma : void Ordena(int A[ ], int n) { int i, j, min, x;

Todos os direitos reservados aos autores

Notas de aulas de AED

28

 for (i = 1; i < n; i ++) {· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · (n−1)×      min = i; · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · O(1)          for (j = i + 1; j <= n; j ++) · · · · · · · · · (n−i)×           if (A[j − 1] < A[min − 1]) · · · O(1) O(n)     O(1)      min = j; · · · · · · · · · · · · · · · O(1)    if (min != i) { · · · · · · · · · · · · · · · · · · · · · · · · · · ·  O(1)  O(n) O(n2 )        x = A[i − 1]; · · · O(1)          A[i − 1] = A[min − 1]; · · · O(1) O(1) O(1)             A[min − 1] = x; · · · O(1)           }    } } Calcule agora a fun¸c˜ ao de complexidade f (n), tal que f (n) represente o n´ umero de compara¸c˜oes entre os elementos do vetor A. De modo a calcular f (n) iremos utilizar de fi (n) = n´ umero de compara¸c˜ oes entre os elementos do vetor A para um dado i. Dessa forma : fi (n) = n − i Logo: f (n)

=

n−1 X

fi (n) = f1 (n) + f2 (n) + f3 (n) + · · · + fn−1 (n) =

i=1

=

n−1 X

(n − i) = (n − 1) + (n − 2) + (n − 3) + · · · + 1 =

i=1

= = =

(n − 1) + 1 · (n − 1) = 2 n · (n − 1) = 2 n n2 − · 2 2

A partir dessa fun¸c˜ ao de complexidade podemos, tamb´em, encontrar a ordem de complexidade, veja:

O(f (n))

= = = = =

Todos os direitos reservados aos autores

n2 n − )= 2 2 n2 n O( ) + O(− ) = 2 2 n n2 O(max( , − )) = 2 2 n2 O( ) = 2 1 O(n2 ) = 2 O(n2 )

= O(

T´ opico 7

Recursividade 7.1

Defini¸ c˜ ao

Informalmente, recurs˜ ao ´e um processo de resolver um problema grande atrav´es de sua redu¸c˜ao a um ou mais subproblemas que s˜ ao (i) idˆenticos em estrutura ao problema original e (ii) de alguma forma mais simples de resolver. Uma vez que subdivis˜ao original tenha sido feita, a mesma t´ecnica de decomposi¸c˜ ao ´e usada para dividir cada um destes subproblemas em novos subproblemas que s˜ ao igualmente mais simples. Eventualmente, os subproblemas tornam-se t˜ao simples que podem ser resolvidos sem uma nova subdivis˜ao. A solu¸c˜ao completa ´e ent˜ao obtida levando-se em considera¸c˜ ao os componentes resolvidos. Uma defini¸c˜ ao simples para uma fun¸c˜ao recursiva ´e que ela chama a ela mesma (como j´a vimos, uma fun¸c˜ ao definida em termos dela mesma). Ainda, uma fun¸c˜ao recursiva n˜ao pode chamar a ela mesma indefinidamente. Se isto ocorresse, o programa nunca acabaria. Por isto, ´e necess´ario haver uma condi¸c˜ ao de parada.

7.2

Ilustra¸ c˜ ao de uma abordagem recursiva

Imagine que vocˆe tenha recentemente aceitado a posi¸c˜ao de coordenador de fundos para uma campanha de combate a fome de sua regi˜ao. Nesta campanha, vocˆe dever´a arrecadar 1000 reais em doa¸c˜oes. Devido ` as regras impostas pelo comitˆe senior da campanha, cada doa¸c˜ao n˜ao pode passar de 1 real por pessoa. Como vocˆe deveria proceder? Obviamente, a primeira solu¸c˜ ao para este problema ´e encontrar 1000 pessoas da comunidade, e pedir a cada uma delas 1 real. Observe que vocˆe mesmo dever´a pedir esta quantia diretamente para estas pessoas. Computacionalmente falando, uma fun¸c˜ao de arrecada¸c˜ao seria: int arrecada1000(){ int soma = 0; for (int i = 0; i < 1000; i++){ cout << "Arrecadou 1 real da pessoa " << i; soma = soma + 1; } return soma; } Observe que esta fun¸c˜ ao ´e baseada em um loop expl´ıcito. Este tipo de constru¸c˜ao ´e chamada de solu¸c˜ao iterativa. Assumindo que vocˆe poderia encontrar as 1000 pessoas, esta solu¸c˜ao seria efetiva, mas ao mesmo tempo muito cansativa. Para evitar este cansa¸co e ainda para tentar agilizar o processo, a divis˜ ao dessa tarefa em sub-tarefas seria uma poss´ıvel solu¸c˜ao. Por exemplo, ao inv´es de pedir o dinheiro para 1000 pessoas, vocˆe pediria a ajuda a 10 pessoas, onde cada pessoa deveria arrecar 100 reais. Partindo desta perspectiva, o problema continua sendo o mesmo, por´em com 29

Notas de aulas de AED

30

valores de arrecada¸c˜ ao diferentes. Ainda, a tarefa de arrecar 100 reais ´e teoricamente mais simples que a tarefa de arrecar 1000 reais. A essˆencia da abordagem recursiva conduz a aplicar a mesma decomposi¸c˜ao em cada est´agio da solu¸c˜ao. Ent˜ ao, seguindo a mesma abordagem, cada novo volunt´ario que deve arrecadar 100 reais deve encontrar 10 outras pessoas que devam arrecar 10 reais cada. Cada um destes, deve ainda, encontrar 10 outras pessoas que concordem em doar 1 real cada. Observe que nesta u ´ltima etapa, a estr´ ategia foi alterada, pois agora foi pedido 1 real de cada doador, e n˜ao feita uma nova sub-divis˜ ao do problema. Recursivamente falando, o 1 real representa um caso simples, que pode ser resolvido diretamente sem uma nova decomposi¸c˜ao, este caso ´e chamado de condi¸c˜ao de parada. Solu¸c˜ oes deste tipo s˜ ao frequentemente referenciadas como estr´atigia dividir para conquistar, uma vez que eles dependam do particionamente do problema em componentes mais gerenci´aveis. Para representar este algoritmo em uma forma computacional mais sugestiva, ´e importante notar que existem diferentes instˆ ancias de um problema similar. No caso espec´ıfica mostrado anteriormente, n´ os temos tarefas independentes de arrecadar 1000 reais, 100 reais, 10 reais e finalmente, 1 real. Estas tarefas correspondem a diferentes n´ıveis da hierarquia de arrecada¸c˜ao. Para explorar esta similaridade, n´ os devemos generalizar o problema `a tarefa de arrecadar, n˜ao mais uma soma espec´ıfica, mas sim uma soma indeterminada de dinheiro, representada por uma vari´avel n. A tarefa de arrecar n reais pode ser dividida em dois casos. Primeiro, se n ´e 1 real, ent˜ao n´os simplesmente contribuimos com o nosso pr´oprio dinheiro. Alternativamente, n´os procueramos 10 volut´arios para n´ os ajudar a arrecar os n reais. Entretanto, cada volunt´ario dever´a arrecar somente um d´ecimo de n reais. Essa estrutura ´e representada a seguir. const int N_VOLUNTARIOS = 10; int arrecada(int n){ int soma = 0; if ( n == 1){ cout << "Contribua voce mesmo com 1 real \n"; return 1; }else{ for (int i = 0; i < N_VOLUNTARIOS; i++){ soma = soma + arrecada(n/N_VOLUNTARIOS); } return soma; } } Esta estrutura ´e tipicamente de um algoritmo recursivo. Observe que mesmo havendo um loop expl´ıtico este algoritmo ´e recursivo pois h´a uma chamada a pr´opria fun¸c˜ao. Vamos entender cada uma das etapas deste algoritmo. A primeira etapa, representada pelo comando if , consiste em testar se o problema corrente ´e t˜ ao simples que possa ser resolvido sem uma nova decomposi¸c˜ao. Se for verdade, j´ a arrecada 1 real diretamente, se n˜ao, o problema dever´a ser dividido em subproblemas, cada um dos quais ´e resolvido pela aplica¸c˜ao da mesma estrat´egia.

7.3

Caracter´ısticas de algoritmos recursivos

Na maioria da vezes, a decis˜ ao de usar recurs˜ao ´e sugerida pela natureza do problema. Para ser um candidato apropriado para a solu¸c˜ ao recursiva, um problema deve ter trˆes propriedades distintas: 1. Deve ser poss´ıvel decompor o problema original em instˆancias mais simples do mesmo problema. 2. Uma vez que cada um desses sub-problemas tenha sido resolvido, deve ser poss´ıvel combinar estas solu¸c˜ oes para produzir uma solu¸c˜ao para o problema original. Todos os direitos reservados aos autores

Notas de aulas de AED

31

3. Como problemas grandes s˜ ao quebrados, sucessivamente, em problemas menos complexos, estes sub-problemas devem, eventualmente, tornar-se t˜ao simples que eles possam ser resolvidos sem uma outra subdivis˜ ao. Normalmente, procedimentos recursivos tendem a fornecer um modelo conceitual bem natural quando tendem a implementar problemas matem´aticos. Isto ´e verdade pois muitas defini¸c˜oes matem´aticas, tais como a fatorial e a Fibonacci, s˜ao particularmente elegantes quando expressas na forma recursiva. As fun¸c˜ oes recursivas tamb´em podem ser implementadas de forma n˜ao recursiva, mas esta implementa¸c˜ ao ´e, as vezes, mais complicada pois depende de um profundo entendimento do problema a ser resolvido. Existem t´ecnicas, que n˜ao ser˜ao tratadas neste texto, para a convers˜ao de programa recursivo para um programa n˜ao recursivo. Os programas recursivos, embora possuam uma mesma complexidade computacional que suas respectivas solu¸c˜oes n˜ao recursivas, s˜ao mais lentos devido ` as diversas chamadas de fun¸c˜oes, que produz um overhead de processamento.

7.4

Exemplos

Nesta se¸c˜ ao, ser˜ ao ilustrados alguns problemas bem como suas solu¸c˜oes recursivas. O primeiro problema a ser considerado ser a fun¸c˜ ao fatorial, definida pela f´ormula: ( n × (n − 1)! para n ≥ 1 n! = 1 caso contr´ario

(7.1)

Esta defini¸c˜ ao de fatorial corresponde diretamente a seguinte fun¸c˜ao recursiva. int fatorial(int n){ if (n==0) return 1; else return n*fatorial(n-1); } Por um lado, este programa ilustra as caracter´ısticas b´asicas de uma programa recursivo: ele chama a sim mesmo e ele possui uma condi¸c˜ao de parada. Por outro lado, n˜ao existe mascara¸c˜ao do fato que este programa nada mais ´e que um loop for. Tamb´em, vale ressaltar que o fatorial n˜ao trabalha com n´ umeros negativos, logo ´e fundamental n˜ao deixar que exista uma chamada a esta fun¸c˜ ao quando o valor de n seja negativo. Um solu¸c˜ao n˜ao recursiva para este problema ser´a int fatorial_nrec(int n){ int fat = 1; for (int i = 1; i <= n; i++) fat = fat * i; return fat; } Uma segunda bem conhecida rela¸c˜ ao de recorrˆencia ´e aquela que define os n´ umeros de Fibonacci de ordem 2.   F ib(n − 1) + F ib(n − 2) F ib(n) = 1   1

para n ≥ 2 para n = 1 para n = 0

(7.2)

Da mesma forma que o fatorial, essa rela¸c˜ao de recorrˆencia corresponde de forma direta o programa recursivo a seguir

Todos os direitos reservados aos autores

Notas de aulas de AED

32

int fibonacci(int n){ if (n==0) return 1; else if (n==1) return 1; else return fibonacci(n-1)+fibonacci(n-2); } Estes algoritmos recursivos n˜ ao representam de forma convincente o poder da recurs˜ao, muito pelo contr´ ario, ele nos convence o qu˜ ao ineficiente pode ser. O problema na fun¸c˜ao de fibonacci ´e que as chamadas recursivas indicam que as chamadas fibonacci(n-1) e fibonacci(n-2) s˜ao computadas independentemente, quando na realidade poder´ıamos usar uma para computar a outra. Assim, podemos usar um procedimento n˜ao recursivo para computar os n´ umeros de fibonacci. Entretanto, este procedimento precisar´a armazenar os resultados intermedi´arios. Uma poss´ıvel solu¸c˜ao ´e ilustrada a seguir. const int MAX = 100; int fibonacci_nrec(int n){ int fat = 1; int vetor[MAX]; vetor[0] = 1; vetor[1] = 1; for (int i = 2; i <= n; i++) vetor[i] = vetor[i-1] + vetor[i-2]; return vetor[i-2]; }

7.5

Anatomia de chamadas recursivas

Como j´a estudado anteriormente, quando ocorre uma chamada de fun¸c˜ao, v´arias informa¸c˜oes (irrelevantes para ATP2) s˜ ao enviadas para a pilha de execu¸c˜ao. Dentre as informa¸c˜oes enviadas para a pilha, o endere¸co de retorno assim como os parˆametros da fun¸c˜ao s˜ao armazenados na pilha. Nesta se¸c˜ ao, veremos de maneira informal o que acontece quando se tem uma chamada recursiva. Considere o problema de elevar um n´ umero x ao expoente n. A seguir ´e ilustrada uma defini¸c˜ao recursiva deste problema em que o valor n ´e inteiro n˜ao negativo. ( x(n−1) × x para n > 0 x = 1 para n = 0 n

Usando esta defini¸c˜ ao o valor de x4 pode ser computado do seguinte modo. 0 x4 = x × x3 = x × (x × x2 )= x × (x × (x × x1 ))= x × (x × (x × (x × x ))) = x × (x × (x × (x × 1)))= x × (x × (x × (x)))= x × (x × (x × x))= x × (x × x × x)= x × x × x × x De forma direta, esta defini¸c˜ ao recursiva pode ser implementada pela fun¸c˜ao a seguir. double potencia(double x, int n){ if (n==0) return 1.0; else return x*potencia(x,n-1); } A aplica¸c˜ ao indutiva desta fun¸c˜ ao para a chamada potencia(x,4) ´e ilustrada a seguir. chamada 1 chamada 2 chamada 3

x4 = x × x3 x × x2 x × x1

Todos os direitos reservados aos autores

=x × x × x × x =x × x × x =x × x

(7.3)

Notas de aulas de AED

33

x × x0 1

chamada 4 chamada 5

=x × 1=x

ou alternativamente, chamada chamada chamada chamada chamada chamada chamada chamada chamada chamada

1 2 3 4 5 5 4 3 2 1

potencia(x,4) potencia(x,3) potencia(x,2) potencia(x,1) potencia(x,0) 1 x x×x x×x×x x×x×x×x

Observe que os resultados intermedi´arios, armazenados em algum lugar, s˜ao computados das chamadas mais internas para as mais externas.

Todos os direitos reservados aos autores

T´ opico 8

Estudo de Caso: TAD Pilha 8.1

Defini¸ c˜ ao

Uma Pilha representa um conjunto de elementos em que o u ´nico elemento vis´ıvel ´e o elemento que foi inserido h´ a menos tempo no conjunto. As opera¸c˜ oes sobre Pilhas s˜ ao as seguintes: • Constru¸c˜ ao: cria uma pilha vazia; • empilha: insere o elemento no topo da pilha; • desempilha: retira o elemento do topo da pilha; • topo: retorna o elemento do topo da pilha, sem desempilh´a-lo; • vazia: verifica se a pilha est´ a vazia. Au ´nica forma de inserir elementos em uma pilha ´e via opera¸c˜ao empilha e a u ´nica forma de retirar elementos ´e via opera¸c˜ ao desempilha. Para termos acesso ao pen´ ultimo elemento empilhado, devemos desempilhar o u ´ltimo; o mesmo ocorre com os demais elementos que tiverem sido inseridos anteriormente. Dizemos que uma Pilha ´e uma estrutura FIFO (First In, First Out = o primeiro que entra ´e o primeiro que sai).

8.2

Aplica¸ c˜ oes

Pilhas s˜ao utilizadas em programas de computadores em chamadas de fun¸c˜oes e procedimentos e chamadas recursivas. Utilizam-se pilhas tamb´em no processamento de estruturas aninhadas de profundidade imprevis´ıvel. Nesta situa¸c˜ ao ´e necess´ ario garantir que as estruturas mais internas sejam processadas antes da estrutura que as contenha. A pilha ´e uma estrutura adequada nesta situa¸c˜ao, pois a ordem de remo¸c˜ ao garante que as estruturas mais internas ser˜ao processadas antes das estruturas mais externas. Podemos utilizar pilhas tamb´em em editores de texto e na interpreta¸c˜ao de express˜oes aritm´eticas.

8.3

Interface da Classe Pilha

A implementa¸c˜ ao do TAD Pilha pode ser feita por meio da classe com a seguinte assinatura:

34

Notas de aulas de AED

35

typedef int Elemento; // Facilita alterar o tipo do elemento da pilha class Pilha { public: Pilha(); ~Pilha(); bool vazia(); void empilha(Elemento novoElemento); bool topo(Elemento & valorTopo); bool desempilha(); };

Os m´etodos topo e desempilha retornam verdadeiro ou falso, indicando se a opera¸c˜ao foi realizada com sucesso; se retornar falso, ent˜ao a pilha estava vazia, o que impediu que a opera¸c˜ao fosse feita; se a opera¸c˜ ao retornar verdadeiro, ent˜ao a opera¸c˜ao foi conclu´ıda com sucesso. O valor do topo da pilha ´e retornado pelo parˆametro de referˆencia valorTopo do m´etodo topo.

8.3.1

Implementa¸c˜ ao do TAD Pilha Utilizando Vetores

Para implementar o TAD Pilha, incluiremos na classe Pilha os atributos vetor, que armazena os valores da pilha, indTopo, que cont´em o ´ındice da primeira posi¸c˜ao vazia do vetor, e tamanho que cont´em o n´ umero de posi¸c˜ oes alocadas para o vetor. O vetor utilizar´a crescimento autom´atico, via m´etodo realoca, que tamb´em ´e privativo da classe. typedef int Elemento; const int TAMANHO_INICIAL = 10; class Pilha { private: Elemento * vetor; int indTopo, tamanho; void realoca(); public: Pilha(); ~Pilha(); bool vazia(); bool cheia(); void empilha(Elemento novoElemento); bool topo(Elemento & valorTopo); bool desempilha(); };

O construtor aloca o vetor dinamicamente com tamanho TAMANHO_INICIAL e inicializa o atributo indTopo com o valor zero: Pilha::Pilha() { tamanho = TAMANHO_INICIAL; vetor = new Elemento[tamanho]; indTopo = 0; }

O destrutor ir´ a liberar a ´ area de mem´oria reservada para o vetor: Pilha::~Pilha() { delete [] vetor; }

O m´etodo vazia retorna verdadeiro se o ´ındice do topo (indTopo) for igual a zero, ou falso, caso contr´ ario: bool Pilha::vazia() { return (indTopo == 0); }

O m´etodo empilha verifica se o ´ındice do topo ´e igual ao tamanho do vetor; se for igual, ent˜ao a pilha est´ a cheia e ser´ a necess´ ario realocar o vetor; isto ´e feito chamando-se o m´etodo realoca. Ap´os o teste, e poss´ıvel realoca¸c˜ ao, atribui-se o valor a ser empilhado `a primeira posi¸c˜ao do vetor e aumenta em um o valor de indTopo: Todos os direitos reservados aos autores

Notas de aulas de AED

36

void Pilha::empilha(Elemento novoElemento) { if (indTopo == tamanho) realoca(); vetor[indTopo++] = novoElemento; }

O m´etodo realoca ´e idˆentico ao m´etodo de mesmo nome definido na classe Vetor. O m´etodo topo verifica se a pilha est´a vazia; se estiver, retorna falso; se n˜ao estiver, atribui o valor do topo ao parˆ ametro por referˆencia valorTopo e retorna verdadeiro: bool Pilha::topo(Elemento & valorTopo) { if (vazia() == true) return false; valorTopo = vetor[indTopo - 1]; return true; }

O m´etodo desempilha verifica se a pilha est´a vazia; se estiver, retorna falso; se n˜ao estiver, diminui em um o valor de indTopo, indicando que h´a uma posi¸c˜ao livre a mais, e retorna verdadeiro: bool Pilha::desempilha() { if (vazia() == true) return false; indTopo--; return true; }

8.4

Exemplos

As fun¸c˜oes abaixo devem funcionar com qualquer implementa¸c˜ao de pilha, pois respeitam a assinatura da classe: void inicializa(Pilha & P) { for (int x = 1; x <= 10; x++) P.empilha(x); } void transfere(Pilha & P1, Pilha & P2) { Elemento valorTopo; while (P1.vazia() == false) { P1.topo(valorTopo); // obt´ em o valor do topo P1.desempilha(); P2.empilha(valorTopo); } } void main(void) { Pilha P1, P2; Elemento valorTopo; inicializa(P1); P1.desempilha(); P1.desempilha(); P1.desempilha(); P1.empilha(11); transfere(P1,P2); P1.empilha(12); P1.empilha(13); P1.empilha(14); cout << "Pilha P1: "; while (P1.topo(valorTopo) == true) { cout << valorTopo << " "; P1.desempilha(); } cout << "Pilha P2: "; while (P2.topo(valorTopo) == true) {

Todos os direitos reservados aos autores

Notas de aulas de AED

37

cout << valorTopo << " "; P2.desempilha(); } }

A fun¸c˜ ao inicializa empilha os valores de 1 a 10 na pilha. A fun¸c˜ao copia retira todos os elementos de P1 e empilha em P2. Como a pilha inverte os elementos no momento da retirada, a pilha P2 conter´ a os mesmos elementos que havia em P1, mas na ordem inversa. Observe que a fun¸c˜ao copia esvazia a pilha P1, pois n˜ao ´e poss´ıvel acessar um elemento sem retirar todos que tiverem sido inseridos depois. Este programa dever´ a imprimir o seguinte resultado na tela: Pilha P1: 14 13 12 Pilha P2: 11 7 6 5 4 3 2 1

Todos os direitos reservados aos autores

T´ opico 9

Estudo de Caso: TAD Fila 9.1

Defini¸ c˜ ao

Uma Fila representa um conjunto de elementos em que o u ´nico elemento vis´ıvel ´e o elemento que foi inserido h´ a mais tempo no conjunto. As opera¸c˜ oes sobre Filas s˜ ao as seguintes: • Constru¸c˜ ao: cria uma fila vazia; • insere: insere o elemento no final da fila; • retira: retira o elemento da frente da fila; • frente: retorna o elemento da frente da fila; • vazia: verifica se a fila est´ a vazia. A u ´nica forma de inserir elementos em uma fila ´e via opera¸c˜ao insere e a u ´nica forma de retirar elementos ´e via opera¸c˜ ao retira. Para termos acesso ao segundo elemento inserido, devemos retirar o primeiro; o mesmo ocorre com os demais elementos que tiverem sido inseridos posteriormente. Dizemos que uma Fila ´e uma estrutura LIFO (Last In, First Out = o u ´ltimo que entra ´e o primeiro que sai).

9.2

Aplica¸ c˜ oes

Filas em geral s˜ ao utilizadas para controlar o processamento de elementos na ordem em que eles aparecerem, como por exemplo, em filas de impress˜ao e em filas de processos do Sistema Operacional. Utilizamos filas tamb´em para implementa¸c˜ao de buscas em largura em Grafos e em Inteligˆencia Artificial.

9.3

Interface da Classe Fila

A implementa¸c˜ ao do TAD Fila ser´ a por meio da classe com a seguinte assinatura: typedef int Elemento; // Facilita alterar o tipo do elemento da pilha class Fila { public: Fila(); ~Fila(); bool vazia(); void insere(Elemento novoElemento); bool frente(Elemento & valorFrente); bool retira(); };

38

Notas de aulas de AED

39

Assim como na pilha, os m´etodos frente e retira retornam verdadeiro ou falso, indicando se a opera¸c˜ ao foi realizada com sucesso; se retornar falso, ent˜ao a fila estava vazia, o que impediu que a opera¸c˜ ao fosse feita; se a opera¸c˜ao retornar verdadeiro, ent˜ao a opera¸c˜ao foi conclu´ıda com sucesso. O valor da frente da fila ´e retornado pelo parˆametro de referˆencia valorFrente do m´etodo frente.

9.3.1

Implementa¸c˜ ao do TAD Fila Utilizando Vetores

Para implementarmos o TAD Fila, incluiremos na classe Fila os atributos vetor, que armazena os valores da fila, indFrente, que cont´em o ´ındice onde se encontra o elemento na frente da fila, numElementos, que armazena o n´ umero de elementos inseridos na fila, e tamanho que cont´em o n´ umero de posi¸c˜ oes alocadas para o vetor. O vetor utilizar´a crescimento autom´atico, via m´etodo realoca, que tamb´em ´e privativo da classe. // Facilita se for necess´ ario alterar o tipo do elemento da pilha typedef int Elemento; const int TAMANHO_INICIAL = 10; class Pilha { private: Elemento * vetor; int indFrente, numElementos, tamanho; void realoca(); public: Fila(); ~Fila(); bool vazia(); void insere(Elemento novoElemento); bool frente(Elemento & valorFrente); bool retira(); };

O construtor aloca o vetor dinamicamente com tamanho TAMANHO_INICIAL e inicializa os atributos indFrente e numElementos com o valor zero: Fila::Fila() { tamanho = TAMANHO_INICIAL; vetor = new Elemento[tamanho]; indFrente = 0; numElementos = 0; }

O destrutor ir´ a liberar a ´ area de mem´oria reservada para o vetor: Fila::~Fila() { delete [] vetor; }

O m´etodo vazia retorna verdadeiro se o n´ umero de elementos (armazenado em numElementos) for igual a zero, ou falso, caso contr´ ario: bool Fila::vazia() { return (numElementos == 0); }

O m´etodo frente verifica se a Fila est´a vazia; se estiver, retorna falso; se n˜ao estiver, atribui ao parˆametro por referˆencia valorFrente o valor da frente da fila e retorna verdadeiro: bool Fila::frente(Elemento & valorFrente) { if (vazia() == true) return false; valorFrente = vetor[indFrente]; return true; }

Todos os direitos reservados aos autores

Notas de aulas de AED

40

Os m´etodos insere e retira trabalham em conjunto implementando o que chamamos de Fila Circular. Considere que a fila esteja representada por um vetor de 10 posi¸c˜oes e que tenhamos inserido os n´ umeros de 1 a 10. Ap´ os estas opera¸c˜oes, considere que houve 3 retiradas. Para termos menos trabalho na movimenta¸c˜ ao dos elementos, podemos supor que o estado do objeto ser´a o seguinte ao longo da execu¸c˜ ao (X marca posi¸c˜ ao livre no vetor): Inicialmente: F = fila vazia vetor: X X X X indFrente: 0 numElementos: 0 tamanho: 10 Ap´ os as inser¸ c~ oes dos n´ umeros de 1 F = 1, 2, 3, 4, 5, 6, 7, 8, 9, vetor: 1 2 3 4 indFrente: 0 numElementos: 10 tamanho: 10 Ap´ os as tr^ es retiradas: F = 4, 5, 6, 7, 8, 9, 10 vetor: X X X 4 indFrente: 3 numElementos: 7 tamanho: 10

X

X

X

X

X

a 10: 10 5 6 7

8

9 10

5

8

9 10

6

7

X

Observe que n˜ ao ´e necess´ ario movimentar os n´ umeros de 4 a 10 para o in´ıcio do vetor, basta indicar que o ´ındice da frente ´e igual a 3, o que significa que h´a sete elementos iniciando no ´ındice 3 e terminando no ´ındice 9. Entretanto, suponha agora que precisemos inserir o valor 11 na fila. H´a diversas formas de inserirmos este valor na fila. A primeira ´e copiar todos os elementos algumas casas para tr´as e continuarmos inserindo no final da seq¨ uˆencia; isto acarretaria em um custo muito alto para uma simples inser¸c˜ao. Outra alternativa consiste em realocar o vetor e continuar fazendo a inser¸c˜ao no final, como j´a estava sendo feito. Tamb´em isto acarreta em executarmos opera¸c˜oes sup´erfluas, visto que h´a posi¸c˜oes livres (de 0 a 2). A alternativa de menor custo ´e aproveitar o in´ıcio do vetor (que est´a vazio) e imaginar que ele ´e uma continua¸c˜ ao do final. Em outras palavras, imaginaremos que o vetor inicia na posi¸c˜ao 3, onde est´a o primeiro elemento, cont´em elementos at´e a posi¸c˜ao 9, e continua nas posi¸c˜oes de 0 a 2. Isto ´e, estamos considerando que os elementos do vetor est˜ao em ordem, mas esta ordem n˜ao ´e necessariamente o primeiro elemento est´a na posi¸c˜ao zero e os demais nas posi¸c˜oes seguintes. Agora, imaginamos que a seq¨ uˆencia inicia em um ponto qualquer do vetor e pode ultrapassar o limite f´ısico do vetor; entretanto, quando a seq¨ uˆencia ultrapassar este limite, os elementos estar˜ao armazenados no in´ıcio do vetor. Utilizando esta abordagem, considere a inser¸c˜ao dos valores 11, 12 e 13 na fila. Estas opera¸c˜oes gerar˜ao a seguinte configura¸c˜ ao do objeto: Ap´ os a inser¸ c~ ao do 11: F = 4, 5, 6, 7, 8, 9, 10, 11 vetor: 11 X X 4 5 indFrente: 3 numElementos: 8 tamanho: 10 Ap´ os a inser¸ c~ ao do 12: F = 4, 5, 6, 7, 8, 9, 10, 11, 12 vetor: 11 12 X 4 5 indFrente: 3 numElementos: 9

Todos os direitos reservados aos autores

6

7

8

9 10

6

7

8

9 10

Notas de aulas de AED

41

tamanho: 10 Ap´ os a inser¸ c~ ao do 13: F = 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 vetor: 11 12 13 4 5 6 7 indFrente: 3 numElementos: 10 tamanho: 10

8

9 10

Agora temos um vetor cheio. A u ´nica diferen¸ca ´e a modifica¸c˜ao nos conceitos de in´ıcio e t´ermino da seq¨ uˆencia no vetor. Neste u ´ltimo exemplo, a seq¨ uˆencia inicia no ´ındice 3, vai at´e o ´ındice 9 (que ´e o final do vetor), e depois continua nas posi¸c˜oes 0, 1 e 2. Observe tamb´em que se quisermos inserir mais um elemento, a realoca¸c˜ao ser´a inevit´avel, pois n˜ao h´a mais posi¸c˜ oes livres no vetor. Desta forma, o m´etodo retira dever´a sempre aumentar o valor do atributo indFrente em um elemento. Para simular a circularidade, se o valor de indFrente ficar igual ao tamanho do vetor, que est´a no atributo tamanho, ent˜ ao passaremos este valor para 0. N˜ao podemos esquecer que, no in´ıcio do m´etodo, devemos testar se a fila est´a vazia, pois isto definir´a o valor de retorno. O m´etodo abaixo mostra a implementa¸c˜ ao da t´ecnica explicada: bool Fila::retira() { if (vazia() == true) return false; indFrente++; if (indFrente == tamanho) indFrente = 0; numElementos--; return true; }

O m´etodo insere utilizar´ a o mesmo conceito. Inicialmente, verificamos se o n´ umero de elementos da fila ´e igual ao seu tamanho. Se for igual, ser´a necess´ario realocar o vetor, chamando-se o m´etodo realoca. Ap´ os a verifica¸c˜ ao, e poss´ıvel realoca¸c˜ao, devemos verificar onde a seq¨ uˆencia de elementos termina, para inserirmos o elemento na posi¸c˜ao seguinte. Por simplicidade, iniciemos com uma fila com a seguinte configura¸c˜ao: Uma fila qualquer: F = 4, 5, 6, 7, 8 vetor: X indFrente: 3 numElementos: 5 tamanho: 10

X

X

4

5

6

7

8

X

X

Se quisermos inserir outro elemento nesta fila, deveremos fazer a inser¸c˜ao na pen´ ultima posi¸c˜ao do vetor, isto ´e, na posi¸c˜ ao 8. Como era de se esperar, esta posi¸c˜ao ´e exatamente igual a indFrente + numElementos. Considere agora que a fila possui a configura¸c˜ao abaixo: Outra fila qualquer: F = 4, 5, 6, 7, 8 vetor: 7 indFrente: 7 numElementos: 5 tamanho: 10

8

X

X

X

X

X

4

5

6

Observe que esta fila inicia na posi¸c˜ao 7, vai at´e o final do vetor, volta `a posi¸c˜ao zero e ocupa at´e a posi¸c˜ ao 1. Se aplicarmos a f´ ormula anterior, obteremos a posi¸c˜ao 12, que ´e a terceira posi¸c˜ao ap´os a u ´ltima posi¸c˜ ao do vetor, posi¸c˜ ao 9. Se subtrairmos ent˜ao o tamanho do vetor, obteremos a posi¸c˜ao 2, que ´e exatamente a primeira posi¸c˜ao livre. Unindo todos estes elementos, chegamos `a seguinte implementa¸c˜ao do m´etodo insere: Todos os direitos reservados aos autores

Notas de aulas de AED

42

void Fila::insere(Elemento novoElemento) { if (indFrente == tamanho) realoca(); int pos_insercao = indFrente + numElementos; if (pos_insercao >= tamanho) pos_insercao = pos_insercao - tamanho; v[pos_insercao] = novoElemento; numElementos++; }

Estes m´etodos poderiam ser escritos em menos linhas, utilizando a opera¸c˜ao de resto da divis˜ao: void Fila::insere(Elemento novoElemento) { if (indFrente == tamanho) realoca(); int pos_insercao = (indFrente + numElementos) % tamanho; v[pos_insercao] = novoElemento; numElementos++; } bool Fila::retira() { if (vazia() == true) return false; indFrente = (indFrente + 1) % tamanho; numElementos--; return true; }

9.4

Exemplos

As fun¸c˜oes abaixo devem funcionar com qualquer implementa¸c˜ao de fila, pois respeitam a assinatura da classe: void inicializa(Fila & F) { for (int x = 1; x <= 10; x++) F.insere(x); } void transfere(Fila & F1, Fila & F2) { Elemento valorFrente; while (F1.vazia() == false) { F1.frente(valorFrente); // obt´ em o valor da frente F1.retira(); F2.insere(valorFrente); } } void main(void) { Fila F1, F2; Elemento valorFrente; inicializa(F1); F1.retira(); F1.retira(); F1.retira(); F1.insere(11); transfere(F1,F2); F1.insere(12); F1.insere(13); F1.insere(14); cout << "Fila F1: "; while (F1.frente(valorFrente) == true) { cout << valorFrente << " "; F1.retira(); } cout << "Fila F2: "; while (F2.frente(valorFrente) == true) {

Todos os direitos reservados aos autores

Notas de aulas de AED

cout << valorFrente << " "; F2.retira(); } }

Este programa dever´ a imprimir o seguinte resultado na tela: Fila F1: 12 13 14 Fila F2: 4 5 6 7 8 9 10 11

Todos os direitos reservados aos autores

43