Prof. Mauro Fonseca - UTFPR - DAINF

User Tools

Site Tools

Trace: • lab1
cursos:if63c:lab1

Table of Contents

Trabalho 1 - Lista de clientes

  1. Faça um programa que use as duas formas de armazenar os dados em paralelo e mostre a diferença de tempo e as as Métricas C(n) e M(n) entre cada ação realizada nas duas listas. (Pode ser separada em dois programas)
    1. Lista sequencial
    2. Lista encadeada
  2. Cada dado consiste dos campos de nome e RG.
    1. O usuario pode ficar escolhendo entre as funções:
      1. Inserção de um nó no início da lista e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
      2. Inserção de um nó no fim da lista e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
      3. Inserção de um nó na posição N e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
      4. Retirar um nó do início da lista e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista..
      5. Retirar um nó no fim da lista e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
      6. Retirar um nó na posição N e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
      7. Procurar um nó com o campo RG e apresentar Nome, RG, C(n), M(n), Tempo de execução e sua posição N na lista.
        1. Usando busca sequencial.
      8. Mostrar a lista na tela.
      9. Salvar a lista em um arquivo.
        1. no formato nome,RG
      10. Ler a lista de um arquivo.
        1. no formato nome,RG
        2. (colocar na lista)
      11. Sair do sistema.
  1. Cada trabalho deve usar os arquivos prontos com 10, 100, 1K, 1M e 100M nomes e RG cadastrados.
    1. Estes arquivos são somente para comparar a diferença de custo entre as listas.
    2. Arquivos com Nome e RG para o trabalho
    3. A avaliação será feita usando estes arquivos de dados.
    4. O arquivo maior esta com a última linha somente com o nome sem o RG.
    5. A avaliação usará o multiplicador de 100% se usar 100M, 90% 1M, 80% 1K e 50% outros, para o maior arquivo que funcione.

Análise de Desempenho: Entendendo as Métricas C(n) e M(n)

Após cada operação solicitada pelo usuário, o sistema realizará a mesma ação em ambas as estruturas de dados (Lista Sequencial e Lista Encadeada) e exibirá um quadro comparativo de desempenho. A análise se baseia em duas métricas fundamentais de custo computacional:

C(n) - Número de Comparações

Quantifica o esforço de busca e processamento do algoritmo. Esta métrica é incrementada toda vez que uma comparação lógica é executada para guiar o fluxo do programa.

  • O que é contado? Testes condicionais como if (rg == rg_procurado), verificações de laços como while (no_atual != NULL) e o controle de contadores como for (i = 0; i < total; i++).
  • O que significa? Um valor de C(n) elevado sugere que a função precisou percorrer uma grande parte da lista para encontrar uma posição ou um dado específico.

M(n) - Número de Movimentações

Quantifica o esforço de manipulação e reorganização dos dados na memória.

Esta métrica representa o custo de copiar, mover ou vincular os nós da lista.

  • O que é contado?
    • Na Lista Sequencial: Principalmente as cópias de elementos inteiros de uma posição para outra (ex: lista[i] = lista[i-1];) durante inserções e remoções.
    • Na Lista Encadeada: A reatribuição de ponteiros (ex: no_anterior→proximo = novo_no;), além das operações de alocação (malloc) e liberação (free) de memória.
  • O que significa? Um valor de M(n) elevado indica que a estrutura de dados exigiu um grande trabalho para se reorganizar após a operação.
Resumo Prático do Significado
  • C(n) está associado ao “trabalho para encontrar o local da ação”.
  • M(n) está associado ao “trabalho para realizar a ação naquele local”.

Esta análise permitirá observar na prática os pontos fortes e fracos de cada estrutura. Por exemplo, uma inserção no início de uma lista sequencial terá um M(n) altíssimo devido ao deslocamento de todos os outros elementos, enquanto na lista encadeada o custo será mínimo.

Funções Padrão ANSI C Essenciais para o Trabalho "Lista de Clientes"

Esta tabela serve como um guia rápido das funções da biblioteca padrão C que são mais úteis para implementar as funcionalidades do projeto.

Biblioteca Padrão: <stdio.h> Objetivo da Função
``printf()`` Exibir informações formatadas na tela (menus, resultados, listas, etc.).
``scanf()`` Ler dados formatados digitados pelo usuário (opções do menu, números, etc.).
``getchar()`` Ler um único caractere do teclado. Muito útil para criar funções de limpeza de buffer.
``fopen()`` Abrir um arquivo em um modo específico (leitura “r” ou escrita “w”).
``fclose()`` Fechar um arquivo que foi aberto anteriormente, salvando as alterações.
``fprintf()`` Escrever dados formatados dentro de um arquivo. Perfeito para salvar no formato “nome,RG”.
``fgets()`` Ler uma linha inteira de texto de um arquivo. É a forma mais segura de ler os dados para a lista.
``sscanf()`` String Scan Formatted: Ler e extrair dados de uma string de acordo com um formato. Essencial para separar a linha “nome,RG” em duas variáveis distintas.
``perror()`` Exibir uma mensagem de erro padrão do sistema (ex: “Arquivo não encontrado”) quando uma operação falha.
Biblioteca Padrão: <stdlib.h> Objetivo da Função
``malloc()`` Memory Allocate: Alocar um bloco de memória do tamanho especificado. Essencial para criar novos nós na lista encadeada.
``free()`` Liberar um bloco de memória que foi alocado com ``malloc()``, prevenindo vazamentos de memória.
``atol()`` ASCII to Long: Converter uma string de texto (lida do arquivo) em um número do tipo ``long int``. Ideal para o RG.
``exit()`` Terminar a execução do programa imediatamente. Pode ser usada em caso de um erro crítico.
Biblioteca Padrão: <string.h> Objetivo da Função
``strcpy()`` String Copy: Copiar o conteúdo de uma string para outra. Útil para mover nomes lidos para dentro da struct.
``strchr()`` String Character: Localizar a primeira ocorrência de um caractere em uma string. Perfeito para encontrar a vírgula que separa o nome do RG.
``strlen()`` String Length: Retornar o comprimento de uma string (o número de caracteres).
Biblioteca Padrão: <time.h> Objetivo da Função
``clock()`` Obter o número de “ticks” de clock do processador desde que o programa começou. Usada para medir o tempo de execução de uma operação.
cursos/if63c/lab1.txt · Last modified: 2025/08/23 21:12 by fonseca