Linguagem de Programação IIParte V
Professora: Flávia Balbino da Costa
Conteúdo Programático:
• Revisão (estruturas de decisão e repetição, procedimentos e funções )
• Trabalhando com a Linguagem C• Estrutura de dados homogêneas I - vetores• Estrutura de dados homogêneas II - matrizes• Estrutura de dados heterogêneas - registros• Recursividade• Ponteiros, alocação dinâmica, listas
Tipos Estruturados
• Até o momento trabalhamos os nossos exemplos com
variáveis de tipos básicos (exceto o caso de strings).
• O grande problema de uma variável de tipo básico que
ela só pode armazenar um valor em um certo instante,
ou seja, caso ela já armazene um certo valor, se
atribuímos a ela um novo valor, o primeiro é perdido!
Tipos Estruturados
• No entanto, é muito comum, em programas um pouco
mais elaborados, haver a necessidade de armazenar
uma grande quantidade de valores.
• Como fazer isso? Criar uma variável para armazenar
cada valor? Isso seria simplesmente loucura se
imaginarmos uma quantidade de 200 valores, por
exemplo.
Tipos Estruturados
• Para solucionar tal tipo de problema, as linguagens
atuais permitem a criação basicamente de dois tipos
estruturados: os vetores e os registros.
• Vejamos as características de cada um deles nas seções
seguintes.
Estrutura de dados homogêneas I VETORES
• Os vetores são chamados de tipos estruturados
homogêneos porque estes têm como objetivo fazer com
que uma variável do tipo vetor possa armazenar ao
mesmo tempo diversos valores, porém, todos do
mesmo tipo.
• Neste caso, além do tipo, precisaremos determinar a
quantidade de valores que tal variável poderá
armazenar.
Estrutura de dados homogêneas I VETORES
• Em C, normalmente declaramos diretamente a variável
como um vetor do seguinte modo:
tipo IDENTIFICADOR[TAMANHO];
• Se lembrarmos da declaração de strings, veremos que
tal sintaxe é totalmente familiar (afinal, como já foi
definido anteriormente, string é, na verdade, um vetor
de caracteres).
Estrutura de dados homogêneas I VETORES
• Devemos lembrar que TAMANHO deve ser um valor
inteiro ou uma constante igual a um valor inteiro.
NUNCA poderá ser uma variável!
Estrutura de dados homogêneas I VETORES
Algumas características de vetores e da linguagem são bastante importantes e serão agora aqui listadas:
1)Ao se declarar um vetor de um certo tamanho T, em termos
de gasto de memória, é o mesmo que se declarar T variáveis.
Portanto, cada valor que se deseja armazenar em um vetor
deve ser feito em posições distintas, ou seja, se armazenarmos
um valor em uma posição que já estava sendo utilizada por
outro valor, este é perdido;
Estrutura de dados homogêneas I VETORES
2) O tamanho definido ao se declarar um vetor determina a
quantidade máxima de valores que poderão ser
armazenados no vetor ao mesmo tempo. Portanto, não é
obrigatório utilizar todas as posições do vetor, mas não
podemos utilizar além do seu tamanho;
Estrutura de dados homogêneas I VETORES
3) As posições de um vetor, em C, são sempre identificadas
por valores inteiros ou valores contidos em variáveis
inteiras e começam a partir do valor 0, ou seja, em um
vetor de 80 posições, por exemplo, os índices das posições
vão de 0 até 79, inclusive. No caso de se utilizar uma
variável para determinar uma posição do vetor, é de total
responsabilidade do programador garantir que o valor
desta esteja entre os limites permitidos;
Estrutura de dados homogêneas I VETORES
4) Exceto para o caso de strings (que é sempre um caso a
parte), caso se queira utilizar os comandos da linguagem
para trabalhar com vetor, isso não poderá ser feito com o
vetor de uma vez só, mas sim, um elemento de cada vez.
Para isso, geralmente utilizamos a ação que desejamos
fazer dentro de um comando de repetição;
Estrutura de dados homogêneas I VETORES
5) Em C, há uma relação entre vetor e endereçamento: ao se
referenciar ao vetor como um todo (sem indicar posição) é
o mesmo que se referenciar ao endereço de memória onde
os valores estão sendo armazenados, ou ainda, o endereço
da primeira posição do vetor (posição de índice igual a
zero).
Estrutura de dados homogêneas I VETORES
• Para se ter acesso a uma posição de qualquer vetor,
devemos indicá-la entre colchetes, após a variável vetor,
como é visto no modelo a seguir:
variável[posição]
Estrutura de dados homogêneas I VETORES
• Devemos nos lembrar que a partir do momento que
manipulamos uma posição do vetor é como se
estivéssemos manipulando uma variável do tipo do
vetor. Por exemplo, se temos um vetor de inteiros e
desejarmos trabalhar com a segunda posição (índice
igual a 1), podemos fazer qualquer ação que
normalmente faríamos como se estivéssemos
trabalhando com uma variável inteira.
Estrutura de dados homogêneas I VETORES
• Por exemplo, se quisermos ler um valor pelo teclado
para armazenar em tal posição, devemos utilizar o
comando scanf, com o código de formatação %d, não
esquecendo do símbolo de & antes da variável vetor,
seguida da indicação da posição.
Exemplo:1) Faça um programa em C que leia as notas da primeira
prova e as notas da segunda prova de cada aluno de
uma turma de 80 alunos. Após a leitura, informe para
cada aluno sua média e se este está aprovado,
reprovado ou em prova final.
Solução:
Solução:
Algoritmos Básicos para Manipulação de Vetores
• Quando trabalhamos com vetor, em diversos casos,
para alcançarmos o objetivo do programa,
possivelmente teremos que realizar algum tipo de ação
como fazer a procura (busca) de algum valor no vetor
ou ordenar o vetor .
• Veremos alguns tipos destes algoritmos a seguir.
Busca em um Vetor• Realizamos uma busca no vetor quando desejamos
saber a informação sobre algum valor específico no
vetor. Temos duas situações de busca:
• Busca por valor – Quando estamos procurando saber se
um valor especificado é igual (ou alguma outra relação)
ao valor de alguma posição do vetor.
• Busca da frequência - Quando estamos procurando
saber quantas posições do vetor tem o valor igual (ou
alguma outra relação) ao valor especificado.
Busca por valor
• Existem duas formas básicas de se fazer uma busca por
um certo no valor, conhecidas como busca seqüencial e
busca binária.
Busca por valor - sequencial
• A procura pelo valor é geralmente feita a partir da
primeira posição (índice igual a 0) e percorre o vetor
através de posições consecutivas até que se encontre a
situação desejada.
• Neste caso, não há nenhuma restrição sobre a
disposição dos valores no vetor.
Exemplo de busca por valor - sequencialint Vet[N], chave, pos, i;
.../* Suponha que o vetor Vet já esteja devidamente preenchido e o valor que se deseja procurar esteja armazenado na variável chave */
pos = -1;for (i=0; i<N; i++) {
if (Vet[i]==chave) {pos = i;i = N; /* para terminar a repetição */
}}
Busca por valor - binária
• Neste tipo de busca o vetor deverá estar previamente
ordenado.
• Este tipo de busca é similar à feita quando desejamos
procurar uma palavra no dicionário. A idéia é simples,
verifica se o valor armazenado na posição do meio é
igual ao valor procurado.
Busca por valor - binária• Caso não seja, se o valor procurado é menor que o valor
da posição do meio, a procura passará ser realizada no
(“sub”)vetor cujas posições têm índices menores que o
índice da posição do meio.
• Caso contrário, a procura passará a ser realizada no
(“sub”)vetor cujas posições possuem índices maiores
que o índice da posição do meio. Assim é feito até se
encontrar o valor ou chegar à conclusão que tal valor
não está armazenado no vetor.
Busca por valor - binária
• A busca binária é considerada, de modo geral, mais
eficiente do que a busca seqüencial, apesar do código
um pouco mais elaborado.
• Devemos lembrar, no entanto, que ao se afirmar que um
algoritmo é mais eficiente que outro é porque, na média
e não em todos os casos, este chega ao resultado mais
rapidamente que o outro.
Busca por valor - binária
• Outra importante observação é que, normalmente, nos
algoritmos de busca se deseja não só saber se o valor
existe ou não, mas também, se existir, em que posição
do vetor este se encontra.
Busca por valor - binária
• Por isso, em C, normalmente utilizamos como resultado
da busca um valor inteiro que armazenará o índice da
posição do vetor em que foi encontrado o valor
desejado, ou simplesmente, o valor -1, quando tal valor
não existir no vetor, já que não existe posição de índice
negativo em C.
Exemplo de busca por valor - bináriaint Vet[N], chave, pos, inicio, meio, fim;
.../* Suponha que o vetor Vet já esteja devidamente preenchido e o valor que se deseja procurar esteja armazenado na variável chave */
pos = -1; inicio = 0; fim = N-1;while (inicio <= fim) {
meio = (inicio + fim)/2;if (Vet[meio]==chave) {
pos = meio;inicio = fim + 1; /* para terminar a repetição */
}/*continua na próxima página…*/
Exemplo de busca por valor - bináriaelse {
if (Vet[meio]<chave) {inicio = meio + 1;
}else {
fim = meio – 1;}
}
Busca da frequência• Neste caso, a busca é similar à busca por valor
seqüencial, porém, necessariamente percorrendo o
vetor todo.
• Como o desejo é saber quantas vezes um valor aparece
no vetor, o resultado deste tipo de busca será um valor
inteiro.
• Vejamos a seguir a implementação deste tipo de busca
para se saber quantas vezes um valor aparece em um
vetor de inteiros de tamanho N.
Exemplo de busca da frequência
int Vet[N], chave, qtd, i;...
/* Suponha que o vetor Vet já esteja devidamente preenchido e o valor que se deseja procurar esteja armazenado na variável chave */
qtd = 0;for (i=0; i<N; i++) {
if (Vet[i]==chave) {qtd++;
}}
Ordenação de um Vetor
• Existem diversos algoritmos de ordenação, que variam
desde a eficiência até a complexidade.
• Devemos lembrar que, ao se realizar uma ordenação,
temos que definir se os dados deverão ficar organizados
crescentemente (do menor para o maior) ou
decrescentemente (do maior para o menor).
Ordenação de um Vetor
• Um dos algoritmos de ordenação mais simples de se
implementar é o algoritmo da bolha (Bubble Sort).
• Por outro lado, os algoritmos conhecidos como Merge
Sort e Quick Sort são conhecidos como sendo os mais
complexos de implementar, no entanto, são
considerados os mais eficientes.
Ordenação de um Vetor
• Como observação, o Quick Sort já vem implementado
em C através de uma função chamada qsort e que faz
parte da biblioteca stdlib.h.
• A utilização desta função não será explicada aqui, mas
vale a pena dar uma olhada sobre ela em alguma outra
referência.
Exemplo de ordenação - Algoritmo da Bolha
int i, j;float Vet[N], aux;
.../* Suponha que o vetor Vet já esteja devidamente preenchido*/for (i=0; i<N-1; i++) {
for (j=i+1; j<N; j++) {if (Vet[i]>Vet[j]) {
aux = Vet[i];Vet[i] = Vet[j];Vet[j] = aux;
}}
}
Exercícios:1) Faça um programa em C que leia as notas da primeira
prova e as notas da segunda prova de cada aluno de
uma turma de 80 alunos. Após a leitura, informe para
cada aluno sua média, quais foram as três maiores
médias da turma e quantos alunos foram aprovados.
2) Faça um programa que leia e imprima o resultado da
soma entre dois vetores inteiros de 50 posições.
Exercícios:3) Faça um programa que leia uma seqüência de 10
números e informe o total de ocorrências do último
número lido.
Exemplo: supondo a seguinte seqüência de
números
3 8 4 2 3 5 6 7 4 12 4
O resultado será: O número 4 apareceu 3 vezes
Exercícios:4) Faça um programa que leia um vetor 10 de números
inteiros. O programa deve inverter a ordem dos
elementos do vetor, de modo que o primeiro elemento
passe a ser o último, o segundo passe a ser o
penúltimo e assim por diante.
Exercícios:5) Faça um programa que leia um vetor ordenado de 10
números inteiros e uma chave, informe a posição da
chave no vetor ou uma mensagem de erro se o
número não for encontrado.
Exemplo: supondo a seguinte seqüência:
1 2 3 8 97 412 446 957 8912 8974
se a chave for 446, o resultado será: Chave na posição 6.
se a chave for 413, o resultado será: Chave não encontrada.
Exercícios:6) Faça um programa que leia um vetor de 20 inteiros
(ordenados de forma crescente) e informe os valores
maiores que a média de seus elementos.
7) Faça um programa que leia dois vetores de 10 inteiros
e imprima os elementos comuns aos dois vetores.
Exercícios:8) Faca um programa capaz de corrigir provas de múltipla
escolha. Cada prova terá 10 questões, valendo 1
ponto cada uma. O programa deve inicialmente ler o
gabarito da prova. Ele será constituído de um conjunto
de dez caracteres representando a resposta para cada
uma das questões. Cada questão pode ter uma das
seguintes respostas: 'a', 'b', 'c', 'd' ou 'e‘.
Exercícios:8) Continuação - Após a leitura do gabarito, o programa
devera ler as respostas dos alunos. Para cada aluno
deverá ser lido o seu numero de matricula e suas
respostas. O programa devera calcular a nota do aluno
e imprimi-la de acordo com o gabarito. A leitura
termina com um código de matricula negativo. Ao final,
o programa devera imprimir a percentagem de
aprovação, sabendo-se que a nota mínima é 6.