Prof. Frederico Brito Fernandes [email protected] Estrutura, Pesquisa e Ordenação de Dados CONTEÚDO (1) Apresentação da disciplina (2) Compilador DevC++

Prof. Frederico Brito [email protected]

Estrutura, Pesquisa e Estrutura, Pesquisa e Ordenação de Dados Ordenação de Dados Estrutura, Pesquisa e Estrutura, Pesquisa e Ordenação de Dados Ordenação de Dados

CONTEÚDO

(1) Apresentação da disciplina(2) Compilador DevC++(3) ANSI C: visão geral

Frederico Brito FernandesFrederico Brito Fernandes 2Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados

Informações GeraisInformaçõ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)

(1) Apresentação da Disciplina


CronogramaCronograma

SEMANA DESCRIÇÃO REF

UNID IEstruturas de dados básicas (listas encadeadas, filas e pilhas)

1ª sem/AGO 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) UFPBOBS: PDFs disponíveis

no site do professor

2ª sem/AGO

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/SETRecursividade, pilhas e filas PROVA 1 (unidade I): 09/09

(1) VILLAS

(2) TENENBAUM

UNID IIMétodos de busca e classificação de dados

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/OUTTabela Hash

− PROVA 2 (unidade II): 21/10

(1) VILLAS

(2) DROZDEK

UNID IIIÁrvores e Grafos

4ª sem/OUT

1ª sem/NOV

2ª sem/NOV

3ª sem/NOV

Árvores (1) VILLAS

(2) DROZDEK

4ª sem/NOV

1ª sem/DEZGrafos

− PROVA 3 (unidade III): 09/12

(1) TENENBAUM

(2) DROZDEK



Motivação inicial...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


Compiladores de CCompiladores de C

• C é uma linguagem compilada

.C.C

Código-FonteCódigo-Fonte

CompilarCompilar

.EXE.EXE

1001010010

.OBJ.OBJ

LinkarLinkar

.OBJ.OBJ

Código-ObjetoCódigo-Objeto

ExecutávelExecutável

BibliotecasBibliotecasOPÇÕES:OPÇÕES: Turbo C++Turbo C++ DevC++ (Free)DevC++ (Free) Borland C++Borland C++ C++BuilderC++Builder NotepadNotepad

Processo de Geração de Código

WindowsWindowsUNIXUNIXLinuxLinux

(2) DevC++


• 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

HistóricoHistórico

(3) ANSI C


• 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 () {printf ("Ola! Eu estou vivo!\n");

getchar();

return(0);

}

1.1. Biblioteca de E/S: stdio.hBiblioteca de E/S: stdio.h2.2. Comentário: /* aqui */Comentário: /* aqui */3.3. Função: main() retorna inteiroFunção: main() retorna inteiro4.4. Delimitador de bloco {bloco}Delimitador de bloco {bloco}5.5. Função de E/S: printf()Função de E/S: printf()6.6. Constante de nova linha: \nConstante de nova linha: \n7.7. Retorno de função: return()Retorno de função: return()

1.1. Biblioteca de E/S: stdio.hBiblioteca de E/S: stdio.h2.2. Comentário: /* aqui */Comentário: /* aqui */3.3. Função: main() retorna inteiroFunção: main() retorna inteiro4.4. Delimitador de bloco {bloco}Delimitador de bloco {bloco}5.5. Função de E/S: printf()Função de E/S: printf()6.6. Constante de nova linha: \nConstante de nova linha: \n7.7. Retorno de função: return()Retorno de função: return()

CONSIDERAÇÕESCONSIDERAÇÕESCONSIDERAÇÕESCONSIDERAÇÕES

Primeiro programa...Primeiro programa...

(3) ANSI C


• C possui os seguintes tipos

TiposTipos

(3) ANSI C


• 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.1. Declaração de Variável: tipo <id>Declaração de Variável: tipo <id>Ex: float Anos; /* variável de ponto flutuate, ie, real de Pascal */Ex: float Anos; /* variável de ponto flutuate, ie, real de Pascal */

2.2. Função de E/S: scanf()Função de E/S: scanf()““%d” – leia um inteiro%d” – leia um inteiro&Dias – armazene nesse endereço&Dias – armazene nesse endereço

3.3. Conversão de tipo: float <- intConversão de tipo: float <- int4.4. Função printf() com vários argumentosFunção printf() com vários argumentos

1.1. Declaração de Variável: tipo <id>Declaração de Variável: tipo <id>Ex: float Anos; /* variável de ponto flutuate, ie, real de Pascal */Ex: float Anos; /* variável de ponto flutuate, ie, real de Pascal */

2.2. Função de E/S: scanf()Função de E/S: scanf()““%d” – leia um inteiro%d” – leia um inteiro&Dias – armazene nesse endereço&Dias – armazene nesse endereço

3.3. Conversão de tipo: float <- intConversão de tipo: float <- int4.4. Função printf() com vários argumentosFunção printf() com vários argumentos


Segundo programa...Segundo programa...

(3) ANSI C


– 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;

a) x = a / b;

b) y = a % b;

c) z1 = z / b;

d) z2 = a/b;

e) z3 = w/b;

Operadores aritméticos e de atribuiçãoOperadores aritméticos e de atribuição

(3) ANSI C


• if: desvio condicional

– Sintaxe:• If (condição) instrução;

– Ex1:#include <stdio.h>

int main ()

{

int num;

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();

}

1.1. O comando “if” exige o uso de parêntesesO comando “if” exige o uso de parênteses2.2. O que está de errado no teste?O que está de errado no teste?

if(num=10) ... // isto estah erradoif(num=10) ... // isto estah errado3.3. Operadores de comparação: >, <, >=, >=, == e !=Operadores de comparação: >, <, >=, >=, == e !=4.4. Operador de atribuição: =Operador de atribuição: =

1.1. O comando “if” exige o uso de parêntesesO comando “if” exige o uso de parênteses2.2. O que está de errado no teste?O que está de errado no teste?

if(num=10) ... // isto estah erradoif(num=10) ... // isto estah errado3.3. Operadores de comparação: >, <, >=, >=, == e !=Operadores de comparação: >, <, >=, >=, == e !=4.4. Operador de atribuição: =Operador de atribuição: =


Comandos de Controle de FluxoComandos de Controle de Fluxo

(3) ANSI C


• for: laço de repetição

– Sintaxe:• for(inicialização;condição;incremento){

instrução;

}


int main ()

{

int i;

for (i=0;i<10;i++) {printf ("\n Executou %d vez(es)“,i);

}

}

• while: laço de repetição

– Sintaxe:• while(condição){

instrução;

}


int main ()

{

int i;

i=0; // inicialização

while (i<10) { //condiçãoprintf ("\n Executou %d vez“,i);

i++; //incremento

}

}


(3) ANSI C


• 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);

}

1.1. O valor inicial de “letra” é 65 ou ‘A’ O valor inicial de “letra” é 65 ou ‘A’ 2.2. Portanto, letra pode ser incrementadoPortanto, letra pode ser incrementado1.1. O valor inicial de “letra” é 65 ou ‘A’ O valor inicial de “letra” é 65 ou ‘A’ 2.2. Portanto, letra pode ser incrementadoPortanto, letra pode ser incrementado



(3) ANSI C


• 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.


(3) ANSI C


• Sintaxe de uma função em C:

tipo_de_retorno nome_da_função (lista_de_argumentos)

{

código_da_função

}

Se for “void” não retorna nadaSe for “void” não retorna nada Se estiver vazio, não possui argumentosSe estiver vazio, não possui argumentos

FunçãoFunção

(3) ANSI C

Ex1: uma função que imprime uma string

#include <stdio.h>int mensagem () /* Funcao simples: so imprime Ola! */{

printf ("Ola! ");return(0);

}int main (){

mensagem();printf ("Eu estou vivo!\n");return(0);

}

1.1. Saída igual ao “Primeiro Programa”Saída igual ao “Primeiro Programa”2.2. Diferença entre main() e o restoDiferença entre main() e o resto1.1. Saída igual ao “Primeiro Programa”Saída igual ao “Primeiro Programa”2.2. Diferença entre main() e o restoDiferença entre main() e o resto



• 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

FunçãoFunção

(3) ANSI C


• Expressão– Combinação de variáveis, constantes

e operadores

– Em C, toda expressão resulta em um valor• 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

– 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);

() [] ->! ~ ++ -- . -(unário)

(cast) *(unário)&(unário) sizeof

* / %+ -

<< >><<= >>=

== !=&^|

&&||?

= += -= *= /=

Tabela de PrecedênciaTabela de Precedência

MAIORMAIOR

prec

edên

cia

prec

edên

cia

menormenor

Tabela de PrecedênciaTabela de Precedência

(3) ANSI C


• 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

Palavras reservadasPalavras reservadas

(3) ANSI C

Documents

Prof. Frederico Brito Fernandes [email protected] Estrutura, Pesquisa e Ordenação de Dados CONTEÚDO (1) Apresentação da disciplina (2) Compilador DevC++