Linguagem de Programação II Parte V Professora: Flávia Balbino da Costa

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.


• 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).


• Devemos lembrar que TAMANHO deve ser um valor

inteiro ou uma constante igual a um valor inteiro.

NUNCA poderá ser uma variável!


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;


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;


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;


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;


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).


• 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]


• 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.


• 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.


• 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.


• 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.


• 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).


• 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.


• 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.

Documents

Linguagem de Programação II Parte V Professora: Flávia Balbino da Costa