UNDB
ESTRUTURAS DE DADOS
Prof. Alessandro Gonçalves
[email protected]
Revisão de C
Exercícios – individual (5 min)
1) Crie um programa em C que aguarde a
digitação de três variáveis e exiba seus valores
de forma concatenada
Ex: usuário digitou '1', 'a', 'x' e a saída a ser
exibida é
1ax
Função getchar()
Lê o teclado até que se pressione ENTER
#include <stdio.h>
#include <stdlib.h>
main() {
char ch;
ch=getchar();
printf("%c\n",ch);
system("PAUSE");
return 0;
}
Função putchar()
Exibe um caractere
#include <stdio.h>
#include <stdlib.h>
main() {
char ch;
printf("digite uma letra minúscula : ");
ch=getchar();
putchar(toupper(ch));
putchar('\n');
system("PAUSE");
return 0;
}
Operadores incremento e
decremento
[variável] ++
[variável] - -
Incrementa 1 unidade após a operação
Decrementa 1 unidade após a operação
#include <stdio.h>
#include <stdlib.h>
main() {
int i;
printf ("Digite um número\n");
scanf("%i", &i);
printf("i = %i\n", i);
printf("i++ = %i\n", i++);
printf("i-- = %i\n", i- -);
system("PAUSE");
return 0;
}
Operadores incremento e
decremento
++[variável]
--[variável]
Incrementa 1 unidade antes da operação
Decrementa 1 unidade antes da operação
#include <stdio.h>
#include <stdlib.h>
main() {
int i;
printf ("Digite um número\n");
scanf("%i", &i);
printf("i = %i\n", i);
printf("++i = %i\n", ++i);
printf("--i = %i\n", --i);
system("PAUSE");
return 0;
}
Estruturas de condição - if
If [condicao] {
[comandos se verdadeiro]
} else {
[comandos se falso]
}
Operadores relacionais
>
>=
<
<=
==
!=
maior que
maior ou igual
menor
menor ou igual
igual
diferente
Operadores lógicos
&&
||
!
e
ou
não
Exercícios
Exercícios – individual (5 min)
1) Crie um programa em C que aguarde a
digitação de duas variáveis e exiba qual delas é
maior
#include <stdio.h>
#include <stdlib.h>
main() {
int x,y;
printf("digite numero 1: ");
fflush(stdin);
scanf("%i",&x);
printf("digite numero 2: ");
fflush(stdin);
scanf("%i",&y);
if ( x > y) {
printf("1 eh maior\n");
} else if ( x < y) {
printf("2 eh maior\n");
} else printf("são iguais\n");
system("PAUSE");
return 0;
}
Operador ternário
Maneira simples de implantar testes com duas
possibilidades: sim/não, > ou <=, 0 ou 1...
main(){
int x,y,max;
printf("Entre com dois números: ");
scanf(“%d%d”,&x,&y);
max=(x>y)?1:2;
printf("max= %d\n",max);
}
Qual será o resultado ?
Estruturas de condição - switch
switch(variável)
{
case constante1:
seqüência de comandos
break;
case constante2:
seqüência de comandos
break;
default:
seqüência de comandos
}
Estruturas de condição - switch
main()
{
char x;
printf("1. inclusão\n");
printf("2. alteração\n");
printf(" Digite sua opção:");
x=getchar();
switch(x)
{
case '1':
printf("escolheu inclusão\n");
break;
case '2':
printf("escolheu alteração\n");
break;
default:
printf("opção inválida\n");
}
}
Video
Programador x Webdesigner
Array
Vetor unidimensional
Matriz de 1 linha
Ex: int x[9];
É um vetor com 10 posições, cada uma cabendo um
inteiro
Pilha – implantação em C
Definição das variáveis
Adicionar 1 elemento – Push
Extrair 1 elemento – Pop
Listar a pilha
Destruir a pilha
Pilha – Definição das variáveis
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
char *pilha[MAX];
int qt = 0;
Pilha – Exibe pilha
Exibe_pilha() {
int i;
printf("\n\npilha atual");
printf("\n-----------\n");
if (qt == 0) {
printf("\nPilha vazia.");
} else {
for (i = qt-1; i >=0 ; i-- ) {
printf("---\n”);
printf("|%s|\n",pilha[i]);
}
printf("---\n“);
}
printf("total de elementos: %i\n",qt);
printf("------------------------------------------------\n",qt);
}
Pilha – Inclui elemento
Push (char *elemento){
if (qt >= MAX){
printf("Estouro de pilha. Impossivel incluir");
exit;
} else {
printf("\nOperacao PUSH no elemento %s",
elemento);
pilha[qt] = elemento;
qt++;
}
}
Pilha – Exclui elemento
Pop (){
if (qt == 0){
printf(“Pilha vazia. Impossivel excluir");
exit;
} else {
printf("\nOperacao POP no elemento %s", pilha[qt-1]);
qt--;
}
}
Pilha – Programa Principal
main ()
{
exibe_pilha();
push(‘a’);
push(‘b’)
push(‘c’);
exibe_pilha();
pop();
exibe_pilha();
pop();
exibe_pilha();
pop();
exibe_pilha();
}
Desafio – inversão de pilha
Crie uma pilha em C. Inverta a pilha e exiba seus
resultados.
Pilha invertida – Definição das
variáveis
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
char *pilha[MAX];
char *pilhainv[MAX];
int qt = 0;
Int qtinv = 0;
Pilha – Exclui elemento
char *Pop (){
char *r;
if (qt == 0){
printf(“Pilha vazia. Impossivel excluir");
exit;
} else {
printf("\nOperacao POP no elemento %s", pilha[qt1]);
r = pilha[qt-1];
qt--;
}
return r;
}
Estrutura de repetição em C
Sintaxe:
while(condição)
{
comando;
}
Ex:
main()
{
char ch;
while(ch!='a') ch=getchar();
}
Estrutura de repetição em C
Sintaxe:
do
{
comando;
}
while(condição)
Ex:
main()
{
char ch;
do {ch=getchar();}
while(ch!='a');
}
Estrutura de repetição em C
char ch;
printf("1. inclusão\n 2. alteração\n 3. sair\n");
printf(" Digite sua opção:");
do
{
ch=getchar();
switch(ch) {
case '1':
break;
case '2':
break;
case ‘3':
printf("sair\n");
}
}
while(ch!='1' && ch!='2' && ch!='3');
Lista
Pode-se inserir um elemento em qualquer posição
Pode-se excluir qualquer elemento
Serial
início
Fim
Lista encadeada
Elemento 1 aponta para elemento 2 que aponta para
elemento 3...
Último elemento aponta para “vazio”
1
2
3
null
Lista encadeada - inclusão
Descobre em qual posição deve entrar
NOVO ELEMENTO aponta para onde o elemento
apontava
Elemento anterior aponta para o NOVO ELEMENTO
1
2
novo
3
Lista encadeada - exclusão
Varre a lista e descobre o elemento
Elemento anterior aponta para onde o elemento
excluído aponta
1
2
Elemento excluído
3
Lista encadeada - problemas
Como saber o início da lista ?
Ponteiros perdidos
Alocação dinâmica de memória
1
início
2
3
Estruturas
Tipo de dado que define nova estrutura de dados,
agrupando com tipos primitivos ou complexos.
Exemplo:
struct lapis
{
int dureza;
char fabricante;
int numero;
};
Estruturas
main()
{
struct lapis p[3];
p[0].dureza=2;
p[0].fabricante='F';
p[0].numero=482;
p[1].dureza=0;
p[1].fabricante='G';
p[1].numero=33;
p[2].dureza=3;
printf("dureza = %i\n",p[1].dureza);
printf("fabricante = %c\n",p[1].fabricante);
printf("numero = %i\n",p[1].numero);
system("PAUSE");
}
Estruturas
Exercício (15 min):
Crie uma estrutura para guardar dados de até 100
alunos:
Nome, Série, Email
Ponteiros
Tipo de dado que “aponta” para outro dado
Sintaxe:
tipo *nomevar;
*nomevar = &variável2;
Como se comporta na memória ?
Ponteiros - exemplo
main(){
int x,*px,*py;
x=5;
px=&x;
py=px;
printf("x= %d\n",x);
printf("&x= %d\n",&x);
printf("px= %d\n",px);
printf("*px= %d\n",*px);
printf("*py= %d\n",*py);
x = 7;
printf("*px= %d\n",*px);
printf("*py= %d\n",*py);
}
Ponteiros – operações
++ - aponta para a próxima posição de memória
- - aponta para a posição de memória anterior
Sintaxe:
*p++
*p—
Diferenciar
*p++ # (*p)++
*p- - # (*p) - -
Ponteiros – operações
main(){
int x[5],*px,*py;
px = &x[0];
x[0] = 2;
x[1] = 5;
x[2] = 9;
x[3] = 15;
x[4] = 21;
printf("x[0] = %i\n",x[0]);
printf("*px = %i\n",*px);
*px++;
printf("*px = %i\n",*px);
printf(“\n”);
}
Manipular o código acima com “px” e observar resultados.
Ponteiros – exercícios
Exercício – individual (20 min)
Criar um programa em C que aguarde 5 números e
armazene em um vetor. Exiba estes números através de
ponteiros, de forma descendente.
Função Malloc
Reserva espaço de memória para alocação dinâmica de
variáveis
Sintaxe:
Variável = malloc(sizeof (tipo));
Ex:
v = malloc(100* sizeof(tipo));
Que é o mesmo que a alocação estática
int v[100];
Função Free
Libera espaço de memória alocado dinamicamente por
alguma variável, destruindo seu conteúdo
Sintaxe:
free(variável);
Ex:
v = malloc(100* sizeof(tipo));
free(V);
Ponteiros de estruturas
Como gerar uma lista assim ?
5
0
1
3
NULL
Ponteiros de estruturas
Ver exemplo em C
Lista duplamente encadeada
Elemento 1 aponta para elemento 2 que aponta para
elemento 3... e vice-versa
Existe o “ponteiro” de fim, além do início
Último elemento aponta para o ponteiro fim
1
2
Início
3
Fim
Lista duplamente encadeada
A lista pode ser lida em qualquer ordem facilmente
Se torna um pouco mais difícil para implementar
Muito mais maleável
1
2
Início
3
Fim
UNDB
ESTRUTURAS DE DADOS
Prof. Alessandro Gonçalves
[email protected]