Obs.: Soluções alternativas para as correções dos problemas dos exercícios foram consideradas durante a correção.

1. (2,0)

Desenvolva um programa em C que leia a representação ASCII de números decimais de um arquivo texto (um número por linha) cujo nome é especificado na linha de comando e armazene esses valores em um arranjo de inteiros. O seu programa deve contemplar as seguintes funcionalidades (que devem estar associadas a distintas funções C da sua aplicação):

• Descobrir a quantidade de números (linhas) no arquivo;
• Alocar espaço para o arranjo;
• Ler cada linha e realizar a conversão de formato;
• Apresentar alguns dos valores lidos e sua posição para permitir a verificação da corretude da implementação.

#include <stdio.h
#include <stdlib.h
#include <string.h

FILE *arq;
int qtde_numeros;
int *arranjo;

int abrir_arquivo(int, char *);
int numero_de_linhas(void);
int alocar_espaco_para_arranjo(void);
void transferir(void);
void apresentar_valores(void);

void main(int argc, char *argv[])
{
    if (!(abrir_arquivo(argc, argv[1])))
        exit(0);

    qtde_numeros = numero_de_linhas();

    printf("Quantidade de numeros no arquivo: %d\n\n", qtde_numeros);

    if (!(alocar_espaco_para_arranjo()))
        exit(0);

    transferir();

    apresentar_valores();
}

int abrir_arquivo(int qtde_arg, char *nome_arq)
{
    if (qtde_arg < 2)
    {
        printf("Nome do arquivo ausente.\n");
        return(0);
    }
    else if (qtde_arg 2)
        printf("O excesso de parametros sera desprezado.\n\n");

    if (!(arq = fopen(nome_arq, "rw")))
    {
        printf("Arquivo nao encontrado.\n");
        return(0);
    }

    return(1);
}

int numero_de_linhas(void)
{
    const int qtde_max = 7;

    int cont = 0;
    char *linha;

    while(!feof(arq))
    {
        fgets(linha, qtde_max, arq);
        cont++;
    }

    if (!(strlen(linha)))
        cont--;

    return(cont);
}

int alocar_espaco_para_arranjo(void)
{
    if ((arranjo = (int *) malloc(qtde_numeros * sizeof(int))) == NULL)
    {
        printf("Falta de memoria.\n");
        return(0);
    }
    else
        return(1);
}

void transferir(void)
{
    const int qtde_max = 7;

    int cont = 0;
    char *linha;

    fseek(arq, 0, 0);

    for (cont = 0; cont < qtde_numeros; cont++)
    {
        fgets(linha, qtde_max, arq);
        *(arranjo+cont) = atoi(linha);
    }

    fclose(arq);
}

void apresentar_valores(void)
{
    int pos;

    do
    {
        printf("Digite uma posicao para ser apresentado o seu valor [digite 0 para nenhuma]: ");
        scanf("%d", &pos);

        if (pos)
            printf("O valor para a posicao %d eh: %d\n\n", pos, *(arranjo+pos-1));
    } while (pos);
}

2. (1,5)

Modifique esta implementação de quicksort de forma a obter um traço da execução recursiva da rotina -- para cada invocação, indique o pivot e qual faixa do arranjo está sendo ordenada.

#include <stdio.h
#define MAX 10

/* this program uses the median of the first and last element
   as its pivot value */

/* initially set :
   l = 0;
   r = MAX-1 ; */

void swap(int*, int*);
void quick_sort(int [], int, int);

main()
{
    int X[10] = {5,1,0,8,3,4,7,2,6,9};
    int i;

    quick_sort(X, 0, 9);

    for(i = 0; i < 10; i++)
        printf("\n%d", X[i]);
}

void quick_sort(int A[], int l, int r)
{
    int i=0, j=0, pivot=0;

   int k=0;                                    // linha inserida

    if (l < r)
    {
        i=l;
        j=r;
        pivot=(A[l]+A[r])/2;

        printf("\nPivot: %d - faixa: ", pivot); // linha inserida

        for (k = l; k <= r; k++)                // linha inserida
          printf("%d(%d) ", k, A[k]);         // linha inserida

        while (i < j)
        {
            while(i <= r && A[i] < pivot)
                i++;
            while(j l && A[j] pivot)
                j--;
            if ( i <= j)
                swap(A+i, A+j);
            i++; j--;
         }
         j++;
         quick_sort(A, l, j);
         quick_sort(A, j+1, r);
    }
}

void swap(int *x, int *y)
{
    int temp=0;

    temp = *x;
    *x = *y;
    *y = temp;
}

3. (2,0)

Integre os dois programas dos exercícios 1 e 2 para realizar a ordenação de um arranjo criado a partir de um arquivo. Use a função bsearch da biblioteca C para verificar se um valor inteiro, especificado como um argumento adicional na linha de comando, está ou não entre os elementos do arranjo.

#include <stdio.h
#include <stdlib.h
#include <string.h

FILE *arq;
int qtde_numeros;
int *arranjo;

int abrir_arquivo(int, char *);
int numero_de_linhas(void);
int alocar_espaco_para_arranjo(void);
void transferir(void);
void apresentar_valores(void);

void swap(int *, int *);
void quick_sort(int [], int, int);

int compara(int *, int *);

void main(int argc, char *argv[])
{
    int cont = 0;

    if (!(abrir_arquivo(argc, argv[1])))
        exit(0);

    qtde_numeros = numero_de_linhas();

    printf("Quantidade de numeros no arquivo: %d\n\n", qtde_numeros);

    if (!(alocar_espaco_para_arranjo()))
        exit(0);

    transferir();

    quick_sort(arranjo, 0, qtde_numeros - 1);

    if (bsearch(atoi(argv[2]), arranjo, qtde_numeros, sizeof(int), compara))
        printf("Número encontrado no arranjo.\n");
    else
        printf("Número não encontrado no arranjo.\n");
}

int abrir_arquivo(int qtde_arg, char *nome_arq)
{
    if (qtde_arg < 2)
    {
        printf("Nome do arquivo ausente.\n");
        return(0);
    }
    else if (qtde_arg 2)
        printf("O excesso de parametros sera desprezado.\n\n");

    if (!(arq = fopen(nome_arq, "rw")))
    {
        printf("Arquivo nao encontrado.\n");
        return(0);
    }

    return(1);
}

int numero_de_linhas(void)
{
    const int qtde_max = 7;

    int cont = 0;
    char *linha;

    while(!feof(arq))
    {
        fgets(linha, qtde_max, arq);
        cont++;
    }

    if (!(strlen(linha)))
        cont--;

    return(cont);
}

int alocar_espaco_para_arranjo(void)
{
    if ((arranjo = (int *) malloc(qtde_numeros * sizeof(int))) == NULL)
    {
        printf("Falta de memoria.\n");
        return(0);
    }
    else
        return(1);
}

void transferir(void)
{
    const int qtde_max = 7;

    int cont = 0;
    char *linha;

    fseek(arq, 0, 0);

    for (cont = 0; cont < qtde_numeros; cont++)
    {
        fgets(linha, qtde_max, arq);
        *(arranjo+cont) = atoi(linha);
    }

    fclose(arq);
}

void apresentar_valores(void)
{
    int pos;

    do
    {
        printf("Digite uma posicao para ser apresentado o seu valor [digite 0 para nenhuma]: ")
        scanf("%d", &pos);

        if (pos)
            printf("O valor para a posicao %d eh: %d\n\n", pos, *(arranjo+pos-1));
    } while (pos);
}

void quick_sort(int A[], int l, int r)
{
    int i=0, j=0, pivot=0;

    if (l < r)
    {
        i=l;
        j=r;
        pivot=(A[l]+A[r])/2;

        while (i < j)
        {
            while(i <= r && A[i] < pivot)
                i++;
            while(j l && A[j] pivot)
                j--;
            if ( i <= j)
                swap(A+i, A+j);
            i++; j--;
         }
         j++;
         quick_sort(A, l, j);
         quick_sort(A, j+1, r);
    }
}

void swap(int *x, int *y)
{
    int temp=0;

    temp = *x;
    *x = *y;
    *y = temp;
}

int compara(int *s1, int *s2){
      return *s1 - *s2;
}

4. (1,5)

Uma função hash está sendo definida para mapear strings para a faixa de valores entre 0 e 63 da seguinte maneira: o resultado intermediário é a somatória dos valores ASCII de cada caráter não-nulo da string; esse resultado é dividido por 64 e o resto da divisão é o valor de hash.

(a) Implemente uma função C que realize essa função.
(b) Avalie o resultado dessa função para as seguintes strings:

• FEEC
• Universidade Estadual de Campinas
• EA876
• FA875
• Estruturas de dados

a)

#include <stdio.h

int funcao_hash(char *);

void main(void)
{
    char *info;

    printf("\nDigite a string: ");
    gets(info);

    printf("\nO resultado da funcao hash para esta string eh: %d\n", funcao_hash(info));
}

int funcao_hash(char *info)
{
    int res = 0;
    int som = 0;

    while(*info)
    {
        som = som + *info;
        info++;
    }

    res = som % 64;

    return res;
}

b)

• FEEC - 19
• Universidade Estadual de Campinas - 43
• EA876 - 43
• FA875 - 43
• Estruturas de dados - 22

5. (1,5)

Repita o exercício anterior substituindo o cômputo do valor de hash por divisão pelo método do meio do quadrado.

a)

#include <ctype.h
#include <math.h
#include <stdlib.h
#include <stdio.h
#include <conio.h

int funcao_hash(char *);

main()
{
    char *info;

    printf("\nDigite a string: ");
    gets(info);

    printf("\nO resultado da funcao hash para esta string eh: %d\n", funcao_hash(info));
}

int funcao_hash(char * info)
{
    int som = 0;
    unsigned long int quad = 0;
    int n_word = 0;
    int desl = 0;

    while(*info)
    {
        if (*info != 10)
            som = som + *info;
        info++;
    }

    quad = som * som;

    n_word = (int) (((log(quad) / log(2)) + 4) / 4);

    desl = (2 * n_word) - 3;

    quad = quad << (26 - desl);
    quad = quad (26);

    return quad;
}

b)

• FEEC - 14
• Universidade Estadual de Campinas - 17
• EA876 - 58
• FA875 - 58
• Estruturas de dados - 40

6. (2,0)

Implemente em C as funcionalidades para inserir (INSERT, Alg.2.9) e busca (FIND, Alg.2.13) elementos em uma lista cujas chaves são inteiros. Modifique o programa do exercício 1 para preencher a lista a partir dos valores de um arquivo e verificar se o valor especificado na linha de comando encontra-se entre os elementos da lista.

#include <stdio.h
#include <stdlib.h

typedef struct NODE
{
    int elem;
    struct NODE *prox;
} NODE;

NODE *busca(NODE *, int);
void insere(NODE **, int);

int main(int argc, char *argv[])
{
    FILE *arquivo;
    NODE *inicio, *no_atual;
    int  linhas = 0;
    char chlido = 0,
    *temp_ascii = (char *)malloc(11);
    register int i, linha_atual = 1;

    no_atual = (NODE *)malloc( sizeof(NODE) );
    inicio = (NODE *)malloc( sizeof(NODE) );
    inicio-elem = 0;
    inicio-prox = 0;

    if( argc < 3 )
    {
        printf("Ausência do arquivo e/ou do número a ser procurado.\n");
        return(1);
    }

    arquivo = fopen(argv[1], "r");

    while( chlido != EOF )
    {
        chlido = (char)fgetc(arquivo);
        if(chlido == 10) //line feed
        linhas++;
    }

    rewind(arquivo);

    while( linha_atual <= linhas )
    {
        for(i = 0; i < 11; i++)
            *(temp_ascii + i) = 0;

        i = 0;

        do
        {
            chlido = (char)fgetc(arquivo);
            if(chlido != 10)
                *(temp_ascii + i) = chlido;
            i++;
        } while(chlido != 10);

        insere(&inicio, atoi(temp_ascii) );
        linha_atual++;
   }

   fclose(arquivo);

   if( (no_atual = busca(inicio, atoi(argv[2])) ) != 0)
       printf("\nValor encontrado! - %d\n\n", no_atual-elem);
   else
       printf("\nValor nao encontrado na lista!\n\n");
}

NODE *busca(NODE *foo, int valor)
{
    NODE *node;

    node = (NODE *)malloc( sizeof(NODE) );
    node = foo;
 
    do
    {
        node = node-prox;
    } while( (node-elem != valor) && (node != 0) );
 
    return( node );
}

void insere(NODE **foo, int valor)
{
    static NODE *novo;
    novo = (NODE *)malloc( sizeof(NODE) );
    novo-elem = valor;
    novo-prox = (*foo)-prox;
    (*foo)-prox = novo;
}