buscas.c

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

typedef struct LinkedList {
    int val;
    struct LinkedList *next;
} LinkedList;

LinkedList * create_node(int x) {
    LinkedList * node = (LinkedList *) malloc(sizeof(LinkedList));
    node->val = x;
    node->next = NULL;
    return node;
}

LinkedList * insert_at_end(LinkedList *ll, int x) {
    if (ll == NULL) return create_node(x);
    LinkedList * walker = ll;
    while (walker->next != NULL) walker = walker->next;
    walker->next = create_node(x);
    return ll;
}

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

int length_ll(LinkedList *ll) {
    int n = 0;
    LinkedList *walker = ll;
    while(walker != NULL) {
        n++;
        walker = walker->next;
    }
    return n;
}

int * to_array(LinkedList *ll){
    int n = length_ll(ll);
    int i = 0;
    LinkedList *walker = ll;
    int * arr = (int *) malloc(sizeof(int)*n);
    while (walker != NULL) {
        arr[i] = walker->val;
        ++i;
        walker = walker->next;
    }
    return arr;
}

void free_ll(LinkedList *ll) {
    if (ll->next != NULL) free_ll(ll->next);
    free(ll);
}

int busca_seq(int x, LinkedList *ll) {
    LinkedList *walker = ll;
    while (walker != NULL) {
        if ( walker->val == x) return 1;
        walker = walker->next;
    }
    return 0;
}

int busca_bin (int k, int * x, int n) {
    int left = 0, right = n-1;
    int mid = (left+right)/2;
    while (x[mid] != k)
    {
        if (x[mid] > k) right = mid-1;
        else left = mid+1;
        mid = (left+right)/2;
        if (left > right) return 0;
    }
    return 1;
}

int aplica_busca(int *arr, int n, LinkedList *ll, int x, int busca) {
    switch(busca) {
        case 0: busca_seq(x, ll);
                break;
        case 1: qsort(arr, n, sizeof(int), cmpfunc);
                busca_bin(x, arr, n);
                break;
    }
}

int main(int argv, char *argc[]) {
    if (argv < 5) {
        printf("Uso: ./buscas min max loops busca\n");
        return -1;
    }

    int x, i, n, cnt = 0;
    LinkedList *ll = NULL, *walker;
    int *arr;
    int min = atoi(argc[1]), max = atoi(argc[2]), loops = atoi(argc[3]);
    int busca = atoi(argc[4]);
    time_t t0, t1;

    while (scanf("%d", &x) != EOF) {
        ll = insert_at_end(ll, x);
    }
    n = length_ll(ll);
    printf("Len: %d\n", n);
    arr = to_array(ll);

    for (i=0, walker=ll; walker != NULL; i++, walker=walker->next) {
        printf("%d %d\n", arr[i], walker->val);
    }

    t0 = time(NULL);
    for (i=0; i<loops; ++i) {
        x = min + (int)((double)rand() / ((double)RAND_MAX / (max - min + 1) + 1));
        cnt += aplica_busca(arr, n, ll, x, busca);
    }
    t1 = time(NULL);
    printf("%d buscas bem sucedidas, tempo total: %ld segundos\n", cnt, t1-t0);

    free(arr);
    free_ll(ll);

    return 0;

}