Aula 01 - Estruturas de Dados - Funções - Exemplos

Prévia do material em texto

Aula 01 
Objetivo: 
O aluno deverá ser capaz de : 
 
1. Conceituar estrutura de dados; 
2. Compreender o objetivo do estudo de estrutura de dados 
3. Identificar estruturas de dados lineares e não lineares 
4. Identificar, através de exemplos do cotidiano, a estrutura de dados 
mais adequada para determinado problema; 
5. Conceituar lista linear 
6. Compreender as possíveis formas de armazenamento de dados de uma 
lista linear 
7. Compreender o uso de funções definidas pelo programador 
8. Implementar funções simples com e sem retorno, com e sem 
passagem de parâmetros 
9. Compreender a diferença entre parâmetros passados por valor e 
parâmetros passados por referência 
10. Compreender escopo de variáveis (global e local) 
 
Estrutura do Conteúdo: 
1. Motivação para o estudo de Estrutura de Dados (objetivo de 
Estrutura de Dados) 
2. Definição de estrutura de dados 
3. Estruturas de dados lineares e não lineares : estudo informal 
através de exemplos, analisando o uso de pilha, fila, lista, árvore e 
grafo em problemas do cotidiano. 
4. Definição de Listas Lineares e identificação dos tipos quanto às 
formas de armazenamento (sequencial e encadeada) 
5. Funções : 
· motivação, 
· definição, 
· funções pré-definidas e definidas pelo programador, 
· passagem de parâmetros (por valor e por referência), 
· retorno de função 
· escopo de variáveis (local e global)através de exemplos 
simples, sem usar vetor. 
 
 
Suporte conceitual : 
 
1- “As estruturas de dados estudam as relações lógicas existentes entre 
os dados (ex: relação linear, relação hierárquica ..) e serão manipuladas 
através de operações sobre os dados (ex: consultar uma informação em um 
conjunto de fichas de alunos, remover um assinante de uma lista de 
assinantes, apagar um diretório em uma árvore de diretórios e 
subdiretórios...). A escolha da estrutura de dados a ser utilizada 
refletirá diretamente na construção de uma solução mais ou menos eficiente 
para o problema.” 
 
2- Definição de lista linear : Uma lista linear (ou tabela) pode ser definida 
como uma sequência de n >= 0 elementos, denominados nós, L0, L1, ...., L N-1, 
tais que as propriedades estruturais decorrem, inicialmente, das posições 
relativas dos elementos da lista. 
Temos : Se n >= 0 : 
 L0 é o primeiro elemento 
 Ln-1 é o último elemento 
· L i+1 é o sucessor de L i e 
 L i é o antecessor de L i+1 . “ 
Características de uma lista linear: 
• possui 0 ou mais nós; 
• todos os elementos podem ser acessados 
• podemos incluir ou excluir qualquer elemento 
• agrupa informações referentes a um conjunto de elementos que 
relacionam-se entre si . 
 
3 - Uma função é um bloco de instruções que é executado quando é chamada 
de algum outro ponto do programa. Seu formato geral na definição é : 
tipo nome ( tipo1 parâmetro1, tipo2 parâmetro2, ..., tiponparâmetroN) 
{ corpo da função } 
no qual: 
 · tipo é o tipo de dados que a função retorna. 
 · nome é o nome pelo qual será possível chamar a função. 
 · parâmetros e seus tipos. Cada parâmetro é precedido por um tipo de 
dados, como na declaração de uma variável (por exemplo, int x) e funciona 
dentro da função como qualquer outra variável. Eles permitem a passagem 
de dados para a função quando é ela chamada. Os parâmetros são separados 
por vírgulas e podem ser passados por valor ou por referência. 
Objetivo : Listas lineares: definição e identificação dos tipos quanto 
às formas de armazenamento (sequencial e encadeada). 
 
 - Sugestão de exposição dialogada com perguntas, que também 
poderá ser encontrada no resumo acessado pelos alunos : 
 
 “O objetivo do curso é o estudo de listas lineares (lista, pilha e 
fila). Tais estruturas manipulam dados do mesmo tipo e existe uma 
linearidade, pois pode-se determinar o primeiro elemento da lista, seu 
último elemento, e uma vez determinado um elemento qualquer, que não seja 
o 1º. e nem o último, ele possui um antecessor e um sucessor. É fácil ver 
que, o 1º. elemento só tem sucessor, ao passo que o último elemento só 
possui antecessor. Note ainda que, a lista pode ser vazia ou ter um ou mais 
elementos. Por exemplo, uma pilha com 1 livro, uma fila vazia de clientes, 
uma lista de livros ... 
 
 Formalmente, os elementos de uma lista linear são denominados nós 
ou nodos. 
 
 Como representar na memória do computador os dados organizados 
de forma linear ? Note que é importante determinar uma representação 
física que respeite as representações lógicas e permita operações através 
de procedimentos simples e eficientes. 
 
 Existem 2 formas para representar fisicamente uma lista linear: 
 
· sequencial (contígua) ou 
· encadeada. 
 
 Ou seja, ou os dados estão dispostos de forma sequencial na memória, 
um após o outro, em endereços sequenciais ou contíguos, ou então, estão 
dispostos de forma encadeada na memória, não seguindo uma ordem 
sequencial, mas sim um armazenamento aleatório. No caso de uma lista 
sequencial devemos pré-determinar até onde, no máximo, a lista crescerá. 
Já em uma lista encadeada não é necessário tal tipo de determinação, ou 
seja, a lista vai crescendo desde que haja memória disponível, sem que os 
dados tenham que ser armazenados de forma contígua. 
 
 Portanto, as listas lineares são classificadas em listas lineares 
sequenciais e listas lineares encadeadas. 
 
 Por hora, estudaremos as listas sequencias. Mais tarde, falaremos 
mais de listas encadeadas.“ 
 
Que recurso devemos usar para implementar as listas sequencias já que os 
dados são todos do mesmo tipo, estão alocados de forma contígua na 
memória e há um tamanho máximo pré-definido ? Resposta : vetor 
 
Que manipulações poderão ser feitas com os dados das listas sequencias ? 
Ou seja, que operações iremos estudar ? 
 
 “ Imagine uma lista com as notas dos alunos de uma turma. Como posso 
manipular as notas ? 
Primeiramente, não há notas, ou seja, a lista está vazia. Depois, podemos 
adicionar uma nota, e outra, etc. (adicionar = operação de inserção). 
Podemos remover alguma nota (operação de remoção), podemos substituir 
uma nota (operação de substituição), ou querer procurar por uma certa nota 
(operação de busca ou pesquisa), ou querer listar todas as notas 
armazenadas (operação de percurso), etc ... Todas as operações indicam 
como os dados vão ser manipulados e serão implementadas respeitando as 
representações lógica e física. 
 
 Cada operação vai ser implementada como um módulo de código que vai 
desempenhar uma tarefa bem específica e que pode ser reaproveitado 
várias vezes. Veremos como em breve ! 
 
Como seria procurar uma nota em um conjunto de notas ? Como seria 
procurar os nomes de alunos em um conjunto todo embaralhado de nomes ? 
 
Resposta : Procurar notas ou nomes em um conjunto embaralhado segue a 
mesma sequência de passos básicos ! 
 
 
 “ Cada operação (procurar, inserir, remover, etc...) vai se implementada 
por um módulo de código, uma caixinha cheia de instruções que é 
denominada função. Esse módulo pode ser chamado a qualquer momento que 
se deseje que o conjunto de instruções nele programado seja executado. 
 
 Mas como se escreve uma função ? Como se ativa o módulo de 
instruções, seja para trabalhar com uma lista de notas ou uma lista de 
nomes ou qualquer outra informação? 
 
 Sabemos que existem na linguagem diversas funções pré-definidas, ou 
seja, funções já programadas, que basta serem chamadas, receberem o 
dado certo e pronto. Algumas dessas funções são : sqrt (calcula a raiz 
quadrada), pow (calcula uma base elevada a um expoente), abs (calcula o 
valorabsoluto ou módulo), etc ... 
 
 Antes de continuarmos o estudo de lista linear sequencial e suas 
operações, veremos um pouco de programação básica : funções. Este 
estudo nos ajudará na implementação das operações de listas lineares 
 
 
 
 - Objetivo : Motivação e definição de funções 
 - Sugestão para motivação: 
 
1) Uso da função abs, que calcula o valor absoluto (ou módulo) 
para inteiros. Note : A função abs está declarada em cstdlib. 
Por exemplo : Seja o trecho onde int x; 
 x = -4; 
 cout<< “Valor absoluto de “ 
 << x <<“ = “ <<abs(x) 
 <<endl; 
 
2) O que você faria se não houvesse uma função já programada 
como a abs e você tivesse que calcular em diversas etapas do 
seu programa o módulo de um número inteiro ? Imagine que 
você não fizesse isso seguidamente, de forma a usar um loop, 
tendo que realmente, repetir código várias vezes em trechos 
distantes do seu programa. 
 
Solução (a pior): Repetir código em toda etapa em que fosse necessário. 
Considerando que num é uma variável inteira e a entrada já foi lida, o trecho 
seria : 
if (num >= 0) 
 cout<< “Valor absoluto = “ << num 
 <<endl; 
else 
 cout<< “Valor absoluto = “ << -num 
 <<endl; 
 
 
 
 Solução (a melhor): Se não existisse uma função abs na linguagem, a 
melhor solução seria que o trecho virasse uma função, pois desta forma, 
seria possível chamá-la toda vez que fosse necessário. É bom observar que, 
funções de uma só linha não compensam o esforço computacional. 
 
 
 Objetivo : Função (definição, passagem de parâmetros, retorno de 
valores e escopo de variáveis). 
 Como fazer ? : 
 - Um programa simples. Para conhecer: o que é função, 
chamada de função, declaração ou protótipo de função, definição de 
função (código da função), funções com e sem retorno, com e sem 
passagem de parâmetros (por valor e por referência, usando 
referência). 
 
Exemplos: 
 
1. Função sem parâmetros e sem retorno. Obs.: Explicação de void 
como tipo de retorno e void na lista de parâmetros(protótipo). Neste 
último caso, void é opcional. 
 
2. Função sem parâmetros e que retorna um valor (inteiro ou real ou 
caracter). Objetivo: um programa simples que realiza algum cálculo, 
para mostrar o uso de variáveis locais e ensine o comando return. 
 É possível se ter return; em funções que não retornam valor 
algum. Em breve, no estudo de operações com listas, o uso de 
return; aparecerá. 
3. Função que recebe um ou mais parâmetros passados por valor, faz 
cálculos e retorna um valor. Objetivo: ressaltar que os parâmetros 
passados por valor funcionam como variáveis locais e que são cópias 
dos argumentos da chamada. 
 
4. Função que recebe parâmetros passados por valor, os usa e não 
retorna nada. 
 
5. Função que recebe parâmetros passados por valor, modifica algum 
deles (ou todos) e não retorna valor algum. 
Objetivo: alertar para o fato que os argumentos da chamada não 
serão realmente modificados. 
 
6. Função que recebe parâmetro passado por referência, modifica e 
nada retorna. Atenção para o uso de &. 
 
 
 Variável global e o seu uso. Objetivo: comparar as variáveis globais 
com as locais. Alerta: usar variáveis globais não é uma boa prática de 
programação. 
Exercícios de fixação no final das aulas : 
 
 
1) Assinale a estrutura de dados que pode ser usada para representar 
cada um dos casos descritos a seguir. Justifique, resumidamente, 
sua resposta. 
 
a) Na maioria dos sistemas operacionais, os arquivos são 
organizados hierarquicamente em um esquema de diretórios 
(pastas) e sub-diretórios. 
Opções : A) ( ) pilha B) ( ) fila 
 C) ( ) árvore d) ( ) grafo 
 
b) Navegadores para internet armazenam os últimos endereços 
visitados em uma estrutura de dados. Cada vez que um novo site é 
visitado, o endereço do site é adicionado na estrutura de 
endereços. Quando se aciona o retorno (“back”), o navegador 
permite que o usuário retorne no último site visitado e retira o 
endereço do site da estrutura de dados. 
 Opções : A) ( ) pilha B) ( ) fila 
 C) ( ) árvore d) ( ) lista 
 
2) Faça um programa em C++ para ler a largura e o comprimento de 
um retângulo, calcular e imprimir o valor da área. O cálculo da área 
deverá ser feito por uma função que receberá a largura e o 
comprimento como parâmetros e retornará o valor calculado da 
área. 
Protótipo da função : 
double calcularAreaVersao1(double, double); 
 
3) Considere o exercício 2 acima e escreva uma função diferente 
para o cálculo da área de acordo com o seguinte protótipo : void 
calcularAreaVersao2(double, double, &double); 
A função receberá a largura e o comprimento passados por valor e 
receberá um parâmetro area passado por referência, cujo objetivo 
é armazenar o resultado do cálculo da área.