Linear search on a file with data

**telmo_d** · 04-21-2015

Hey. It's my first post. I decided to register here because i started learning C some months ago but it's not easy without some help. So i hope this will help my learning and i can also contribute to the forums later.

In this exercise i had to use Linear Search on a file with data of students, it had id, name and mark. Here is the code i used. It does the job but i'd like to know simpler solutions for this. Sorry for the language, i should start writing everything in english now.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define numtestes 100



void Trocar (int *a, int *b)
{
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}


int DeterminarPivot (int V[], int inicio, int fim)
{
    int i, k = inicio; // k = posição do pivot V[inicio]
    for (i = inicio+1; i <= fim; i++)
        if (V[i] < V[inicio])
    {
        k++;
        Trocar (&V[i], &V[k]);
    }
    Trocar (&V[inicio], &V[k]);
    return (k);
}        


    void OrdenarQuicksort(int V[], int inicio, int fim)
    {
        int k; // k = pos    ição do pivot V[inicio]
        if (inicio < fim)
        {
            k = DeterminarPivot (V, inicio, fim);
            OrdenarQuicksort (V, inicio, k-1);
            OrdenarQuicksort (V, k+1, fim);
        }
    }




int PesquisaSequencial(int Num, int v[], int tam)
{
    int i=0;
    while((i<tam) &&  (v[i]<Num))
        i++;
    if((i<tam) && (Num==v[i]))    
        return i;
    else
        return -1;
    
    
}


typedef struct
{
    int numero;
    char nome[100];
    float nota;
    
}DADOS;


int main()
{
    DADOS testes[numtestes];
    int N=0;
    char auxnum[100];
    char auxnota[100];
    FILE *f;
    f=fopen("C:\\Users\\PC\\Documents\\dados5.txt", "r");
    if(f==NULL)
    {
        printf("Erro\n");
        return 0;
    }
    while(fgets(auxnum, 100, f)!=NULL)
    {
        testes[N].numero=atoi(auxnum);
        fgets(testes[N].nome, 100, f);
        fgets(auxnota, 100, f);
        testes[N].nota=atof(auxnota);
        N++;
    }
    printf("Foram lidos %d alunos\n", N+1);
    
    int notas_2[100];
    for(int i=0;i<100;i++)
    {
        notas_2[i]=testes[i].numero;    
    }
    DeterminarPivot(notas_2, 0, 65);
    OrdenarQuicksort(notas_2, 0, 65);
    int indicenum = PesquisaSequencial(3121791, notas_2, 66);
    printf("resultado encontra-se no indice %d\n", indicenum);
    printf("Indice 15 corresponde ao numero %d\n", notas_2[15]);    
}

**Prelude** · 04-21-2015

There's not a whole lot you can do to simplify the code, though using qsort instead of your own hand rolled quicksort would be a start. You might also defer to fscanf for some of the niggling conversions to simplify your parsing loop (note that atoi is evil due to how it responds to erroneous input). Finally, for simplicity I'd simply sort the testes array directly unless you have a good reason not to:

Code:

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

#define SIZE 100

typedef struct
{
    int num;
    char name[100];
    float mark;
} record_t;

int compare(const void *a, const void *b)
{
    return ((const record_t*)a)->num - ((const record_t*)b)->num;
}

size_t linear_search(record_t *src, size_t n, int num)
{
    for (size_t i = 0; i < n; i++)
    {
        if (src[i].num == num)
        {
            return i;
        }
    }

    return (size_t)-1;
}

int main(void)
{
    FILE *in = fopen("test.txt", "r");

    if (in == NULL)
    {
        perror("Error opening file");
    }
    else
    {
        record_t records[SIZE];
        size_t n = 0;

        while (n < SIZE && fscanf(in, "%d %99[^\n] %f", &records[n].num, records[n].name, &records[n].mark) == 3)
        {
            ++n;
        }

        fclose(in);

        qsort(records, n, sizeof *records, compare);

        for (size_t i = 0; i < n; i++)
        {
            printf("%d: %s -- %f\n", records[i].num, records[i].name, records[i].mark);
        }

        printf("%zd\n", linear_search(records, n, 2));
        printf("%zd\n", linear_search(records, n, 12345));
    }

    return 0;
}

On a side note, I got a kick out of "testes" as a variable name. Yay for crude humor.

**telmo_d** · 04-21-2015

I didn't sort the testes array directly because i didn't know how to pass it to the function. But i see i could have just written testes. But seeing that i would have though it should be written testes.numero. Why not this way?

That wasn't intentional... :P "Testes" is simply the plural of "test" in portuguese

**Prelude** · 04-21-2015

But seeing that i would have though it should be written testes.numero. Why not this way?

If you mean in the call to qsort, that wouldn't work as numero isn't an array, testes is the array that happens to contain objects which have a single member named numero. You could certainly use qsort with an array of int that's populated with the numero values as you did originally. It's also not a bad option either, especially if you have concerns about swap performance of DADOS objects. There are many ways to solve a problem, and it's rare when one of them can be called "bad" across the board.

That wasn't intentional... :P "Testes" is simply the plural of "test" in portuguese

I know, but it was still funny to me.

Thread: Linear search on a file with data

Thread Tools

Search Thread

Display

Linear search on a file with data

Similar Threads

Help with Linear Search

Linear Search

Difference Between A Linear Search And Binary Search

Linear search

binary search or linear search