How to write a C Program to Find Dictionary Word Search ?
Solution For C Program to Find a Word in Dictionary :
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//#Prototypes
struct Dictionary buildDictionary();
struct WordGrid buildSearchGrid();
char *reverStr();
void printDictionary();
void printWordGrid();
void binaryWordSearch();
void parseGrid();
//#Structs
struct Dictionary{
int wordLength;
int numOfWords;
char **ppWords;
};
struct WordGrid{
int height;
int width;
char **ppGrid;
};
//#Functions
int main(){
int i;
int numOfCases;
FILE *pFile = fopen("dictionary.txt", "r");;
if(pFile == NULL){
printf("Can not open file.");
return 1;
}
//build the dictionary.txt to memory
struct Dictionary dictionary = buildDictionary(pFile, dictionary);
//get number of grids to search
scanf("%d", &numOfCases);
//loop through each grid
for( i = 0; i < numOfCases; i++){
printf("Words found in grid #%d\n", i+1);
//build the word grid to memory
struct WordGrid wordGrid = buildSearchGrid(wordGrid);
parseGrid(wordGrid, dictionary);
}
return 0;
}
//returns a string in reverse order
char* reverStr(const char *str){
size_t len = strlen(str);
char* revStr = (char*)malloc(len + 1);
size_t dst, src;
for (dst = len - 1, src = 0; src < len; src++, dst--) {
revStr[dst] = str[src];
}
revStr[len] = '\0';
return revStr;
}
void parseGrid(struct WordGrid wordGrid, struct Dictionary dictionary){
char *searchKey;
int x, y;
//search through each row
for( y = 0; y < wordGrid.height; y++){
searchKey = wordGrid.ppGrid[y];
binaryWordSearch(dictionary, searchKey);
}
//search each row in reverse
for( y = 0; y < wordGrid.height; y++){
searchKey = reverStr(wordGrid.ppGrid[y]);
binaryWordSearch(dictionary, searchKey);
}
}
void binaryWordSearch(struct Dictionary dictionary, char *searchKey){
int first = 0;
int last = dictionary.numOfWords - 1;
int mid = (first + last) / 2;
//loop until numOfWords cannot be divided any longer
while(first <= last){
//set mid point to the front
if( strcmp(dictionary.ppWords[mid], searchKey) < 0 ){
first = mid + 1;
}
//return once its found
else if( strcmp(dictionary.ppWords[mid], searchKey) == 0 ){
printf("%s\n", dictionary.ppWords[mid]);
break;
}
//set mid point to the back
else{
last = mid - 1;
}
//divide again
mid = (first + last) / 2;
}
if(first > last){
///printf("%s", "NOT FOUND\n");
}
}
struct Dictionary buildDictionary(FILE *pFile, struct Dictionary dictionary){
//set the known max langth for dictionary words
dictionary.wordLength = 20;
//scan in the value for number of words
fscanf(pFile, "%d", &dictionary.numOfWords);
//allocate space for each word
dictionary.ppWords = malloc( dictionary.numOfWords * sizeof(char*));
//allocate and set each word from the list to memory
for(int i = 0; i < dictionary.numOfWords; i++){
dictionary.ppWords[i] = malloc( dictionary.wordLength * sizeof(char));
fscanf(pFile, "%s", dictionary.ppWords[i]);
}
return dictionary;
}
struct WordGrid buildSearchGrid(struct WordGrid wordGrid){
//get the grid deimension from the file
scanf("%1d", &wordGrid.height);
scanf("%1d", &wordGrid.width);
//allocate space for the word grid
wordGrid.ppGrid = malloc( wordGrid.height * sizeof(char*));
//parse through each row and assign the string to memory
for(int x = 0; x < wordGrid.width; x++){
wordGrid.ppGrid[x] = malloc( wordGrid.width+1 * sizeof(char));
scanf("%s", wordGrid.ppGrid[x]);
}
return wordGrid;
}
void printDictionary(struct Dictionary dictionary){
for(int i = 0; i < dictionary.numOfWords; i++){
printf("%s\n", dictionary.ppWords[i]);
}
}
void printWordGrid(struct WordGrid wordGrid){
printf("%d ", wordGrid.height);
printf("%d\n", wordGrid.width);
for(int i = 0; i < wordGrid.height; i++){
printf("%s\n", wordGrid.ppGrid[i]);
}
}