mod4-estruturas-dadosestaticas-ordenacao

Vectores e Matrizes

Escola Secundária Filipa de Vilhena

Estruturas de Dados

Já percebemos que ao executar um programa os valores lidos sucessivamente “limpam” o valor anterior da variável utilizada… E se pretendermos guardar t e m p o r a r i a m e n t e u m determinado conjunto de valores? Como fazemos?

Armazenar…

¡  Arrays ou Vectores

¡  São cadeias de variáveis do mesmo tipo, relacionados entre si e que ocupam determinada posição indicada por um índice §  Arrays de inteiros §  Arrays de reais §  Arrays de strings §  …

¡  São variáveis indexadas, com um número fixo de elementos do mesmo tipo èESTRUTURAS DE DADOS ESTÁTICAS

¡  Arrays ou Vectores

¡  São cadeias de variáveis do mesmo tipo, relacionados entre si e que ocupam determinada posição indicada por um índice §  Arrays de inteiros §  Arrays de reais §  Arrays de strings §  …

¡  São variáveis indexadas, com um número fixo de elementos do mesmo tipo èESTRUTURAS DE DADOS ESTÁTICAS

¡  Unidimensionais -‐ vectores

Arrays unidimensionais -‐ Vectores

§ Os elementos de um vector são sempre armazenados em posições contíguas da memória. § Os elementos de um vector declarado mas não inicializado contêm valores aleatórios. § O índice do primeiro elemento de um vector é sempre ZERO.

§  Se o número de inicializações for menor que o número de elementos do vector, os elementos em falta são inicializados com o valor zero.

§  É possível declarar um vector sem indicar o número de elementos que irá conter, desde que estes sejam colocados na inicialização.

§  Não se podem declarar vectores sem dimensão.

tipo nome_variavel [nº_elementos] Exemplo: int codigo[6]; ou

int codigo[]={123,435,234,987,657,354}; ou

int codigo[6]={123,435,234};

A expressão int codigo[6]; Reserva seis posições de memória de tipo int

A expressão int codigo[]={123,435,234,987,657,354}; Reserva seis posições de memória de tipo int e atribui-‐lhes valores.

O compilador dimensiona o vector com o nº de elementos atribuídos

A expressão int codigo[6]={123,435,234}; Reserva seis posições de memória de tipo int e atribui valores aos três primeiros.

O compilador dimensiona o vector com o nº de elementos referido… 6.

¡  Exemplo:

#include <iostream> using namespace std; main( ) {

int i, a[6];

a[0]= 2; a[1]= 8; a[2]= 5; a[3]= 3; a[4]= 4; a[5]= 6;

for(i=0; i<6; i++) {

cout<<“a[“<<i<<“] = “<<a[i]<<“\n”;

} system(“PAUSE”);

}

Recordam-‐se dos ciclos de repetição? Vamos usá-‐los para percorrer o vector…

Tem de ser feita elemento a elemento. Sem recurso a ciclos Exemplo: a[0]= 2; a[1]= 8; a[2]= 5; a[3]= 3; a[4]= 4; a[5]= 6;

Com recurso a ciclos Exemplo: for(i=0; i<7; i++) { cin>>a[i]; }

função srand() e rand() #include <stdlib.h> #include <iostream> using namespace std; main( ) {

int i, vector[10];

srand(time(NULL));

for(i=0;i<10;i++) { vector[i]=rand(); } cout<<“Numeros aleatorios positivos\n"; for(i=0;i<10;i++) { cout<<"vector["<<i<<"]="<<vector[i]<<"\t\n"; } system("PAUSE");

}

Gera números aleatórios e armazena-‐os num vector.

Valor Valor Valor Valor Valor

Valor Valor Valor

Valor

¡  Cada elemento do vector tem de ser tratado individualmente.

Sem recurso a ciclos Exemplo soma = a[0] + a[1] + a[2] + a[3] + a[4] + a[5];

Com recurso a ciclos

Exemplo soma=0; for(i=0; i<7; i++) { soma = soma + a[i]; }

Actividade 1:

Comecemos por treinar a escrita / leitura de valores de e para um vector de inteiros: §  Peça ao utilizador para introduzir 20 valores que deverão ser guardados num vector; §  Limpe o ecrã no da introdução dos valores; §  Imprima os valores que o utilizador introduziu por ordem de introdução e o índice

correspondente; §  No final imprima também a soma de todos os valores:

Actividade 2: Crie um programa que permita a introdução de n (máximo 100) valores inteiros, este número é definido pelo utilizador. Em seguida, deverá imprimi-‐los pela ordem inversa da introdução.

Actividade 3: Crie um programa que leia a pontuação dos 16 clubes da 1ª Liga, época 2012 /2013… que visionários… depois de fazer a leitura dos pontos (sem tendências clubísticas :o) deve dizer quem é o Campeão e o último classificado, com os respectivos pontos. Deve também escrever qual a média de pontos dessa época.

Dica: Utilize dois vectores, um para os pontos (inicialmente vazio) e outro para o nome das equipas (que deve ser inicializado com o nome das equipas). Faça corresponder a primeira posição do vector de pontos com a primeira posição do vector equipas, ou seja:

Vector Pontos

49

49

35

…

15

14

Vector Equipas

FC Porto

SL Benfica

P. Ferreira

…

Beira-‐Mar

Moreirense

Índice

0

1

2

…

15

16

Índice

0

1

2

…

15

16

Actividade 4: Implemente um programa que peça ao utilizador o número de elementos de um vector e o

preencha. No final, o mesmo vector deve ter os seus elementos pela ordem inversa.

Input: Número de Elementos do vector: 3

Indíce 0: 1

Indíce 1: 2

Indíce 2: 3

Output: Elementos pela ordem inversa: 3 2 1

Sugestão: utilize uma variável auxiliar para efectuar a troca…

Actividade 5: Faça um programa como o anterior, mas em que os valores invertidos são colocados num outro

vector inicialmente vazio.

Input: Número de Elementos do vector: 3

Indíce 0: 1

Indíce 1: 2

Indíce 2: 3

Output: vector um: 1 2 3

vector dois: 3 2 1

Actividade 6: Implemente um programa em que são dados dois vectores diferentes com o mesmo tamanho (5

elementos) em que o seu conteúdo deve ser trocado, ou seja, no final os valores do vector dois

devem estar no vector um e vice-‐versa.

Inicialmente: vector 1: 0 1 2 3 4

vector 2: 5 6 7 8 9

Output: vector 1: 5 6 7 8 9

vector 2: 0 1 2 3 4

Uma dimensão já começa a ser pouco para nós e oferece pouco desafio… … mas, apesar de as 3 dimensões (3D) estarem na moda, também é demais e é preciso óculos … … fiquemos então pelas duas dimensões, que é como quem diz, pelas:

Matrizes (ou Arrays / Vectores Bidimensionais) Como será então a representação de uma matriz tendo em conta que tem duas dimensões??? Algum iluminado??? Alguém??? §  Duas dimensões (linhas e colunas);

§  Disposição faz lembrar tabela;

§  Podem ser vistas como: vector de vectores;

§  Todos os elementos são do mesmo tipo;

§  …

Colunas

Linhas

Exemplo da declaração de um array bidimensional:

int b[2][3]

Qual o nome do array??? Quantas linhas e colunas o compõe???

Trata-‐se de uma matriz de nome b com 2 linhas e 3 colunas…

Quantos elementos / valores pode conter / guardar?

6, como??? Fácil: 2 linhas x 3 colunas = 6 “células”

Como se pode aceder a cada um dos elementos do vector??? Ainda mais fácil:

Colunas

Linha

0 1 2

0 b[0][0] b[0][1] b[0][2]

1 b[1][0] b[1][1] b[1][2]

Com base nesta matriz:

Qual o valor de b[0][2]???



Como acede ao valor 56? E 1?

Coloca-‐se agora uma questão pertinente??? Como percorrer os elementos de uma matriz???

Boa pergunta, quase que parecia minha…

O raciocínio é simples, se num vector se utilizava um ciclo for…

… numa matriz utilizam-‐se dois:

§  Um para percorrer as linhas;

§  Outro para percorrer todas as respectivas células dessa linha (colunas).

Ou seja:

Já sei o que estão a pensar… e não, não tenho nenhum dom adivinhatório, mas desta vez é fácil:

“E o C++ Professor(a)??? Vamos traduzir isto para a nossa linguagem, o C++ …”

Declaração da matriz e de duas variáveis para percorrer o vector (linhas e colunas):

§  int b[2][3] (tipo_vector[num_linhas][num_colunas]);

§  int i, j; (em que i vai ser a variável que controla as linhas e j as colunas, podem ter outro nome).

Agora está na altura de aplicar todos os seus conhecimentos de vectores para percorrer a matriz,

não se esqueça … dois ciclos:

§  O mais exterior para as linhas: for(i = 0; i < 2; i++) {

§  O mais interior, para as colunas de cada linha: for(j = 0; j < 2; j++) {

Isto já merece uma traçagem não acham??? Bem, eu acho …

Que tal um exemplo??? Já dava uma ajudinha, não é verdade??? Uma mãozinha, quiçá duas …

Então cá vai um exemplo, é só passar meus senhores … é só passar …

int main ( ) {

int mat [5][3] int n ,m;

for (n = 0; n < 5; n++) { for (m = 0; m < 3; m++) {

mat [n] [m] = (n + 1) * (m + 1);

} }

system(“PAUSE”);

}

Atividade 7:

Escreva um programa que atribua os números do Euromilhões a uma matriz e os imprima como

se tratasse de um boletim. Output:

§  São 50 números;

§  Cada linha tem 6 números;

§  Começa do número um:

Atividade 8: Imagine que vai ao cinema com uns amigos para ver o filme Rango, acabadinho de estrear. Ao

pedir os bilhetes, a meninada bilheteira diz-‐lhe que os lugares são marcados e começa a marcá-‐

los à mão numa folhinha de papel. Que tal dar-‐lhe uma mãozinha???

Nada de ideias… e não, não é a preencher a grelha que a menina tem à frente. Para fazerem

mesmo sucesso e a impressionarem, que me dizem a chegarem no dia a seguir com um

programa que permite:

§  Marcar lugares;

§  Desmarcar lugares;

§  Apresentar planta do cinema;

§  …

Atividade 9: Imagine que os Professores de PSI estão cansados de programar…só mesmo em imaginação :o)

mas pretendem um programinha que registe as notas dos alunos do turno aos módulos da

disciplina. Ajude os Professores na elaboração desse programa utilizando uma matriz:

§  Preencher inicialmente a matriz com-‐1 (módulo não dado);

§  Utilizador pode preencher as notas por aluno, por módulo, ou

especificando um determinado aluno /módulo (psi[alu][mod]);

§  Se nota < 10 é colocado 0 na célula da matriz senão é colocada a

nota entre 10 e 20;

§  Deve ser possível ter acesso a informação como:

ü  Módulos em atraso de um aluno qualquer;

ü  Média dos alunos (ou de um aluno);

ü  Média de Módulos (ou de um módulo);

ü  Módulos com maior sucesso / dificuldades;

Módulos

Num

do Aluno

Mód 1 Mód 2

…

0 13 0 -‐1

1 12 0 -‐1

2 14 15 -‐1

… … … -‐1

12 0 0 -‐1

Atividade 9 -‐ Sugestões Sugestão de Menus : 1. Preencher Matriz

1.1 Por Módulo 1.2 Por Aluno 1.3 Aluno / Módulo

2. Estatísticas Alunos 2.1 Média Todos Alunos 2.2 Média Aluno 2.3 Aluno com Mais / Menos Módulos 2.4 Nota Mais Alta / Baixa de Aluno

3. Estatísticas Módulos 3.1 Média Todos Módulos 3.2 Média Módulo 3.3 Módulo com Maior / Menor Aproveitamento 3.4 Alunos que (Não) Fizeram Módulo

4. Visualizar Resultados 5. Sair

Valores da Matriz:

1. Inicialmente tudo a -‐1 (módulo não

leccionado)

2. 0 representa módulo não feito (0 < nota < 10)

3. Nota entre 10 e 20, é a nota final ao módulo

Utilize vectores para guardar nomes e

designação de módulos e não os apresentar

como valores entre 0 e …

nomes[10] = {“Tiago”, “Pedro”, …, “Nuno”}

modulos[5] = {“Mod1”, “Mod2”, … “Mod5”}

Já têm utilizado um pseudo tipo de dados, string, em alguns programas elaborados nas aulas. No entanto,

será esta a forma mais correcta de declarar uma string???

Não…

Uma string não é mais que um vector de caracteres (o que já não é pouco), pelo que deve ser

declarada como:

char s[número de caracteres máximo da string];

Outra forma de criar uma string é inicializá-‐la aquando da sua declaração:

char s[ ] = {‘P’, ‘S’, ‘I’, ‘\0’};

Ou

char s[ ] = “PSI”;

Notas: Apesar de PSI ter 3 caracteres, a string terá tamanho 4;

A 2ª forma não precisa do ‘\0’ no final porque ao usar aspas ele é colocado no final de forma automática;

O ‘\0’ indica o fim da string, uma vez que se pode inicializar string com mais posições que as utilizadas …

Vejamos então o seguinte exemplo…

Uma string (str) de 20 caracteres:

§  char str[20]={’B’,’o’,’m’,’ ’,’d’,’i’,’a’,’ ’,’m’,’u’,’n’,’d’,’o’,’\0’};

§  char str[20]="Bom dia mundo";

Um outro aspecto importante, não se pode fazer atribuição directa de uma string a um array:

str = “Bom Dia Mundo”;

str[ ] = “Bom Dia Mundo”;

Só pode ser feita na declaração (inicialização) ou e uma das formas que vamos ver mais à frente.

Podem ser utilizadas as funções normais de input e output , ou seja, cin e cout…

Senão, vejamos a seguinte declaração:

char s[8] = “PSI2013”;

A instrução

cout << s;

Faz aparecer / escrever no ecrã: PSI2013

O mesmo aconteceria, mas em linhas diferentes, com:

for(i=0; i < 5; i++) { // caracter a caracter

cout << s[i] << endl;

}

Para fazer a leitura de uma string para um array, poderíamos fazer:

cin >> s; (Problema a nível dos espaços entre as palavras)

Actividade 10:

Observe com atenção o seguinte programa e a utilização de strings / arrays de caracteres:

#include<iostream>

using namespace std;

Int main() {

char discip[4] = “PSI”, nome[20];

cout << discip;

cout << endl << “Escreva o seu nome: ” << endl;

cin>>nome;

cout << discip << “ … Is Simply The Best …” << endl;

for (int i=0;i<4;i++) {

cout<<nome[i]<<“\n”;

}

}

Será que a implementação anterior tem problemas???

Nunca vos enganamos, mas desta vez há que admitir que existem pequenos bugs…propositados…

§  Se o número de caracteres introduzidos for superior à capacidade do array ;

§  No caso de o utilizador escrever palavras separadas por espaço, o programa só reconhece a primeira

(entende o espaço como separador de dados diferentes).

Então, como podemos manipular estas strings???

§  Existe uma biblioteca que contém conjunto de funções que permitem manipular strings:

<string.h>

§  A Maioria das funções anteriores partem do princípio que na última posição "válida“ está o caracter

especial, ou seja, null ou ’\0’.

Pode efectuar a leitura a partir do teclado com a instrução

gets(string)-‐>lê string a partir do teclado (incluir a biblioteca <stdio.h>)

Actividade 11

:

Escreva um programa, que utiliza a instrução anterior, para ler o nome completo da pessoa a

partir do teclado e que depois o imprima numa mensagem de boas vindas.

#include <iostream>

#include <stdio.h>

using namespace std;

main () {

char nome[100];

cout << "\n Escreva o seu nome: ";

gets(nome);

system(“CLS");

cout <<"Olá, " << nome << endl;

system("PAUSE");

}

Para ler a string pode-‐se

utilizar:

cin.getline(array,

tamanho)

Nota: Ver referências …

Se incluir a biblioteca <string.h> terá acesso a um conjunto de funções que operam directamente sobre

strings, como por exemplo:

§  strcopy(str_destino, str_origem) -‐> copia a string de origem para a string de destino, ou seja:

str_destino = str_origem;

§  strcat(str1, str2)-‐> acrescenta / concatena a string2 à string1;

§  strlen(str)-‐> mede o comprimento da string e retorna o número de caracteres que a compõe.

§  strcmp(str1,str2)-‐> compara as duas strings, str1 e str2. Se as strings forem iguais, devolve o valor 0.

Entre outras…

Actividade 12:

Passe o programa que se segue e observe os resultados da aplicação das funções anteriores:

#include<iostream>

#include<string.h>

intmain ( ) {

char string1[50] = “Aula de PSI 10!!!!”, string2[50];

int n ;

strcpy(string2, string1);

if(strcmp(string2 ,string1) == 0) {

cout << “As strings sao iguais…” << endl;

}

n = strlen(string1) ;

cout<<“A string1 tem “ << n << “ caracteres.” << endl ;

system(“PAUSE”);

}

Actividade 13:

Implemente um programa, em que utilizando as várias funções da biblioteca string, e que:

§  peça ao utilizador para inserir uma password (utilizando a função gets);

§  após a introdução da password, o ecrã é limpo;

§  é dado o número de caracteres da password inserida pelo utilizador;

§  se password do utilizador:

§  igual à do sistema, devolve: “Password Correcta”;

§  senão, devolve: “Password Inválida”;

Devem ser dadas ao utilizador 3 oportunidades para adivinhar a password, senão …

Actividade 14: ¡  Elabore um programa que leia suas palavras do utilizador. O programa deve determinar se

as palavras são iguais. Se não forem, deve determinar qual delas tem maior número de caracteres.

Actividade 15: ¡  Imagine que quer saber, para fins estatísticos, qual o número de espaços em branco, vogais

e consoantes que estão presentes numa frase escrita pelo utilizador. Faça uma implementação.

Actividade 16: ¡  E que tal inverter uma string com um máximo de 20 caracteres que o utilizador introduz??? Actividade 17: ¡  Verifique se uma palavra é um palíndromo, ou seja, palavra que se lê da mesma forma da

direita para a esquerda e da esquerda para a direita. Por exemplo: ovo, radar, salas, sopapos,…

Education

mod4-estruturas-dadosestaticas-ordenacao