Apresentação do Curso
Núcleo de Computação Aplicada NCA - UFMA
Dep. de Informática - Universidade Federal do Maranhão
Estrutura de Dados I
} Objetivo } Programação
} consolidar os conhecimentos em } Apresentação do Curso
algoritmos, programação e } Práticas de Programação
desenvolvimento de programas } Vetores e Matrizes
} familiarizar com as principais } Tipos de Dados Abstratos
estruturas de dados.
} Pilhas e Filas
} Desenvolver capacidade de
raciocínio abstrato e modelagem } Listas
baseada em dados e comportamento } Complexidade de Algoritmos
} Apresenta noções de } Árvores
complexidade, as estruturas de
dados lineares e as árvores
Bibliografia
} Tenembaum, A.M.; Langsam,Y.; Augenstein, M.J. Estruturas de Dados Usando C, São Paulo, Makron
Books, 1995.
} Velloso, P., Estruturas de Dados, Rio de Janeiro: Campus. 1991.
} W. Celes, R. Cerqueira, J. L. Rangel. Introdução a Estruturas de Dados, Editora Campus Elsevier, 2004
} Borin, Vinícius Pozzobon, Estrutura de dados [recurso eletrônico] / Vinícius Pozzobon Borin. Curitiba:
Contentus, 2020.
} Edelweiss, Nina. Estruturas de dados [recurso eletrônico] / Nina Edelweiss, Renata Galante. – Dados
eletrônicos. – Porto Alegre : Bookman, 2009.
} ZIVIANI, Nivio Projetos de Algoritmos com Implementações em Pascal e C , Livraria Pioneira Informática ,
1993
} Thomas H. Cormen ... [et all], Algoritmos : teoria e prática 1; tradução da segunda edição [americana]
Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 –
} KNUTH, Donald E., The Art of Computer Programming, Volume I, Third Edition, Addison-Wesley, 1997
} Weiss, M. A. Data Structures and Algorithm Analysis in C, Benjamin/Cummings Publishing Co., 1993.
} Leung, B., Tondo, C. L., Kruse, R. L. Data Structures and Program Design in C, Prentice Hall, 1997.
Avaliação
} Frequências:
} Obrigatória – Curso exclusivamente presencial
} Listas de Exercício:
}Manuscritas (digitalizadas/fotografadas) postadas no Google
Classroom
} Trabalhos de Implementação
} Exclusivamente individuais apresentado para o professor/monitor
pelo google meeting
} Avaliação: Corretude e Qualidade do código escrito
} Regras da Resolução Acadêmica da UFMA seguidas
rigorosamente.
Avaliação
} Notas: } Reposição
} Notai(i = 1, 2 ou 3) = α *Pi + (1- α)*MTi +1 } Primeira Nota
# "#$%&$ '(%)*+,*$ } Prova - Assunto da primeira prova
α = 0,8 ∗ ( )
# -.%&/ "#$%&$ } Segunda Nota
} Pi } Prova - Assunto da segunda prova
}Nota da Prova } Terceira Nota
} MLi } Prova - Assunto da terceira prova
}Média das Notas das Listas de exercício
} MTi
}Médiadas Notas dos Trabalhos de
Implementação
Princípios de Programação
Estrutura de Dados
Prof. Anselmo C. de Paiva
Departamento de Informática – Núcleo de Computação Aplicada NCA-UFMA
“Any fool can write code that a computer can
understand. Good programmers write code that
humans can understand. (Martin Fowler)”
1 - Estilo de Programação
} Regras usadas ao codificar um } Bom estilo de código:
programa } lógica direta
} facilitar a leitura do código. } expressão natural
} Escrever bem -> código mais } uso convencional da linguagem
correto. } nomes significativos
} Base: } formatação simples
} bom senso e experiência, } comentários úteis
} consistência. } KISS
} Keep It Simple Sujeito
Estilo de Programação - Nomes
} Nome de uma variável ou função } Escopo mais amplo
} rotula um objeto } mais informações devem ser
} veicula informações sobre seu veiculadas no nome.
propósito.
} Convenções de nomeação
} Deve ser: facilitam
} informativo, } compreensão do código
} conciso,
} invenção de novos nomes
} memorizável
} pronunciável.
Estilo de Programação - Nomes
} Use nomes descritivos para variáveis globais e nomes curtos para
variáveis locais
Globais: Locais: RetornaNumeroDePontos
int numEntradas; int n;
int nPontos;
int numeroDePontos; !!exagero
} Variáveis globais usadas de maneira tradicional requerem nome
curto.
} i, j contadores de loop. p,q ponteiros. s, t strings
for(indiceElemento=0; indiceElemento<numeroElementos; indiceElemento++) {
vetorElementos[indiceElemento] = indiceElemento;
}
for(i=0;i<numElem;i++) {
elem[i] = i;
}
Estilo de Programação - Nomes
} Seja consistente:
} coisas relacionadas -> nomes relacionados
} mostram relacionamento e destaca diferenças.
typedef struct _Fila_ { typedef struct _Fila_ {
int noDeItensNaF, int numItens,
primeiroDaFila, primeiro,
filaCapacidade; capacidade;
} Fila; } Fila;
} Use nomes ativos para função:
} baseados em verbos ativos, que podem ser seguidos por substantivos
agora = pegaHora(); numElem = RetornaNumElems();
} Renomear funções que retornam valores lógicos
} evitar ambiguidades
if( checkOctal(c)) …. If( IsOctal(c)) …..
Estilo de Programação - Nomes
} Seja preciso:
} nome não apenas rotula, ele veicula informações para o leitor.
} nome enganoso pode resultar em bugs difíceis de resolver.
#define isoctal(c) ( (c) >=‘0’ && (c) <= ‘7’)
#define isoctal(c) ( (c) <‘0’ && (c) > ‘7’)
Estilo de Programação - Expressões e Declarações
for (i=0;i<37;i++) {
} Escreva expressões de maneira clara.
} Use espaços nos operadores p/ sugerir agrupamento }
} Recue para mostrar a estrutura
for(n++;n<100;campo[n++]=‘\0’); for(n++;n<100;campo[n++]=‘\0’) { for(n++;n<100;n++){
*i = ‘\0’; return(‘\n’); ; campo[n]=‘\0’;
n++;
} }
*i = ‘\0’; *i = ‘\0’;
return(‘\n’); return(‘\n’);
} Use forma natural das expressões:
} escreva expressões como vc as falaria em voz alta.
Expressões condicionais com negações são sempre difíceis de entender
if( !(blocoId < blocoAtivo) || !(blocoId >= numBlocos)) …
if( blocoId >= blocoAtivo) || (blocoId < numBlocos)) …
Estilo de Programação - Expressões e Declarações
} Parênteses para resolver as ambiguidades,
} Não confie na ordem de precedência dos operadores
if(x&MASCARA == BITS) significa:
if(x&(MASCARA == BITS)) ou if((x&MASCARA) == BITS))
} Mesmo quando não necessários os parênteses podem ajudar se o agrupamento
da expressão for difícil de entender
ano = y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
ano = ((y % 4 == 0) && (y % 100 != 0)) || (y % 400 == 0);
} Divida as expressões complexas
*x +=(*xp=2*k < (n-m)? c[k+1] : d[k--];
if(2*k < (n-m)) {
*xp = c[k+1];
} else {
*xp : d[k--];
}
Estilo de Programação - Expressões e Declarações
} Seja Claro if(LC == 0 && RC == 0 ) {
child = 0;
}else if (LC == 0 ) {
} Operador ?: pode levar a construções
child = RC
misteriosas } else {
child = (!LC&&!RC)?0:(!LC?RC:LC);
child = LC
}
} Cuidado com os efeitos colaterais
str[i++] = str[i++];
vetor[i++] = i;
scanf(“%d %d”, &yr, &teste[yr]);
Estilo de Programação - Consistência e Idiomas
} Mesmo cálculo é feito sempre da mesma maneira
} Toda variação sugere uma diferença genuína e digna de nota.
} Use um estilo de identação e chaves consistente
} Use idiomas pra ter consistência:
} linguagens de programação tem maneiras convencionais pelas
quais os programadores experientes escrevem código comun.
i=0; for(i=0; i<n; ){ for( i = 9; i < n; i++) {
while(i < n-1) { array[i++] = 1.0; array[i] = 1.0;
array[i++] =1.0; } }
}
forma idiomática mais usada
} Recuo tambem deve ser idiomático
Estilo de Programação - Macros de função
} Justificativa: overhead de uma chamada de função.
} Hoje em dia
} irrelevante e suas desvantagens superam em muito seus benefícios.
} Evite macros de função.
} Problemas:
} parâmetro que aparece mais de uma vez na definição poderia ser avaliado mais de uma vez.
#define isupper(c) ((c) >= ‘A’ && (c) <= ‘Z’)
chamada assim: while (isupper(c=getchar())) …
toda vez que um caracter de entrada maior ou igual a A for lido, ele será descartado e outro caractere
será lido para ser testado com relação a Z.
} Inevitável usar macros?
} coloque o corpo e os argumentos da macro entre parênteses.
1/square(x) #define square(x) (x) * (x) 1/ (x) * (x)
#define square(x) ((x) * (x)) 1/((x)*(x))
Estilo de Programação - Números mágicos
} Valores numéricos literais que aparecem nos programas
} constantes, tamanhos de vetores, posições de caracteres, fatores de conversão.
} Dê nome aos números mágicos:
} todo numero diferente de 0 ou 1 pode ser mágico e deve receber seu próprio nome.
} Exemplo: Calcular um histograma de frequência de letras em terminal com 24x80
#define LIM 30 fac = lim/20;
fac = lim/LIM; if(fac < 1) {
draw(23, 2, ' '); /* eixo x de rótulo */
if(fac < 1) { fac = 1;
for(i='A'; i<= 'Z';i++) {
fac = 1; }
printf("%c ", i);
} /* gerar histograma */
}
/* gerar histograma */ for( i = 0, col = 0; i < 27; i++, j++) {
for( i = 0, col = 0; i < 27; i++, j++) { col += 3;
#define TRUE 1
col += 3; k=21-(let[i]==0);
#define FALSE 0
k=LIM+1-(let[i]==0); star = (let[i] == 0 ) ? ' ' : '*';
#define TAM_COFO 20
star = (let[i] == 0 ) ? ' ' : '*'; for(j=k; j<22; j++) {
for(j=k; j<LIM+2; j++) { draw(j, col, star);
draw(j, col, star); }
} }
Estilo de Programação - Números Mágicos
O código inclui entre outros números 20, 21, 22, 23 e 27
Podemos verificar que existem três números críticos
24 - número de linhas da tela; 80 - número de colunas e
26 - número de letras do alfabeto
O código então fica assim:
enum {
MIN_ROW = 1, /* lado superior */ for( i = 0; i < NLET; i++) { /* gerar histograma
MIN_COL = 1, /* lado esquerdo */ */
MAX_ROW = 24, /* lado inferior (<=) */ if ( let[i] != 0 ) {
MAX_COL = 80, /* lado direito (<=) */ for (j=HEIGHT-let[i]/fac; j<HEIGHT; j++) {
LABEL_ROW = 1, /* posição dos rótulos */ draw(j+1 + LABEL_ROW, (i+1)*WIDTH, '*');
NLET = 26, /* tamanho do alfabeto */ } /* rof */
HEIGHT = MAX_ROW - 4, /* altura das barras */ } /* fi */
WIDTH = (MAX_COL-1)/NLET /* larg. barras */ } /* rof */
}
fac = (lim + HEIGHT -1)/HEIGHT; draw(MAX_ROW-1, MIN_COL+1,' '); /* eixo x
if(fac < 1) { de rótulo */
fac = 1;
} for(i='A'; i<= 'Z';i++) {
printf("%c ", i);
}
Estilo de Programação - Números Mágicos
} Defina os números mágicos inteiros como enum.
} Use o #define apenas para constantes reais
} Use constantes de caracteres não inteiros
if ( c >= 65 && c <= 90 ) ...
if ( c >= 'A' && c <= 'Z' ) …
} Use a linguagem para calcular o tamanho de um objeto
} Não use nenhum tamanho explícito para tipos de dados
} Use sempre sizeof(int) ao invés de 2 ou 4
} Para calcularn o tamanho de um vetor em C use a seguinte macro:
#define NELEMS(vetor) (sizeof(vetor)/sizeof(vetor[0])
este é um uso apropriado para uma macro porque faz algo que uma função não faria, calcular o
tamanho de um vetor a partir de sua declaração.
Estilo de Programação - Comentários
} Destinam-se a ajudar o leitor de um programa.
} Não enfatize o óbvio:
/* default */ /* retorna SUCCESS */ /* incrementa o contador de entrada zero */
default: return SUCCES; zerocount++
…
} Comente funções, dados globais, definições de constantes, campos
de estruturas, e tudo que o comentário possa auxiliar na
compreensão.
typedef struct _state_ { /* prefixo + lista de sufixos */
char *pref[NPREF]; /* palavras de prefixo */
Suffix *suf; /* lista de sufixos */
State *next; /* próximo da tabela */
} State;
} Um comentário que apresenta cada função, prepara a leitura do
próprio código.
/* random : retorna um inteiro na faixa [0..r-1] */
int random ( int r ) {
...
Estilo de Programação - Comentários
} Código realmente difícil -> comentário que indique uma
referência que possa auxiliar o leitor
/*
* idct: Implementação da transformada discreta do cosseno.
* Algoritmo de Chen-wang ( IEEE ASSP-32, págs. 803-816, Agosto de 1984).
*/
static void idct (int b[8*8])
{
...
} Não comente código ruim rescreva-o.
} Não contradiga o Código
} Ao solucionar um bug não se esqueça de verificar se os
comentários estão de acordo com as suas modificações no código
2 - Depuração
} Bug
} "Um defeito ou falha em uma máquina, plano, ou similar”.
} Origem EUA 1889 Paull Mall Gaz. …
(Oxford English Dictionary, 2nd Edition)
} Passa-se tanto tempo depurando quanto escrevendo bons
programas.
} Técnicas para reduzir tempo de depuração:
} bom projeto;
} bom estilo;
} testes de condições limites;
} programação defensiva;
} ferramentas de verificação;
Depuração - Boas pistas, bugs fáceis
} Procure padrões conhecidos
int n; int n; GITHUB
scanf("%d",n); scanf("%d", &n); CopiaArquivo
} Examine a alteração mais recente
} preserve a versão correta anterior do código;
} mantenha registro das alterações feitas;
} procure usar um sistema de controle de código(Ex. RCS, SourceSafe,
git, etc.)
} Não cometa o mesmo erro duas vezes
} verifique se a mesma construção errada não foi usada em outros
locais do código
} Depure agora, não mais tarde
} mesmo que o bug não lhe atrapalhe, procure-o logo
Depuração - Boas pistas, bugs fáceis
} Obtenha um rastreamento de pilha
} depuradores possibilitam exame do estado pós-morte do programa;
} número da linha de código onde ocorreu a FALHA (ERRO)
} Leia antes de digitar
} leia e analize o código fonte antes de tentar fazer alterações para
encontrar o problema;
} Explique seu código para outra pessoa (ursinho)
Lista de Exercício 01 – Depuração
} Faca um texto descrevendo como usar as seguintes funcionalidades na
IDE de programação em C que voce usa.
a) Executar o seu programa passo a passo (uma linha de código por vez).
b) Executar o seu programa até uma linha de código especifica ( marca) break
point
c) Executar uma chamada de uma função sem entrar nela
d) Executar uma chamada de função entrando na função para executa-la linha a
linha
e) Mostrar todas as chamadas de função ate a linha de código onde esta parada
a execução
f) Consultar o valor de uma variável com a execução parada numa linha de
código
g) Colocar uma janela informando o valor de uma variável enquanto estou
executando o código passo a passo.
Depuração - Boas pistas, bugs fáceis
} Procure padrões conhecidos
int n; int n;
scanf("%d",n); scanf("%d", &n);
} Examine a alteração mais recente
} preserve a versão correta anterior do código;
} mantenha registro das alterações feitas;
} procure usar um sistema de controle de código(Ex. RCS, SourceSafe,
etc.)
} Não cometa o mesmo erro duas vezes
} verifique se a mesma construção errada não foi usada em outros locais do
código
} Depure agora, não mais tarde
} mesmo que o bug não lhe atrapalhe, procure-o logo
Depuração -Sem pistas, bugs difíceis
} Torne o bug reproduzível
} gaste algum tempo construindo entrada e definições de parâmetro que certamente
causarão o problema;
} Divida e conquiste
} crie o menor exemplo possível que reproduz o bug
} Utilize o depurador printf
} coloque impressões de mensagens "passei por aqui", ou com a impressão de
resultados intermediários no meio do código
} Escreva código autoverificador
} caso seja necessário escreva funções que testam se determinado estado do
programa esta ok.
} Desenhe uma figura
} Use as ferramentas
} Mantenha registros das alterações
Depuração - Bugs não reproduzidos
} Verifique se todas as variáveis foram inicializadas
} Se o erro muda de comportamento ou desaparece qdo código
de depuração for adicionado, pode ser um erro de alocação de
memória
} Quando um programa funciona com uma pessoa e falha pra
outra: pode ser o ambiente externo:
} arquivos lidos
} permissões de acesso aos arquivos
} caminho de pesquisa dos comandos(path)
3 - Testes
} Depuração:
} aquilo que vc faz quando sabe que um programa está com problemas.
} Teste:
} tentativa determinada e sistemática de quebrar um programa que você
acha que esta funcionando.
} "Testes podem demonstrar a presença de um bug mas não sua
ausência" (Edsger Dijkstra)
Testes -Teste Enquanto codifica
} Qdo mais cedo um problema for encontrado melhor;
} Teste o código nos seus limites:
} "Teste da condição limite"
} a medida que cada parte do código é escrita verifique logo se a
condição se ramifica na direção certa ou se o loop tem o número
adequado de repetições.
} Teste as pré e pós condições
} verifique se as propriedades esperadas ou necessárias mantidas
antes(precondição) ou depois (pós-condição) de alguma parte do
código são executadas.
} Verifique se os valores de entrada são aceitáveis
} Verifique o retorno de erro
Testes - Teste sistemático
} Teste incrementalmente
} Teste primeiro as partes mais simples
} Ex: Teste sistematico de uma função que executa pesquisa binária em
um vetor de inteiros
} vetor sem elementos
} vetor com um elemento e um valor de pesquisa:
} menor que o elemento único do vetor
} igual ao elemento único do vetor
} maior ao elemento único do vetor
} vetor com dois, três e quatro elementos e valores experimentais que testem as
várias posições possíveis (cinco para o vetor com dois elementos)
} vetor com elementos repetidos e valor de pesquisa:
} menores, iguais ou maiores que os valores do vetor
4 - Desempenho
} Quando devemos agilizar um programa?
} somente se o problema for importante e houver possibilidade dele
ficar mais rápido mantendo a mesma robustez, correção e clareza.
} Primeiro princípio: "Não otimize"
} Como podemos fazer isso?
} Quais ganhos podemos esperar?
Desempenho - Sincronização e perfil
} Automatize as medições de sincronização
% time slowprogram clock_t before;
real 7.0 double elapsed;
user 6.2 before = clock();
sys 0.1 slow_function();
elapsed = clock() - before;
printf("function used %.3f seconds\n",
elapsed/CLOCKS_PER_SEC);
} Use um profiler - gerador de perfis de programas
} perfil - medida de onde o programa gasta seu tempo
} util para determinar os gargalos do programa
} "Menos de 4% de um programa geralmente representam mais da metade
de seu tempo de execução" (Don Knuth)
% cc -p spamtest.c -o spamtest
%spamtest
prof spamtes
Desempenho - Sincronização e perfil
} Concentre-se nos gargalos
} Desenhe uma figura
Testes - Teste sistemático
} Saiba qual saída deve esperar
} Verifique as propriedades de conservação
Leitura Suplementar
Esta seção é completamente baseada no livro:
Kernighan, B. W. e Pike, R. "A Prática da Programação", Ed. Campus, Rio
de Janeiro, 1999.
Outras Referências sobre o Assunto:
Kernighan, B. W. e Plauger, P. J. "The Elements of Programming Style", McGraw-Hill, 1993.
Maguire, S. "Writing Solid Code"Microsoft Press, 1993.
