13 August 2010

simple dictionary using binary search


//strcmp.c

#include <stdio.h>

int my_strcmp(const char[], const char[]);

/*
// testing..
int main(void)
{

printf("%i\n", strcmp("alpha", "altered"));
printf("%i\n", strcmp("zioty", "yucca"));

getchar();
return 0;
}
*/

int my_strcmp(const char str1[], const char str2[])
{
int i=0;

while (str1[i] == str2[i] && str1[i] != '\0' && str2[i] != '\0')
i++;

if (str1[i] > str2[i])
return 1;
else if (str1[i] < str2[i])
return -1;
else
return 0;
}



// simple dictionary using binary search
// auther mhewedy
// date : 2010-08-13
// compiled under GCC 4.x

#include <stdio.h>
#include <string.h>
#include "strcmp.c"

#define DICT_LENGTH 3

typedef struct _dictionary_s dictionary;
struct _dictionary_s
{
char word[20];
char definition[50];
};

int lookup(const char[], const dictionary[], int);
int binary_lookup(const char[], const dictionary[], int, int);

int main(void)
{
static const dictionary dict[DICT_LENGTH] =
{
{"a", "first letter in alphabatic"},
{"b", "second letter"},
{"c", "third letter"}
};
char word[20];
int ret=-1;

do{
printf("Enter word: \n");
if (gets(word) == NULL)
break;
ret = binary_lookup(word, dict, 0, DICT_LENGTH-1);

if (ret < 0)
{
fprintf(stderr, "word not found!\n");
}
else{
printf("%s : %s\n", word, dict[ret].definition);
}
printf("\n");
}while (1);

return 0;
}

int binary_lookup(const char word[], const dictionary dict[], int start, int end)
{
if (start > end)
return -1;

int middle = (start+end)/2;
int cmp = my_strcmp(word, dict[middle].word);

if (cmp == -1)
{
end = middle -1;
binary_lookup(word, dict, start, end);
}
else if (cmp == 1)
{
start = middle +1;
binary_lookup(word, dict, start, end);
}
else // 0
{
return middle;
}
}

int lookup(const char word[], const dictionary dict[], int length)
{
int i;
for (i=0; i<length; i++)
{
if (strcmp(word, dict[i].word) == 0)
return i;
}
return -1;
}




2 comments:

Striky said...

Hi Hewedy,

Great job! but check "Trie" data structure if you are really interested.

mhewedy said...

Thanks Striky for your comment.
I was some example in some basic C books.

Thanks for the note, seems interesting :)