//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:
Hi Hewedy,
Great job! but check "Trie" data structure if you are really interested.
Thanks Striky for your comment.
I was some example in some basic C books.
Thanks for the note, seems interesting :)
Post a Comment