apostila

. . . . . . . . . . . . . . . . . . . . . 163
10.2 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.2.1 Matrizes em Pascal . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.2.2 Exemplos elementares . . . . . . . . . . . . . . . . . . . . . . . 180
10.2.3 Procurando elementos em matrizes . . . . . . . . . . . . . . . . 186
10.2.4 Inserindo uma coluna em uma matriz . . . . . . . . . . . . . . . 188
10.2.5 Aplicac¸o\u2dces de matrizes em imagens . . . . . . . . . . . . . . . . 190
10.2.6 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
10.3 Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10.3.1 Introduc¸a\u2dco aos registros . . . . . . . . . . . . . . . . . . . . . . 209
10.3.2 Vetores de registros . . . . . . . . . . . . . . . . . . . . . . . . . 210
10.3.3 Registros com vetores . . . . . . . . . . . . . . . . . . . . . . . . 212
10.3.4 Observac¸o\u2dces importantes . . . . . . . . . . . . . . . . . . . . . . 213
10.3.5 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
11 Desenvolvendo programas de maior porte 225
11.0.1 Campo minado . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
11.1 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12 Tipos abstratos de dados 241
12.1 Tipo Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
12.2 Tipo Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
12.2.1 Exerc´\u131cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
6 SUMA´RIO
Cap´\u131tulo 1
Introduc¸a\u2dco
Este material conte´m notas de aulas da disciplina CI055 \u2013 Algoritmos e Estruturas de
Dados I, ministrada para os curso de Bacharelado em Cie\u2c6ncia da Computac¸a\u2dco (BCC),
Matema´tica Industrial (MatInd) e para o Bacharelado em Informa´tica Biome´dica
(BIB) da Universidade Federal do Parana´.
Esta disciplina e´ ministrada no primeiro semestre (para os calouros) e e´ a primeira
das quatro que cobrem o conteu´do ba´sico de algoritmos sem o qual um curso de
computac¸a\u2dco na\u2dco faz sentido. As disciplinas subsequentes sa\u2dco:
\u2022 Algoritmos e Estruturas de Dados II;
\u2022 Algoritmos e Estruturas de Dados III; e
\u2022 Algoritmos e Teoria dos Grafos.
A orientac¸a\u2dco da Coordenac¸a\u2dco dos cursos e´ que este deve ter um conteu´do forte
em conceitos de algoritmos no qual a implementac¸a\u2dco final em uma linguagem de pro-
gramac¸a\u2dco e´ vista apenas como um mecanismo facilitador ao aprendizado dos conceitos
teo´ricos.
O texto esta´ dividido em duas partes bem definidas, a primeira entre os cap´\u131tulos 2
e 9, conte´m os princ´\u131pios ba´sicos da construc¸a\u2dco de algoritmos elementares, incluindo
a parte de subprogramas, com especial atenc¸a\u2dco a questo\u2dces tais como passagem de
para\u2c6metros e varia´veis locais e globais. A noc¸a\u2dco de modularidade e´ bastante explorada.
A segunda parte, a partir do cap´\u131tulo 10, conte´m princ´\u131pios de estruturas de dados
ba´sicas, onde se introduz a noc¸a\u2dco de vetores unidimensionais, a primeira das estruturas
de dados. Nesta estrutura, praticamos a elaborac¸a\u2dco de algoritmos modulares e ja´ na\u2dco
escrevemos um co´digo inteiro, mas sim um conjunto de func¸o\u2dces e procedimentos que,
em uma abordagem por refinamentos sucessivos (top down), sa\u2dco constru´\u131dos passo a
passo.
Alguns algoritmos importantes sa\u2dco estudados em suas verso\u2dces ba´sicas: busca e
ordenac¸a\u2dco de vetores. Noc¸o\u2dces de complexidade de algoritmos sa\u2dco mencionadas, ainda
que de modo informal, pois isto e´ conteu´do de per´\u131odos mais avanc¸ados. Contudo, e´
importante ao aprendiz ter noc¸a\u2dco clara da diferenc¸a de custo entre diferentes algorit-
mos.
7
8 CAPI´TULO 1. INTRODUC¸A\u2dcO
As u´ltimas estruturas de dados relevantes para o primeiro per´\u131odo sa\u2dco as matrizes
e o conceito de registro. Havendo tempo, tambe´m se discute estruturas um pouco
mais sofisticadas, misturando-se vetores, registros e matrizes.
Finalmente se oferece um desafio aos alunos. O objetivo e´ o de mostrar uma
aplicac¸a\u2dco interessante dos conceitos que eles ja´ dominam. Normalmente trabalha-se
em sala de aula o desenvolvimento de um programa que tem sido a construc¸a\u2dco de um
jogo simples que pode ser implementado em uma estrutura de matriz, eventualmente
com registros. A ideia e´ que eles possam fazer um programa mais extenso para
treinarem a construc¸a\u2dco de programas modulares. Este material constitui o u´ltimo
cap´\u131tulo deste material.
O estudante na\u2dco deve iniciar uma parte sem antes ter compreendido o conteu´do
das anteriores. Tambe´m na\u2dco deve iniciar um novo cap´\u131tulo sem ter compreendido os
anteriores.
Sobre a linguagem, o estudante e´ encorajado a buscar apoio na literatura e nos
guias de refere\u2c6ncia dispon´\u131veis para o compilador escolhido (Free Pascal), incluindo
um guia de refere\u2c6ncia ba´sico que foi escrito pelos monitores da disciplina no ano de
2009.
A leitura destas notas de aula na\u2dco isenta o estudante de buscar literatura comple-
mentar, sempre bem-vinda. Em particular, uma o´tima histo´ria da computac¸a\u2dco pode
ser encontrada em [Tre83]. Alguns excelentes textos introduto´rios em algoritmos esta\u2dco
em [Car82], [Sal98], [Med05] e [Wir78]. Para mais detalhes de programac¸a\u2dco em Pascal
o leitor pode consultar [Far99] e tambe´m os guias de refere\u2c6ncia da linguagem [Gui].
Finalmente, embora talvez de dif´\u131cil compreensa\u2dco para um iniciante, recomendamos
pelo menos folhear o material em [Knu68].
Cap´\u131tulo 2
Sobre problemas e soluc¸o\u2dces
Vamos iniciar nosso estudo com uma breve discussa\u2dco sobre problemas e soluc¸o\u2dces. O
objetivo e´ deixar claro desde o in´\u131cio que:
\u2022 na\u2dco existe, em geral, uma u´nica soluc¸a\u2dco para o mesmo problema;
\u2022 algumas soluc¸o\u2dces sa\u2dco melhores do que outras, sob algum crite´rio;
\u2022 alguns problemas sa\u2dco casos particulares de outros similares;
\u2022 as vezes, e´ melhor resolver o problema mais gene´rico, assim, resolve-se uma
classe de problemas, e na\u2dco apenas um.
Sera\u2dco apresentados dois problemas reais e para cada um deles segue uma discussa\u2dco
sobre a existe\u2c6ncia de diversas soluc¸o\u2dces para um dado problema. A e\u2c6nfase sera´ dada
nas diferenc¸as entre as soluc¸o\u2dces e tambe´m na discussa\u2dco sobre ate´ que ponto deve-se
ficar satisfeito com a primeira soluc¸a\u2dco obtida ou se ela pode ser generalizada para
problemas similares.
2.1 Contando o nu´mero de presentes em um evento
No primeiro dia letivo do primeiro semestre de 2009, um dos autores deste material
colocou o seguinte problema aos novos alunos: quer´\u131amos saber quantos estudantes
estavam presentes na sala de aula naquele momento. A sala tinha capacidade aproxi-
mada de 100 lugares e a naquele momento estava razoavelmente cheia.
Os estudantes discutiram va´rias possibilidades. Apresentamos todas elas a seguir.
Primeira soluc¸a\u2dco
A primeira soluc¸a\u2dco parecia ta\u2dco o´bvia que levou algum tempo ate´ algum aluno verbali-
zar: o professor conta os alunos um por um, tomando o cuidado de na\u2dco contar algue´m
duas vezes e tambe´m de na\u2dco esquecer de contar algue´m.
Quais sa\u2dco as vantagens deste me´todo? Trata-se de uma soluc¸a\u2dco simples, fa´cil de
executar e produz o resultado correto. E´ uma soluc¸a\u2dco perfeita para salas de aula com
9
10 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O\u2dcES
poucos alunos, digamos, 20 ou 30. Outro aspecto considerado foi o fato de que este
me´todo na\u2dco exige nenhum conhecimento pre´vio de quem vai executar a operac¸a\u2dco, a
na\u2dco ser saber contar. Tambe´m na\u2dco exige nenhum equipamento adicional.
Quais as desvantagens? Se o nu´mero de alunos na sala for grande, o tempo ne-
cessa´rio para o te´rmino da operac¸a\u2dco pode ser insatisfato´rio. Para piorar, quanto
maior o nu´mero, maior a chance de aparecerem erros na contagem. Foi discutida a
adequac¸a\u2dco desta soluc¸a\u2dco para se contar os presentes em um com\u131´cio ou manifestac¸a\u2dco
popular numa prac¸a pu´blica. Concluiu-se pela