Algoritmos e Estruturas de dados Flashcards
Estruturas de sequenciação, decisão e repetição. Modularização. Estruturas elementares de dados. Implementação em uma linguagem de alto nível.
Quando e por quem o C/C++ foi inventado?
A historia começa pela linguagem BCPL, desenvolvida por Martin Richards, a qual influenciou a linguagem B, inventada por Ken Thompson e esta levou ao desenvolvimento do C que teve inicio nos anos 70 por Dennis Ritchie. Em 1980 Bjarne Stroustrup acrescentou várias extensões à linguagem. Em 1983, o nome foi alterado para C++.
O que é um interpretador de comandos?
O interpretador lê o codigo fonte linha a linha, executando uma instrução por vez. Este sempre estará presente na execução do programa.
O que é um compilador?
Um compilador lê o programa inteiro e converte-o em um código executavel. Uma vez compilado o programa poderá ser executado sem a presença do compilador.
Qual a diferença entre tempo de compilação e tempo de execução?
Os termos estão ligados à erros sobre os eventos que acontecem durante a compilação ou execução do codigo-fonte, respectivamente.
O que é uma função em C?
É uma sub-rotina que contém uma ou mais declarações e realiza uma ou mais tarefas. Convencionou-se que uma função sempre possui parenteses, ex: somar().
Escreva o código abaixo utilizando uma função separada da função main.
#include
int main ()
{
printf (“meu primeiro programa em C!! \n”);
return 0;
}
include
void hello()
{
printf (“meu primeiro programa em C!! \n”);
}
int main () { hello(); return 0; }
O que é um argumento de uma função?
Como é chamada uma função que utiliza argumentos?
É um valor que é passado para a função no momento em que ela é chamada. São chamadas funções parametrizadas.
Escreva uma função que receba o valor 100 e calcule seu valor quadrático (1002)
include <cstdio></cstdio>
int square(int x)
{
printf (“%d elevado ao quadrado eh %d\n”, x, x * x);
}
int main () { int num = 100; square(num); return 0; }
Retorno de valores, escreva uma rotina mull() que calcule o produto entre 5 e 8 e retorne o valor para que a função main o exiba.
include <cstdio></cstdio>
int produto(int a, int b) { return(a \* b); }
int main () { int num; num = produto(5 , 8); printf ("O produto de 5 e 8 eh %d\n", num); return 0; }
O que deve ser observado sobre funções que retornam valores?
a variável que recebe o valor de retorno deve ser do mesmo tipo que o valor retornado. Quando não especificado, a linguagem C assume que é int.
Quais as regras para nomes de funções ou identificadores?
Devem começar com letras (a,A,…,z,Z) .
Em C, um identificador pode possuir até 32 caracteres.
A linguagem C é CaseSensitive.
Quais os 5 tipos de dados utilizados em C?
A linguagem C não possui cadeia de caracteres String. Para isso é utilizado um vetor de caracteres.
char - 8bits
int - 16bits
float - 32bits
double - 64bits
void - sem retorno
Quais são os modificadores de tipo utilizados em C e qual a função de cada um?
signed - extende a valores negativos e positivos
unsigned - limita a valores positivos
long - extende a capacidade de armezanamento
short - reduz a capacidade de armazenamento
O que são variáveis globais?
são declaradas fora do escopo das funções e podem ser acessadas por todas as funções do programa.
o que são variaveis locais?
são declaradas dentro de um bloco e estão restritas somente a esse bloco.
Como se define uma constante em C?
a definição é feita no inicio do programa e diz ao pre-compilador para substituir um nome por um valor
#define constante 8
O que são códigos de barra invertida?
são constantes especiais para uso específico:
\b - retrocesso
\n - Nova linha
\r - retorno de carro
\t - tabulação horizontal
\v - tabulação vertical
\a - sinal sonoro
" - imprime “
|’ - imprime ‘
O que são e quais são os operadores em C?
[Consulta]
É um simbolo que diz ao compilador para realizar manipulações matemáticas ou lógicas. São divididos em três classes:
aritméticos: +, =, *, /, %,
relacionais: >, >=, <, <=, ==, !=,
lógicos: &&, ||, !
Operadores de Endereço:
& - endereço de uma variavel
* - conteudo do endereço
são utilizados com pointers para acesso a endereços de memória:
int var, *x; //declara a variavel var e o ponteiro *x
x = &var; // x recebe o endereço de var
var = *x; //var recebe o conteudo do endereço *x
O que são expressões em C?
É a combinação de operadores, constantes e variáveis.
O que se afirma em C quanto ao uso de parenteses e espaçamentos?
o uso de parenteses redundantes ou adicionais não causa erros ou diminuit a velocidade de execução da expressão. É interessante utilizá-los para facilitar a leitura do codigo.
Qual o esqueleto (estrutura) de um programa em C?
#include <cstdio></cstdio> //declara de bibliotecas e constantes
int produto; //declara variaveis globais
void func(); //declara protótipos de funções
- *int main ()** //declaração obrigatoria da função main
- *{**
int x; // declaracao de variaveis locais
// comandos da funcao principal
return 0;
}
//funções do programador
Regra de comandos e blocos
todo comando é finalizado com um ponto-virgula ;
todo bloco de comandos é definido entre chaves {}
Especificações de conversão em C utlizando scanf() ou prinf()
%d - Número decimal inteiro (int).
- *%i** - equivalente a %d.
- *%u** - Número decimal natural (unsigned int), ou seja, sem sinal.
- *%o** - Número inteiro representado na base octal.
- *%x** - Número inteiro representado na base hexadecimal.
- *%X** - Hexadecimal com letras maiúsculas
- *%f** - Número decimal de ponto flutuante.
- *%e** - Número em notação científica,
- *%E** - Número em notação científica com o “e”maiúsculo
- *%g** - Escolhe automaticamente o mais apropriado entre %f e %e.
- *%p** - Ponteiro: exibe o endereço de memória do ponteiro em notação hexadecimal.
- *%c** - Caractere: imprime o caractere que tem o código ASCII correspondente ao valor dado.
- *%s** - Sequência de caracteres (string, em inglês).
- *%%** - Imprime um %
Como é utilizada a declaração if-else
if (condição 1) {
comandos;
}
else if (condição 2) {
comandos;
}
else {
comandos;
}
Escreva um programa que receba duas variaveis inteiras e apresente o maior valor.
include
int a,b;
int maior(int x, int y) { if (x \> y) return x; else if (y \> x) return y; else return 0; }
int main () { int resultado; printf("Digite os numeros para comparar, separados por espaco\n"); scanf("%d%d", &a, &b); resultado = maior(a,b); if (resultado == 0) printf ("Os valores sao iguais"); else printf("O maior numero eh %d\n", resultado); return 0; }
Escreva um algoritmo que leia um valor real informado pelo o usuário e retorne “positivo” se > 0, “negativo” se < 0, ou “neutro” se = 0;
include <cstdio></cstdio>
float a;
int main () { printf("Digite um valor real\n"); scanf("%f", &a); if (a \> 0) printf ("positivo"); else if ( a \< 0) printf("negativo"); else printf("neutro"); return 0; }
escreva um algoritmo que receba um par de coordenadas e informe em qual quadrante está o ponto referente as coordenadas.
float a,b;
int CalculaQuadrante(int x, int y) { if (a \> 0) if (b \> 0) return 1; else return 4; else if ( a \< 0) if (b \> 0) return 2; else return 3; else return 0; }
int main () { printf("Digite um par de coordenadas\n"); scanf("%f,%f", &a, &b); int result = CalculaQuadrante(a, b); if (result == 1) printf("O ponto esta no primeiro quadrante"); else if (result == 2) printf("O ponto esta no segundo quadrante"); else if (result == 3) printf("O ponto esta no terceiro quadrante"); else if (result == 4) printf("O ponto esta no quarto quadrante"); else printf("O ponto esta sobre algum eixo"); return 0; }
Como é utilizada a declaração switch?
switch (variavel) {
caso cte1:
comandos;
break;
caso cten:
comandos;
break;
default:
comandos;
}
Escreva um programa que receba um valor entre 1 e 7 e apresente o dia da semana correspondente.
include <cstdio></cstdio>
int dia=0;
int main() { printf("Informe um valor entre 1 e 7\n"); scanf("%d", &dia); switch (dia) { case 1: printf("domingo"); break; case 2: printf("segunda-feira"); break; case 3: printf("terça-feira"); break; case 4: printf("quarta-feira"); break; case 5: printf("quinta-feira"); break; case 6: printf("sexta-feira"); break; case 7: printf("sabado"); break; default: printf("dia invalido"); } }
Como é utilizada a declaração for
for (valor inicial; valor final; incremento){
comandos;
}
Fazer uma rotina para contar as ocorrencias da letra ‘a’ em uma string.
#include #include
char dig;
int cont=0;
int main() { printf("Vou contar quantas vezes vc digitou a letra \"a\", digite algo e pressione \"enter\". "); printf("Digite \"Q\" para sair\n"); for( ; ; ) { scanf("%s", &dig); if (dig == 'Q') break; else if (dig == 'a') cont++; } printf("voce digitou a letra a %d ", cont); printf(" vezes"); return 0; }
Como é utlizada a declaração while?
while (condição) {
comandos;
}
ou
do {
comandos;
} while (condição);
Escreva uma função que receba um número e retorne o fatoria deste número. Lembre-se que 0! e 1! = 1
include
int valor;
int main() { int aux=1; printf("Informe um valor\n"); scanf("%d", &valor); printf("O fatorial de %d eh: ",valor); if((valor == 1)||(valor == 0)) { printf("1"); return 0; } while(valor \>0) { aux = aux \* valor; valor--; } printf("%d", aux);
return 0;
}
O que são vetores e como são declarados?
vetores são um conjunto de elementos com as mesmas características.
tipo nome [tamanho];
int vet[3] = { 1, 10, 3 };
O são cadeias de caracteres?
é um conjunto de caracteres terminado por um caractere nulo. Este caracter deve ser contado sempre.
O que são matrizes e como são declarados?
São vetores multidimensionais:
tipo nome [dim1] [dim2] [dimN];
float mat [3] [4] = { 1.0, 3.0, 4.3, 9.9,
3.8, 3.3, 6.4, 2.53,
2, 6.7, 9.67, 10 }
O que são ponteiros e qual a sua utilizaçao em C?
Ponteiro é uma variavel que guarda um endereço de memória de outro objeto. Os ponteiros provêem o meio para que as funções modifiquem os seus argumentos de chamada.
escreva um algoritmo que armazene o valor 100 em uma variavel cont e atribua esse valor a outra variavel val através do ponteiro cont_addr.
#include <cstdio></cstdio>
int main()
{
int *cont_addr, cont=100, val;
cont_addr = &cont;
val = *cont_addr;
printf(“%d”, val);
return 0;
}
O que são os tipos de dados definidos pelos usuário e quais são eles?
Estrutura - agrupamento de variáveis sobre um nome, união - habilita um mesmo pedaço de memória a dois ou mais tipos diferentes, enumeração - lista de simbolos e typedef - cria um novo nome para um tipo existente.
Como é declarada uma estrutura e uma váriavel desse tipo?
A estrutura é declarada como:
struct endereço {
char nome[30];
char sobrenome[30];
};
uma variavel do tipo struct é declarada como:
struct endereço nome;
Declare uma estrutura com um elemento inteiro e um double. Atribua valores a estes elementos e copie os elementos dessa estrutura para outra semelhante e imprima esses valores.
#include <cstdio></cstdio>
**int main()
{
struct exemplo {
int i;
double d;
} est1, est2;
est1. i = 11;
est1. d = 11.11;
est2 = est1;
printf(“%d %1f”, est2.i, est2.d);
}**
Enumerações são conjuntos de constantes inteiras. Declare uma enumeração e exiba seus valores para as moedas de Real.
include <cstdio></cstdio>
int main() { enum moeda { UM,CINCO,DEZ,QUARTO,MEIO,REAL };
enum moeda dinheiro;
printf(“%d %d %d %d %d %d”, UM, CINCO, DEZ, QUARTO, MEIO, REAL);
}
O Typedef permite dar novos nomes para os tipos de dados existentes. Renomei o tipo int, float e char.
include <cstdio></cstdio>
int main() { typedef int inteiro; typedef float flutuante; typedef char caractere;
inteiro i=100;
flutuante f=11.11;
caractere c=’a’;
printf(“%d %f %c”, i, f, c);
}
Qual a diferença entre chamada por valor e chamada por referencia de uma função?
Chamada por valor ou por cópia - esse método copia o valor de um argumento para o escopo. Mudança no paramentro não tem efeito na variável original.
Chamada por referencia - esse método copia o endereço de um argumento para o escopo. Alterações no paramentro implicam em aterações na variável utilizada.
construa um algoritmo que chame uma rotina por valor e calcule esse valor ao quadrado e o imprima na tela juntamente com o valor enviado.
include <cstdio></cstdio>
int a; int sqr(int x) { return (x \* x); }
int main() { printf("Digite um valor inteiro\n"); scanf("%d", &a); printf("%d %d", sqr(a), a); return 0; }
construa um algoritmo que chame uma rotina por referencia e calcule esse valor ao quadrado e o imprima na tela juntamente com o valor enviado.
include <cstdio></cstdio>
int sqr(int \*x) { int a = \*x; return (a \* a); }
int main() { int a; printf("Digite um valor inteiro\n"); scanf("%d", &a); printf("%d %d", sqr(&a), a); return 0; }
O que são funções recursivas?
A recursividade é o processo de definição de algo em torno de si mesmo.
Utilizando a recursividade faça um programa que calcule o fatorial de um nº inserido pelo usuário.
include <cstdio></cstdio>
int fatorial(int x) { int result; if ((x == 0)||(x == 1)) return 1; result = x \* fatorial(x - 1); return result; }
int main() { int n,f; printf("Informe um numero positivo\n"); scanf("%d", &n); f = fatorial(n); printf("%d", f); return 0; }
orientação_objetos
Definição de objeto.
Entidade lógica que contém dados e métodos de manipulação de dados. Os dados e métodos podem ser públicos ou privados.
Definição de Encapsulamento.
o nome se dá ao fato dos objetos possuirem partes públicas acessiveis em todo programa e partes privadas acessiveis apenas do próprio dono.
Definição de Polimorfismo.
E suma significa que um objeto pode assumir varias formas. O objetivo é permirtir uma classificação mais generalizada para especificar uma classe geral.
Definição de Herança
É o processo em que um objeto pode adquirir as propriedades de outro objeto. É uma instância específica de uma classe mais geral (polimórfica).
Qual a forma geral de declaração de uma classe em C++?
class NomeDaClasse {
dados e funções privadas
public:
dados e funções publicas
} lista de objetos;
Como identificar uma função membro de uma classe mae?
A função é identificada pelo operador de escopo de resolução ::
classe_mae::funcao_membro() {}
Qual a definição de sobrecarga de uma função?
Várias funções podem compartilhar o mesmo nome, desde que suas declarações de parametros sejam diferentes.
Faça um programa que leia um int, um double e um long e utilizando a sobrecarga, utilize a funçao correta para processar a informação.
- *#include**
- *using namespace std;**
**void leia(const char \*str, int \*i); void leia(const char \*str, double \*d); void leia(const char \*str, long \*l);**
**main(){
int i;
double d;
long l;
leia(“Informe um inteiro:”, &i);
leia(“Informe um double:”, &d);
leia(“Informe um long:”, &l);
cout << “O inteiro foi: “ << i;
cout << “O double foi: “ << d;
cout << “O long foi: “ << l;
return 0;
}**
void leia(const char *str, int *i){
cout << str;
cin >> *i;
}
void leia(const char *str, double *d){
cout << str;
cin >> *d;
}
void leia(const char *str, long *l){
cout << str;
cin >> *l;
}
Construtores de Destrutores
É comum um objeto requerer inicialização antes de ser utilizado. Isto pode ser feito com uso de classes contrutoras
faça um programa que atraves de uma classe principal, intancie uma classe filha utilizando construtor e destrutor.
#include <iostream><br></br> //declara um espaço de nomes do std para não ter que declarar std::funcao em todas as funcoes do std, cin, cout, cerr<br></br>using namespace std;<br></br> // declara a classe<br></br>class fila<br></br>{ // por definição todos os item de uma classe são privados<br></br> int q[100];<br></br> int sloc, rloc;<br></br> <br></br>public:<br></br> // para tornar um membro desse classe público, este deve vir apos essa linha<br></br> fila(); //construtor<br></br> ~fila(); //destrutor<br></br> void qput(int i);<br></br> int qget(void);<br></br>}; <br></br> //quando codificar uma função membro, deve ser informado a qual classe essa funcao pertence atraves do class::funcao</iostream>
fila::fila(void){ //construtor
rloc = sloc = 0;
cout << “fila inicializada\n”;
}
fila::~fila(void){ //destrutor
cout << “fila destruida\n”;
}
void fila::qput(int i){
if (sloc == 3){
cout << “A fila esta cheia\n”;
return;
}
sloc++;
q[sloc] = i;
}
**int fila::qget(){
if (rloc == sloc){
cout << “A fila esta vazia\n”;
return 0;
}
rloc++;
return q[rloc];
}
main() {
//cria dois objetos fila
fila a, b;
a. qput(1);
b. qput(4);
a. qput(2);
b. qput(5);
a. qput(3);
b. qput(6);
cout << a.qget() << “ “;
cout << b.qget() << “ “;
cout << a.qget() << “ “;
cout << b.qget() << “ “;
cout << a.qget() << “ “;
cout << b.qget() << “ \n”;
return 0;
}**
Como é possível para uma função não-membro de uma class ter acesso a partes privadas dessa class?
Através da declaração da função como uma friend da class.
Definição da palavra reservada this
Sempre que se invoca uma função membro, automaticamente é passa um ponteiro para o objeto que a invoca. Esse ponteiro é acessado atraves da palavra this
Coloque cada classe no seu próprio arquivo
Para melhorar a manutenção do código, procure sempre manter dois arquivos para cada classe, um para declaração (arquivo .h ou .hpp) e outro para a implementação (arquivo .cpp). Evite colocar mais de uma classe num único arquivo, a não ser que as classes sejam extremamente dependentes uma da outra, tipo inseparáveis.
Separe em dois arquivos a declaração da classe e sua implementação
Em C++ costuma-se separar a definição de cada classe em dois arquivos: um para declaração (arquivo .h ou .hpp) e outro para a implementação (arquivo .cpp).
Sempre dê nomes descritivos aos identificadores
Se uma variável guarda o nome de um funcionário, o nome mais provável é nomeDoFuncionario ou nome_do_funcionario. Se um método calcula o salário, o nome mais óbvio seria calculaSalario() ou calcula_salario(). Dê nomes que façam sentido.
Use consistentemente alguma convenção para nomear identificadores
palavras em nomes de classes e enumerações sempre começam com letra maiúscula e as restantes minúsculas. Nomes de variáveis e métodos sempre em letra minúscula e em nomes compostos cada palavra exceto a primeira começa com letra maiúscula. Constantes sempre com todas as letras maiúsculas e separando palavras com underscore. Exemplos:
class AlgumaClasse {}; enum AlgumEnum {}; void algumMetodo(); int algumaVariavel; const int ALGUMA\_CONSTANTE;
Use consistentemente um estilo de formatação que facilite a clareza do programa
Para melhorar a clareza e a legibilidade do seu código, é bom manter um estilo que seja convencional, como por exemplo, indentar usando a tecla TAB ou com no mínimo uns 3 espaços. Usar linhas em branco antes e depois da implementação de métodos, etc.
Comentários são valiosos, mas não abuse deles
Comentários podem tanto esclarecer o leitor do código como confundir, se você não os manter atualizado. De que adianta um comentário que está no código há uma década se o código já foi alterado mil vezes e nem sequer faz o que o comentário diz que ele faz? Se vai encher o código de comentários então os mantenha atualizados com o que o código realmente está fazendo. Outro detalhe, comentário demais é sinônimo de código ruim. Se você precisa comentar tanto assim pra explicar o que o código faz, provavelmente é porque o seu código em si não está claro o suficiente.
Evite números mágicos, usando constantes com nome
Números mágicos são aqueles números que aparecem às vezes no código e que não são dados introduzidos de fora do programa, são constantes numéricas que não mudam nunca. O problema é que quando você vê uma constante numérica assim perdida em qualquer lugar, dependendo do caso não é possível entender o que aquele número significa. Uma forma muito mais atraente e que clarifica o código é usar constantes com nome ou constantes simbólicas.
Prefira enumerações a constantes simbólicas
#define SOLIDO 0 #define LIQUIDO 1 #define GRANDE 3 #define MEDIO 2 #define PEQUENO 1
Usando enumerações:
enum Estado { SOLIDO, LIQUIDO };
enum Tamanho { GRANDE, MEDIO, PEQUENO };
Evite repetições de código sempre que possível
Sempre que você ver que no programa existe algum trecho de código que se repete em vários pontos, é sinal de que talvez aquele código poderia estar encapsulado em uma função, método ou classe. Sempre preste atenção em código repetido e elimine sempre que for possível substituí-lo por uma chamada de função.
Escolha o tipo mais eficiente para variáveis primitivas
Sempre lembre-se da capacidade das variáveis primitivas em C++. um char pode armazenar um valor entre -128 e 127. Um short pode armazenar um valor entre -32768 a 32767. Existem compiladores atualmente que otimizam o código e substituem os tipos das variáveis transparentemente quando possível, mas se você valoriza o seu trabalho não confie no compilador para fazê-lo por você.
Aprenda a usar os contêineres da STL ou de outras bibliotecas
Na STL você encontra duas classes imprescindíveis e extremamente úteis no dia-a-dia: string e vector. Com a classe string você obtém strings reais e com a classe vector você obtém arrays de tamanho variável, então é importante conhecer e estudar esta biblioteca.
Ao retornar objetos grandes ou contêineres, retorne referências ao invés de cópias
Retorne referências ao invés de cópias. Quando você retorna uma referência para um objeto ou contênier, o sistema não copia nada, a única coisa que ele faz é te retornar o objeto original.
Ponteiros devem ser sempre inicializados
Todo ponteiro deve ser inicializado na declaração para evitar que ele seja utilizado incorretamente. Se não tiver como inicializar um ponteiro logo na declaração, então aponte-o para NULL
Delete e anule sempre os ponteiros quando terminar de utilizá-los
atribua NULL ao ponteiro
Passe objetos grandes sempre por referência ou ponteiro
Passar parâmetros para funções e métodos leva tempo. Dependendo do tamanho do objeto, e dependendo de quantas vezes esse objeto é passado inteiro por parâmetro
Evite longas listas de parâmetros, prefira passar referência a um único objeto
Se você tem um método ou função que recebe 10 parâmetros, pare e pense na possibilidade de passar uma estrutura contendo esses parâmetros. crie uma estrutura que encapsule esses dados e passe uma referência da estrutura por parâmetro.
Declare os membros de uma classe sempre como sendo privados
Uma das idéias principais por trás da orientação a objetos é que as classes encapsulam dados e métodos para operar sobre esses dados. Se você tem uma classe onde todos os membros são públicos, você está desrespeitando o princípio do encapsulamento
Crie métodos de acesso para controlar alterações nos membros privados
Para cada membro de dados ao qual seja permitido o acesso, você implementa métodos que alterem ou retornem o seu valor. A diferença está no fato de que, quando o acesso é feito apenas através de métodos, é possível controlar e restringir as alterações que podem ser feitas em um objeto, evitando assim a manipulação indevida dele e mantendo a integridade de seus dados.
Em uma hierarquia declare destrutores de superclasse sempre como sendo virtuais
quando um objeto de subclasse for destruído, o sistema seja capaz de invocar os destrutores tanto da subclasse quanto o da superclasse.
Cada método deve ter somente uma única responsabilidade
Ao implementar um método, sempre lembre-se de verificar que ele executa uma única tarefa. Se você perceber que um método está fazendo coisas que não tem relação nenhuma entre si, é sinal de que é preciso dividí-lo em dois ou mais métodos.
Cada classe deve ter somente uma única responsabilidade
Se o seu programa em C++ consiste numa única classe que faz tudo, então o seu programa não é orientado a objetos.
Prefira composição a herança
a composição é quando você inclui membros em uma classe que são instâncias ou referências a objetos de outras classes. Em certos casos, é possível modelar um problema usando herança ou composição. Sempre que você tiver essa escolha, prefira composição.
Polimorfismo só ocorre com método virtual
Polimorfismo no C++ é, na prática, quando você consegue acessar o método da subclasse através de um ponteiro de superclasse, desde que ele aponte para um objeto de subclasse. O erro de tentar obter polimorfismo de um método não-virtual é muito comum, então lembre-se sempre de declará-lo virtual na superclasse para ver a mágica polimórfica diante dos seus olhos!