View
50
Download
0
Category
Preview:
Citation preview
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[]={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]???
Qual o valor de b[2][0]???
Qual o valor de b[1][0]???
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,…
Recommended