Estrutura, Pesquisa e
Ordenação de Dados
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Apresentação da disciplina
(2) Compilador DevC++
(3) ANSI C: visão geral
(1) Apresentação da Disciplina
Informações Gerais
• Horário:
– Terça e quinta às 20:30
• Objetivos:
– Introduzir o conceito de tipo de dados (TAD), evidenciando aspectos de
implementação, aplicações e complexidade
– Apresentar estruturas de dados básicas (listas lineares, pilhas, filas,
árvores)
– Apresentar métodos de busca e classificação de dados em memória
principal utilizando estruturas de dados básicas
• Bibliografia:
– TENENBAUM, A.; Langsam, Y.; Augenstein, M.: Estruturas de dados
usando C. São Paulo: Bookman. (LIVRO TEXTO)
– VILLAS, Marcos Vianna et AL. Estrutura de dados: conceitos e técnicas
de implementação. Rio de Janeiro: Campus. (LIVRO TEXTO)
– DROZDEK, Adam. Estruturas de Dados e Algoritmos em C++.São
Paulo: Pioneira Thomson Learning (LEITURA COMPLEMENTAR)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(1) Apresentação da Disciplina
Cronograma
SEMANA
UNID I
Estruturas de
dados
básicas
(listas
encadeadas,
filas e pilhas)
UNID II
Métodos de
busca e
classificação
de dados
UNID III
Árvores e
Grafos
DESCRIÇÃO
REF
Nivelamento em ANSI C
 Duas semanas iniciais de conceitos básicos (apresentação do compilador,
estruturas de controle, estruturas, vetores, strings e ponteiros)
 Essencial a resolução das listas de exercícios em casa
(1) UFMG
(2) UFPB
3ª sem/AGO
Listas encadeadas
 Essencial a presença na aula de exercícios em laboratórios dia 21/8
(1) VILLAS
(2) TENENBAUM
4ª sem/AGO
1ª sem/SET
Recursividade, pilhas e filas
 PROVA 1 (unidade I): 09/09
(1) VILLAS
(2) TENENBAUM
2ª sem/SET
3ª sem/SET
4ª sem/SET
1ª sem/OUT
Busca linear e binária
Bubble sort, selection sort, quick sort, insertion sort, merge sort
(1) TENENBAUM
(2) DROZDEK
2ª sem/OUT
3ª sem/OUT
Tabela Hash
− PROVA 2 (unidade II): 21/10
(1) VILLAS
(2) DROZDEK
4ª sem/OUT
1ª sem/NOV
2ª sem/NOV
3ª sem/NOV
Árvores
(1) VILLAS
(2) DROZDEK
4ª sem/NOV
1ª sem/DEZ
Grafos
− PROVA 3 (unidade III): 09/12
(1) TENENBAUM
(2) DROZDEK
1ª sem/AGO
2ª sem/AGO
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
OBS: PDFs disponíveis
no site do professor
3
(1) Apresentação da Disciplina
Motivação inicial...
• Troque as posições
dos sapos (os machos
para a direita e as
fêmas para a
esquerda)
http://www.fredbf.com/disciplinas/christus/ed/SAPO.xls
• Depois de resolvido o problema, represente sua solução no papel
– Estamos interessados no passo a passo para achar a solução
– Forma livre de representação: português, desenho, algoritmo, etc
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
4
(2) DevC++
Compiladores de C
• C é uma linguagem compilada
Windows
UNIX
Linux
Código-Fonte
Compilar
.C
Código-Objeto
Processo de
Geração de Código
.OBJ
Executável
10010
OPÇÕES:
Turbo C++
DevC++ (Free)
Borland C++
C++Builder
Notepad
Estrutura, Pesquisa e Ordenação de Dados
Linkar
Bibliotecas
.EXE
.OBJ
Frederico Brito Fernandes
5
(3) ANSI C
Histórico
• Criada na Bell Labs
– divisão da AT&T, famosa companhia americana de telecomunicações
• Idealizada e implementada por Dennis Ritchie
– Quando? 1970
• Objetivo:
– gerar uma linguagem de “alto nível”, em oposição à linguagem
Assembly
– desenvolver uma linguagem capaz de executar em qualquer plataforma
• Uso geral:
– Unix, Clipper, Lotus 1 2 3, Excel, DBase III e IV, Oracle
• Principais características:
– Modularidade e Portabilidade
• Padrão ANSI C
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
6
(3) ANSI C
Primeiro programa...
• C é CASE SENSITIVE
– Soma, SOMA, SoMa ou sOmA.
– Comandos em letras minúsculas
• if e for, por exemplo
• If ou For são interpretados como variáveis
• Primeiro Programa:
#include <stdio.h>
/* Um Primeiro Programa */
int main () {
CONSIDERAÇÕES
printf ("Ola! Eu estou vivo!\n");
getchar();
return(0);
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
1.
2.
3.
4.
5.
6.
7.
Biblioteca de E/S: stdio.h
Comentário: /* aqui */
Função: main() retorna inteiro
Delimitador de bloco {bloco}
Função de E/S: printf()
Constante de nova linha: \n
Retorno de função: return()
7
(3) ANSI C
Tipos
• C possui os seguintes tipos
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
8
(3) ANSI C
Segundo programa...
• Segundo Programa:
#include <stdio.h>
int main ()
{
int dias; /* Declaracao de Variaveis */
float Anos;
printf ("Entre com o número de dias: "); /* Entrada de Dados*/
scanf ("%d",&Dias);
Anos=Dias/365.25; /* Conversao Dias->Anos */
printf ("\n\n%d dias equivalem a %f anos.\n",Dias,Anos);
getchar();
}
1.
2.
3.
4.
Estrutura, Pesquisa e Ordenação de Dados
CONSIDERAÇÕES
Declaração de Variável: tipo <id>
Ex: float Anos; /* variável de ponto flutuate, ie, real de Pascal */
Função de E/S: scanf()
“%d” – leia um inteiro
&Dias – armazene nesse endereço
Conversão de tipo: float <- int
Função printf() com vários argumentos
Frederico Brito Fernandes
9
(3) ANSI C
Operadores aritméticos e de atribuição
– Aritméticos e de Atribuição
• Binários: +, -, *, /, %
• Unários: +, -, ++, --
Ex: int a = 17, b = 3;
int x, y, w;
float z = 17, z1, z2, z3;
Estrutura, Pesquisa e Ordenação de Dados
a)
b)
c)
d)
e)
Frederico Brito Fernandes
x = a / b;
y = a % b;
z1 = z / b;
z2 = a/b;
z3 = w/b;
10
(3) ANSI C
Comandos de Controle de Fluxo
• if: desvio condicional
– Sintaxe:
• If (condição) instrução;
– Ex1:
CONSIDERAÇÕES
1.
2.
O comando “if” exige o uso de parênteses
O que está de errado no teste?
if(num=10) ... // isto estah errado
Operadores de comparação: >, <, >=, >=, == e !=
Operador de atribuição: =
#include <stdio.h>
int main ()
{
3.
int num;
4.
printf ("Digite um numero: ");
scanf ("%d",&num);
if (num>10) printf ("\n\nO numero eh maior que 10");
if (num==10)
{
printf ("\n\nVoce acertou!\n");
printf ("O numero e igual a 10.");
}
if (num<10) printf ("\n\nO numero eh menor que 10");
getchar();
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
11
(3) ANSI C
Comandos de Controle de Fluxo
• for: laço de repetição
• while: laço de repetição
– Sintaxe:
– Sintaxe:
• for(inicialização;condição;incremento){
instrução;
}
• while(condição){
instrução;
}
– Ex2:
– Ex3:
#include <stdio.h>
int main ()
{
int i;
for (i=0;i<10;i++) {
#include <stdio.h>
int main ()
{
int i;
i=0; // inicialização
while (i<10) { //condição
printf ("\n Executou %d vez(es)“,i);
printf ("\n Executou %d vez“,i);
i++; //incremento
}
}
}
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
12
(3) ANSI C
Comandos de Controle de Fluxo
• Ex: Este programa imprime o alfabeto (letras maiúsculas)
#include <stdio.h>
int main()
{
char letra;
for(letra = 'A' ; letra <= 'Z' ; letra =letra+1)
printf("%c ", letra);
}
CONSIDERAÇÕES
1.
2.
Estrutura, Pesquisa e Ordenação de Dados
O valor inicial de “letra” é 65 ou ‘A’
Portanto, letra pode ser incrementado
Frederico Brito Fernandes
13
(3) ANSI C
Comandos de Controle de Fluxo
• Auto-avaliação
– Explique porque está errado fazer a instrução abaixo. O que irá acontecer?
• if (num=10) ...
– Escreva um programa que coloque os números de 1 a 100 na tela na ordem
inversa (começando em 100 e terminando em 1)
– Escreva um programa que coloque os números ímpares de 1 a 100 na tela. O
operador MOD de pascal é o % em C, ex: 10 % 2 resulta em 0.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
14
(3) ANSI C
Função
• Sintaxe de uma função em C:
Se for “void” não retorna nada
Se estiver vazio, não possui argumentos
tipo_de_retorno nome_da_função (lista_de_argumentos)
{
código_da_função
Ex1: uma função que imprime uma string
}
#include <stdio.h>
int mensagem () /* Funcao simples: so
imprime Ola! */
{
printf ("Ola! ");
return(0);
}
int main ()
{
CONSIDERAÇÕES
mensagem();
printf ("Eu estou
vivo!\n");
1. Saída
igual ao “Primeiro Programa”
return(0);
2. Diferença entre main() e o resto
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
15
(3) ANSI C
Função
• Auto-avaliação
– Escreva uma função que recebe dois inteiros e retorna a soma entre eles
– Escreva uma função que receba dois floats e retorne o menor entre eles
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
16
(3) ANSI C
Tabela de Precedência
• Expressão
Tabela de Precedência
• Ex:
int i=1,a=4,b=2,c=1,d=8,e=4;
i = i+3; //resulta em 4
c= a*b + d/e;
c= a*(b+d)/e;
c>2?1:0
MAIOR
precedência
– Combinação de variáveis, constantes
e operadores
– Em C, toda expressão resulta em um valor
– As sub-expressões são avaliadas de
acordo com a Tabela de Precedência
• Ex:
c= a*b + d/e; // é o mesmo que
// c = (a*b) + (d/e);
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
menor
() [] ->
! ~ ++ -- . -(unário)
(cast) *(unário)
&(unário) sizeof
* / %
+<< >>
<<= >>=
== !=
&
^
|
&&
||
?
= += -= *= /=
17
(3) ANSI C
Palavras reservadas
• Toda linguagem de programação possui palavras usadas
para fins diversos:
– Controle de repetição, desvio condicional e incondicional,
tipos e seus modificadores, etc.
– Ao longo do curso, veremos como funcionam...
• Palavras Reservadas do ANSI C:
– auto, break, case, char, const, continue, default, do, double,
else, enum, extern, float, for, goto, if, int, long, register, return,
short, signed, sizeof, static, struct, switch, typedef, union,
unsigned, void, volatile, while
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
18