apostila_AED Algoritmos e Estruturas de Dados

8/9/2019 apostila_AED Algoritmos e Estruturas de Dados

1/24

Apostila de COM146Algoritmos e Estruturas de Dados I

Disciplina do 1o mdulo doCurso de Cincia da Computaoda Universidade Federal de Lavras

Olinda Nogueira Paes Cardoso1

Agosto de 2002

1 Professora Auxiliar do Departamento de Cincia da Computao da UFLA


2/24

1

NDICE

1. Introduo ......................................................................................................................................... 21.1. Necessidade do uso da lgica ...................................................................................................... 21.2. Conceitos Bsicos......................................................................................................................... 21.3. Conceito de Algoritmo................................................................................................................... 2

2. PORTUGOL...................................................................................................................................... 32.1. Definio de Variveis Tipos Bsicos........................................................................................ 32.2. Comandos Bsicos ....................................................................................................................... 42.3. Blocos e Comandos Bsicos de Controle..................................................................................... 42.4. Outras estruturas de repetio...................................................................................................... 72.5. Definio de novos tipos de dados............................................................................................... 82.6. Estruturas Condicionais Encadeadas ........................................................................................... 8

3. Ordenao ........................................................................................................................................ 9

3.1.

Ordenao de Vetores .................................................................................................................. 93.1.1. Ordenao por insero ........................................................................................................ 9

3.1.2. Ordenao por seleo........................................................................................................ 104. Matrizes .......................................................................................................................................... 11

4.1. Matrizes Bidimensionais ............................................................................................................. 115. Registros......................................................................................................................................... 12

5.1. Registro com Vetor ..................................................................................................................... 125.2. Conjuntos de Registros............................................................................................................... 13

6. Arquivos .......................................................................................................................................... 136.1. Organizao de Arquivos............................................................................................................ 14

6.1.1. Organizao Seqencial...................................................................................................... 146.2. Organizao Direta ..................................................................................................................... 15

7. Modularizao ................................................................................................................................ 177.1.

Benefcios da modularizao ...................................................................................................... 18

7.2. Ferramentas para modularizao ............................................................................................... 187.3. Modos de transferncia de parmetros ...................................................................................... 19

8. Recursividade ................................................................................................................................. 198.1. Exemplo de problema recursivo ................................................................................................. 208.2. Recurso Iterao.................................................................................................................... 208.3. Exemplos mais famosos de problemas recursivos..................................................................... 20

9. Apontadores ................................................................................................................................... 2110. Listas Lineares................................................................................................................................ 22

10.1. Operaes em listas lineares .................................................................................................. 2210.2. Implementao de listas lineares ............................................................................................ 23


3/24

2

1. INTRODUO

1.1. NECESSIDADE DO USO DA LGICA

A lgica a cincia que estuda as leis e os critrios de validade que regem o pensamento e ademonstrao, ou seja, cincia dos princpios formais do raciocnio. A lgica usada no dia a dia daspessoas que trabalham com computao para solucionar problemas de forma eficiente.

A tcnica mais importante no projeto da lgica de programas chamada programaoestruturada, a qual consiste em uma metodologia de projeto que objetiva:

agilizar a codificao da escrita da programao; facilitar a depurao da leitura da mesma; permitir a verificao de possveis falhas apresentadas pelos programas; facilitar as alteraes e atualizaes dos programas.

1.2. CONCEITOS BSICOS

O conceito central da programao em cincia da computao o de algoritmo. SegundoWirth a programao estruturada a arte ou tcnica de construir e formular algoritmos de uma formasistemtica.

Programas so formulaes concretas de algoritmos abstratos, baseados em representaese estruturas especficas de dados. Estruturas de dadosso usadas no algoritmo para representar asinformaes do problema a ser resolvido.

Na programao deve-se distinguir claramente dois aspectos:Aspecto esttico a formulao de um algoritmo consiste em um texto contendo comandos(instrues) que devem ser executados numa ordem prescrita.Aspecto dinmico os efeitos que so causados pela execuo do programa no tempo, dado umconjunto de valores iniciais.

1.3. CONCEITO DE

ALGORITMO

Um algoritmo uma norma executvel para estabelecer um certo efeito desejado, que na

prtica ser geralmente a obteno de uma soluo a um certo tipo de problema.

Exemplo de algoritmo para trocar uma lmpada queimada:pegar uma lmpada nova no armrio;pegar a escada na rea de servio;subir na escada com a lmpada nova na mo;retirar a lmpada queimada;colocar a lmpada nova;descer a escada;testar se a lmpada nova est funcionando

O smbolo de seqenciamento (;) tem duas funes: no texto a de separar um comando dooutro; e no evento a de indicar que os comandos separados devem ser executados na mesmaseqncia em que aparecem no texto.

O smbolo ;representa a mais simples estrutura de controle, a seqncia simples.

Exerccio: escreva um algoritmo para se trocar um pneu furado. Assuma que esto disponveis ummacaco e um estepe em boas condies.

Seguindo com o exemplo da troca de lmpadas, vamos supor que h a possibilidade de que aescada disponvel no seja alta suficiente para alcanar a lmpada e que, neste caso, gostaramosprever este possvel erro. Poderamos reescrever o algoritmo desta forma:

pegar uma lmpada nova no armrio;

pegar a escada na rea de servio;subir na escada com a lmpada nova na mo;


4/24

3sefor possvel alcanar a lmpada a ser trocada ento

retirar a lmpada queimada;colocar a lmpada nova;

descer da escada;guardar a escada;

Outro caso: supondo que havia vrias lmpadas para serem trocadas na casa. Poderamosreescrever o algoritmo desta forma:pegar todas as lmpadas novas no armrio;pegar a escada na rea de servio;enquantoexistirem lmpadas novas disponveis faa

subir na escada com uma lmpada nova na mo;sefor possvel alcanar a lmpada a ser trocada ento

retirar a lmpada queimada;colocar a lmpada nova;

descer da escada;guardar a escada;

2. PORTUGOL

A partir de agora ser introduzida uma linguagem de expresso de algoritmos, o PORTUGOL.Sero apresentadas a sintaxe e a semntica dos comandos da linguagem. PORTUGOL umapseudolinguagem de programao utilizada para obter uma notao para algoritmos, a ser usada nadefinio, na criao, no desenvolvimentoe na documentaode um programa.

O objetivo no criar mais uma linguagem de programao, por isso as regras no precisamser seguidas de forma muito rgida. Considerando o PORTUGOL, a sintaxe definida e a formaapresentada e aceita como padro. Para cada declarao e/ou comando a semntica deve serexplicada.

O identificador o elemento bsico da linguagem, a sua sintaxe definida pelo diagramaapresentado na Figura 1:

Figura 1: Diagrama que representa um identificador

2.1. DEFINIO DE VARIVEIS TIPOS BSICOS

No PORTUGOL existem quatro tipos bsicos, isto , tipos bsicos de dados que podem serutilizados: INTEIRO, REAL, CARACTER e LGICO.

Uma varivel pode ser entendida como um local onde se pode colocar qualquer valor doconjunto de valores possveis do tipo bsico associado. O nome da varivel o identificador tal comodefinido anteriormente. Por exemplo:

Toda varivel deve ser declarada conforme a sintaxe apresentada na Figura 2.A semntica de uma declarao de variveis corresponde criao de locais na memria,

rotulada com o nome do identificador (varivel) e marcada com o tipo de valores que ela pode conter.

SOMA

VarivelSOMA

letra

letra

dgito


5/24

4

Figura 2: Diagrama que representa a definio de uma varivel.

2.2. COMANDOS BSICOS

O comando de ATRIBUIO utilizado para atribuir um valor a uma varivel. Para isso usa-se o smbolo , conforme a seguinte sintaxe:

A notao usada para expresses basicamente uma forma linear comumente usada namatemtica, que pode conter operadores:

ARITMTICOS: +, -, /, *, raiz( ), **, sen( ), cos( ), mod, div,...LGICOS: e, ou, no ( , V, )RELACIONAIS: =, , >, (ou >=),

fim

Uma seqncia simples um conjunto de comandos separados por ponto e vrgula (;), quesero executadas numa seqncia linear de cima para baixo.Exemplo:

comando1;comando2;comando3;...comandoN;

Quando a ao a ser executada depender de uma inspeo (teste), teremos uma alternativa,ou estrutura condicional, simples ou composta.

inteiro identificador

real

caracter

l ico

;

,

:

identificador expresso ;


6/24

5

Exemplo de uma estrutura condicional simples:se < condio >

entocomando1;

comando2;...comandoN;

fim se;

Exemplo de uma estrutura condicional composta:se < condio >

entocomando1;comando2;...comandoN;

seno

comando1;comando2;...comandoN;

fim se;

Nos comandos apresentados, < condio > qualquer expresso cujo resultado seja falsoouverdadeiro.

Exerccio: Qual ser o valor final das variveis A e B depois da execuo do seguinte algoritmo?incio

inteiro: A, B;A 1;

B 2;se A > B

entoA 5;

senoA 10;

fim se;fim;

Uma estrutura de repetio quando um conjunto de aes executado repetidamenteenquanto uma determinada condio permanece vlida (ou seja, quando o resultado de da expresso um valor lgico verdadeiro).

Exemplo de uma estrutura de repetio:

enquanto < condio > faacomando1;comando2;...comandoN;

fim enquanto;

Enquanto o valor da < condio > for verdadeiro, as aes dos comandos so executadas equando se tornar falso, o comando abandonado. Se j da primeira vez o resultado falso, oscomandos no so executados.


7/24

6Exerccio: Qual ser o valor final das variveis declaradas no seguinte algoritmo, depois de sua

execuo?incio

inteiro: A, B, C, I;A 1;

B 1;I 1;enquanto I < 10 faa

C A + B;A B;B C;I I + 1;

fim enquanto;fim;

At agora todos os valores calculados pelos algoritmos foram gerados e permaneceram namemria. Para obter ou para fornecer dados ao ambiente exterior ao algoritmo, por exemplo do tecladoe para o vdeo, preciso utilizar comandos de entrada e sada. O comando de entrada leia e ocomando de sada imprima, e suas sintaxes so apresentadas a seguir.

Exemplo de um algoritmo que usa comandos de entrada e sada:incio

inteiro: A, B, SOMA;leia (A, B);SOMA A + B;imprima (A soma entre , A, e , B, , SOMA);

fim;

Exerccio: Escreva o algoritmo que realize a multiplicao de dois nmeros inteiros, utilizando apenas ooperador da soma (+).

Regras prticas para a construo de algoritmos legveis:

Procure incorporar comentrios no algoritmo para descrever o significado das variveis eaes utilizadas. Para isso use chaves {}.

Escolha nomes de variveis que sejam significativos, isto , que traduzam o tipo deinformao a ser armazenada na varivel. Por exemplo: NOTA, SOMA, MDIA, etc.

Grife as palavras-chave (escritas com letras minsculas) do algoritmo, destacando asestruturas de controle.

Procure alinhar os comandos de acordo com o nvel a que pertencem, isto , destaque aestrutura na qual esto contidos.

identificadorimprima ;( )

expresso

caracter

,

identificadorleia ;( )

,


8/24

7

Exerccios de Fixao: Construa algoritmos para solucionar os seguintes problemas.

1. Como saber se um nmero divisvel por outro.

2. Calcular a mdia final de um aluno que realizou 4 avaliaes, sabendo que todas tm o mesmopeso.3. Dados 3 nmeros, verificar qual deles o menor.

2.4. OUTRAS ESTRUTURAS DE REPETIO

Sero apresentadas a seguir outras duas estruturas de repetio que tambm podem serutilizadas na construo de algoritmos usando o PORTUGOL, so elas: repitae para.

A estrutura de repetio repitadifere da enquantono que diz respeito ao momento em que oteste da condio submetido.

repitacomando1;

comando2;...

comandoN;at < condio >;

Na estrutura enquantoo teste realizado antes da execuo do primeiro loop, ou seja, podeser que os comandos no sejam realizados sequer uma vez, caso a condio seja falsa j na primeiravez em que foi testada. J na repitaos comandos sempre sero executados pelo menos uma vez, atque a condio seja testada, no final da estrutura.

A estrutura de repetio paradifere das estruturas enquantoe repita, pois utiliza uma varivelde controle, que atua como um contador de repeties.

para I de 1 at 10 passo 1 faa

comando1;comando2;...

comandoN;fim para;

Observando o exemplo, percebe-se que foi utilizada uma varivel do tipo inteiro ( I), que deveter sido declarada anteriormente. Esta estrutura ir executar os comandos 10 vezes, pois possui Ivariando automaticamente de 1 em 1 (passo 1) at 10, ou seja, no necessrio fazer o incrementodeste dentro da estrutura de repetio.

Exerccio: Avalie os algoritmos construdos at o presente momento e, quando achar vivel, substitua aestrutura de repetio enquantopela estrutura repitaou para, a fim de melhorar o seu desempenho.

O comando abandones tem sentido dentro de um comando de repetio (enquanto, repitaepara). Alm disso, estar sempre associado ao teste de uma condio com comando se.Sintaxe: abandone;

A semntica do comando a seguinte: quando o abandone encontrado, o prximo comandoa ser executado o primeiro logo aps o fim do comando de repetio mais interno onde este aparece.Exemplo:

...enquanto I > 0 faa

I I + 1;imprima (I);se I2 + 1


9/24

8fim se;

fim enquanto;2.5. DEFINIO DE NOVOS TIPOS DE DADOS

Nem sempre os tipos bsicos (inteiro, real, caracter e lgico) so suficientes para exprimir

estruturas de dados em algoritmos. Da a necessidade de novos tipos de dados serem criados. Umdestes tipos o vetor.No PORTUGOL a criao de um vetor segue as especificaes:

tipo nome_do_tipo= vetor [li:ls] ; dado um nome_do_tipoao novo tipo de vetor criado, onde li o limite inferior e ls o limite

superior de um intervalo que define o tamanho do vetor (valores inteiros), e tipo_bsico um dos tiposbsicos j conhecidos. Esta especificao apenas indica um modelo para a criao de variveis destenovo tipo. Para efetivar esta estrutura dentro do algoritmo, necessrio declar-la dando um nome avarivel que ser criada segundo o modelo especificado.

Exemplo: um vetor que armazena as notas de todos os alunos de uma turma com 25 alunos.tipo v = vetor [1:25] real;v: NOTAS;

O nmero de elementos de um vetor dado por ls-li+1. Isto significa que as posies do vetor

so identificadas a partir de li, com incrementos unitrios at ls.li li+1 li+2 lsCada elemento de um vetor tratado como se fosse uma varivel simples. Para referncia a umelemento do vetor utiliza-se o nome do vetor e a identificao do elemento (ndice) entre colchetes ([ ]).

Por exemplo, se quisermos atribuir o valor de uma 45 a nota do 6o aluno (que identificadopelo ndice 6 do vetor de notas): NOTAS [6] 45;

Exemplo: O que ser impresso no algoritmo abaixo?incio

inteiro: I;tipo vc = vetor [1:7] caracter;vc: DIAS;DIAS [1] domingo;DIAS [2] segunda-feira;

DIAS [3] tera-feira;DIAS [4] quarta-feira;DIAS [5] quinta-feira;DIAS [6] sexta-feira;DIAS [7] sbado;para I de 1 at 7 passo 2 faa

imprima (DIAS [I]);fim para;

fim.

Exerccio: Um professor de uma turma com 30 alunos quer armazenar as notas de seus alunos em umvetor e depois calcular a mdia geral da turma. Escreva um algoritmo que solucione este problema

usando uma estrutura de vetor.2.6. ESTRUTURAS CONDICIONAIS ENCADEADAS

Existem casos em que necessrio se estabelecerem verificaes de condies sucessivas,onde uma determinada ao poder ser executada se um conjunto anterior de condies for satisfeito.Isto significa usar uma condio dentro de outra. Este tipo de estrutura pode possuir diversos nveis decondio, sendo chamada de aninhamentoou encadeamentode estruturas condicionais. Exemplo:

se entoseno

se ento

seno


10/24

9fim se; {final do se mais interno}

fim se; {final do primeiro se (mais externo)}

Exerccio: Escreva um algoritmo que efetue o clculo de reajuste de salrio de um funcionrio.Considere que o aumento ser de 15% se o salrio for at R$500,00, de 10% se for entre R$501,00 e

R$1.000,00 e de 5% se for maior que R$1.000,00.

3. ORDENAO

A atividade de ordenao o processo de rearranjo de um certo conjunto de objetos deacordo com um critrio (ordem) especfico. O objetivo da ordenao facilitar a localizao dosmembros de um conjunto de dados.

3.1. ORDENAO DE VETORES

A preocupao mais importante a ser estabelecida em relao aos mtodos de ordenao devetores corresponde ao uso econmico da memria disponvel. Isto implica que a permutao deelementos, responsvel por levar o elemento ordem desejada, deve ser efetuada in situ, e que,

portanto, so de menor interesse os mtodos que efetuam o transporte fsico dos elementos de umvetor A para um vetor resultante B.

Restringindo-se a escolha dos mtodos, dentre as inmeras solues possveis, de acordocom o critrio de economia de memria, pode-se promover uma primeira classificao de acordo com aeficincia do mesmo em relao economia de tempo.

Uma boa medida de eficincia obtida contando-se o nmero Cde comparaes necessriase o nmero Mde movimentos (transposies) dos elementos. Estes nmeros so funes do nmero nde elementos a serem ordenados.

Os mtodos de ordenao que ordenam os elementos in situpodem ser classificados em trsprincipais categorias:

Ordenao por insero Ordenao por seleo Ordenao por troca

Estes trs princpios sero examinados e comparados. Os exemplos operam sobre a varivel A,cujos componentes sero ordenados e se referem a um vetor de inteiros de tamanho varivel (N),definido como se segue:

inteiro: N;tipo vet = vetor [1:N] inteiro;vet: A;

3.1.1. ORDENAO POR INSERO

Em cada passo, iniciando-se com i=2e incrementando-se ide uma em uma unidade, o i-simoelemento da seqncia vai sendo comparado com os elementos anteriores e, se for o caso, retirado e

inserido na posio apropriada.O processo de ordenao por insero ser mostrado em um exemplo, em que so ordenadosoito nmeros (N=8) escolhidos aleatoriamente. O algoritmo deve fazer o seguinte:

para I de 2 at N faaX A[I];inserir X no local adequado em A[1]...A[I]

fim para

Valores iniciais 44 55 12 42 94 18 06 67

i = 2 44 55 12 42 94 18 06 67i = 3 12 44 55 42 94 18 06 67i = 4 12 42 44 55 94 18 06 67

i = 5 12 42 44 55 94 18 06 67i = 6 12 18 42 44 55 94 06 67


11/24

10i = 7 06 12 18 42 44 55 94 67i = 8 06 12 18 42 44 55 67 94

Para encontrar o local apropriado do elemento observado conveniente utilizar, de modoalternado, operaes de comparao e de movimentao, examinando X, e comparando-o com oelemento A[J], e ento efetuando ou a insero de X ou a movimentao do elemento A[J], e

prosseguindo-se para a esquerda no tratamento dos outros elementos.Para isso ser necessrio testar duas condies distintas que causam o trmino desteprocesso de anlise:

Um elemento A[J] encontrado com um elemento de valor menor do que o seu A extremidade esquerda atingida

um caso tpico de uma repetio com duas condies de trmino, que conduz a utilizao deum elemento sentinela (para armazenar temporariamente o valor de algum elemento que est sendoanalisado). Para isso, ser utilizada uma posio do vetor A como sentinela, o A[0]que receber o valorde X.

inciointeiro: I, J, N, X;tipo vet = vetor [0:N] inteiro;

vet: A; {supondo que o vetor A tenha sido preenchido}...para I de 2 at N faaX A[I];A[0] X;J I;enquanto X < A[J-1] faa

A[J] A[J-1];J J-1;

fim enquanto;A[J] X;

fim para;fim;

3.1.2. ORDENAO POR SELEO

Este mtodo baseado no seguinte princpio: Selecionar o elemento que apresenta o menor valor Troc-lo com o primeiro elemento da seqncia A[1] Repetir estas operaes, envolvendo agora os N1 elementos restantes, depois os N2

elementos, ..., at restar um s elemento, o maior deles.

Valores iniciais 44 55 12 42 94 18 06 6706 55 12 42 94 18 44 6706 12 55 42 94 18 44 6706 12 18 42 94 55 44 67

06 12 18 42 94 55 44 6706 12 18 42 44 55 94 6706 12 18 42 44 55 94 6706 12 18 42 44 55 67 94

inciointeiro: I, J, N, K;tipo vet = vetor [1:N] inteiro;vet: A; {supondo que o vetor A tenha sido preenchido}...para I de 1 at N1 faa

K I;X A[I];para J de I+1 at N faa

se A[J] < X ento

K J;


12/24

11X A[K];

fim se;

fim para;A[K] A[I];

A[I] X;fim para;fim;

4. MATRIZES

Uma matriz uma estrutura de dados homognea, ou seja, todos os elementos de uma matrizso do mesmo tipo. Um vetor uma matriz unidimensional, a partir de agora sero apresentadasmatrizes com mais de uma dimenso.

4.1. MATRIZES BIDIMENSIONAIS

A forma mais comum de trabalhar com matrizes utilizando duas dimenses, apesar de queem alguns casos possa ser necessrio trabalhar com mais de duas. Uma matriz bidimensional composta por linhas e colunas. As linhas podem ser consideradas como a primeira dimenso e ascolunas a segunda dimenso. preciso definir o tamanho de cada uma dessas dimenses, ou seja, onmero de linhas e o nmero de colunas que esta matriz dever possuir.

Exemplo: Definio de uma matriz com 8 linhas e 5 colunas.

tipo mat = matriz [1..8, 1..5] inteiro;mat: TABELA;

TABELA 1 2 3 4 51

2345678

Exemplo de algoritmo utilizando matriz com duas dimenses:

Seja uma matriz a representao das notas obtidas pelos alunos em uma determinada disciplina. Aquantidade de linhas dever ser equivalente ao nmero de alunos, neste caso 25. Cada coluna deverconter o valor de uma das avaliaes de cada aluno, neste caso so 3 avaliaes. O algoritmo deve

preencher a matriz com as notas.

inciointeiro: I, J;tipo m = matriz [1..25, 1..3] real;m: NOTAS;para J de 1 at 3 faa

imprima (Digite as notas referentes a prova, J);para I de 1 at 25 faa

leia (NOTAS [I, J]);fim para;

fim para;fim.


13/24

12Exerccio: Escreva um algoritmo que receba as notas referentes a trs avaliaes realizadas por 25

alunos, e as armazene numa matriz, juntamente com a mdia total obtida pelo aluno. Sabendo que: asduas primeiras avaliaes tm peso de 35 cada uma e a terceira tem peso de 30 pontos. Alm disso,para cada mdia total deve ser enviada uma mensagem informando se o aluno foi aprovado (>=50) oureprovado (


14/24

13imprima (Digite a idade do aluno);leia (ALUNO.IDADE);

imprima (Digite a turma do aluno);leia (ALUNO.TURMA);

imprima (Digite o perodo do aluno);leia (ALUNO.PERIODO);imprima (Digite as notas do aluno);para I de 1 at 6 faa

leia (ALUNO.NOTAS[I]);fim para;

fim

5.2. CONJUNTOS DE REGISTROS

No conjunto de registros so armazenados dados de vrias ocorrncias de um determinadotipo de registro. Por exemplo, para armazenar os dados de diversos alunos:

incio

inteiro: I, J, N;tipo vet = vetor [1..6] real;tipo reg = registro

caracter: MATcaracter: NOMEinteiro: IDADEcaracter: TURMAinteiro: PERIODOvet: NOTAS

fim registro;tipo aluno = conjunto [1..N] reg;aluno: ALUNOS;imprima (Digite o nmero de alunos);

leia (N);para I de 1 at N faaimprima (Digite a matrcula do aluno);leia (ALUNOS[I].MAT);imprima (Digite o nome do aluno);leia (ALUNOS[I].NOME);imprima (Digite a idade do aluno);leia (ALUNOS[I].IDADE);imprima (Digite a turma do aluno);leia (ALUNOS[I].TURMA);imprima (Digite o perodo do aluno);leia (ALUNOS[I].PERIODO);imprima (Digite as notas do aluno);

para J de 1 at 6 faaleia (ALUNOS[I].NOTAS[J]);fim para;

fim para;fim

6. ARQUIVOS

At o momento, todas as estruturas de dados estudadas ficaram armazenadas no ambiente doalgoritmo, ou seja, tinham durao apenas enquanto o algoritmo estava sendo executado. O arquivo uma alternativa para estrutura de dados que pode ser fisicamente alocado em outro meio dearmazenamento, em disco, por exemplo.


15/24

14Um registro a parte lgica de uma estrutura de dados, enquanto que um arquivo,

constitudo por um conjunto de um ou mais registros, a parte fsica, e pode ser chamado de registrofsico.

6.1. ORGANIZAO DE ARQUIVOS

As operaes bsicas que podem ser feitas em um arquivo atravs de um algoritmo so:obteno de um registro do arquivo, insero de um novo registro, modificao ou excluso de umregistro.

A disposio (organizao) de registros no arquivo pode favorecer determinadas operaesem detrimento de outras. Conhecendo a organizao, o projetista de algoritmos pode escolher aquelaque seja mais adequada soluo do seu problema em termos de eficcia e eficincia.

Basicamente, existem duas possibilidades de organizao de arquivos: Seqencial na qual os registros so obtidos ou inseridos no arquivo em ordem seqencial; Direta em que o acesso do registro feito de forma direta atravs do uso de um

identificador para o registro.O fato de o arquivo ser armazenado em uma memria secundria o torna independente de

qualquer algoritmo, ou seja, ele pode ser criado, consultado, processado e at mesmo removido por

algoritmos distintos.Sendo o arquivo uma estrutura fora do ambiente do algoritmo, para que este tenha acessoaos dados do arquivo so necessrias as operaes de leitura e escrita de registros no arquivo.

No algoritmo, o arquivo deve ser declarado e aberto antes que o acesso possa ser feito. Nofinal do algoritmo, ou quando houver necessidade, o arquivo deve ser fechado.

A declarao de um arquivo feita atravs da especificao:arquivo de NOME-DO-REGISTRO: NOME;

Exemplo:tipo reg_aluno = registro

...fim registro;

reg_aluno: ALUNO;

arquivo seqencial de ALUNO: ALUNOS;

A declarao do arquivo a definio, para o algoritmo, do modelo e dos nomes que estaroassociados estrutura de dados. A associao deste modelo ao arquivo fsico feita no algoritmo comum comando de abertura:

abra NOME-DO-ARQUIVO ;onde o tipo de utilizao pode ser para leitura, escrita ou ambos.

Exemplos:abra ALUNOS leitura;abra ALUNOS escrita;abra ALUNOS;

Para se desfazer a associao entre o modelo e o arquivo fsico, usa-se o comando defechamento:

feche NOME-DO-ARQUIVO;

Os formatos para leitura e escrita de um arquivo so dependentes do seu tipo de organizao.

6.1.1. ORGANIZAO SEQENCIAL

A principal caracterstica da organizao seqencial a de que os registros so armazenadoscontiguamente, isto , um aps o outro na ordem em que foram inseridos. A acesso aos registros doarquivo, tanto na leitura quanto na escrita, so feitos seqencialmente, ou seja, a leitura de um registros possvel aps a leitura de todos os registros anteriores e a escrita de um registro s feita aps oltimo registro.


16/24


17/24

16Se a organizao for direta, a disposio dos registros no arquivo no ser

necessariamente a apresentada no arquivo seqencial.

Atravs de funes internas ao computador, cada registro ser alocado em uma posiounivocamente determinada pela chave escolhida, como mostra a tabela abaixo:

{funo que associa chave ao registro}MATRICULA NOME TURMA PERIODO9800002 Maria Arajo A 39800005 Joaquim Silva A 29800012 Carlos Menezes B 39800040 Ftima Andrade C 19900001 Ana Lcia Dias B 19900003 Marcelo Costa C 39900010 Flvio Martins C 29900025 Luiz Carvalho A 2

Para se ter acesso a um registro, basta efetuar-se a leitura no arquivo usando a chave, no

caso o nmero da matrcula, desejada. No h necessidade do algoritmo fazer nenhum tipo depesquisa.

O mecanismo de gerncia do arquivo direto no computador capaz de associar a chave aoregistro procurado. Caso a chave no exista, uma condio de chave invlida (INV) poder ser testada.A escolha da chave feita pelo usurio no momento da criao do arquivo de organizao direta e, emgeral, um dos campos do registro.

Observaes importantes: Cada registro dever ser gravado usando sua chave. No pode haver registros usando a mesma chave ( nica).

As operaes de leitura e escrita num arquivo de organizao direta so indicadas nosalgoritmos pelos seguintes comandos:

leia item [chave] NOME-ARQUIVO.NOME-REGISTRO;eescreva item [chave] NOME-ARQUIVO.NOME-REGISTRO;

O algoritmo desenvolvido anteriormente para encontrar os dados do aluno e imprimir seunome, cuja matrcula seja 9900003, seria:

inciotipo regaluno = registro

caracter: MATRICULAcaracter: NOMEcaracter: TURMAinteiro: PERIODO

fim registro;regaluno: DADOS;arquivo direto de DADOS chave MATRICULA: ALUNOS;abra ALUNOS leitura;leia item [9900003]ALUNOS.DADOS;se ALUNOS.INV {erro se a chave no for encontrada}

entoimprima (Aluno no existe);

senoimprima (DADOS.NOME);

fim se;feche ALUNOS;

fim.


18/24

17Exerccios:1. Escreva um algoritmo que abra um arquivo VENDAS contendo os seguintes campos: cdigo da pea,quantidade vendida, valor unitrio, cliente e data. E crie dois outros arquivos da seguinte forma:

Contendo os nomes dos clientes que compraram mais de R$500,00 (valor total da compra).

Contendo os cdigos das peas que venderam mais de 100 unidades para um cliente, no msde junho de 2002.2. No mesmo arquivo da questo anterior, faa a busca de uma determinada pea por seu cdigo.Implemente com os dois tipos de organizao de arquivos e discuta os problemas relacionados a estasdiferentes solues.

7. MODULARIZAO

No fim da dcada de 60, alguns problemas no desenvolvimento de sistemas de programaolevaram os pases desenvolvidos a um evento chamado crise de software. Os custos das atividades deprogramao mostravam a cada ano uma clara tendncia a se elevarem muito em relao aos custosdos equipamentos, e isto era devido ao avano tecnolgico na fabricao dos equipamentos de

computao e a lenta evoluo de tcnicas aplicadas ao desenvolvimento de software.A ausncia de uma metodologia para a construo de programas conduzia a programas

geralmente cheios de erros e com altos custos de desenvolvimento que, conseqentemente, exigiamcustos elevados para a sua correo e manuteno futuras. A programao estruturada foi o resultadode uma srie de estudos e propostas de metodologias para desenvolvimento de software. Uma dastcnicas aplicadas na programao estruturada, a modularizao de programas uma ferramenta paraa elaborao de programas visando, os aspectos de confiabilidade, legibilidade, manutenibilidade eflexibilidade, dentre outros.

A modularizao um processo que aborda os aspectos da decomposio de algoritmos emmdulos. Mdulo um grupo de comandos, constituindo um trecho do algoritmo, com uma funo bemdefinida e o mais independente possvel em relao ao resto do algoritmo.

Exemplo Seja um algoritmo para calcular o salrio lquido de um empregado, com as seguintes

etapas:incio

Leia os dados do empregadoDetermine o salrioEscreva o salrio

fim.

Onde Determine o salrio pode ser refinado como:Calcule as vantagensCalcule as deduesSALARIOLIQ VANTAGENS DEDUES

No refinamento anterior no houve preocupao de como o processo de clculo dasvantagens e dedues seria efetuado. Essas aes constituem funes bem definidas e que seroexecutadas por mdulos especficos, neste caso, o algoritmo anterior ficaria:

incioLeia os dados do empregadoAtive o mdulo Clculo das vantagensAtive o mdulo Clculo das deduesSALARIOLIQ VANTAGENS DEDUESEscreva o salrio

fim.

Exemplo da descrio estrutural da modularizao:

Mdulo Principal

Mdulo Vantagens Mdulo Dedues


19/24

18

A maneira mais intuitiva de proceder a modularizao de problemas feita definindo ummdulo principal de controle e mdulos especficos para as funes do algoritmo. Recomenda-se que osmdulos de um programa tenham um tamanho limitado, pois mdulos muito grandes so difceis de sercompreendidos e, em geral, so multifuncionais.

As linguagens de programao dispem de recursos que facilitam a construo e manipulaode mdulos, permitindo no s a modularizao dos comandos do programa, como tambm dos dadosutilizados.

Cada mdulo pode definir as prprias estruturas de dados, suficientes e necessrias apenaspara atingir o objetivo final do mdulo. Todo mdulo constitudo por uma seqncia de comandos queoperam sobre um conjunto de objetos, que podem ser globais ou locais.

Objetos globais so entidades que podem ser usadas em mdulos internos a outro mdulodo algoritmo onde foram declaradas.

Objetos locais so entidades que s podem ser usadas no mdulo do algoritmo onde foramdeclaradas. Estes objetos no possuem nenhum significado fora deste mdulo.

So exemplos de objetos globais ou locais: variveis, arquivos, outros mdulos, etc.A comunicao entre mdulos dever ser feita atravs de vnculos, utilizando-se objetos

globais ou transferncia de parmetros.

7.1. BENEFCIOS DA MODULARIZAO

A independncia do mdulo permite uma manuteno mais simples e evita efeitos colateraisno restante do algoritmo;

A elaborao do mdulo pode ser feita independentemente e em poca diferente dorestante do algoritmo;

Testes e correes dos mdulos podem ser feitos separados; Um mdulo pode ser utilizado em outros algoritmos que requeiram o mesmo processamento

por ele executado.

7.2. FERRAMENTAS PARA MODULARIZAO

Sub-rotinas e funes so mdulos que servem aos objetivos: Evitar que em certa seqncia de comandos necessria em vrios locais de um algoritmo

tenha que ser escrita repetidamente nesses locais; Dividir e estruturar um algoritmo em partes fechadas e logicamente coerentes; Aumentar a legibilidade de um algoritmo.

Sub-rotinas e funes so mdulos hierarquicamente subordinados a um algoritmo,comumente chamado de mdulo principal. Da mesma forma uma sub-rotina ou uma funo pode conteroutras sub-rotinas e funes aninhadas.

A sub-rotina e a funo so criadas atravs das suas declaraes em um algoritmo e paraserem executadas, necessitam de ativao por um comando de chamada. A declarao de uma sub-rotina ou funo constituda de um cabealho, que a identifica e contm seu nome e uma lista deparmetros formais, e de um corpo que contm declaraes locais e os comandos.

Criao de sub-rotinasubrotina NOME (lista-de-parmetros-formais)

declaraes dos objetos locais a sub-rotinacomandos da sub-rotina

fim subrotina;

Chamada da sub-rotinaNOME (lista-de-parmetros-atuais);

As funes tm a caracterstica de retornar ao algoritmo que as chamou um valor associadoao nome da funo.


20/24

19

Criao de funofuno tipo NOME (lista-de-parmetros-formais)

declaraes dos objetos locais a funocomandos da funo

fim funo;Chamada da funo

NOME (lista-de-parmetros-atuais);

Como esta funo ir retornar um valor, este pode ser atribudo a alguma varivel, contantoque esta seja de tipo compatvel.

A NOME (lista-de-parmetros-atuais);

Ao terminar a execuo dos comandos de uma sub-rotina ou funo, o fluxo de controleretorna ao comando seguinte quele que provocou a chamada.

7.3. MODOS DE TRANSFERNCIA DE PARMETROS

Os parmetros de uma sub-rotina ou funo classificam-se em:de entrada so aqueles que tm seus valores estabelecidos fora da sub-rotina ou funo e nopodem ser modificados dentro dela.de sada so aqueles que tm seus valores estabelecidos dentro da sub-rotina ou funo.de entrada-sada so aqueles que tm seus valores estabelecidos fora da sub-rotina ou funo, maspodem ter seus valores alterados dentro dela.

A vinculao entre mdulos pode ser feita atravs da transferncia ou passagem deparmetros, que associam parmetros atuais com parmetros formais. Dentre os modos detransferncia de parmetros, pode-se destacar: a passagem por valor, a passagem por resultado e apassagem por referncia.

Na passagem de parmetros por valor, as alteraes feitas nos parmetros formais, dentro da

sub-rotina ou funo, no se refletem nos parmetros atuais. O valor do parmetro atual copiado noparmetro formal, na chamada da sub-rotina ou funo. Assim, quando a passagem por valor significaque o parmetro de entrada.

Na passagem de parmetros por resultado, as alteraes feitas nos parmetros formais, nasub-rotina ou funo, refletem-se nos parmetros atuais. O valor do parmetro formal copiado noparmetro atual, ao retornar da sub-rotina ou funo. Assim, quando a passagem por resultadosignifica que o parmetro de sada.

Na passagem de parmetros por referncia, a toda alterao feita num parmetro formalcorresponde a mesma alterao feita no seu parmetro atual associado. Neste caso, quando apassagem por valor significa que o parmetro de entrada-sada.

8. RECURSIVIDADE

Um objeto dito recursivo se ele consistir parcialmente ou for definido em termos de siprprio.


21/24

20

Uma funo recursiva quando no corpo dessa funo existe uma chamada a si prpria,podendo utilizar os mesmos parmetros de entrada (correndo riscos de provocar um ciclo infinito) ououtros.

8.1. EXEMPLO DE PROBLEMA RECURSIVOImagine que temos um monte de pregos e queremos saber quantos so. Se pegarmos num

prego, sabemos que temos um prego, mas no sabemos quantos ainda existem no monte restante...efetuamos a mesma operao (recursividade) e somamos o prego ao que j temos.

Fazemos o mesmo at no existir mais pregos para contar, isto , pegamos num e somamosaos que temos, repetimos a mesma operao perguntando sempre entre as operaes, "ainda h maispregos para contar?", caso haja, repetimos, caso contrrio paramos.

A recursividade uma ferramenta muita poderosa quando bem implementada, seno podeser muita perigosa. preciso ter cuidado com as condies de parada, se faltar alguma condio deparada ou alguma condio de parada est errada pode acontecer um ciclo infinito.

8.2. RECURSO ITERAO

Paradigma iterativo: uma seqncia de instrues executada de uma forma repetitiva,controlada por uma dada condio (ciclo iterativo).

Paradigma recursivo: existncia de casos simples, em que a resposta determinada diretamente; ser possvel uma decomposio recursiva de uma instncia do problema, em instncias

mais simples da mesma forma.

Numa funo recursiva, so criadas vrias ativaesdela prpria que desaparecem medidaque a execuo avana. Em cada momento apenas uma das ativaes est ativa, estando as restantes espera que essa termine para continuarem.

Os dois paradigmas so equivalentes: dada uma funo recursiva existe sempre uma iterativa

e vice-versa.

8.3. EXEMPLOS MAIS FAMOSOS DE PROBLEMAS RECURSIVOS

Fatorial: Clculo de n! = nx (n- 1) x...x 1

Seqncia de Fibonacci: 0 1 1 2 3 5 8 13 21 34 55 89 144

Exemplo de problema: Considerar uma populao de coelhos que se reproduz segundo as seguintesregras:Cada par de coelhos produz um novo par por msOs coelhos so frteis a partir do segundo ms

Os coelhos no morremSupondo que nasce um par de coelhos em Janeiro, quantos pares de coelhos existem no fim do ano?Algoritmo Determinar o nmero de pares em cada ms:0 1 2 3 4 5 6 7 8 9 10 11 120 1 1 2 3 5 8 13 21 34 55 89 144Generalizando, ao fim de n> 1 etapas temos: fn = fn - 1+fn - 2 e f0=0 e f1=1.


22/24


23/24

22

10. LISTAS LINEARES

Uma lista linear uma estrutura dinmica caracterizada por uma seqncia ordenada deelementos, no sentido da sua posio relativa: E1, E2, ..., En, onde:

Existem nelementos na seqncia; E1 o primeiro elemento da seqncia; En o ltimo elemento da seqncia; Para todo i,jentre 1 e n, se i


24/24

23

Devido s caractersticas das operaes da pilha, o primeiro elemento a ser inserido ser oltimo a ser retirado e o ltimo a ser inserido ser o primeiro a ser retirado. Estruturas deste tipo so

chamadas de LIFO (Last In, First Out).10.2. IMPLEMENTAO DE LISTAS LINEARES

Alternativas: Contigidade fsica (com o uso de vetores) Encadeada (com o uso de apontadores)

Contigidade

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

R O T P X

incio fim

Pilha:6

topo 5 X4 P3 T2 O1 R

Encadeamento Simples

Exerccios:

1) Considere um conjunto de informaes relativas a alunos, constitudo de nome, nmero de matrculae data de nascimento. Organize estas informaes em uma lista encadeada, ordenada pelo nome doaluno. Escreva funes que efetuem as seguintes aes:

imprimir os nomes e nmeros de matrcula dos alunos que nasceram aps uma determinadadata (passada como parmetro);

procurar as informaes relativas a um determinado aluno, cujo nmero de matrcula passadocomo parmetro; incluir um novo aluno na lista, respeitando a ordenao.

2) Construa um procedimento que recebe uma lista encadeada (endereo inicial no apontador Lista) emonta uma nova lista a partir dos dados desta, com os elementos em ordem inversa. Somente a listafinal deve estar alocada ao final da execuo do procedimento.

3) Escreva um procedimento que recebe duas filas, que contm valores numricos ordenados. Oprocedimento dever formar uma terceira fila, tambm ordenada, na qual estaro os valoresarmazenados nas filas originais. Considere duas possibilidades: as filas implementadas sobre arranjos,e as filas implementadas atravs de apontadores.

PR O T X

Documents

apostila_AED Algoritmos e Estruturas de Dados