Apostila de AED em C++

Conteudo

1 Qualidade de Codigo 1

2 Classes 6

3 Tipos Abstratos de Dados 113.1 Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Implementacao de um TAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Estudo de caso: TAD Vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3.1 Exemplo de Cliente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.3.2 Uma primeira implementacao . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Apontadores 16

5 Alocacao Dinamica 19

6 Analise de complexidade 246.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246.2 Complexidade computacional e analise assintotica . . . . . . . . . . . . . . . . . . . 246.3 Notacao O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

7 Recursividade 297.1 Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297.2 Ilustracao de uma abordagem recursiva . . . . . . . . . . . . . . . . . . . . . . . . 297.3 Caracterısticas de algoritmos recursivos . . . . . . . . . . . . . . . . . . . . . . . . 307.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317.5 Anatomia de chamadas recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

8 Estudo de Caso: TAD Pilha 348.1 Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348.2 Aplicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348.3 Interface da Classe Pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

8.3.1 Implementacao do TAD Pilha Utilizando Vetores . . . . . . . . . . . . . . . 358.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

9 Estudo de Caso: TAD Fila 389.1 Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389.2 Aplicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389.3 Interface da Classe Fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

9.3.1 Implementacao do TAD Fila Utilizando Vetores . . . . . . . . . . . . . . . . 399.4 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

1

italogiovanistefani

Stamp

italogiovanistefani

Typewritten Text

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

Topico 1

Qualidade de Codigo

Para determinarmos se um programa e bom, diversos fatores devem ser analisados. Entre eles,alguns dos mais importantes sao:

• Do ponto de vista do usuario: se o programa esta correto, se e eficiente e se e de facilutilizacao;

• Do ponto de vista da equipe de programadores: se e facil fazer alteracoes, seja para correcaode erros ou para atualizacoes.

A correcao do programa depende particularmente do metodo de desenvolvimento utilizadoe dos testes que foram feitos. Em geral, este fator esta intimamente relacionado as tecnicasde programacao utilizadas. Os testes devem estar centrados principalmente em determinar ocomportamento do programa em casos extremos e em detectar pontos crıticos do codigo.

Um programa e eficiente quando faz bom uso dos recursos computacionais existentes. Quandoeconomizamos o tempo de CPU para realizar determinado processamento, dizemos que temoseficiencia de tempo; quando economizamos memoria disponıvel, dizemos que tempo eficiencia deespaco. Como veremos, nem sempre estes dois tipos de eficiencia sao compativeis, isto e, emgeral devemos escolher qual dos dois sera escolhido. Para sabermos se um programa e eficiente,desenvolveremos metricas para determinar o comportamento do algoritmo em casos crıticos eformas de comparar dois algoritmos que resolvam um mesmo problema.

Aqui, estamos interessados nos fatores de qualidade do ponto de vista do programador, vistoque estes garantirao que o programa seja alterado com mais facilidade quando for necessario.

Os elementos que chamam a atencao quando falamos em qualidade do codigo sao a indentacao,os comentarios, a documentacao, a escolha dos identificadores e modularizacao.

A indentacao permite visualizar as relacoes de dependencia entre as diversas construcoes doprograma.

Os comentarios ajudam a entender algoritmos complexos e a resolver duvidas que possamsurgir ao ler um fragmento de codigo.

A documentacao e normalmente confundida com comentarios. A documentacao e um relatorioque explica a logica do programa, detalhando as etapas do desenvolvimento e descrevendo osalgoritmos e as estruturas de dados utilizados, sendo a primeira leitura para quem tiver queentender o programa.

A escolha dos identificadores diz respeito a quais nomes dar a variaveis, funcoes, classes emodulos do programa. Nomes de variaveis como x ou a dizem muito pouco (ou quase nada) sobrea finalidade da variavel no programa. Mas, dependendo das caracterısticas do problema a serresolvido podem dizer muito. Por exemplo, no desenvolvimento de um programa para calcular oresultado de um polinomio, o uso de uma variavel idenficada por x esta correto, pois este nome estadiretamente relacionado ao problema em questao. Suponha agora, que estamos desenvolvimentoum programa para identificar se uma data esta correta, o uso de uma variavel identificada por x,neste caso, nao e recomendada, pois esta nao se relaciona com o problema.

1

Notas de aulas de AED 2

A modularizacao e a divisao do programa em funcoes, classes e modulos; ao dividir o programaem partes, facilitamos sua leitura, visto que e possıvel desenvolver metodos para a leitura doprograma, via construcoes de alto nıvel; por exemplo, ler a funcao main da a ideia do que oprograma faz; para conhecermos os detalhes, devemos entender as funcoes individualmente.

Ainda no item modularizacao, uma grande dificuldade e descobrir como dividir um programaem funcoes, isto e, o que devem ser as funcoes de um programa, como elas devem ser relacionadas,etc. Em geral, podemos procurar partes do programa que estao duplicadas e transforma-las emchamadas a uma nova funcao, devidamente parametrizada. Tambem e interessante que partesdistintas do programa fiquem em funcoes distintas. Tomemos por exemplo um programa que leiadois vetores de 10 numeros inteiros e exiba um numero que represente a distancia de hammingentre os dois vetores. Mesmo sem saber o que significa a distancia de hamming entre dois vetores,podemos escrever a seguinte funcao 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 funcao main ja permite ter uma ideia do que o programa faz. A formacomo as etapas do programa sao realizadas dependerao de cada uma das funcoes. Quanto melhoras funcoes estiverem escritas, mais facil sera a compreensao. Observe tambem que a criacao dafuncao leVetor permitiu que eliminassemos codigo redundante no programa.

E indiscutıvel que dividir o programa em partes facilita a compreensao do programa e a loca-lizacao de erros. Entretanto, e importante que esta divisao siga criterios bem definidos.

Uma tecnica interessante e a chamada Programacao Defensiva, inspirada livremente na DirecaoDefensiva. Ambas seguem a mesma ideia de que devemos nos prevenir dos erros dos outros, demodo a evitar problemas, sejam na programacao ou no transito. Nossa definicao sera bem seme-lhante a famosa maxima “voce deve dirigir para voce e para os outros”. No caso da programacao,ao escrever uma funcao, devemos imaginar que qualquer dado externo passado para a funcao deveser testado; se o seu valor for incompatıvel com o esperado pela funcao, entao alguma coisa deve serfeita. Em outras palavras, uma funcao nao deve executar comandos invalidos devido a erros quenao sejam exclusivamente de sua responsabilidade, devendo estar assim prevenida para evita-los.Por exemplo, considere o que aconteceria na funcao abaixo, se o valor zero fosse passado comosegundo parametro:

int divide(int x, int y) {

return (x/y);

}

Uma boa regra de programacao a ser seguida e: teste todos os valores que a funcao forutilizar, sejam parametros, entradas do usuario, ou variaveis globais.

Outro ponto importante diz respeito ao grau de dependencia entre as funcoes. Isto recebe onome de Acoplamento. Quanto maior for o grau de dependencia entre duas funcoes, maior sera oacoplamento, e mais difıcil sera compreender e modificar uma das funcoes. Isto porque alteracoessimples em uma funcao podem gerar alteracoes drasticas na outra.

Varios fatores fazem duas funcoes estar relacionadas. Entre eles, destacamos:

• Retorno das funcoes: se uma funcao F1 chama uma funcao F2 e utiliza o resultado retornadopor esta, entao estaremos estabelecendo uma relacao de dependencia.Muitas vezes, esta relacao pode ser confusa, como no exemplo a seguir: suponha que afuncao posicaoDe seja utilizada para verificar se um elemento x esta presente em um vetorv contendo n elementos; se x estiver presente no vetor, entao sera retornada a posicao daprimeira ocorrencia de x, senao, retornaremos o valor -1. Uma implementacao possıvel destafuncao e a seguinte:

Todos os direitos reservados aos autores


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 funcao e utilizar o seu valor de retorno para duas finalidades distin-tas: (a) informar se o elemento foi encontrado; (b) caso o elemento tenha sido encontrado,informar a posicao de sua primeira ocorrencia.

• Parametros: se uma funcao F1 chama uma funcao F2, entao e importante que ao escrevera funcao F1, estejamos cientes dos parametros que F2 espera. Considere por exemplo que afuncao extenso, receba uma data e escreva na tela esta data por extenso; esta funcao podeter varios cabecalhos 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 sao totalmente validas, e irao depender do programador: no Brasil,possivelmente utilizarıamos a primeira forma, mas em outros locais, a segunda forma poderiaser preferida. Observe entao que a quantidade de parametros utilizados pode gerar confusoesna utilizacao da funcao. Na terceira forma, estamos supondo a existencia de uma estruturaData que possua campos para dia, mes e ano. Observe que esta forma e mais atraente, vistoque nao havera duvidas com relacao a ordem em que os parametros devem ser passados.

Os parametros devem ser muito bem escolhidos, pois estes poderao gerar dificuldades aotentar entender as relacoes entre as funcoes.

• Variaveis Globais: Dada a chamada da funcao F2 de dentro da funcao F1, um importantefator de dependencia entre as funcoes e o uso de globais. Por exemplo, considere o fragmentode codigo abaixo:

int x; // Variavel global

F2(...) {

...

x = ...; // variavel x alterada

...

}

F1(...) {

...

F2(...)

... x ... // uso do valor de x

}

Veja que o valor de x dentro de F1 depende da atribuicao feita em F2. Esta dependencia e umadas mais difıceis de serem encontradas e sao as que causam maiores efeitos ao tentar corrigirou fazer alteracoes de manutencao em um programa. Claro que variaveis globais nao devemser simplesmente desconsideradas para sempre; entretanto, e importante que haja criteriosbastante rigorosos para que o seu uso nao crie dependencias maleficas no programa.

Considere o programa abaixo:



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 impressao dosseus elementos em ordem invertida a de leitura. Para facilitar alteracoes futuras neste programa,e aconselhavel o uso de funcoes, 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 implementacao: o uso da variavel global tornou as duas funcoes totalmentelimitadas, isto e, se precisassemos ler e imprimir invertido um outro vetor, digamos u, precisarıamoscriar novas funcoes, duplicando um codigo ja existente. [Observe que neste caso o problema nao ev ter sido declarada como global, mas as funcoes estarem totalmente dependentes desta variavel.]Este programa poderia ser entao 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 ja foi resolvido: funcoes dependendo de variaveis globais. Agora, se houver anecessidade de ler um outro vetor e imprimi-lo tambem invertido, precisaremos somente declara-loe chamar as funcoes com parametros apropriados, como mostra o codigo abaixo:

int u[10], v[10];


for (int i = 0; i < 10; i++)

cin >> vetor[i];

}


for (int i = 9; i >= 0; i--)


}

void main(void) {



leVetor(v);

leVetor(u);


imprimeInvertido(u);

}

Ainda restam outros problemas: primeiramente, estamos trabalhando somente com vetores de10 posicoes. Se tivermos que modificar este programa para trabalhar com vetores de 20 posicoes,por exemplo, terıamos que alterar 4 pontos no codigo (as duas declaracoes e os limites dos comandosfor dentro das funcoes). E interessante, entao, definirmos uma constante para o tamanho do vetor.Observe que a modificacao supracitada no programa a seguir requer a alteracao de somente umponto do programa (a declaracao da constante):

const int tamanho = 10;

int u[tamanho], v[tamanho];


for (int i = 0; i < tamanho; i++)

cin >> vetor[i];

}


for (int i = tamanho - 1; i >= 0; i--)


}

void main(void) {

leVetor(v);

leVetor(u);


imprimeInvertido(u);

}


Topico 2

Classes

Considere um outro fator de qualidade que nos levara a novos conceitos na programacao: se doisou mais elementos de um programa possuirem alguma relacao conceitual, entao estes elementosdeverao estar agrupados no codigo. Uma forma de seguir esta regra e sempre colocar funcoes deuma mesma especie seguidas ao longo do programa. Por exemplo, se um programa possuir dezfuncoes, sendo que tres fazem operacoes sobre datas, entao faz sentido deixar estas funcoes emsequencia ao longo do programa.

Esta e uma tecnica importante, que sera futuramente estendida para a criacao de bibliotecasde funcoes. 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


cout << "Data invalida";

}

Um problema neste programa e o fato de termos varios parametros nas funcoes que sao ne-cessarios na representacao das datas. Por exemplo, se o programador que escreveu as funcoesfosse de alguma nacionalidade em que a ordem da descricao da data e diferente da nossa, entaoterıamos problemas com relacao a ordem correta dos parametros. Entao, e interessante criarmosuma estrutura que represente uma data e usa-la ao longo do programa. Desta forma, ficaremoslivres de saber a ordem dos parametros 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


}

Ate agora, a unica vantagem que obtivemos foi nao precisarmos nos preocupar com a ordemdos parametros. Entretanto, o nıvel de organizacao do programa foi melhorado. Observe que osdados que representam uma data foram agrupados em uma estrutura do programa, seguindo aregra definida acima.

Mostraremos agora uma evolucao do conceito de estrutura que nos permitira englobar todasas operacoes relacionadas em uma mesma parte do programa: uma Classe.

Uma Classe e um tipo de dados semelhante a uma estrutura, constituıdas por Atributos eMetodos. Atributos de classe sao semelhantes a campos de estruturas; por exemplo, uma classeData poderia conter os atributos dia, mes e ano. Metodos de classe sao funcoes que operam sobreos atributos.



Se declararmos uma variavel cujo tipo e uma classe, esta variavel sera composta, assim comonas estruturas. Havera uma copia de cada um dos atributos para cada variavel declarada daquelaclasse. Por exemplo, se Data for uma classe definida no programa, entao a declaracao:

Data d1, d2, d3;

criara tres variaveis cujo tipo e Data; cada uma destas variaveis possui os campos dia, mes eano.

Uma classe e geralmente dividida em duas partes: a parte privativa contem elementos que seraode uso exclusivo da classe, isto e, nao poderao ser acessados por entidades externas a classe; a partepublica contem os elementos exportados pela classe, isto e, elementos que podem ser utilizadospor entidades externas a classe. Por simplicidade, convencionaremos que todos os atributos saoprivativos e todos os metodos sao publicos.

Uma classe pode possuir tambem metodos especiais denominados construtores. Um construtore um metodo especial que possui o mesmo nome da classe e nao possui tipo de retorno, tendo porfinalidade iniciar os atributos do objeto.

No exemplo abaixo, vemos uma classe completa com atributos e um construtor e um exemplode utilizacao 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() {


}

bool valida() {

int maiordia;

if (mes > 12 || mes < 1) return false;


maiordia = 30;


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


}

Neste exemplo, iniciemos com a parte privativa que inicia por private:. Observe que fizemosuma declaracao semelhante aos campos da estrutura Data do exemplo anterior. A partir depublic:, iniciamos a parte publica da classe, que contem os seus metodos.

O primeiro metodo e o construtor, que e responsavel por definir os valores iniciais dos atributosdo objeto. Observe que os valores dos parametros sao atribuıdos aos atributos da classe no cons-trutor. Analisando a primeira linha da funcao main, vemos a declaracao Data d(10,3,2003);.



Exatamente neste ponto e feita a chamada do construtor. Ao declararmos o objeto d, definimosquais serao os parametros passados para o construtor. Estes valores serao entao atribuıdos aosatributos dia, mes e ano, de modo que o objeto d representara a data 10/3/2003. E importanteressaltar que a ordem de atribuicao foi definida pela ordem dos parametros, nao havendo relacaoalguma com a ordem em que os atributos foram definidos.

O segundo metodo utiliza somente o atributo ano. E um metodo que verifica se o ano arma-zenado na data e um ano bissexto.

O metodo imprime e semelhante a funcao imprime anterior, com a diferenca que os valoresde dia, mes e ano sao os atributos da classe e nao mais os parametros. Observe como o metodoimprime e chamado na terceira linha da funcao main. A sintaxe e semelhante a uma chamadade funcao, sendo que a utilizacao do operador “ponto”define que os valores dos atributos durantea execucao do metodo serao obtidos do objeto para o qual o metodo foi chamado. Neste caso,a chamada d.imprime() chama o metodo imprime e os valores de dia, mes e ano sao os valoresdestes atributos armazenados em d.

A funcao main abaixo mostra a utilizacao de duas datas distintas. E importante ressaltar quecada objeto possui uma copia de cada um dos atributos de modo que a chamada d1.imprime()imprimira os atributos de d1 e a chamada d2.imprime() imprimira 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 umconstrutor sem parametros. Em outras palavras, o construtor default de uma classe e um metodosem parametros e sem tipo de retorno e cujo nome e o mesmo da classe. Este construtor especialserve para iniciar objetos com valores padrao. No exemplo completo abaixo, o objeto d1 e iniciadocom os valores passados como parametro para o primeiro construtor e o objeto d2 e iniciado como valor padrao 1/1/2003.

class Data {


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() {


}

bool valida() {

int maiordia;

if (mes > 12 || mes < 1) return false;


maiordia = 30;


if (bissexto()) maiordia = 29;

else maiordia = 28;

else maiordia = 31;

if (dia < 1 || dia > maiordia) return false;

return true;



}

};

void main(void) {

Data d1(10,3,2003), d2;

d1.imprime();

d2.imprime();

}

A diferenciacao na chamada do construtor e feita pelo compilador por meio da lista de parametros.Ao iniciar d1, utiliza-se o primeiro construtor, pois passamos 3 parametros para a sua iniciacao;ao iniciar d2, utiliza-se o segundo construtor, pois nenhum parametro foi passado. Se tentassemosutilizar 1, 2 ou mais de 3 parametros, haveria um erro de compilacao; o mesmo ocorreria se algumdos parametros passados para d1 fosse incompatıvel com o tipo int, da mesma forma que ocorrecom chamadas de funcoes.

Observe que, ate agora, nao houve ganho algum em poder de expressao da linguagem, isto e, oque fizemos utilizando classes poderia ter sido feito corretamente utilizando estruturas e funcoesindependentes. Entretanto, melhoramos a organizacao do nosso codigo, pois deixamos todas asfuncoes em um mesmo local do programa: a classe Data, alem de representar uma data, tambemagrupa as operacoes sobre este tipo de dado. Alem disso, a atribuicao de valores iniciais a atributosficou mais simples, pois podemos passa-los diretamente para o construtor, sem a necessidade deiniciarmos campo a campo.


Topico 3

Tipos Abstratos de Dados

3.1 Definicao

Um Tipo Abstrato de Dados (TAD) e um conjunto de dados munido de operacoes sobre estesdados. Por exemplo, o TAD Data representa todas as datas existentes, munidas das operacoesusuais sobre datas.

Quando um programa utiliza um TAD, entao dizemos que este programa e um Cliente doTAD. Por exemplo, podemos definir a funcao main abaixo, que utiliza o TAD Data; desta formamain e cliente do TAD Data.

void main(void) {

Data d1(10,3,2003), d2;

d1.imprime();

d2.imprime();

}

3.2 Implementacao de um TAD

Na Programacao Orientada por Objetos, dizemos que uma Classe implementa um Tipo Abstratode Dados. Em outras palavras, uma classe contem os elementos que representam o tipo, e agrupatodas as operacoes realizadas sobre estes elementos.

Ao definirmos um TAD, devemos nos preocupar sempre em definir a interface de comunicacaodo cliente com o TAD. Na implementacao via classe, isto significa determinar quais serao osmetodos, os seus cabecalhos e o que cada metodo faz. Os algoritmos que serao utilizados saoirrelevantes nesta fase. No nosso exemplo de data, os cabecalhos e uma descricao dos objetivos decada metodo sao suficientes para escrevermos algoritmos que utilizem datas.

Na implementacao de um TAD, alguns fatores elevam a qualidade do codigo:

• Ocultamento de informacoes: e importante que o cliente conheca o menor numero possıvelde informacoes a respeito do TAD. Por exemplo, na classe Data, os atributos dia, mes e anonao podem ser alterados em qualquer cliente, visto que sao privativos da classe. Se quisermospermitir que o cliente altere algum dos campos, sera melhor criarmos metodos para fazeremesta alteracao, como mostrado no fragmento de codigo abaixo:

class Data {


public: Data(int d, int m, int a) { // Com validac~ao

ano = a;

mes = (m >= 1 && m <= 12) ? m : 1;

dia = d;

if (! valida()) dia = 1;

}

11


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 valida

d.mes = 13; // Tentativa de atribuir valor invalido

// e impedida pelo compilador

d.alteraMes(13); // Tentativa de atribuir valor invalido

// e impedida pelo metodo alteraMes

d.imprime();

}

Suponha agora que, em vez de utilizarmos os tres campos para dia, mes e ano, utilizemosum unico campo armazenando o numero de dias de diferenca entre a data desejada e umadata base qualquer (por exemplo, poderıamos utilizar como base 1/1/1 ou 1/1/1970 ouentao 1/1/2000. Neste caso, se a base for o dia 01/01/2000, entao a data 03/02/2003seria representada por um unico numero: 1130. Esta representacao possui duas vantagens:economia de espaco, ao utilizarmos um unico numero no lugar de tres, e facilidade pararealizar operacoes sobre datas, como por exemplo, determinar que dia foi 456 dias antesde 10/01/2003. Se esta mudanca for necessaria, o cliente acima continua funcionando semproblemas, ao passo que se a segunda linha da funcao main acima fosse permitida, deverıamosalterar tambem o cliente e nao somente a classe. Isto tornaria o trabalho de alterar arepresentacao interna da data muito mais complexo.

• Interface simples e bem definida: o TAD deve ser definido de forma que seja facil utilizar assuas funcionalidades. Uma das consequencias da boa definicao da interface e a possibilidadede alterar os algoritmos sem que isto altere a interface dos metodos. Por exemplo, observe quepodemos alterar o algoritmo da funcao 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 validacao da data indepen-dente do algoritmo utilizado. Isto significa que se quisermos alterar o algoritmo utilizadopara validacao, o cliente nao precisara ser alterado.

Outros fatores de qualidade serao discutidos no momento oportuno. Resumindo, chegamos a duascaracterısticas importantes de um Tipo Abstrato de Dados:

• independencia da representacao interna: nao importa se ha tres numeros ou somente umpara representar a data, pois isto nao ira afetar os clientes; na verdade, os clientes estaoindependentes desta decisao.

• independencia dos algoritmos: nao importa como a data sera validada, mas sim qual e ainterface do metodo, isto e, o que sao os parametros esperados e o que significa o valorretornado.



3.3 Estudo de caso: TAD Vetor

Para exemplificar todo o conteudo visto ate agora, faremos uma implementacao do Tipo Abstratode Dados Vetor, que armazena numeros inteiros e possui as seguintes operacoes:

• Criacao: inicializa o vetor como vazio;

• obtemTamanho(): Retorna o numero de elementos armazenados no vetor;

• insereNoFinal(x): Insere x na primeira posicao vazia do vetor;

• alteraEm(p,x): Atribui x ao elemento da posicao p do vetor, caso p seja uma posicao valida;

• elementoEm(p): Retorna o valor armazenado na posicao p, caso esta seja uma posicaovalida; retorna −1 caso contrario;

• posicaoDe(x): Retorna a posicao da primeira ocorrencia de x no vetor ou o valor −1 casox nao seja encontrado;

• imprime(): Imprime os elementos do vetor, separados por um espaco.

3.3.1 Exemplo de Cliente

Abaixo, temos um exemplo de funcao que deve funcionar com a implementacao 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 implementacao

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 implementacao que utiliza alocacao estatica e que nao permite queo vetor possua mais do que 100 elementos. Se nao houver possibilidade de insercao do elemento,exibiremos uma mensagem de erro. O mesmo sera feito nas operacoes alteraEm e elementoEm.

Uma implementacao desta classe pode ser a seguinte:



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 necessarios sao o vetor, que esta definido estaticamente com 100elementos, e o numero de elementos.

O construtor devera simplesmente inicializar o atributo numElementos com zero, indicandoque nao ha elementos armazenados. Pode-se tambem zerar todas as posicoes do vetor, mas istonao e totalmente necessario, pois os demais metodos utilizarao o numero de elementos para evitaracesso a posicoes inexistentes do vetor.

Vetor::Vetor() {

numElementos = 0;

// Inicializac~ao opcional do vetor

for (int i = 0; i < TAMANHO_MAXIMO; i++)

v[i] = 0;

}

O metodo obtemTamanho devera retornar o numero de elementos presentes no vetor. Pode-sesimplesmente retornar o valor do atributo numElementos, como abaixo:

int Vetor::obtemTamanho() {

return numElementos;

}

A insercao no final do vetor devera verificar se o vetor esta cheio. Se estiver, entao naopoderemos fazer a insercao e uma mensagem de erro sera exibida. Senao, faremos a insercao naposicao numElementos e este atributo sera incrementado em um:

void Vetor::insereNoFinal(int novo_valor) {

if (numElementos == TAMANHO_MAXIMO)

cout << "ERRO: O vetor esta cheio!" << endl;

else {

v[numElementos] = int novo_valor;

numElementos++;

}

}

O metodo alteraEm(p,x) verifica se p e uma posicao valida do vetor. Se for, atribui o valorde x a posicao p; senao, exibe uma mensagem de erro:

void Vetor::alteraEm(int pos, int novo_valor) {

if (pos < 0 || pos >= numElementos)

cout << "ERRO: A posic~ao " << pos << " n~ao e valida!" << endl;

else

v[pos] = novo_valor;

}

O metodo elementoEm(p) funciona de modo semelhante:

int Vetor::elementoEm(int pos) {

if (pos >= 0 && pos < numElementos)

return v[pos];

cout << "ERRO: A posic~ao " << pos << " n~ao e valida!" << endl;

return -1;

}



O metodo posicaoDe(x) procura a primeira ocorrencia de x no vetor. Se o elemento nao forencontrado, retornara −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 metodo imprime() simplesmente faz a impressao dos elementos do vetor:

void Vetor::imprime() {

for (int i = 0; i < numElementos; i++)

cout << v[i] << " ";

cout << endl;

}


Topico 4

Apontadores

Durante a execucao do programa, as variaveis sao armazenadas na memoria em enderecos especi-ficados pelo compilador. Se imaginarmos a memoria como um grande vetor, podemos considerarque as variaveis ocupam posicoes especıficas neste vetor, denominadas enderecos de memoria. Ateagora, trabalhamos somente com variaveis cujos enderecos foram determinados pelo compiladordurante o processo de compilacao. Quando isto ocorre, dizemos que a variavel e estatica, ou queela foi alocada estaticamente. Posteriormente, veremos como criar variaveis dinamicamente, istoe, durante a execucao do programa.

Como um endereco de memoria e um numero inteiro, e possıvel armazenarmos enderecos dememoria de variaveis existentes em posicoes da memoria. Isto e o que ocorre quando armazenamoso ındice de um vetor em uma variavel em um comando de repeticao que percorre o vetor.

Um Apontador e uma variavel cujo valor e um endereco de memoria.Em C++, para criarmos apontadores, devemos inicialmente determinar qual o tipo da variavel

que tera seu endereco armazenado. Mesmo sabendo que os enderecos de uma variavel do tipo chare de uma variavel do tipo double sao numeros inteiros, o compilador C++ utiliza esta informacaopara ajudar a evitar erros cometidos ao confundir os tipos.

Para criarmos um apontador que contera o endereco de uma variavel do tipo T, ou em outraspalavras, um apontador para alguma informacao do tipo T, utilizamos a sintaxe T * var. Porexemplo, o trecho de codigo a seguir declara tres variaveis do tipo char (c1, c2 e c5), doisapontadores para o tipo char (c3 e c3), uma variavel do tipo int (i2), tres apontadores para otipo int (i1, i3 e i4), uma variavel do tipo float (f2) e um apontador para o tipo float (f1).Observe que o asterisco deve preceder a declaracao de cada apontador.

char c1, c2, *c3, *c4, c5;

int *i1, i2, *i3, *i4;

float *f1, f2;

Para manipularmos enderecos de memoria, podemos utilizar dois operadores: endereco de (&)e conteudo de (*).

O fragmento de codigo abaixo declara uma variavel inteira (x) e um apontador para inteiros(ptr) e atribui a ptr o endereco de memoria onde x esta armazenada:

int x, *ptr;

ptr = &x; // Atribui a ptr o endereco de x

E possıvel alterar o valor de x via um apontador que contenha o seu endereco. Isto e feitoutilizando o operador conteudo de (*), como no exemplo abaixo:

int x = 0, *ptr;

ptr = &x; // Atribui a ptr o endereco de x

*ptr = 1; // Atribui 1 a variavel cujo endereco esta

// armazenado no apontador ptr, isto e, x

cout << x; // Imprime 1 e n~ao 0

16


Considere o programa abaixo.

#include <iostream.h>

int x = 10;

int * ptr = &x;

void mostrar() {

cout << "Valor de x: " << x << endl;

cout << "Valor de ptr: " << ptr << endl;

cout << "Conteudo de ptr: " << *ptr << endl;

cout << "Endereco de x: " << &x << endl;

cout << "Endereco de ptr: " << &ptr << endl;

}

void main(void) {

mostrar();

*ptr = 123;

mostrar();

}

A funcao mostrar esta exibindo na sequencia:

• o valor de x;

• o valor de ptr, que e o endereco de x;

• o conteudo de ptr, que e o valor de x;

• o endereco de x;

• o endereco de ptr.

Considerando que, no programa acima, a variavel a seja alocada pelo compilador no enderecoFF50 e p seja alocada pelo compilador no endereco FF54, entao a saıda obtida na tela sera:

Valor de x: 10

Valor de ptr: FF50

Conteudo de ptr: 10

Endereco de x: FF50

Endereco de ptr: FF54

Valor de x: 123

Valor de ptr: FF50

Conteudo de ptr: 123

Endereco de x: FF50

Endereco de ptr: FF54

Considere agora o programa abaixo:


void main(void) {

char ch1, ch2, *p, *q;

ch1 = ’A’; p = &ch1; q = &ch2;

*p = *p + 1; // comando 1

*q = *p + 1; // comando 2

*p = ch2 + 1; // comando 3

cout << "Valor de ch1: " << ch1 << endl;

cout << "Valor de ch2: " << ch2 << endl;

}

Lembrando que *p significa variavel cujo endereco esta armazenado em p, temos que o comando1 altera o valor de ch1 para ‘B’ (lembre-se que somar 1 a uma variavel char que contenha umaletra 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:




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 endereco de x a apont1. O comando 2 atribui o valor de apont1 aapont2, isto e, o apontador apont2 contera, assim como apont1, o endereco da variavel x. Istosignifica que tanto *apont1 quanto *apont2 significam x. Deste modo, o comando 3 atribui 0.4a x e o comando 4 atribui 0.2 a x.


Topico 5

Alocacao Dinamica

Considere que voce esteja escrevendo um programa que leia um valor n indicando o numero deelementos de uma sequencia e, em seguida, leia n numeros fornecidos pelo usuario, armazenando-osem um vetor.

Como o valor de n e a princıpio desconhecido, podemos supor um valor maximo (por exemplo,100.000 elementos) e impedirmos, no programa, que o usuario forneca um valor de n maior que estemaximo especificado. Entretanto, dois problemas ocorrem: pode ser que o valor maximo aindaseja pequeno para alguma sequencia de elementos; por outro lado, se a quantidade de elementosfor muito pequena, teremos desperdicado muito espaco de memoria ao reservarmos area para umvetor muito grande.

Quando declaramos um vetor como mostrado a seguir, o endereco da primeira posicao do vetore o numero de bytes que este vetor ocupa sao definidos pelo compilador. Esta alocacao e chamadade Alocacao Estatica:

int vetor[100]; // Vetor alocado estaticamente

O mesmo ocorre com todas as variaveis declaradas no programa. O compilador define onde avariavel estara armazenada e quantos bytes serao utilizados para conter o seu valor.

Um problema como o especificado acima requer que tenhamos a possibilidade de definir otamanho de um vetor durante a execucao, pois, somente apos o usuario fornecer o valor de n,saberemos o numero de elementos que o vetor devera possuir. Isto pode ser feito utilizandoAlocacao Dinamica.

Alocar dinamicamente uma variavel significa definir, em tempo de execucao, o endereco e onumero de bytes que esta variavel ocupara.

Para alocarmos dinamicamente um vetor de elementos, declaramos um apontador e atribuımosa este apontador o endereco retornado pelo operador new da linguagem C++.

Ha duas formas de alocarmos uma variavel dinamicamente:

1. Alocacao de uma variavel simples:

int * p; // p e um apontador para inteiros

p = new int; // aloca nova area para um inteiro

2. Alocacao de um vetor de elementos:

int * p; // p e um apontador para inteiros

int n;

... obtenc~ao do valor de n ...

p = new int[n]; // aloca area para um vetor de n inteiros

Inicialmente, iremos nos concentrar na segunda forma. A resolucao do problema acima podeser feita utilizando este recurso linguıstico da seguinte maneira:

19



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 posic~ao " << i << ": ";

cin >> vetor[i];

}

... uso do vetor ...

}

Observe que o vetor alocado dinamicamente e manipulado da mesma forma que um vetoralocado estaticamente, isto e, utilizando [] para indexacao. A diferenca e que agora declaramoso vetor como um apontador e utilizamos o operador new para fazermos a alocacao.

Quando uma variavel e alocada estaticamente, a area de memoria que ela ocupa e liberadaautomaticamente durante a execucao e coincide com o final do escopo da variavel. Por exemplo,uma variavel local de funcao tem a sua area de memoria liberada automaticamente quando estafuncao retorna; uma variavel global deixa de existir quando o programa termina.

Uma variavel alocada dinamicamente deixa de existir quando o programador utiliza o operadordelete. Este operador tem por objetivo liberar a area de memoria reservada para uma variavel.

O programa acima fica assim, com o uso do delete:


void main(void) {

int * vetor, n, i;


cin >> n;

vetor = new int[n]; // Alocac~ao de vetor

for (i = 0; i < n; i++) {


cin >> vetor[i];

}

... uso do vetor ...

delete [] vetor; // Libera area de memoria

}

O uso dos colchetes entre o delete e a variavel apontador e necessario quando liberamos areade memoria reservada para um vetor. Se tivessemos feito a alocacao como uma variavel simples,nao utilizarıamos os colchetes.

E importante salientar que o delete opera sobre a area de memoria cujo endereco esta noapontador, e nao sobre o apontador. Por exemplo, considere o seguinte fragmento de codigo:

int * v1, * v2, n;


cin >> n;

v1 = new int[n]; // Alocac~ao de v1

v2 = v1; // v1 e v2 apontam para o mesmo local

for (i = 0; i < n; 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 endereco de inıcio navariavel apontador v1. Em seguida, atribuımos o valor de v1 a v2; isto faz com que tenhamos



dois apontadores contendo o mesmo endereco de memoria. E vital percerbermos que nao ha doisvetores, mas somente um vetor, cujo endereco esta armazenado em duas variaveis apontadores.Desta forma, apos esta atribuicao, tanto faz se utilizarmos o vetor via variavel v1 ou via variavelv2.

Alem disso, observe que ao fazer a liberacao de memoria, podemos utilizar o delete com v1ou com v2; todos os dois apontadores contem o endereco do mesmo vetor, e esta area de memoriasera liberada. E importante salientar que, se fizessemos a liberacao como:

delete [] v1;

delete [] v2;

ocorreria um erro de execucao: a primeira linha liberaria a area do vetor e ao tentarmos fazer osegundo delete, tentarıamos liberar uma area de memoria que nao esta mais reservada para oprograma (v1 e v2 sao o mesmo vetor).

Considere por exemplo que precisemos fazer uma funcao que aloque dinamicamente um vetorcom o numero de elementos especificado como parametro da funcao. O endereco onde o vetorfoi alocado (isto e, um apontador) sera retornado pela funcao. O vetor, apos ser alocado, serapreenchido com zeros.

Esta funcao pode ser escrita como:

// n e o tamanho do vetor a ser alocado

// retornaremos o endereco de memoria 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; // Endereco zero: marca erro na alocac~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 endereco do novo vetor

}

Facamos um outro exemplo: considere que precisemos ler uma sequencia de numeros de pontoflutuante e armazenar esta sequencia em um vetor. Os numeros que serao inseridos serao semprenumeros no intervalo fechado [1, 100], de modo que poderemos utilizar um valor qualquer comosentinela no final da entrada; em outras palavras, considere que o usuario digitara diversos numerose que, ao final, ele digitara algum valor invalido para marcar o final da entrada. Por exemplo, seo usuario digitar 1.2, 3.7, 41.3, 82.3, 7.42, -1, entao saberemos que a sequencia desejada e 1.2, 3.7,41.3, 82.3, 7.42.

Faremos uma funcao de cabecalho

double * leSequencia(int & n);

que lera o vetor e retornara dois valores: o endereco onde o vetor foi alocado, por meio dereturn, e o numero de elementos lidos, por meio do parametro de referencia n.

Facamos uma versao inicial desta funcao, lendo no maximo 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 proximo elemento? ";

cin >> x;

}



return v;

}

Observe que, se o usuario tentar fornecer mais elementos que o limite especificado, entao oprograma cessara a leitura e retornara os 100 primeiros elementos no vetor. Alem disso, o numerode elementos e armazenado diretamente no parametro de referencia n. Um exemplo de clientedesta funcao e:

void main(void) {

double * meuVetor;

int numElementos, i;

meuVetor = leSequencia(numElementos);

cout << "Numeros 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 endereco do vetor alocado dentro da funcaoe a numElementos, o numero de elementos lidos;

• A liberacao de memoria e feita utilizando o apontador que contem o endereco de memoriada area alocada dinamicamente; isto significa que:

– Tivemos que utilizar a variavel meuVetor e nao a variavel v, pois esta e local da funcaoleSequencia;

– Fazer a liberacao de memoria dentro da funcao leSequencia e um erro, pois este vetorainda sera utilizado ao longo do programa.

Devemos salientar que esta funcao possui ainda um grave problema: se quisermos armazenarmais do que 100 elementos, devemos alterar o valor da constante, o que trara os problemas jadiscutidos anteriormente.

Para evitarmos tais problemas, utilizaremos uma nova abordagem. Se o numero de elementosultrapassar o tamanho especificado, entao faremos a alocacao de um novo vetor maior que ooriginal, copiaremos todos os elementos para este novo vetor e utilizaremos este novo vetor nolugar do original. Uma vez que o vetor original pode ser substituıdo pelo novo vetor, liberaremosa area de memoria que continha inicialmente os elementos.

Esta abordagem, denominada realocacao, esta implementada na funcao 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;



}

vetor[n] = x; n++; // Salva o valor no vetor e incrementa n

cout << "Qual e o proximo elemento? ";

cin >> x;

}

return vetor;

}

Nesta nova funcao, fazemos um teste dentro do while, verificando se o numero de elementos jalidos e igual ao tamanho do vetor; se for igual, entao o vetor esta cheio e nao e possıvel inserir novoselementos. Se isto ocorrer, entao fazemos a realocacao, cujo codigo esta dentro do if, realizandoas seguintes operacoes:

• Definimos o tamanho do novo vetor: neste exemplo, criamos um novo vetor com o dobro dotamanho do vetor utilizado, isto e, o vetor inicia com 100 elementos e passa a 200, 400, 800elementos, conforme a necessidade; poderıamos aumentar de 1 em 1 elemento, ou entao de10 em 10, ou outra quantidade qualquer, poderıamos aumentar em 20% ou outra quantidadeproporcional, etc.

• Alocamos o novo vetor com o tamanho especificado.

• Copiamos todos os elementos do vetor antigo para o novo vetor.

• Liberamos area de memoria do vetor antigo: este vetor nao e mais necessario, pois todos oselementos ja estao em novo vetor, que e um vetor maior que o original.

• Atribuımos o valor do novo tamanho a variavel tamanho.

• Atribuımos o endereco do novo vetor ao apontador que contem o vetor utilizado: esta atri-buicao faz com que a variavel vetor que esta sendo utilizada ao longo da funcao contenhaagora o endereco do vetor maior, de modo que as insercoes seguintes serao possıveis.

Agora, podemos fornecer qualquer quantidade de elementos, pois a funcao nao precisa maislimitar esta quantidade. A unica limitacao que temos agora e de maquina.


Topico 6

Analise de complexidade

6.1 Introducao

Normalmente, o mesmo problema pode ter diversas solucoes computacionais utilizando diferentestecnicas de programacao, assim como, diferentes logicas de programacao. Uma pergunta surgeentao: como devemos fazer para escolher qual solucao usar? A resposta para esta questao pareceobvia. E claro que iremos considerar a solucao que seja mais rapida. Mas como determinarqual solucao e mais rapida? Para isto, sera necessario implementar programas que resolvameste problema, seguido de uma verificacao de tempo para cada solucao. Essa metodologia paraa determinacao do programa mais rapido e bastante custosa pois devemos ter um computador,um compilador, conhecer alguma linguagem de programacao, assim como, tempo sobrando parao seu desenvolvimento. Ainda, essa metodologia e altamente dependente das configuracoes docomputador usado. Para diminuir o custo deste processo, tentaremos desenvolver uma metodologiaque determinara o custo computacional de um algoritmo, com relacao ao tempo mas tambem aoespaco utilizado.

6.2 Complexidade computacional e analise assintotica

Dentre os objetivos de ATP2, estamos interessados em resolver problemas da melhor formapossıvel, isto e, desenvolver algoritmo cujo custo computacional seja o menor possıvel (dentrodas limitacoes e possibilidades oferecidas ate o momento) para um dado problema. Em outraspalavras, buscamos programas eficientes. Por exemplo, faca uma funcao de cabecalho

int posicaoDe(int x, int * v, int tam);

que retorne a posicao da ocorrencia do elemento x no vetor v contendo tam elementos distintos.Caso nao exista este elemento, retorne -1.

A primeira solucao para essa funcao 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 solucao podemos observar que todos os elementos serao sempre pesquisados e verificados,logo podemos afirmar que serao feitas tam comparacoes para determinar a posicao do elemento.Mas se o elemento estiver na primeira posicao, sera necessario comparar todos os elementos como elemento a ser pesquisado? Veja a segunda solucao

24


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 solucao, podemos ter 3 situacoes crıticas: (i) o elemento esta na primeira posicao do vetor; (ii)o elemento esta na ultima posicao do vetor; e (iii) o elemento nao esta no vetor. Para a situacao (i)teremos somente uma comparacao, ja para as outras situacoes teremos tam comparacoes. Aindae possıvel melhorar a solucao deste problema? A resposta ficara como exercıcio, assim como,possıveis solucoes, caso existam.

Como podemos observar, existem diferentes formas para se resolver o problema de localizacaode um elemento em um vetor, entretanto nenhuma comparacao entre as abordagens foi realizada.Para compararmos diferentes programas, relativo a sua eficiencia, definimos uma medida de graude dificuldade de um algoritmo, denominada complexidade computacional. A complexidadecomputacional indica quanto esforco e necessario para se aplicar um algoritmo, ou quao custosoeste algoritmo e. Dois diferentes criterios de eficiencia podem ser considerados: tempo e espaco.Aqui, consideraremos somente o tempo.

Quando consideramos tempo, a primeira ideia que temos e: quantos minutos (ou segundos)sao necessarios para a execucao de um programa? Esta abordagem e muito custosa, visto quetodos os programa devem ser implementados, na mesma linguagem, e executados em maquinascom as mesmas configuracoes, e ainda nas mesmas condicoes de teste. Contrariamente ao uso detempo real, a avaliacao de eficiencia de um algoritmo, da-se pela utilizacao de unidades logicas,que expressam a relacao entre o tamanho n da entrada e a quantidade de tempo f(n) necessariapara processar os dados. A definicao de uma unidade logica esta associada a(s) operacao(oes) quese deseja considerar para comparar algoritmos, por exemplo, quantas comparacoes sao realizadaspara localizar um elemento dentro de um vetor? Neste caso, a unidade logica a ser considerada ea comparacao.

Normalmente, a funcao para expressar a eficiencia de um algoritmo e complexa e cheia determos. Quando consideramos grandes quantidades de dados, termos que nao modifiquem agrandeza da expressao devem ser eliminados de forma a simplificar a comparacao entre diferentesfuncoes. Essa medida de eficiencia e denominada complexidade assintotica. 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 numero de elementos de um vetor).Nesta funcao, 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 sao quase irrisorios no calculoda funcao. Com isto, podemos concluir que a complexidade assintotica desse algoritmos esta emfuncao do termo n3.

Vale ressaltar que a avaliacao de eficiencia de um algoritmo faz sentido quando consideramosentradas de tamanho muito grande, pois para pequenas entrada, normalmente todos os algoritmossao rapidos. Por isto, a necessidade do estudo da complexidade assintotica, que ficara mais clarana proxima secao.

6.3 Notacao O

Uma abordagem para o estudo da eficiencia de um algoritmo e a analise do pior caso, tentandodeterminar a dependencia funcional do tempo de execucao com o tamanho da entrada. O primeiro



passo no processo e definir a nocao de “proporcional a”de forma precisa matematicamente, se-parando ainda, a analise do algoritmo de uma implementacao em particular. A ideia e ignorarfatores constantes na analise, como vista na complexidade assintotica. Por exemplo, na maioriados casos, nos desejamos saber se o algoritmo e proporcional a n ou a n log n, independentementese sera executado em um micro-computador ou em um super-computador. O artefato matematicopara tornar esta definicao precisa e chamada de notacao O (ou notacao grande O), que e usadapara especificar a complexidade assintotica.

Definicao 6.3.1 (Notacao O) f(n) e O(g(n)) se existem numeros positivos c e n0 tais quef(n) ≤ c g(n) para todo n ≥ no

Essa definicao e lida da seguinte forma: f e O de g se existe um numero positivo c tal quef nao seja maior do c g para n suficientemente grande, isto e, para todo n maior que algumnumero n0. Informalmente, essa definicao encapsula a nocao de “e proporcional a”e libera aanalise dos detalhes de maquinas particular. Alem disso, a declaracao que o tempo de execucaode um algoritmo e O(g(n)) e independente da entrada do algoritmo. Uma vez que nos estamosinteressados em estudar um algoritmo e nao a entrada nem sua implementacao, a notacao O e amaneira util de definir limites superiores sobre o tempo de execucao.

A notacao O tem sido extremamente util e tem ajudado bastante os analistas a classificaros algoritmos pelo desempenho e a guiar os projetistas de algoritmos na pesquisa para o melhoralgoritmo para problemas importantes. Entretanto, devemos ser extremamente cuidadosos nainterpretacao dos resultados expressos na notacao O, dentre as razoes para este cuidado podemoscitar: (i) por ser um limite superior, o tamanho da entrada poderia ser muito menor que aidentificada pela definicao; (ii) a entrada que provoca o pior caso, pode dificilmente ocorrer napratica; (iii) a constante c e desconhecida e nao precisa ser pequena; e (iv) a constante n0 edesconhecida e nao precisa ser pequena. A seguir iremos considerar cada um destes itens emdetalhe.

A afirmacao que o tempo de execucao de um algoritmo e O(g(n)) nao implica que o algoritmosempre sera tao longo, esta afirmacao diz somente que a analise foi capaz de mostrar que ele nuncatomara um tempo maior que g(n).

Mesmo se a entrada do pior caso e conhecida, pode ser o caso que as entrada na praticaconduzam a tempos de execucao muito inferiores. Por exemplo, um algoritmo de ordenacao (seraestudado posteriormente) chamada Quicksort possui o tempo de execucao no pior caso O(n2), mase possible arranjar a entrada de forma que o tempo de execucao seja proporcional a n log n.

As constantes c e n0 implıcitas na notacao O frequentemente escondem detalhes de imple-mentacao que sao importantes na pratica. Obviamente, dizer que um algoritmo tem um tempode execucao O(g(n)) nao considera nada sobre o tempo de execucao se n for menor que n0, ec 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 queexecuta em log n seculos, mas infelizmente, nos nao poderıamos fazer esta escolha com base nanotacao O.

De forma geral, os algoritmos podem ser classificados de acordo com o seu custo computacionalcrescente segundo a notacao O, como veremos a seguir:



O(1) A maioria das instrucoes da maioria dos programas sao executados umaunica vez, ou no maximo, poucas vezes. Se todas as instrucoes de umprograma tivessem esta propriedade, nos dirıamos que seu tempo de e-xecucao e constante. Essa e a situacao que todos os programadores e/ouprojetistas de software devem se esforcar para conseguir.

O(log n) Este tempo de execucao normalmente ocorre em algoritmos quando parti-cionamos um problema grande em pedacos menores de interesse. Quandoisto ocorre nos dizemos que o algoritmo possui tempo de execucao lo-garıtmico.

O(n) Quando o tempo de execucao e linear, a soma de processamento normal-mente e pequena para cada elemento da entrada.

O(n log n) Este tempo de execucao e computado para algoritmos que resolvem umproblema atraves da sua quebra em subproblemas menores, resolve cadaum destes subproblemas independentemente, e entao combina as solucoes.

O(n2) Este tempo de execucao normalmente e computado quando todos os paresde itens de dados sao processados. Quando isto ocorre dizemos que otempo de execucao e quadratico. Normalmente, algoritmos quadraticosdevem ser usados para problemas relativamente pequenos.

O(n3) Similarmente ao anterior, um algoritmo que processa triplas de itens dedados possui um tempo de execucao cubico.

O(2n) Poucos algoritmos com tempo de execucao exponenciais sao apropriadospara usos praticos. Estes algoritmos sao chamados de forca bruta pois,geralmente, processam n-uplas itens de dados.

6.4 Exemplos

Calcular a ordem de complexidade do seguinte algoritmo :

void Ordena(intA[ ], 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 calculo da ordem de complexidade deve ser efeito, entao, da seguinte forma :

void Ordena(intA[ ], int n){

int i, j,min, x;



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)min = j; · · · · · · · · · · · · · · · O(1)

}O(1)

O(n)

if (min != i) { · · · · · · · · · · · · · · · · · · · · · · · · · · · O(1)x = A[i− 1]; · · ·O(1)A[i− 1] = A[min− 1]; · · ·O(1)A[min− 1] = x; · · ·O(1)

O(1)

}

O(1)

O(n)

}

O(n2)

}

Calcule agora a funcao de complexidade f(n), tal que f(n) represente o numero de comparacoesentre os elementos do vetor A. De modo a calcular f(n) iremos utilizar de fi(n) = numero decomparacoes entre os elementos do vetor A para um dado i.

Dessa forma :fi(n) = n− i

Logo:

f(n) =n−1∑i=1

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

=n−1∑i=1

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

=(n− 1) + 1

2· (n− 1) =

=n

2· (n− 1) =

=n2

2− n

2·

A partir dessa funcao de complexidade podemos, tambem, encontrar a ordem de complexidade,veja:

O(f(n)) = O(n2

2− n

2) =

= O(n2

2) + O(−n

2) =

= O(max(n2

2,−n

2)) =

= O(n2

2) =

=12O(n2) =

= O(n2)


Topico 7

Recursividade

7.1 Definicao

Informalmente, recursao e um processo de resolver um problema grande atraves de sua reducaoa um ou mais subproblemas que sao (i) identicos em estrutura ao problema original e (ii) dealguma forma mais simples de resolver. Uma vez que subdivisao original tenha sido feita, amesma tecnica de decomposicao e usada para dividir cada um destes subproblemas em novossubproblemas que sao igualmente mais simples. Eventualmente, os subproblemas tornam-se taosimples que podem ser resolvidos sem uma nova subdivisao. A solucao completa e entao obtidalevando-se em consideracao os componentes resolvidos.

Uma definicao simples para uma funcao recursiva e que ela chama a ela mesma (como ja vimos,uma funcao definida em termos dela mesma). Ainda, uma funcao recursiva nao pode chamar aela mesma indefinidamente. Se isto ocorresse, o programa nunca acabaria. Por isto, e necessariohaver uma condicao de parada.

7.2 Ilustracao de uma abordagem recursiva

Imagine que voce tenha recentemente aceitado a posicao de coordenador de fundos para umacampanha de combate a fome de sua regiao. Nesta campanha, voce devera arrecadar 1000 reaisem doacoes. Devido as regras impostas pelo comite senior da campanha, cada doacao nao podepassar de 1 real por pessoa. Como voce deveria proceder?

Obviamente, a primeira solucao para este problema e encontrar 1000 pessoas da comunidade,e pedir a cada uma delas 1 real. Observe que voce mesmo devera pedir esta quantia diretamentepara estas pessoas. Computacionalmente falando, uma funcao de arrecadacao 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 funcao e baseada em um loop explıcito. Este tipo de construcao e chamadade solucao iterativa. Assumindo que voce poderia encontrar as 1000 pessoas, esta solucao seriaefetiva, mas ao mesmo tempo muito cansativa. Para evitar este cansaco e ainda para tentar agilizaro processo, a divisao dessa tarefa em sub-tarefas seria uma possıvel solucao. Por exemplo, ao invesde pedir o dinheiro para 1000 pessoas, voce pediria a ajuda a 10 pessoas, onde cada pessoa deveriaarrecar 100 reais. Partindo desta perspectiva, o problema continua sendo o mesmo, porem com

29


valores de arrecadacao diferentes. Ainda, a tarefa de arrecar 100 reais e teoricamente mais simplesque a tarefa de arrecar 1000 reais.

A essencia da abordagem recursiva conduz a aplicar a mesma decomposicao em cada estagioda solucao. Entao, seguindo a mesma abordagem, cada novo voluntario que deve arrecadar 100reais deve encontrar 10 outras pessoas que devam arrecar 10 reais cada. Cada um destes, deveainda, encontrar 10 outras pessoas que concordem em doar 1 real cada. Observe que nesta ultimaetapa, a estrategia foi alterada, pois agora foi pedido 1 real de cada doador, e nao feita umanova sub-divisao do problema. Recursivamente falando, o 1 real representa um caso simples, quepode ser resolvido diretamente sem uma nova decomposicao, este caso e chamado de condicao deparada.

Solucoes deste tipo sao frequentemente referenciadas como estratigia dividir para conquistar,uma vez que eles dependam do particionamente do problema em componentes mais gerenciaveis.

Para representar este algoritmo em uma forma computacional mais sugestiva, e importantenotar que existem diferentes instancias de um problema similar. No caso especıfica mostradoanteriormente, nos temos tarefas independentes de arrecadar 1000 reais, 100 reais, 10 reais efinalmente, 1 real. Estas tarefas correspondem a diferentes nıveis da hierarquia de arrecadacao.Para explorar esta similaridade, nos devemos generalizar o problema a tarefa de arrecadar, naomais uma soma especıfica, mas sim uma soma indeterminada de dinheiro, representada por umavariavel n.

A tarefa de arrecar n reais pode ser dividida em dois casos. Primeiro, se n e 1 real, entaonos simplesmente contribuimos com o nosso proprio dinheiro. Alternativamente, nos procueramos10 volutarios para nos ajudar a arrecar os n reais. Entretanto, cada voluntario devera arrecarsomente um decimo 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 loopexplıtico este algoritmo e recursivo pois ha uma chamada a propria funcao. Vamos entender cadauma das etapas deste algoritmo. A primeira etapa, representada pelo comando if , consiste emtestar se o problema corrente e tao simples que possa ser resolvido sem uma nova decomposicao.Se for verdade, ja arrecada 1 real diretamente, se nao, o problema devera ser dividido em sub-problemas, cada um dos quais e resolvido pela aplicacao da mesma estrategia.

7.3 Caracterısticas de algoritmos recursivos

Na maioria da vezes, a decisao de usar recursao e sugerida pela natureza do problema. Para ser umcandidato apropriado para a solucao recursiva, um problema deve ter tres propriedades distintas:

1. Deve ser possıvel decompor o problema original em instancias mais simples do mesmo pro-blema.

2. Uma vez que cada um desses sub-problemas tenha sido resolvido, deve ser possıvel combinarestas solucoes para produzir uma solucao para o problema original.



3. Como problemas grandes sao quebrados, sucessivamente, em problemas menos complexos,estes sub-problemas devem, eventualmente, tornar-se tao simples que eles possam ser resol-vidos sem uma outra subdivisao.

Normalmente, procedimentos recursivos tendem a fornecer um modelo conceitual bem naturalquando tendem a implementar problemas matematicos. Isto e verdade pois muitas definicoes ma-tematicas, tais como a fatorial e a Fibonacci, sao particularmente elegantes quando expressas naforma recursiva. As funcoes recursivas tambem podem ser implementadas de forma nao recursiva,mas esta implementacao e, as vezes, mais complicada pois depende de um profundo entendimentodo problema a ser resolvido. Existem tecnicas, que nao serao tratadas neste texto, para a conversaode programa recursivo para um programa nao recursivo. Os programas recursivos, embora pos-suam uma mesma complexidade computacional que suas respectivas solucoes nao recursivas, saomais lentos devido as diversas chamadas de funcoes, que produz um overhead de processamento.

7.4 Exemplos

Nesta secao, serao ilustrados alguns problemas bem como suas solucoes recursivas. O primeiroproblema a ser considerado ser a funcao fatorial, definida pela formula:

n! =

{n × (n− 1)! para n ≥ 11 caso contrario

(7.1)

Esta definicao de fatorial corresponde diretamente a seguinte funcao 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 basicas de uma programa recursivo: elechama a sim mesmo e ele possui uma condicao de parada. Por outro lado, nao existe mascaracaodo fato que este programa nada mais e que um loop for. Tambem, vale ressaltar que o fatorialnao trabalha com numeros negativos, logo e fundamental nao deixar que exista uma chamada aesta funcao quando o valor de n seja negativo. Um solucao nao recursiva para este problema sera

int fatorial_nrec(int n){int fat = 1;for (int i = 1; i <= n; i++)fat = fat * i;

return fat;}

Uma segunda bem conhecida relacao de recorrencia e aquela que define os numeros de Fibonaccide ordem 2.

Fib(n) =

Fib(n− 1) + Fib(n− 2) para n ≥ 21 para n = 11 para n = 0

(7.2)

Da mesma forma que o fatorial, essa relacao de recorrencia corresponde de forma direta oprograma recursivo a seguir



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 nao representam de forma convincente o poder da recursao, muitopelo contrario, ele nos convence o quao ineficiente pode ser. O problema na funcao de fibonaccie que as chamadas recursivas indicam que as chamadas fibonacci(n-1) e fibonacci(n-2) sao com-putadas independentemente, quando na realidade poderıamos usar uma para computar a outra.Assim, podemos usar um procedimento nao recursivo para computar os numeros de fibonacci.Entretanto, este procedimento precisara armazenar os resultados intermediarios. Uma possıvelsolucao 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 ja estudado anteriormente, quando ocorre uma chamada de funcao, varias informacoes (ir-relevantes para ATP2) sao enviadas para a pilha de execucao. Dentre as informacoes enviadaspara a pilha, o endereco de retorno assim como os parametros da funcao sao armazenados na pilha.

Nesta secao, veremos de maneira informal o que acontece quando se tem uma chamada re-cursiva. Considere o problema de elevar um numero x ao expoente n. A seguir e ilustrada umadefinicao recursiva deste problema em que o valor n e inteiro nao negativo.

xn =

{x(n−1) × x para n > 01 para n = 0

(7.3)

Usando esta definicao o valor de x4 pode ser computado do seguinte modo.

x4 = x × x3= x × (x × x2)= x × (x × (x × x1))= x × (x × (x × (x × x0)))= 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 definicao recursiva pode ser implementada pela funcao a seguir.

double potencia(double x, int n){if (n==0) return 1.0;else return x*potencia(x,n-1);

}

A aplicacao indutiva desta funcao para a chamada potencia(x,4) e ilustrada a seguir.

chamada 1 x4 = x × x3 = x × x × x × xchamada 2 x × x2 = x × x × xchamada 3 x × x1 = x × x



chamada 4 x × x0 = x × 1 = xchamada 5 1

ou alternativamente,

chamada 1 potencia(x,4)chamada 2 potencia(x,3)chamada 3 potencia(x,2)chamada 4 potencia(x,1)chamada 5 potencia(x,0)chamada 5 1chamada 4 xchamada 3 x× xchamada 2 x× x× xchamada 1 x× x× x× x

Observe que os resultados intermediarios, armazenados em algum lugar, sao computados daschamadas mais internas para as mais externas.


Topico 8

Estudo de Caso: TAD Pilha

8.1 Definicao

Uma Pilha representa um conjunto de elementos em que o unico elemento visıvel e o elemento quefoi inserido ha menos tempo no conjunto.

As operacoes sobre Pilhas sao as seguintes:

• Construcao: 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 desempilha-lo;

• vazia: verifica se a pilha esta vazia.

A unica forma de inserir elementos em uma pilha e via operacao empilha e a unica forma deretirar elementos e via operacao desempilha.

Para termos acesso ao penultimo elemento empilhado, devemos desempilhar o ultimo; o mesmoocorre com os demais elementos que tiverem sido inseridos anteriormente. Dizemos que uma Pilhae uma estrutura FIFO (First In, First Out = o primeiro que entra e o primeiro que sai).

8.2 Aplicacoes

Pilhas sao utilizadas em programas de computadores em chamadas de funcoes e procedimentos echamadas recursivas.

Utilizam-se pilhas tambem no processamento de estruturas aninhadas de profundidade impre-visıvel. Nesta situacao e necessario garantir que as estruturas mais internas sejam processadasantes da estrutura que as contenha. A pilha e uma estrutura adequada nesta situacao, pois aordem de remocao garante que as estruturas mais internas serao processadas antes das estruturasmais externas.

Podemos utilizar pilhas tambem em editores de texto e na interpretacao de expressoes aritme-ticas.

8.3 Interface da Classe Pilha

A implementacao do TAD Pilha pode ser feita por meio da classe com a seguinte assinatura:

34


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 metodos topo e desempilha retornam verdadeiro ou falso, indicando se a operacao foirealizada com sucesso; se retornar falso, entao a pilha estava vazia, o que impediu que a operacaofosse feita; se a operacao retornar verdadeiro, entao a operacao foi concluıda com sucesso.

O valor do topo da pilha e retornado pelo parametro de referencia valorTopo do metodo topo.

8.3.1 Implementacao do TAD Pilha Utilizando Vetores

Para implementar o TAD Pilha, incluiremos na classe Pilha os atributos vetor, que armazena osvalores da pilha, indTopo, que contem o ındice da primeira posicao vazia do vetor, e tamanho quecontem o numero de posicoes alocadas para o vetor. O vetor utilizara crescimento automatico, viametodo realoca, que tambem e privativo da classe.

typedef int Elemento;


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 atri-buto indTopo com o valor zero:

Pilha::Pilha() {

tamanho = TAMANHO_INICIAL;

vetor = new Elemento[tamanho];

indTopo = 0;

}

O destrutor ira liberar a area de memoria reservada para o vetor:

Pilha::~Pilha() {

delete [] vetor;

}

O metodo vazia retorna verdadeiro se o ındice do topo (indTopo) for igual a zero, ou falso,caso contrario:

bool Pilha::vazia() {

return (indTopo == 0);

}

O metodo empilha verifica se o ındice do topo e igual ao tamanho do vetor; se for igual, entaoa pilha esta cheia e sera necessario realocar o vetor; isto e feito chamando-se o metodo realoca.Apos o teste, e possıvel realocacao, atribui-se o valor a ser empilhado a primeira posicao do vetore aumenta em um o valor de indTopo:



void Pilha::empilha(Elemento novoElemento) {

if (indTopo == tamanho)

realoca();

vetor[indTopo++] = novoElemento;

}

O metodo realoca e identico ao metodo de mesmo nome definido na classe Vetor.O metodo topo verifica se a pilha esta vazia; se estiver, retorna falso; se nao estiver, atribui o

valor do topo ao parametro por referencia valorTopo e retorna verdadeiro:

bool Pilha::topo(Elemento & valorTopo) {

if (vazia() == true)

return false;

valorTopo = vetor[indTopo - 1];

return true;

}

O metodo desempilha verifica se a pilha esta vazia; se estiver, retorna falso; se nao estiver,diminui em um o valor de indTopo, indicando que ha uma posicao livre a mais, e retorna verdadeiro:

bool Pilha::desempilha() {


return false;

indTopo--;

return true;

}

8.4 Exemplos

As funcoes abaixo devem funcionar com qualquer implementacao de pilha, pois respeitam a assi-natura 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); // obtem 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) {



cout << valorTopo << " ";

P2.desempilha();

}

}

A funcao inicializa empilha os valores de 1 a 10 na pilha. A funcao copia retira todos oselementos de P1 e empilha em P2. Como a pilha inverte os elementos no momento da retirada,a pilha P2 contera os mesmos elementos que havia em P1, mas na ordem inversa. Observe que afuncao copia esvazia a pilha P1, pois nao e possıvel acessar um elemento sem retirar todos quetiverem sido inseridos depois.

Este programa devera imprimir o seguinte resultado na tela:

Pilha P1: 14 13 12

Pilha P2: 11 7 6 5 4 3 2 1


Topico 9

Estudo de Caso: TAD Fila

9.1 Definicao

Uma Fila representa um conjunto de elementos em que o unico elemento visıvel e o elemento quefoi inserido ha mais tempo no conjunto.

As operacoes sobre Filas sao as seguintes:

• Construcao: 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 esta vazia.

A unica forma de inserir elementos em uma fila e via operacao insere e a unica forma deretirar elementos e via operacao retira. Para termos acesso ao segundo elemento inserido, de-vemos retirar o primeiro; o mesmo ocorre com os demais elementos que tiverem sido inseridosposteriormente. Dizemos que uma Fila e uma estrutura LIFO (Last In, First Out = o ultimo queentra e o primeiro que sai).

9.2 Aplicacoes

Filas em geral sao utilizadas para controlar o processamento de elementos na ordem em queeles aparecerem, como por exemplo, em filas de impressao e em filas de processos do SistemaOperacional. Utilizamos filas tambem para implementacao de buscas em largura em Grafos e emInteligencia Artificial.

9.3 Interface da Classe Fila

A implementacao do TAD Fila sera 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


Assim como na pilha, os metodos frente e retira retornam verdadeiro ou falso, indicandose a operacao foi realizada com sucesso; se retornar falso, entao a fila estava vazia, o que impediuque a operacao fosse feita; se a operacao retornar verdadeiro, entao a operacao foi concluıda comsucesso.

O valor da frente da fila e retornado pelo parametro de referencia valorFrente do metodofrente.

9.3.1 Implementacao do TAD Fila Utilizando Vetores

Para implementarmos o TAD Fila, incluiremos na classe Fila os atributos vetor, que armazenaos valores da fila, indFrente, que contem o ındice onde se encontra o elemento na frente da fila,numElementos, que armazena o numero de elementos inseridos na fila, e tamanho que contem onumero de posicoes alocadas para o vetor. O vetor utilizara crescimento automatico, via metodorealoca, que tambem e privativo da classe.

// Facilita se for necessario alterar o tipo do elemento da pilha

typedef int Elemento;


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 osatributos indFrente e numElementos com o valor zero:

Fila::Fila() {

tamanho = TAMANHO_INICIAL;

vetor = new Elemento[tamanho];

indFrente = 0;

numElementos = 0;

}

O destrutor ira liberar a area de memoria reservada para o vetor:

Fila::~Fila() {

delete [] vetor;

}

O metodo vazia retorna verdadeiro se o numero de elementos (armazenado em numElementos)for igual a zero, ou falso, caso contrario:

bool Fila::vazia() {

return (numElementos == 0);

}

O metodo frente verifica se a Fila esta vazia; se estiver, retorna falso; se nao estiver, atribuiao parametro por referencia valorFrente o valor da frente da fila e retorna verdadeiro:

bool Fila::frente(Elemento & valorFrente) {


return false;

valorFrente = vetor[indFrente];

return true;

}



Os metodos insere e retira trabalham em conjunto implementando o que chamamos de FilaCircular.

Considere que a fila esteja representada por um vetor de 10 posicoes e que tenhamos inseridoos numeros de 1 a 10. Apos estas operacoes, considere que houve 3 retiradas. Para termos menostrabalho na movimentacao dos elementos, podemos supor que o estado do objeto sera o seguinteao longo da execucao (X marca posicao livre no vetor):

Inicialmente:

F = fila vazia

vetor: X X X X X X X X X X

indFrente: 0

numElementos: 0

tamanho: 10

Apos as inserc~oes dos numeros de 1 a 10:

F = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

vetor: 1 2 3 4 5 6 7 8 9 10

indFrente: 0

numElementos: 10

tamanho: 10

Apos as tres retiradas:

F = 4, 5, 6, 7, 8, 9, 10

vetor: X X X 4 5 6 7 8 9 10

indFrente: 3

numElementos: 7

tamanho: 10

Observe que nao e necessario movimentar os numeros de 4 a 10 para o inıcio do vetor, bastaindicar que o ındice da frente e igual a 3, o que significa que ha sete elementos iniciando no ındice3 e terminando no ındice 9.

Entretanto, suponha agora que precisemos inserir o valor 11 na fila. Ha diversas formas deinserirmos este valor na fila.

A primeira e copiar todos os elementos algumas casas para tras e continuarmos inserindo nofinal da sequencia; isto acarretaria em um custo muito alto para uma simples insercao.

Outra alternativa consiste em realocar o vetor e continuar fazendo a insercao no final, comoja estava sendo feito. Tambem isto acarreta em executarmos operacoes superfluas, visto que haposicoes livres (de 0 a 2).

A alternativa de menor custo e aproveitar o inıcio do vetor (que esta vazio) e imaginar que elee uma continuacao do final. Em outras palavras, imaginaremos que o vetor inicia na posicao 3,onde esta o primeiro elemento, contem elementos ate a posicao 9, e continua nas posicoes de 0 a2. Isto e, estamos considerando que os elementos do vetor estao em ordem, mas esta ordem naoe necessariamente o primeiro elemento esta na posicao zero e os demais nas posicoes seguintes.Agora, imaginamos que a sequencia inicia em um ponto qualquer do vetor e pode ultrapassar olimite fısico do vetor; entretanto, quando a sequencia ultrapassar este limite, os elementos estaraoarmazenados no inıcio do vetor.

Utilizando esta abordagem, considere a insercao dos valores 11, 12 e 13 na fila. Estas operacoesgerarao a seguinte configuracao do objeto:

Apos a inserc~ao do 11:

F = 4, 5, 6, 7, 8, 9, 10, 11

vetor: 11 X X 4 5 6 7 8 9 10

indFrente: 3

numElementos: 8

tamanho: 10


F = 4, 5, 6, 7, 8, 9, 10, 11, 12

vetor: 11 12 X 4 5 6 7 8 9 10

indFrente: 3

numElementos: 9



tamanho: 10


F = 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

vetor: 11 12 13 4 5 6 7 8 9 10

indFrente: 3

numElementos: 10

tamanho: 10

Agora temos um vetor cheio. A unica diferenca e a modificacao nos conceitos de inıcio etermino da sequencia no vetor. Neste ultimo exemplo, a sequencia inicia no ındice 3, vai ate oındice 9 (que e o final do vetor), e depois continua nas posicoes 0, 1 e 2.

Observe tambem que se quisermos inserir mais um elemento, a realocacao sera inevitavel, poisnao ha mais posicoes livres no vetor.

Desta forma, o metodo retira devera sempre aumentar o valor do atributo indFrente em umelemento. Para simular a circularidade, se o valor de indFrente ficar igual ao tamanho do vetor,que esta no atributo tamanho, entao passaremos este valor para 0. Nao podemos esquecer que,no inıcio do metodo, devemos testar se a fila esta vazia, pois isto definira o valor de retorno. Ometodo abaixo mostra a implementacao da tecnica explicada:

bool Fila::retira() {


return false;

indFrente++;

if (indFrente == tamanho)

indFrente = 0;

numElementos--;

return true;

}

O metodo insere utilizara o mesmo conceito. Inicialmente, verificamos se o numero de ele-mentos da fila e igual ao seu tamanho. Se for igual, sera necessario realocar o vetor, chamando-seo metodo realoca. Apos a verificacao, e possıvel realocacao, devemos verificar onde a sequenciade elementos termina, para inserirmos o elemento na posicao seguinte.

Por simplicidade, iniciemos com uma fila com a seguinte configuracao:

Uma fila qualquer:

F = 4, 5, 6, 7, 8

vetor: X X X 4 5 6 7 8 X X

indFrente: 3

numElementos: 5

tamanho: 10

Se quisermos inserir outro elemento nesta fila, deveremos fazer a insercao na penultima posicaodo vetor, isto e, na posicao 8. Como era de se esperar, esta posicao e exatamente igual a indFrente+ numElementos.

Considere agora que a fila possui a configuracao abaixo:

Outra fila qualquer:

F = 4, 5, 6, 7, 8

vetor: 7 8 X X X X X 4 5 6

indFrente: 7

numElementos: 5

tamanho: 10

Observe que esta fila inicia na posicao 7, vai ate o final do vetor, volta a posicao zero e ocupaate a posicao 1. Se aplicarmos a formula anterior, obteremos a posicao 12, que e a terceira posicaoapos a ultima posicao do vetor, posicao 9. Se subtrairmos entao o tamanho do vetor, obteremosa posicao 2, que e exatamente a primeira posicao livre.

Unindo todos estes elementos, chegamos a seguinte implementacao do metodo insere:



void Fila::insere(Elemento novoElemento) {


realoca();

int pos_insercao = indFrente + numElementos;

if (pos_insercao >= tamanho)

pos_insercao = pos_insercao - tamanho;

v[pos_insercao] = novoElemento;

numElementos++;

}

Estes metodos poderiam ser escritos em menos linhas, utilizando a operacao de resto da divisao:

void Fila::insere(Elemento novoElemento) {


realoca();

int pos_insercao = (indFrente + numElementos) % tamanho;

v[pos_insercao] = novoElemento;

numElementos++;

}

bool Fila::retira() {


return false;

indFrente = (indFrente + 1) % tamanho;

numElementos--;

return true;

}

9.4 Exemplos

As funcoes abaixo devem funcionar com qualquer implementacao de fila, pois respeitam a assina-tura 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); // obtem 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) {



cout << valorFrente << " ";

F2.retira();

}

}

Este programa devera imprimir o seguinte resultado na tela:

Fila F1: 12 13 14

Fila F2: 4 5 6 7 8 9 10 11


Documents

Apostila de AED em C++