View
217
Download
0
Category
Preview:
Citation preview
Prof. Leticia Winkler 1
Estrutura de Dados
Aula 1
Funções
prof Leticia Winkler
leticia@estacio.br
1. Definição de estrutura de dados, com a identificação de estruturas lineares
e não lineares.
2. Criação de funções, passagem de parâmetros (por valor e por referência)
e escopo de variáveis (local e global).
3. Listas lineares: definição e tipos com relação às formas de
armazenamento.
4. Listas lineares sequenciais (lista, pilha e fila) e suas operações básicas.
5. Ordenação e pesquisa em listas lineares seqüenciais.
6. Agregado de dados heterogêneos: structs.
7. Ponteiros e alocação dinâmica de memória.
8. Listas lineares encadeadas (lista, pilha e fila) e suas operações básicas. Prof. Leticia Winkler 2
Ementa
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian Estruturas de dados e seus algoritmos
3ª. ed. – Rio de Janeiro – LTC – 2010
Koffman, Elliot B. ; Wolfgang, Paul A.T. Objetos, Abstração, Estrutura de dados e Projeto usando C++
1ª. ed. – Rio de Janeiro – LTC – 2008
EDELWEISS,N.; GALANTE,R.M. Estrutura de Dados
Volume 18 – Série Livros Didáticos Informática UFRGS
1ª. ed. – RS – Bookman – 2009
Prof. Leticia Winkler 3
Bibliografia Básica
Unidade 1. Introdução 1.1. Definição e objetivo de estrutura de dados
1.2. Estruturas de dados lineares e não lineares (exemplos
de lista, pilha, fila, árvore e grafo)
1.3. Listas lineares
Prof. Leticia Winkler 4
Conteúdo
Unidade 2. Funções 2.1. Motivação
2.2. Definição
2.3. Passagem de parâmetros (por valor e por referência)
2.4. Escopo de variáveis (local e global)
2.5. Retorno de valores
Prof. Leticia Winkler 5
Conteúdo
Unidade 3. Listas Lineares Sequenciais 3.1. Definição e representação
3.2. Operações básicas com listas seqüenciais
3.3. Aplicações com listas sequenciais
3.4. Pilha
3.5. Fila
3.6. Ordenação (BubbleSort, Inserção, Seleção)
3.7. Pesquisa
3.8. Agregado Heterogêneo
Prof. Leticia Winkler 6
Conteúdo
Unidade 4. Ponteiros e Alocação Dinâmica
4.1. Definição de ponteiro
4.2. Operador de endereço, operador de indireção e
operador seta
4.3. Alocação e desalocação de memória
Prof. Leticia Winkler 7
Conteúdo
Unidade 5. Listas Lineares Encadeadas
5.1. Motivação
5.2. Listas Simplesmente Encadeadas
5.3. Pilha
5.4. Fila
5.5. Listas Circulares Simplesmente Encadeadas
5.6. Listas Duplamente Encadeadas
Prof. Leticia Winkler 8
Conteúdo
Composta de três etapas:
Avaliação 1 (AV1)
Avaliação 2 (AV2)
Avaliação 3 (AV3).
A AV1 contemplará o conteúdo da disciplina até a sua realização, incluindo o conteúdo das atividades estruturadas.
A AV2 e a AV3 abrangerão todo o conteúdo da disciplina, incluindo o conteúdo das atividades estruturadas.
Prof. Leticia Winkler 9
Avaliação
Para aprovação na disciplina o aluno deverá: 1. Atingir resultado igual ou superior a 6,0, calculado a partir da
média aritmética entre os graus das avaliações, sendo
consideradas apenas as duas maiores notas obtidas dentre as
três etapas de avaliação (AV1, AV2 e AV3). A média aritmética
obtida será o grau final do aluno na disciplina.
2. Obter grau igual ou superior a 4,0 em, pelo menos, duas das
três avaliações.
3. Frequentar, no mínimo, 75% das aulas ministradas.
Prof. Leticia Winkler 10
Aprovação
Função
Prof. Leticia Winkler 11
Fazer um programa que leia um número inteiro e informe se o número é par ou não é par
Exercício
#include <iostream>
using namespace std;
int main () {
int num;
cout << ”Numero? ”;
cin >> num;
if (num % 2 == 0)
cout << num << ” - PAR\n”;
else
cout << num << ” - IMPAR\n”;
return 0;
}
Resposta Possível
E se fossem dois números?
#include <iostream>
using namespace std;
int main () {
int num1, num2;
cout << ”Primeiro numero? ”;
cin >> num1;
cout << ”Segundo numero? ”;
cin >> num2;
if (num1 % 2 == 0)
cout << num1 << ”: PAR\n”;
else
cout << num1 << ”: IMPAR\n”;
if (num2 % 2 == 0)
cout << num2 << ”: PAR\n”;
else
cout << num2 << ”: IMPAR\n”;
return 0;
}
Solução:
USAR FUNÇÃO
E se fossem três, dez, etc...?
É uma estrutura que permite ao programador separar
seus programas em blocos.
A idéia é dividir programas grandes e complexos em um
programa formado de pequenos blocos (que são as
funções)
menor complexidade
maior facilidade de manutenção.
Prof. Leticia Winkler 16
Função
Prof. Leticia Winkler 17
Forma Geral de uma Função
Forma Geral em C/C++:
tipo_de_retorno nome_da_função (declaração_de_parâmetros)
{
corpo_da_função
}
tipo_de_retorno é o tipo de dados que a função retorna.
nome_da_função é o nome pelo qual será possível chamar a função,
para que a mesma seja executada.
declaração_de_parâmetros - permite a passagem de dados para a
função quando é ela chamada.
Exemplo #1
#include <iostream>
using namespace std;
int main () {
int num;
cout << ”Numero? ”;
cin >> num;
if (num % 2 == 0)
cout << num << ”: PAR\n”;
else
cout << num << ”: IMPAR\n”;
return 0;
}
#include <iostream> using namespace std; void parImpar (int n) { if (n % 2 == 0) cout << n << ”: PAR\n”; else cout << n << ”: IMPAR\n”; } int main () { int num; cout << ”Numero? ”; cin >> num; parImpar(num); return 0; }
Com função
Exemplo #2 #include <iostream>
using namespace std;
int main () {
int num1, num2;
cout << ”Primeiro numero? ”;
cin >> num1;
cout << ”Segundo numero? ”;
cin >> num2;
if (num1 % 2 == 0)
cout << num1 << ”: PAR\n”;
else
cout << num1 << ”: IMPAR\n”;
if (num2 % 2 == 0)
cout << num2 << ”: PAR\n”;
else
cout << num2 << ”: IMPAR\n”;
return 0;
}
#include <iostream>
using namespace std;
void parImpar (int n) {
if (n % 2 == 0)
cout << n << ”: PAR\n”;
else
cout << n << ”: IMPAR\n”;
}
int main () {
int num1, num2;
cout << ”Primeiro numero? ”;
cin >> num1;
cout << ”Segundo numero? ”;
cin >> num2;
parImpar(num1);
parImpar(num2);
return 0;
}
Com função
void mensagem () {
cout << ”Alo turma!!!\n”;
}
O void indica que não há valor.
A função mensagem não retorna valor algum para função
chamadora.
Prof. Leticia Winkler 20
Tipo void
O return numa função tipo void irá fazer com que a função
termine sua execução voltando para a função chamadora.
Prof. Leticia Winkler 21
Função que não retorna valor
void divide (float a, float b) {
if (b == 0) {
cout << ”Erro: divisão por zero\n”;
return;
}
cout << ”Resultado: ” << a/b <<
endl;
}
void mensagem () {
cout << ”Alo turma!!!\n”;
}
Prof. Leticia Winkler 22
Função que retorna valor
O return abandona a função devolvendo um valor, resultado da
tarefa realizada pela função.
float somaFloat (float x, float y) {
return (x + y);
}
bool ehPar (int n) {
if (n % 2 == 0)
return true;
else
return false;
}
Uma função que retorna parâmetro pode ser usada dentro de uma expressão:
...
if (ehPar (num))
...
ehPar retorna um valor booleano (verdadeiro o falso)
O if está testando se a resposta (valor retornado) da função é verdadeiro ou falso
Observação
void mensagem () {
cout << ”Alo turma!!!\n”;
}
Realiza sua tarefa sem necessidade de uma informação de entrada
Ou, poderia ser escrito:
void mensagem (void) {
cout << ”Alo turma!!!\n”;
}
Prof. Leticia Winkler 24
Função que não recebe parâmetro
void mensagem (int cod) { switch (cod) { case 1: cout << ”Bom Dia, Turma!!!\n”; break; case 2: cout << ”Boa Tarde, Turma!!!\n”; break; case 3: cout << ”Boa Noite, Turma!!!\n”; break; default: cout << ”Alo turma!!!\n”; }
Necessita de uma informação para realizar sua tarefa (neste exemplo).
Prof. Leticia Winkler 25
Função que recebe parâmetro
Prof. Leticia Winkler 26
Função que recebe mais de um parâmetro
float somaFloat (float x, float y) {
return (x + y);
}
Necessita de duas informações para realizar sua tarefa (no exemplo).
A função chamadora deve informar os valores.
...
somaFloat (7.5, 9)
...
Chamada de uma função – 2 parâmetros
Prof. Leticia Winkler 27
#include <iostream>
using namespace std;
float somaFloat (float x, float y){
return (x + y);
}
int main (){
float num1, num2, num3;
cout << "Primeiro valor? ";
cin >> num1;
cout << "Segundo valor? ";
cin >> num2;
num3 = somaFloat (num1, num2);
cout << ”Resultado: ” << num3 << endl;
return 0;
}
Resultado da Execução:
supondo que foram digitados os
valores 5 e 6 quando solicitado
Primeiro valor? 5
Segundo valor? 6
Resultado: 11
Chamada de uma função – 1 parâmetro
Prof. Leticia Winkler 28
Resultado da Execução:
supondo que foi digitado 5
quando solicitado
Número? 5
5 é ímpar
#include <iostream>
using namespace std;
bool ehPar (int n) {
if (n % 2 == 0)
return true;
else
return false;
}
int main (){
float num;
cout << "Número? ";
cin >> num;
if (ehPar(num))
cout << num << ” é par\n”;
else
cout << num << ” é ímpar\n”;
return 0;
}
Chamada de uma função – sem parâmetro
Prof. Leticia Winkler 29
#include <iostream>
using namespace std;
void mensagem () {
cout << ”Alo turma!!!\n”;
}
int main (){
cout << "Início\n";
mensagem();
cout << ”Fim\n”;
return 0;
}
Resultado da Execução:
Início
Alo turma!!!
Fim
Usando o valor retornado pela função dentro de uma expressão:
#include <iostream> using namespace std; float somaFloat (float x, float y){
return (x + y);
} int main (){
float num1, num2; cout << "Primeiro valor? "; cin >> num1; cout << "Segundo valor? "; cin >> num2; cout << ”Resultado: ” << somaFloat (num1, num2) << endl; return 0;
}
Prof. Leticia Winkler 30
Observação
Exemplos
Prof. Leticia Winkler 31
#include <iostream>
using namespace std;
float somaFloat (float x, float y){
return (x + y);
}
int main (){
float num1, num2;
cout << "Primeiro valor? ";
cin >> num1;
cout << "Segundo valor? ";
cin >> num2;
cout << ”Resultado: ” << somaFloat (num1, num2) << endl;
return 0;
}
#include <iostream> using namespace std; void somaFloat (float x, float y){
cout << ”Resultado: ” << (x + y);
} int main (){
float num1, num2; cout << "Primeiro valor? "; cin >> num1; cout << "Segundo valor? "; cin >> num2; somaFloat (num1, num2); return 0;
}
Escopo de uma Variável Variável Local
Prof. Leticia Winkler 32
#include <iostream> using namespace std; bool ehPar (int n) {
if (n % 2 == 0) return true; else return false;
} int main () {
int num; cout << "Numero? "; cin >> num; if (ehPar(num)) cout << "\nO numero e par.\n"; else cout << "\nO numero e impar.\n"; return 0;
}
A variável num é local a função main;
A variável n está sendo declarada dentro da função ehPar – local a função ehPar
num não é vista dentro da função ehPar;
n não é vista dentro da main;
O valor de num é atribuido a variável n – passagem de parâmetros por valor.
Escopo de uma Variável Variável Global
Prof. Leticia Winkler 33
#include <iostream>
using namespace std;
int x;
void func1() {
cout << ”X – func1: ” << x << endl;
}
void func2() {
cout << ”X – func2: ” << x << endl;
x = 20;
cout << ”X – func2: ” << x << endl;
}
int main () {
x = 10;
cout << ”X – main: ” << x << endl;
func1();
cout << ”X – após a chamada de func1: ” << x << endl;
func2();
cout << ”X – após a chamada de func2: ” << x << endl;
}
X é uma variável global É vista por todas as funções dentro do
programa
Pode ser manipulada e alterada por qualquer função
Resultado da Execução: X – main: 10
X – func1: 10
X – após a chamada de func1: 10
X – func2: 10
X – func2: 20
X – após a chamada de func2: 10
Escopo de uma Variável
Prof. Leticia Winkler 34
Resultado: 1 - main => 10
1 - func => 10
2 - func => 20
2 - main => 10
Na passagem de parâmetros por valor, a variável passada
como parâmetro não pode ser alterada na função chamada #include <iostream>
using namespace std;
void func(int x) {
cout << "1 - func => " << x << endl;
x = 20;
cout << "2 - func => " << x << endl;
}
int main () {
int n = 10;
cout << "1 - main => " << n << endl;
func(n);
cout << "2 - main => " << n << endl;
return 0;
}
É uma forma alternativa de acessar uma variável;
Uma referência é como se fosse um apelido dado a uma variável
Declaração:
tipo var, &refVar = var;
Exemplo:
int jose, &ze = jose;
Para indicar que é uma referência, utiliza-se o operador &
Toda referência deve ser inicializada quando declarada
Pode-se manipular a variável através de sua referência
Tudo que se faz com a variável pode ser feito através de sua referência.
Prof. Leticia Winkler 35
Referência
Exemplo de Referência
Prof. Leticia Winkler 36
#include <iostream>
using namespace std;
int main () {
int jose = 10, &ze = jose;
cout << "Jose => " << jose << endl;
cout << "Ze => " << ze << endl;
ze = 5;
cout << "Jose => " << jose << endl;
cout << "Ze => " << ze << endl;
return 0;
}
Resultado:
Jose => 10
Ze => 10
Jose => 5
Ze => 5
Passagem de parâmetros por referência
Prof. Leticia Winkler 37
Exemplo: #include <iostream>
using namespace std;
void func(int &x) {
cout << "1 - func => " << x << endl;
x = 20;
cout << "2 - func => " << x << endl;
}
int main () {
int n = 10;
cout << "1 - main => " << n << endl;
func(n);
cout << "2 - main => " << n << endl;
return 0;
}
Resultado: 1 - main => 10
1 - func => 10
2 - func => 20
2 - main => 20
O uso de referência é interessante na passagem de parâmetros
Calcular informações sobre um circulo. Crie duas
funções:
Uma para calcular a área do círculo, que recebe como
parâmetro de entrada o raio e retorna a área (S = πR2)
A segunda função deve calcular o perímetro do círculo,
que recebe como parâmetro de entrada o raio e retorna o
perímetro (P = 2πR).
Crie a função main, para testar seu programa, que utiliza as
funções acima e apresenta o resultado do cálculo do
perímetro e da área.
Prof. Leticia Winkler 38
Exercício #1
#include <iostream> #include <cmath> using namespace std; float calcPerCirc (float r) { return (2 * M_PI * r); } float calcAreaCirc (float r) { return (M_PI * pow(r,2)); } int main() { float raio; cout << "Raio? "; cin >> raio; cout << "Perimetro do circulo de raio " << raio << ": " << calcPerCirc(raio) << endl; cout << "Area do circulo de raio " << raio << ": " << calcAreaCirc(raio) << endl; return 0; }
Prof. Leticia Winkler 39
Resposta do Exercício #1
Converter uma temperatura de graus Celsius para graus Farenheit e vice-versa. Crie duas funções: A primeira recebe como parâmetro de entrada a temperatura em
°C e retorna o resultado em °F.
A segunda recebe como parâmetro de entrada a temperatura em °F e retorna o resultado em °C.
Crie a função main, para testar seu programa, que:
A) lê um menu com as opções:
1. Converte de °C para °F
2. Converte de °F para °C
B) lê a temperatura, e
C) utiliza uma das funções acima para apresentar a temperatura conforme solicitado.
Prof. Leticia Winkler 40
Exercício #2
𝐶
5=
𝐹 − 32
9
Resposta do Exercício #2
Prof. Leticia Winkler 41
#include <iostream>
#include <cmath>
using namespace std;
float celsiusParaFarenheit (float c) {
return (9 * c / 5 + 32);
}
float farenheitParaCelsius (float f) {
return (5 * (f - 32) / 9);
}
int main() {
float temp;
int op;
do {
cout << "\n\n***Conversor de
Temperatura ***\n\n";
cout << "1 - Celsius para Farenheit\n";
cout << "2 - Farenheit para Celsius\n";
cout << "3 - Sair\n";
cout << "\nOpcao? ";
cin >> op;
switch (op) {
case 1:
cout << "Temperatura em C? ";
cin >> temp;
cout<< celsiusParaFarenheit(temp) << " o.F " << endl;
break;
case 2:
cout << "Temperatura em F? ";
cin >> temp;
cout<< farenheitParaCelsius(temp) << " o.C " << endl;
break;
case 3:
cout << "\nFIM!!!!\n\n";
exit(0);
default:
cout << "opcao invalida\n\n";
}
} while (op !=3);
return 0;
}
Recommended