Programação Estruturada (TCC-00.347)

horários das aulas: terças de 9:00 às 11:00h na sala 202 e quintas de 9:00 às 11:00h no laboratório 306

Objetivos

Tópicos Abordados

• Arquivos;
• Recursividade;
• Ponteiros;
• Alocação Dinâmica de Memória;
• Conceito de Tipo Abstrato de Dado (TAD);
• Implementações alternativas para um mesmo TAD;
• Lista Simplesmente Encadeada, Lista Duplamente Encadeada, Lista Circular, Fila e Pilha;
• Algoritmos de Ordenação.

Critério de avaliação

Bibliografia básica

• T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill, 2009.
• J. Szwarcfiter e L. Markenzon, Estruturas de Dados e Algoritmos, LTC, 1994.
• W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus, 2004.
• B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Campus, Segunda Edição, 1990.

Bibliografia complementar

• A.M. Tenenbaum, Y. Langsam e M.J. Augenstein, Estruturas de Dados Usando C, Pearson, Primeira Edição, 1995.

Aulas ministradas

• 14/08/2018

  • Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
  • Datas importantes:
    • P1: 23/10/18
    • P2: 06/12/18
    • VR: 11/12/18
    • VS: 18/12/18
    • Entrega de todas as notas da disciplina (antes da VS): 13/12/18

• 16/08/2018

  • Compilação versus interpretação;
  • Introdução a linguagem C: tipos primitivos (char, short, long int, float, double e int), indicando a quantidade de bytes usados para armazená-los e suas representatividades, e variáveis (incluindo ponteiros);
  • Variáveis globais versus locais: tempo de vida e visibilidade; e
  • Exemplos.
    

• 21/08/2018

  • Definição de constantes;
  • Operadores: aritméticos, de incremento, de decremento, relacionais, lógicos e bit a bit;
  • Precedência de operadores; e
  • Entrada de dados usando scanf.
    

• 23/08/2018

  • Entrada e saída básicas (scanf e printf);
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break;
  • Exemplos ministrados em sala de aula; e
  • Exercícios.
    

• 28/08/2018

  • Seleção com switch; e
  • Exemplos ministrados em sala de aula:
    • simulação de uma calculadora infinita para operações básicas em inteiros;
    • impressão de todos os primos existentes até um número específico (o programa para quando esse número lido for menor ou igual a 1); e
    • descoberta do maior divisor comum entre dois números lidos (o programa para quando esses números forem menores ou iguais a 0).
    
    

• 30/08/2018

  • Funções;
  • Pilha de execução;
  • Uso de ponteiros para alterar parâmteros de entrada; e
  • Variáveis estáticas.
    

• 04/09/2018

  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Alocação dinâmica de vetores;
  • Explicação das funções malloc, realloc e free da biblioteca stdlib.h;
  • Versões iterativas, void ss_v(int n, int *vet) e int* ss_ad(int n, int *vet), e recursiva, void ss_v_r(int n, int *vet), do algoritmo ordenação por seleção, com o uso na main; e
  • Exercícios.
    

• 06/09/2018

  • Exercícios em laboratório sobre vetores:
    • separação de ímpares e pares num vetor, mantendo a ordem de entrada original (as versões iterativas void ip_v(int n, int *vet) e int* ip_ad(int n, int *vet)); e
    • leitura de elementos de um vetor, desprezando os elementos que não estão em ordem crescente (as versões iterativas void lc_v(int n, int *vet) e int* lc_ad(int n)).
    
    

• 11/09/2018

  • Escrita das funções void lc_v(int n, int *vet) e int* ip_ad(int n, int *vet), incluindo uma main para testá-las;
  • Declaração de matrizes;
  • Passagem de matriz como parâmetro de entrada de funções;
  • Alocação dinâmica de matrizes;
  • Exercício: escrita da função que retorna, ou a matriz triangular inferior, se a matriz passada como parâmetro de entrada é simétrica, ou NULL, se a matriz de entrada não for simétrica; e
  • Exercícios.
    

• 13/09/2018

  • Exercícios em laboratório sobre matrizes:
    • retornar a transposta de uma matriz - int** transp(int **mat, int l, int c);
    • verificar se duas matriz são idênticas - int ig(int **mat1, int l1, int c1, int **mat2, int l2, int c2);
    • testar se uma matriz é um quadrado mágico (uma matriz é um quadrado mágico se a soma dos elementos de cada linha é igual a soma dos elementos de cada coluna é igual a soma dos elementos das diagonais) - int qm(int **mat, int n); e
    • verificar se uma matriz é um quadrado latim de ordem n (uma matriz é um quadrado latim se todas as linhas possuem os elementos de 1 a n, mas nenhum desses elementos podem se repetir em qualquer coluna) - int ql(int **mat, int n).
    
    

• 18/09/2018

  • Implementação da função que testa se uma matriz é um quadrado latim de ordem n - int ql(int **mat, int n);
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Exemplo de aplicação: escrita da função (nas versões iterativa e recursiva) strcmp da biblioteca string.h; e
  • Exercícios.
    

• 20/09/2018

  • Exercícios em laboratório sobre cadeia de caracteres:
    • trocar os caracteres pares e ímpares de uma string - void troca_rec (char *s), void troca_v (char *s) e char* troca_aloc_din (char *s);
    • testar se duas strings são inversas - int inv (char *s1, char *s2);
    • contar quantas vezes a string s1 está contida em s2 - int quant(char *s1, char *s2); e
    • verificar se uma string é uma "boa" senha (uma "boa" senha é uma senha com as seguintes características de formação: (i) ela possui, no mínimo, oito caracteres; (ii) ela tem, no mínimo, um caracter entre '0' a '9'; (iii) ela possui, no mínimo, uma letra maiúscula; (iv) ela tem, no mínimo, uma letra minúscula; e (v) ela possui, ao menos, um caracter do conjunto formato pelos demais caracteres do teclado) - int bs(char *s).
    
    

• 25/09/2018

  • Tipo estrutura;
  • Variáveis do tipo estrutura e ponteiros para estruturas; e
  • Definição de vetores de estruturas e de ponteiros para estruturas.
    

• 27/09/2018

  • Exercícios em laboratório sobre estruturas:
    • considere que você receba um vetor de estruturas geométricas - triângulos e retângulos - e um número n, sendo n o tamanho do vetor. Implemente uma função que ordene, de maneira crescente, as áreas das figuras pertencentes ao vetor. O protótipo da função é void area_ord (TEG *vet, int n) e a estrutura é a que segue: typedef struct geom{int tipo; float dim1, dim2;} TEG;
    • refaça a questão supracitada usando ponteiros para estruturas - void area_ord (TEG **vet, int n);
    • dada a estrutura de pontos em duas dimensões (typedef struct ponto2d{float x,y;} TP2D;), implemente uma função que ordena um vetor de pontos da seguinte maneira: os pontos com menores valores para o eixo x serão armazenados primeiro. Se dois pontos têm o mesmo valor para o eixo x, a ordenação será realizada de maneira crescente para o eixo y. O protótipo da função é void ord_2d (TP2D *vet, int n); e
    • refaça a questão supracitada usando ponteiros para estruturas - void ord_2d (TP2D **vet, int n).
    
    

• 02/10/2018

  • Escrita dos programas Q1 e Q2 da aula de laboratório supracitada;
  • Definição do conceito de tipos abstratos de dados (TAD);
  • Exemplo de TAD: código do TAD aluno, com os arquivos de cabeçalho, de implementação das funções e de teste.
    

• 04/10/2018

  • Exercício em laboratório sobre TAD: dada a estrutura data - typedef struct data{int mes, ano;} TD; - e a estrutura produto - typedef struct prod{int cod; float peso, preco; TD *valid;} TPROD;, escreva as seguintes funções:
    • alocação de uma prateleira de capacidade igual a n produtos - TPROD **aloca (int n);
    • liberação de uma prateleira - void libera (TPROD **prat, int n);
    • leitura de n produtos - void leit (TPROD **prat, int n);
    • escrita de n produtos da prateleira - void escrit (TPROD **prat, int n);
    • ordenação de n produtos na prateleira - void ordena1 (TPROD **prat, int n); - de acordo com os seguintes critérios:
      1. em ordem crescente de código;
      2. se dois produtos possuem o mesmo código, o critério de desempate é a data de validade, isto é, o produto que possui a data de validade mais próxima aparecerá primeiro na prateleira; e
      3. se os empates persistirem, o critério de desempate é o preço, em ordem decrescente.
    • outra ordenação de n produtos na prateleira - void ordena2 (TPROD **prat, int n); - de acordo com os seguintes critérios:
      1. em ordem decrescente de preço;
      2. se dois produtos possuem o mesmo preço, o critério de desempate é a data de validade, isto é, o produto que possui a data de validade mais próxima aparecerá primeiro na prateleira; e
      3. se os empates persistirem, o critério de desempate é o código, em ordem crescente.
    
    

• 09/10/2018

  • Pacote do TAD da aula de laboratório supracitada;
  • Motivação para o uso de listas;
  • Definição de listas simplesmente encadeadas;
  • Operações básicas: (a) inicialização e (b) inserção de um elemento no início da lista;
  • Versões (iterativa e recursiva) da operação de impressão na ordem direta; e
  • Implementação recursiva da operação de impressão na ordem inversa.
    

• 11/10/2018 (não houve aula)

• 16/10/2018 (não houve aula devido a Agenda Acadêmica)

• 18/10/2018 (não houve aula devido a Agenda Acadêmica)

• 23/10/2018 (P1)

• 25/10/2018

  • Versões (iterativa e recursiva) de algumas operações básicas: (a) inserção de um elemento no fim da lista, (b) busca da primeira ocorrência um elemento, (c) inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação, (d) liberação da lista, e (e) remoção da primeira ocorrência de um elemento da lista.
  • Trabalho computacional - manipulação de listas por meio da implementação de uma biblioteca de inteiros gigantes → seu programa deve ser capaz de receber, enquanto qualquer usuário do sistema quiser, dois inteiros gigantes com sinal e realizar as quatro operações básicas, a saber: soma, subtração, multiplicação e divisão. Algumas informações importantes a respeito desse trabalho:
    • grupo de no mínimo dois e de no máximo três discentes;
    • data limite de entrega: até 25/11/2018 às 23:59h; e
    • semana de apresentação: de 26 até 30/11/2018.
    
    

• 30/10/2018

  • Motivação para o uso de listas simplesmente encadeadas com descritor;
  • Definição desse tipo de lista simplesmente encadeada;
  • Operações básicas: (a) inicialização, (b) inserção de um elemento no início da lista, (c) impressão, (d) inserção de um elemento no fim da lista, (e) busca da primeira ocorrência um elemento, (f) liberação da lista, e (g) remoção da primeira ocorrência de um elemento da lista;
  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas; e
  • Operações básicas: (a) inicialização, (b) inserção de um elemento no início da lista, (c) impressão (ordens direta e inversa), (d) busca da primeira ocorrência um elemento, (e) liberação da lista, e (f) remoção da primeira ocorrência de um elemento da lista.
    

• 01/11/2018

  • Bibliotecas usadas na aula de laboratório; e
  • Exercícios sobre listas simplesmente e duplamente encadeadas:
    • ordenar uma lista, alterando o campo info - void ordena_v (TLISTA* l);
    • ordenar lista, mantendo a lista original e gerando uma lista de resposta ordenada - TLISTA* ordena (TLISTA* l);
    • inverter uma lista, alterando o campo info - void inverte_v (TLISTA* l);
    • inverter lista, mantendo a lista original e gerando uma lista de resposta invertida - TLISTA* inverte (TLISTA* l); e
    • para cada ocorrência de um elemento x, modificar a lista para que apareça x - 1 e x + 1 no lugar de x nessa lista - void misc_v (TLISTA* l, int x) e TLISTA* misc (TLISTA* l, int x).
    
    

• 06/11/2018

  • Exemplos de funções desenvolvidas em sala;
  • Motivação para o uso de listas simplesmente encadeadas circulares;
  • Definição de listas simplesmente encadeadas circulares; e
  • Operações básicas: (a) inicialização, (b) inserção em O(1) de um elemento na lista e (c) inserção de um elemento antes do nó apontado pelo token.
    

• 08/11/2018

  • Revisão da nota da primeira prova com parte da Questão 3 implementada; e
  • Gabarito utilizado na correção.

• 13/11/2018

  • Definição dos grupos, dos dias e dos horários das apresentações;
  • Operações básicas em listas circulares: (a) impressão da lista, (b) liberação da lista, (c) retirada da primeira ocorrência de um elemento da lista e (d) busca da primeira ocorrência de um elemento; e
  • Algoritmo de ordenação quickSort.
    

• 22/11/2018

  • Procedimento geral qsort existente na biblioteca stdlib.h; e
  • Exemplos de funções de comparação, usadas em qsort.
    

• 27/11/2018

  • Motivação para o uso de pilhas;
  • Implementação de pilhas com vetores e listas;
  • Operações básicas: (a) inicialização, (b) retirada de um elemento do topo da pilha - a operação pop, (c) inserção de um elemento no topo da pilha - a operação push, (d) teste se a pilha está vazia e (e) liberação da lista; e
  • Exercícios.
    

• 29/11/2018

  • Bibliotecas usadas na aula de laboratório; e
  • Exercícios sobre pilhas, listas simplesmente encadeadas circulares e ordenação:
    • ordenar uma pilha - void ordena_v (TPILHA* p);
    • ordenar pilha, mantendo a pilha original e gerando uma de resposta ordenada - TPILHA* ordena (TPILHA *p);
    • retirar o k-ésimo elemento da lista circular. Se k é menor ou igual a zero, a lista permanece inalterada - TLSEC* retira_k (TLSEC *l, int k);
    • inserir x elementos após a ocorrência de cada x na lista, onde x é maior que zero - void insx (TLSEC *l, int k); e
    • desenvolver uma função de comparação de ponteiros de alunos (typedef struct aluno{int ch, mat, formando; float cr; char nome[31];} TALUNO;) para ser usada em qsort, com os seguintes critérios de desempate: (1) se o aluno é formando, (2) ch em ordem decrescente, (3) cr em ordem decrescente, (4) aluno mais antigo aparece antes de um mais recente, e (5) nome em ordem crescente.
    
    

• 04/12/2018 (aula de dúvidas para a P2)

  • Escrita das funções da aula de laboratório supracitada: (a) void ordena_v (TPILHA* p), (b) TLSEC* retira_k (TLSEC *l, int k) e (c) int cmp_aluno(const void *a1, const void *a2).
    

• 06/12/2018 (P2)

• 11/12/2018 (VR)

• 13/12/2018 (revisão de nota da P2 e da VR, e divulgação de todas as notas da disciplina)

• 18/12/2018 (VS)

• 20/12/2018 (revisão de nota da VS e publicação das notas finais)