A unidade curricular se compõe de conhecimentos relacionados às estruturas de dados, com ênfase em sua utilização na escrita de programas.
Usar as estruturas de dados fila, pilha, lista, tabela de dispersão e árvore binária na escrita de programas;
Identificar as situações e necessidades em que cada estrutura de dados é apropriada;
Conhecer o custo computacional das operações elementares das estruturas de dados, e de algoritmos de busca e ordenamento, para que se possam utilizá-los de forma eficiente;
Conhecer o custo computacional das operações elementares das estruturas de dados, e de algoritmos de busca e ordenamento, para que se possam utilizá-los de forma eficiente;
Os estudos serão guiados por leituras, exercícios, e projetos. O conteúdo da unidade curricular será apresentado por meio de aulas expositivas e aulas práticas de maneira articulada com aplicações do conhecimento.
3.3 Recursos auxiliares
Utilização do sistema acadêmico SIGAA para avisos e registro de frequência
Utilização do moodle para atividades complementares e registros de participação em aula.
4 Referências bibliográficas
4.1 Básica
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. LTC, 2012. (link para minha biblioteca - necessário logar via SIGAA primeiro)
LORENZI, Fabiana; MATTOS, Patrícia de; CARVALHO, Tanisi de. Estruturas de dados. Cengage Learning, 2006. ISBN 978-8522105564.
4.2 Complementar
BACKERS, André. Linguagem C: completa e descomplicada. Grupo GEN, 2023. (link para minha biblioteca - necessário logar via SIGAA primeiro)
KERNIGHAN, Brian W.; RITCHIE, Dennis M. C. A Linguagem de Programação Padrão Ansi. Elsevier, 1989. ISBN 978-8570015860.
O arquivo “.c” é o código-fonte de nosso projeto, é onde digitaremos o código na linguagem C. Trata-se de um arquivo texto simples, porém respeitando a sintaxe do C.
Para editar o arquivo “.c” podemos utilizar qualquer editor como o “gedit” do linux que é bem parecido com o “bloco de notas” do windows.
Depois de criar o arquivo precisaremos compilar este código para transformá-lo em executável e finalmente poder rodá-lo, para compilar utilizaremos o compilador gcc do linux.
Passo-a-passo criando o OlaMundo.c
Abra o gedit com um texto em branco e salve em sua pasta de projetos com o nome “OlaMundo.c”
Digite dentro do arquivo em branco criado o seguinte código:
#include<stdio.h>main(){printf("Olá Mundo!\n");}
Certifique-se de salvar o arquivo “OlaMundo.c” após as alterações
No terminal dê um comando ls para listar os arquivos do diretorio, como resultado deve ser exebido o arquivo OlaMundo.c que você criou no gedit
~/ExerciciosC$ ls
OlaMundo.c
</syntaxhighlight>
No terminal compile o código através do gcc. Neste exemplo a pasta “ExerciciosC” foi criada para gravar o projeto, do gedit foi salvo nesta pasta o programa “OlaMundo.c”. Como resultado nenhuma mensagem deve ser exibida, o terminal simplesmente irá ficar pronto para um novo comando, isso significa que compilou com sucesso (sem erros)
Dê um novo comando ls para listar os arquivos do diretorio, como resultado deve ser exibido dois arquivos, o OlaMundo.c e agora o OlaMundo, um arquivo executável criado pelo compilador
~/ExerciciosC$ ls
OlaMundo OlaMundo.c
</syntaxhighlight>
Execute OlaMundo através do comando a seguir. Observe a mensagem “Olá Mundo!” exibida no terminal.
Observe que foi realizada uma declaração antes da função main. Isto é necessário para utilização do comando de impressão em tela, o printf utilizado abaixo.
include <stdio.h> </syntaxhighlight>
Observe que não foi definido um retorno para main, o compilador deverá tratar esta função com retorno int
A instrução realizada em código é de impressão em tela, neste caso a tela (terminal visualizado pelo monitor) é a saída padrão (standard)
printf("Olá Mundo!\n");</syntaxhighlight>
Enfim, observe que não foi especificado um retorno, do tipo “return”. Isso faz com que o retorno deste programa seja indefinido
Identificadores
São os nomes que o programador dá a suas variáveis, constantes e funções
Deve sempre iniciar com uma letra ou “_” (underscore )
A partir do segundo caracter pode também conter números
A linguagem não suporta caracteres especiais como letras acentuadas
Identificadores não podem ser escritos com espaço, exemplo “buscarCodigo()”, não pode ser escrito como “buscar codigo()”
A linguagem C é case-sensitive. Por exemplo, as variaveis “numero”, “Numero” e “NUMERO” são endereços diferentes
Deve ter no máximo 31 caracteres (compatível com TurboC)
Boas práticas quanto a identificadores
O uso de nomes auto-explicativos facilita a compreensão e manutencão futura
É comum variar maiúsculas e minúsculas para facilitar a leitura como “QtMedidas”, “ValorMedio”
Por uma questão de eficiência de uso de memória e processamento o C possui diversos tipos de variáveis, vamos agora trabalhar com alguns deles que servirão para praticamente todas as nossas necessidades
char: ocupa 1 byte na memória e varia de -127 a +127
int: ocupa 4 bytes e varia de -2.147.483.648 a +2.147.483.647
double: ocupa 8 bytes e possui dez dígitos de precisão
char[]: esta é o mesmo char descrito acima mas aqui simbolizando uma cadeia/vetor de caracteres (string)
Apenas para conhecimento neste momento, há outros tipos como short, float e long double e os tipos que não são de precisão podem ainda ser signed ou unsigned
Como funciona a memória de computadores? - Khan Academy
Digite dentro do arquivo em brando criado o seguinte código:
#include<stdio.h>main(){intx;/* declaração de uma variável inteira */x=5;/* atribuindo o valor 5 (constante) a variável x */printf("O valor de x é %d\n",x);}
Observe que o C permite também que uma variável seja inicializada com determinado valor no momento de sua criação. Ex.:
#include<stdio.h>main(){intx=5;/* declaração de uma variável inteira atribuindo o valor 5*/printf("O valor de x é %d\n",x);}
Compile e execute
Continuação da teoria
C é uma linguagem “compilada”, ou seja, de um código fonte (escrito em C) são gerados códigos de máquina formando um ou mais arquivos executáveis e inteligíveis apenas para o computador
Há diversos compiladores e estes podem ter algumas diferenças de comportamento e aceitarem diferentes parametrizações
Um código é compilado para um sistema operacional específico e uma arquitetura de processador, portanto, um código compilado para um S.O. não tem qualquer garantia de funcionamento em outros sistemas. Da mesma forma um código que roda em um PC, não tem qualquer garantia de rodar em outras arquiteturas diversas
Em oposição ao código compilado temos o código interpretado
Sempre que um código fonte é modificado se faz necessário nova compilação para que as modificações façam efeito na execução
As variáveis que serão utilizadas pelo programa devem ser listadas antecipadamente
A linguagem C tem um conjunto de palavras reservadas, que não podem ser utilizadas para outro propósito se não o que está definido na estrutura da linguagem
Exemplos: break, case, if, for, while, return,...
O C permite que trabalhemos com bibliotecas (lib) que são conjuntos de funções que realizam certas tarefas
Além de podermos criar nossas próprias bibliotecas com funções úteis que podemos reutilizar em vários programas, também podemos nos apropriar de diversas libs já desenvolvidas, sejam padrão ANSI (libc) ou não, desta forma não precisamos “reinventar a roda” e já sair de largada com várias funcionalidades
Exemplos: <stdio.h>, <math.h>, <complex.h>, <float.h>, <string.h>, etc. (são 24 padrão ANSI no total)
Entendendo a compilação
Edição: atividade feita pelo programador
Preprocessamento: compilador processa o código e ignorando comentários, fazendo associações de constantes e controle de código através de diretivas especiais de compilação
Compilação: criação do código-objeto, é a tradução da linguagem C em linguagem de máquina
Linkagem: associação de diferentes código-objeto e bibliotecas
Carregamento: carrega o programa em memória
Execução: cpu realiza a execução das instruções passo a passo, armazenando os resultados em memórias definidas pelo programa e pilhas de dados para controle
Comentários
Como vimos podemos incluir no programa fonte textos livres que ajudam na compreensão do código
Os comentários são ignorados pelo compilador, não se tornam código de máquina
Para incluir comentários inicie com /* digitando então o comentário aqui e terminando com */
Este formato permite que digitemos varias linhas de comentários, normalmente é utilizado para textos mais extensos
A maioria dos compiladores também aceita o formado //comentário, que serve para incluir um comentário de apenas uma linha, apenas os caracteres depois do // serão ignorados e neste caso o terminador é o sinal de nova linha que normalmente está oculto
Operadores aritméticos
“+” adição
“-” subtração
“*” multiplicação
“/” divisão
“%” resto da divisão
Por padrão, multiplicações e divisões são operadas antes de somas e subtrações
Devemos utilizar parênteses para agrupar operações e definir a sequencia mais adequada. O compilador vai sempre resolver o que está dentro dos parênteses primeiro, de “dentro para fora” quando houver mais de um nível
Exemplos
1+2*3 = 7 é o mesmo que 1+(2*3)
(1+2)*3 = 9
1+2*3+4*5 = 27 é o mesmo que 1+(2*3)+(4*5)
(((1+2)*3)+4)*5 = 65
Escrevendo mensagens na tela (saída de dados)
A função printf da lib stdio é bastante completa para esta tarefa, permite escrever mensagens com múltiplos argumentos.
Formato printf (“string de controle”, lista de argumentos);
Exemplo:
printf(“Olá Mundo!\n”);
printf(“Digite sua idade:\n”);
printf(“Sua idade é: %d”,idade);
Para saber mais sobre o printf e seus identificadores ver c_function_printf
Lendo o teclado do usuário (entrada de dados)
A função scanf da lib stdio é bastante útil para esta tarefa, ela aguarda que o usuário entre com uma informação e tecle [ENTER] no final.
Esta função é blocante, ou seja, o programa fica parado esperando a entrada de dados para então dar continuidade a execução
Formato scanf (“string de controle”, lista de argumentos);
Exemplo:
scanf(“%d”,&idade);
Operadores relacionais e lógicos
Relacionais
> maior que, ex.: Se (i > j) printf(“i é maior que j”);
>= maior ou igual que, ex.: Se (i >= j) printf(“i é maior ou igual a j”);
< menor que, ex.: Se (i < j) printf(“i é menor que j”);
<= menor ou igual que, ex.: Se (i <= j) printf(“i é menor ou igual a j”);
Igualdade
== igual a, ex.: Se (i == j) printf(“i é igual a j”);
!= diferente de, ex.: Se (i != j) printf(“i é diferente de j”);
Lógicos
&& Lógica E (AND), ex.: Se (i > j) && (i > 0) printf(“i é maior que j e positivo”);
|| lógica OU (OR), ex.: Se (i > j) || (i == 0) printf(“i é maior que j ou é igual a zero”);
! Lógia negação (NOT), ex.: Se !(i > j) printf(“i não é maior que j”);
Exercícios
Implemente um programa em C que calcula a média de dois números reais digitados pelo usuário e imprime em tela a resposta deste cálculo
Implemente um programa em C que recebe “a”, “b” e “c”, calcula e exibe o delta (delta = b*b-4ac).
Implemente um programa em C que calcule a Potência dissipada por uma carga dados V e I.
Implemente um programa em C que calcula a resistência R dados P e I.
Implementar um programa C para converter um ângulo em radianos para graus.
Implementar um programa C para converter um ângulo em graus para radianos.
Condicionais em C
A declaração “if (expressão) corpo”
Permite o programa escolher por duas alternativas, executando o procedimento presente no corpo ou não
O parênteses é obrigatório
A expressão pode conter múltiplos testes
“if” se escreve com letras minúsculas
O corpo com múltiplos comandos deve ficar dentro de {chaves}
Implementar um programa que lê um número inteiro e imprime se o número é par ou ímpar. SUGESTÃO: Usar o operador de resto.
Um estudo sobre sensibilidade de pessoas a temperaturas da água identificou que a maioria das pessoas considera fria a água com temperaturas abaixo de 25 graus, morna entre 25 e 30 graus, e quente acima de 30 graus. Escreva implemente em C um algoritmo que mostre as palavras "fria", "morna" ou "quente" dependendo da temperatura da água que for informada.
Implementar um programa em C para ler dois números inteiros e imprime uma mensagem indicando se os números lidos são iguais ou diferentes. Caso sejam diferentes, computar a média dos mesmos.
Implementar um programa para ler 4 números inteiros e imprime uma mensagem se a soma dos dois primeiros for igual ou menor que a soma dos dois últimos.
Implemente um programa em C que recebe duas datas fornecidas pelo usuário (três números inteiros cada: dia, mês e ano com 4 dígitos). Deve ser calculada qual a maior data e exibi-la em tela (pesquise sobre if...else para resolver este problema)
Implementar um programa para ler dois números reais e, na sequência, um número inteiro. Se o número inteiro for 1 os dois números iniciais deverão ser somados, se for 2 eles serão subtraídos, se for 3 eles serão multiplicados e se for 4 serão divididos. Mostrar mensagem de erro se o número inteiro não estiver na faixa de 1 a 4. Mostrar mensagem caso a divisão não seja possível.
Melhore o programa de cálculo de delta, e calcule as raízes de uma equação de segundo grau. Faça testes para saber se há duas raízes reais (delta > 0), apenas uma (delta = 0) ou não há raízes reais (delta < 0). Usar a função sqrtf ou sqrt de <math.h> (utilizando funções de math.h talvez seja necessário adicionar a flag "-lm" na compilação).
Uma empresa irá ajustar o salário de seus funcionários de acordo com a categoria de trabalho dos funcionários: CAT A (10% de aumento), CAT B (15% de aumento) e CAT C (20% de aumento). Faça um programa que leia o plano de trabalho e o salário atual de um funcionário e calcula e imprime o seu novo salário. Use o comando switch.
Faça um programa que leia um número entre 0 e 10, e escreva este número por extenso. Use o comando switch.
Estruturas de repetição em C
Vídeos
O que é uma estrutura de repetição? Chris Bosh em Code.org
#include<stdio.h>main(){intopcao;while(opcao!=2){system("clear");printf("MENU\n");printf("0: Faz isso\n");printf("1: faz aquilo\n");printf("2: Sair\n");scanf("%d",&opcao);switch(opcao){case0://Faz isso break;case1://faz aquilobreak;case2:printf("Saindo...\n");break;default:printf("Opção inválida\n");}}}
Exercícios - C
Assistir os vídeos da sessão "Condicionais em C" e "Estruturas de repetição em C"
Dado um número inteiro positivo, calcular a soma de todos os números inteiros compreendidos entre 0 e o número dado. Fazer uma versão com while e outra com for.
Faça um algoritmo que apresente a sequencia de Fibonacci dado um valor “n” que representa a quantidade de números em série que se deseja exibir
Desenvolva uma algoritmo em C para marcar o placar de um jogo de futebol, deve solicitar ao usuário digitar A ou B, ao digitar A é somado um gol a equipe A e o mesmo para a B. Se digitado F deve encerrar e mostrar o placar final.
Implemente um algoritmo em C que obtém um número do usuário e utilizando laço para verifica se um número primo. Valide seu algoritmo comparando com a lista de primos Lista de números primos
Escreva um algoritmo em C que solicita ao usuário digitar 6 números para uma aposta na megasena. O algoritmo deve utilizar a estrutura do...while, gravar em variaveis distintas cada número que deve estar entre 1 e 60. Deve garantir que os 6 números são diferentes entre si e no final mostrar os números digitados (id:1.06)
Implemente em C uma calculadora que realiza operações de soma ou subtração de dois números. A calculadora deve operar em um laço infinito encerrando sua operação se o usuário digitar "q"
Usando o comando for aninhado, construa um programa que implemente a figura abaixo. A margem esquerda (margem de espaços), o caracter do desenho, o número de linhas vazadas e o tamanho horizontal da figura devem ser lidos pelo teclado. Na figura abaixo representa uma saída quando a margem esquerda é 0, o caractere do desenho é 'a', o número de linhas vazadas é 1 e o tamanho horizontal é 10 (id.:1.08)
aaaaaaaaaa
a a
aaaaaaaaaa</syntaxhighlight>
Construa um programa para desenhar a seguinte figura de forma parametrizável (dado caracter, margem, e número de linhas):
AAAAAAAAAA
AAAAAAAA
AAAAAA
AAAA
AA
BB
BBBBB
BBBBBBBB
BBBBBBBBBBB</syntaxhighlight>