C RSS C RSS

BST spell check

Reply

•
•
Join Date: Oct 2008
Posts: 11
Reputation: mikeregas is an unknown quantity at this point 
Solved Threads: 0
mikeregas mikeregas is offline Offline
Newbie Poster

BST spell check

 
0
  #1
Nov 10th, 2008
This program is suppose to be a spell checking program and I just can not get it to work can someone please take a look and let me know what I need to do to fix it




C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. //CONSTANTS 
  7. #define wrdlen [48] 
  8. #define linelen [1024]
  9.  
  10.  
  11. // A struct representing a node in a binary search tree
  12.  
  13. struct BSTnode
  14. {  
  15. char word[wrdlen];// The contents of the node	
  16. struct BSTnode* left;// Links to the node's left and right children
  17. struct BSTnode* right;
  18. };
  19.  
  20. // Adds a new node to the tree. Duplicates are disallowed. Returns 1 if a
  21. // new node was added, returns 0 if newdata was already in the tree
  22. int insert(struct BSTnode** root, char newword[wrdlen])
  23. {
  24.     // If we've reached the right place to insert, create a new node and add it in
  25. 	if( (*root) == NULL)
  26. 	{
  27. 		(*root) = (struct BSTnode*)malloc(sizeof(struct BSTnode));
  28.         strcpy((*root)->word,newword);
  29. 		(*root)->left = NULL;
  30. 		(*root)->right = NULL;
  31. 		return 1;
  32. 	}
  33.     // Otherwise, search for the correct place to insert
  34.  
  35. 	if(strcmp(newword,(*root)->word)<0)
  36. 	{
  37. 		return insert( &((*root)->left), newword);
  38. 	}
  39.  
  40. 	else if(strcmp(newword,(*root)->word)>0)
  41. 	{
  42. 		return insert( &((*root)->right), newword);
  43. 	}
  44. // If the new data is neither less than nor greater than the the data at
  45. // the current node, it must be equal, and duplicates are not allowed
  46. 	else
  47. 	return 0;
  48. }
  49.  
  50. // Returns 1 if target is in the tree and 0 otherwise
  51. int search(struct BSTnode* root, char target[wrdlen])
  52. {
  53.     // An empty tree contains nothing, much less target
  54. 	if(root == NULL)
  55. 		return 0;
  56. 	// If the current node is what we're looking for, we've found it 
  57.  
  58. 	if(strcmp(root->word,target) == 0)
  59. 		return 1;
  60.     // If what we're looking for is smaller than this node, it must be in
  61.     // the left subtree if it exists
  62. 	if(strcmp(target,root->word) < 0)
  63. 		return search(root->left, target);
  64. 	// Similarly, if the target is greater than this node, it can only be in
  65.     // the right subtree
  66. 	else
  67. 	return search(root->right, target);
  68. }
  69.  
  70. // An iterative version of the search algorithm
  71. int searchiterative(struct BSTnode* root, char target[wrdlen])
  72. {
  73. 	struct BSTnode* crnt = root; 
  74. 	// Keep descending through the tree until we reach the bottom or find what
  75. 	// we're looking for
  76. 	while(crnt != NULL && strcmp(crnt->word,target)!=0)
  77. 	{
  78. 		if(strcmp(target,crnt->word)>0)
  79. 		crnt = crnt->left;
  80.  
  81. 		else
  82. 		crnt = crnt->right;
  83. 	}
  84. 	// If we reached the bottom of the tree, then the target isn't present,
  85. 	// otherwise we found what we're looking for
  86. 	if(crnt == NULL)
  87. 		return 0;
  88.  
  89. 	else
  90. 		return 1;
  91. }
  92.  
  93. void spellcheck(struct BSTnode* root, char *token, int line)
  94. {
  95.     //capital letters are from 65 -> 90
  96.     //lowercase letters are from 97-122  
  97.     if(search(root, token))//if you find it normally then 
  98.       return;
  99.  
  100.      else if(token[0] >= 65 && token[0] <= 90)
  101.      {
  102.           token[0] = token[0] + 32;
  103.           if(search(root, token))
  104.              return;
  105.  
  106.           else
  107.           {   
  108.               token[0] = token[0] - 32;
  109.               printf("Line %d: %s\n", line, token); 
  110.               return;
  111.           }
  112.      }
  113.  
  114.      else
  115.      {
  116.          printf("Line %d: %s\n", line, token);
  117.          return;
  118.      }
  119. }
  120.  
  121.  
  122. int main(void)
  123. {
  124.     FILE *ifp; //dictionary file
  125.     FILE *scfp; //file to be spellchecked
  126.     char infile[wrdlen]; //"words.txt";
  127.     char Tinfile[wrdlen]; //"test.txt"; //test file
  128.     int valid = 0;
  129.     struct BSTnode* root;
  130.     char newword[wrdlen];
  131.     root = NULL;
  132.     int i = 0;
  133.     char str[linelen];
  134.     char delims[] = ("~!@#$%^&*()-_=+[]{}\\|;:\'\",.<>/?\n\r\t ");
  135.  
  136.  
  137.     //ask the user for the dictionary file
  138.     while(!valid)
  139.     {
  140.          printf("Please enter the name of the dictionary file you wish to access\n");
  141.          scanf("%s", infile);
  142.          ifp = fopen(infile, "r");         
  143.  
  144.          if(ifp == NULL)
  145.            printf("sorry, could not find that file!\n");
  146.          else
  147.          {   
  148.              valid = 1;
  149.              printf("Reading file now.........\n");
  150.          }
  151.     }    
  152.     valid = 0;
  153.     //read in all the words and place them into a BST
  154.     while(!feof(ifp))
  155.     {
  156.         fscanf(ifp, "%s ", newword);
  157.         insert(&root, newword);
  158.     }   
  159.  
  160.     //ask the user for the file to be spellchecked
  161.     while(!valid)
  162.     {
  163. 		printf("what is the name of the file you would like to spellcheck?\n");
  164. 		scanf("%s", Tinfile);
  165. 		scfp = fopen(Tinfile, "r");
  166. 		if(scfp == NULL)
  167.            printf("sorry, could not find that file!\n");
  168. 		else
  169. 		{   
  170.              valid = 1;
  171.              printf("Reading file now.........\n");
  172. 		}
  173.     }    
  174.  
  175.     printf("The following words were not recognized: \n");    
  176.  
  177.     for(i = 1; !feof(scfp); i++)
  178.     {
  179.      	fgets(str, linelen, scfp);
  180. 		char *token;
  181. 		token = strtok(str, delims);          
  182.  
  183. 		while( token != NULL ) 
  184. 		{
  185. 			spellcheck(root, token, i);    
  186. 			token = strtok( NULL, delims );
  187. 	    }    
  188.     }
  189. 	system("PAUSE");
  190.     return; 
  191. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 11
Reputation: mikeregas is an unknown quantity at this point 
Solved Threads: 0
mikeregas mikeregas is offline Offline
Newbie Poster

Re: BST spell check

 
0
  #2
Nov 10th, 2008
Here is the new code I have got it down to just three errors. yea! I can still use some help with it though
C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. //CONSTANTS 
  7. #define wrdlen 48 
  8. #define linelen 1024
  9.  
  10.  
  11. // A struct representing a node in a binary search tree
  12.  
  13. struct BSTnode
  14. {  
  15. char word[wrdlen];// The contents of the node	
  16. struct BSTnode* left;// Links to the node's left and right children
  17. struct BSTnode* right;
  18. };
  19.  
  20. // Adds a new node to the tree. Duplicates are disallowed. Returns 1 if a
  21. // new node was added, returns 0 if newdata was already in the tree
  22. int insert(struct BSTnode** root, char newword[wrdlen])
  23. {
  24.     // If we've reached the right place to insert, create a new node and add it in
  25. 	if( (*root) == NULL)
  26. 	{
  27. 		(*root) = (struct BSTnode*)malloc(sizeof(struct BSTnode));
  28.         strcpy((*root)->word,newword);
  29. 		(*root)->left = NULL;
  30. 		(*root)->right = NULL;
  31. 		return 1;
  32. 	}
  33.     // Otherwise, search for the correct place to insert
  34.  
  35. 	if(strcmp(newword,(*root)->word)<0)
  36. 	{
  37. 		return insert( &((*root)->left), newword);
  38. 	}
  39.  
  40. 	else if(strcmp(newword,(*root)->word)>0)
  41. 	{
  42. 		return insert( &((*root)->right), newword);
  43. 	}
  44. // If the new data is neither less than nor greater than the the data at
  45. // the current node, it must be equal, and duplicates are not allowed
  46. 	else
  47. 	return 0;
  48. }
  49.  
  50. // Returns 1 if target is in the tree and 0 otherwise
  51. int search(struct BSTnode* root, char target[wrdlen])
  52. {
  53.     // An empty tree contains nothing, much less target
  54. 	if(root == NULL)
  55. 		return 0;
  56. 	// If the current node is what we're looking for, we've found it 
  57.  
  58. 	if(strcmp(root->word,target) == 0)
  59. 		return 1;
  60.     // If what we're looking for is smaller than this node, it must be in
  61.     // the left subtree if it exists
  62. 	if(strcmp(target,root->word) < 0)
  63. 		return search(root->left, target);
  64. 	// Similarly, if the target is greater than this node, it can only be in
  65.     // the right subtree
  66. 	else
  67. 	return search(root->right, target);
  68. }
  69.  
  70. // An iterative version of the search algorithm
  71. int searchiterative(struct BSTnode* root, char target[wrdlen])
  72. {
  73. 	struct BSTnode* crnt = root; 
  74. 	// Keep descending through the tree until we reach the bottom or find what
  75. 	// we're looking for
  76. 	while(crnt != NULL && strcmp(crnt->word,target)!=0)
  77. 	{
  78. 		if(strcmp(target,crnt->word)>0)
  79. 		crnt = crnt->left;
  80.  
  81. 		else
  82. 		crnt = crnt->right;
  83. 	}
  84. 	// If we reached the bottom of the tree, then the target isn't present,
  85. 	// otherwise we found what we're looking for
  86. 	if(crnt == NULL)
  87. 		return 0;
  88.  
  89. 	else
  90. 		return 1;
  91. }
  92.  
  93. void spellcheck(struct BSTnode* root, char *token, int line)
  94. {
  95.     //capital letters are from 65 -> 90
  96.     //lowercase letters are from 97-122  
  97.     if(search(root, token))//if you find it normally then 
  98.       return;
  99.  
  100.      else if(token[0] >= 65 && token[0] <= 90)
  101.      {
  102.           token[0] = token[0] + 32;
  103.           if(search(root, token))
  104.              return;
  105.  
  106.           else
  107.           {   
  108.               token[0] = token[0] - 32;
  109.               printf("Line %d: %s\n", line, token); 
  110.               return;
  111.           }
  112.      }
  113.  
  114.      else
  115.      {
  116.          printf("Line %d: %s\n", line, token);
  117.          return;
  118.      }
  119. }
  120.  
  121.  
  122. int main(void)
  123. {
  124.     FILE *ifp; //dictionary file
  125.     FILE *scfp; //file to be spellchecked
  126.     char infile[wrdlen]; //"words.txt";
  127.     char Tinfile[wrdlen]; //"test.txt"; //test file
  128.     int valid = 0;
  129.     struct BSTnode* root;
  130.     char newword[wrdlen];
  131.     int i = 0;
  132.     char str[linelen];
  133. 	char delims[] = {"~!@#$%^&*()-_=+[]{}\\|;:\'\",.<>/?\n\r\t ""};
  134. 	char *token;
  135.  
  136.  
  137.     //ask the user for the dictionary file
  138.     while(!valid)
  139.     {
  140.          printf("Please enter the name of the dictionary file you wish to access\n");
  141.          scanf("%s", infile);
  142.          ifp = fopen(infile, "r");         
  143.  
  144.          if(ifp == NULL)
  145.            printf("sorry, could not find that file!\n");
  146.          else
  147.          {   
  148.              valid = 1;
  149.              printf("Reading file now.........\n");
  150.          }
  151.     }    
  152.     valid = 0;
  153.     //read in all the words and place them into a BST
  154.     while(!feof(ifp))
  155.     {
  156.         fscanf(ifp, "%s ", newword);
  157.         insert(&root, newword);
  158.     }   
  159.  
  160.     //ask the user for the file to be spellchecked
  161.     while(!valid)
  162.     {
  163. 		printf("what is the name of the file you would like to spellcheck?\n");
  164. 		scanf("%s", Tinfile);
  165. 		scfp = fopen(Tinfile, "r");
  166. 		if(scfp == NULL)
  167.            printf("sorry, could not find that file!\n");
  168. 		else
  169. 		{   
  170.              valid = 1;
  171.              printf("Reading file now.........\n");
  172. 		}
  173.     }    
  174.  
  175.     printf("The following words were not recognized: \n");    
  176.  
  177.     for(i = 1; !feof(scfp); i++)
  178.     {
  179.      	fgets(str, linelen, scfp);
  180.  
  181. 		token = strtok(str, delims);          
  182.  
  183. 		while( token != NULL ) 
  184. 		{
  185. 			spellcheck(root, token, i);    
  186. 			token = strtok( NULL, delims );
  187. 	    }    
  188.     }
  189. 	system("PAUSE");
  190.     return 0; 
  191. }
  192.  
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2008
Posts: 19
Reputation: bionicseraph is an unknown quantity at this point 
Solved Threads: 6
bionicseraph bionicseraph is offline Offline
Newbie Poster

Re: BST spell check

 
0
  #3
Nov 10th, 2008
What are the errors? I bet you are in the same class as me :p
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 11
Reputation: mikeregas is an unknown quantity at this point 
Solved Threads: 0
mikeregas mikeregas is offline Offline
Newbie Poster

Re: BST spell check

 
0
  #4
Nov 10th, 2008
I got all the errors fixed but now it is crashing. it crashes when the program reads the dictionary file
C Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. //CONSTANTS 
  7. #define wrdlen 48 
  8. #define linelen 1024
  9.  
  10.  
  11. // A struct representing a node in a binary search tree
  12.  
  13. struct BSTnode
  14. {  
  15. char word[wrdlen];// The contents of the node	
  16. struct BSTnode* left;// Links to the node's left and right children
  17. struct BSTnode* right;
  18.  
  19. };
  20.  
  21. // Adds a new node to the tree. Duplicates are disallowed. Returns 1 if a
  22. // new node was added, returns 0 if newdata was already in the tree
  23. int insert(struct BSTnode** root, char newword[wrdlen])
  24. {
  25.     // If we've reached the right place to insert, create a new node and add it in
  26. 	if( (*root) == NULL)
  27. 	{
  28. 		(*root) = (struct BSTnode*)malloc(sizeof(struct BSTnode));
  29.         strcpy((*root)->word,newword);
  30. 		(*root)->left = NULL;
  31. 		(*root)->right = NULL;
  32. 		return 1;
  33. 	}
  34.     // Otherwise, search for the correct place to insert
  35.  
  36. 	if(strcmp(newword,(*root)->word)<0)
  37. 	{
  38. 		return insert( &((*root)->left), newword);
  39. 	}
  40.  
  41. 	else if(strcmp(newword,(*root)->word)>0)
  42. 	{
  43. 		return insert( &((*root)->right), newword);
  44. 	}
  45. // If the new data is neither less than nor greater than the the data at
  46. // the current node, it must be equal, and duplicates are not allowed
  47. 	else
  48. 	return 0;
  49. }
  50.  
  51. // Returns 1 if target is in the tree and 0 otherwise
  52. int search(struct BSTnode* root, char target[wrdlen])
  53. {
  54.     // An empty tree contains nothing, much less target
  55. 	if(root == NULL)
  56. 		return 0;
  57. 	// If the current node is what we're looking for, we've found it 
  58.  
  59. 	if(strcmp(root->word,target) == 0)
  60. 		return 1;
  61.     // If what we're looking for is smaller than this node, it must be in
  62.     // the left subtree if it exists
  63. 	if(strcmp(target,root->word) < 0)
  64. 		return search(root->left, target);
  65. 	// Similarly, if the target is greater than this node, it can only be in
  66.     // the right subtree
  67. 	else
  68. 	return search(root->right, target);
  69. }
  70.  
  71. // An iterative version of the search algorithm
  72. int searchiterative(struct BSTnode* root, char target[wrdlen])
  73. {
  74. 	struct BSTnode* crnt = root; 
  75. 	// Keep descending through the tree until we reach the bottom or find what
  76. 	// we're looking for
  77. 	while(crnt != NULL && strcmp(crnt->word,target)!=0)
  78. 	{
  79. 		if(strcmp(target,crnt->word)>0)
  80. 		crnt = crnt->left;
  81.  
  82. 		else
  83. 		crnt = crnt->right;
  84. 	}
  85. 	// If we reached the bottom of the tree, then the target isn't present,
  86. 	// otherwise we found what we're looking for
  87. 	if(crnt == NULL)
  88. 		return 0;
  89.  
  90. 	else
  91. 		return 1;
  92. }
  93.  
  94. void spellcheck(struct BSTnode* root, char *token, int line)
  95. {
  96.     //capital letters are from 65 -> 90
  97.     //lowercase letters are from 97-122  
  98.     if(search(root, token))//if you find it normally then 
  99.       return;
  100.  
  101.      else if(token[0] >= 65 && token[0] <= 90)
  102.      {
  103.           token[0] = token[0] + 32;
  104.           if(search(root, token))
  105.              return;
  106.  
  107.           else
  108.           {   
  109.               token[0] = token[0] - 32;
  110.               printf("Line %d: %s\n", line, token); 
  111.               return;
  112.           }
  113.      }
  114.  
  115.      else
  116.      {
  117.          printf("Line %d: %s\n", line, token);
  118.          return;
  119.      }
  120. }
  121.  
  122.  
  123. int main(void)
  124. {
  125.     FILE *ifp; //dictionary file
  126.     FILE *scfp; //file to be spellchecked
  127.     char infile[wrdlen]; //"words.txt";
  128.     char Tinfile[wrdlen]; //"test.txt"; //test file
  129.     int valid = 0;
  130.     struct BSTnode* root;
  131.     char newword[wrdlen];
  132.     int i = 0;
  133.     char str[linelen];
  134. 	char delims[] = {"~!@#$%^&*()-_=+[]{}\\|;:\'\",.<>/?\n\r\t "};
  135. 	char *token;
  136.  
  137.  
  138.  
  139.     //ask the user for the dictionary file
  140.     while(!valid)
  141.     {
  142.          printf("Please enter the name of the dictionary file you wish to access\n");
  143.          scanf("%s", infile);
  144.          ifp = fopen(infile, "r");         
  145.  
  146.          if(ifp == NULL)
  147.            printf("sorry, could not find that file!\n");
  148.          else
  149.          {   
  150.              valid = 1;
  151.              printf("Reading file now.........\n");
  152.          }
  153.     }    
  154.     valid = 0;
  155.     //read in all the words and place them into a BST
  156.     while(!feof(ifp))
  157.     {
  158.         fscanf(ifp, "%s ", newword);
  159.         insert(&root, newword);
  160.     }   
  161.  
  162.     //ask the user for the file to be spellchecked
  163.     while(!valid)
  164.     {
  165. 		printf("what is the name of the file you would like to spellcheck?\n");
  166. 		scanf("%s", Tinfile);
  167. 		scfp = fopen(Tinfile, "r");
  168. 		if(scfp == NULL)
  169.            printf("sorry, could not find that file!\n");
  170. 		else
  171. 		{   
  172.              valid = 1;
  173.              printf("Reading file now.........\n");
  174. 		}
  175.     }    
  176.  
  177.     printf("The following words were not recognized: \n");    
  178.  
  179.     for(i = 1; !feof(scfp); i++)
  180.     {
  181.      	fgets(str, linelen, scfp);
  182.  
  183. 		token = strtok(str, delims);          
  184.  
  185. 		while( token != NULL ) 
  186. 		{
  187. 			spellcheck(root, token, i);    
  188. 			token = strtok( NULL, delims );
  189. 	    }    
  190.     }
  191. 	system("PAUSE");
  192.     return 0; 
  193. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2008
Posts: 2,001
Reputation: ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of ArkM has much to be proud of 
Solved Threads: 343
ArkM's Avatar
ArkM ArkM is offline Offline
Postaholic

Re: BST spell check

 
0
  #5
Nov 11th, 2008
The root variable is not initialized (by 0) before dictionary loading. It has a garbage pointer value so the program are trying to insert nodes to nowhere (memory access violation or another troubles follows)...
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C Forum
Thread Tools Search this Thread



#include adobe ansi api array asterisks binarysearch changingto char character cm copyimagefile cprogramme creafecopyofanytypeoffileinc createcopyoffile csyntax database directory dynamic execv feet fgets file fork forloop frequency function getlasterror givemetehcodez global grade graphics gtkgcurlcompiling hacking hardware highest histogram i/o include incrementoperators infiniteloop input interest kernel keyboard kilometer license linked linkedlist linux linuxsegmentationfault list locate logical_drives looping loopinsideloop. lowest match matrix meter microsoft motherboard mqqueue mysql number odf opensource owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv repetition research reversing scanf segmentationfault sequential shape socket socketprograming standard string systemcall threads turboc unix user voidmain() wab windows.h windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC