This program reads text from the standard input and builds a binary search tree containing the individual words from the input. The program reads input until no more data is available, counting the frequency of occurrence of each word in the input. Once the input has been exhausted, the tree will be traversed with an in-order traversal to produce an alphabetical list of words with their frequencies.
Problem: I can compile my code without any errors and when I run ./wordFreq < input.1, it runs perfect and outputs the correct answer with no errors...this is the correct output:
additional 1 agree 3 another 3 don't 3 for 1 I 1 input 4 is 3 line 5 need 1 one 1 road 1 the 1 think 1 This 4 we 1 yet 1 you 3
But whenever I submit it to the try server it tests the code and tells me that I didn't output anything, and that I had a "Program failed: Memory fault, core dumped", this is the output I am getting on page 1: Try Submission Output
This is my wordFreq.c file:
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "wordFreq.h"
#define UNUSED(p) ((void)(p))
// Creates a node for each unique word it is given, and then inserts this
// new node in the proper position in the binary search tree, updating
// whatever pointer is necessary.
//
// @param root a pointer to the variable which contains the pointer to the
// root-level node in the tree
// @param word a pointer to the NUL-terminated arrach of characters
void insert_word(TreeNode** root, const char *word){
if (*root == NULL){
*root = (TreeNode*)malloc(sizeof(TreeNode));
unsigned int len = strlen(word);
(*root)->word = (char *)malloc((len + 1) * sizeof(char));
strncpy((*root)->word, word, len);
(*root)->word[len] = 0;
(*root)->frequency = 1;
(*root)->left = NULL;
(*root)->right = NULL;
}
else{
int compare = strcasecmp(word, (*root)->word);
if (compare < 0){
insert_word(&((*root)->left), word);
} else if(compare> 0){
insert_word(&((*root)->right), word);
} else if(compare == 0){
(*root)->frequency++;
}
}
}
// Traverses the entire tree using an in-order traversal and will
// print th contents of each node as it is visited
//
// @param root a pointer to the root node of the tree
void traverse_tree(const TreeNode* root){
if (root == NULL)
return;
if (root != NULL){
traverse_tree(root->left);
printf("%s %d\n", root->word, root->frequency);
traverse_tree(root->right);
}
return;
}
// Deallocates all the nodes that were created in insert_node()
//
// @param a pointer to the root node of the tree
void cleanup_tree(TreeNode* root){
if (root == NULL)
return;
if (root->left != NULL){
cleanup_tree(root->left);
}
if(root->right != NULL){
cleanup_tree(root->right);
}
free(root->word);
free(root);
return;
}
int main(int argc, char* argv[]){
UNUSED(argv);
if (argc > 1)
printf("Usage: bst");
else{
FILE* pFile = fopen("input.1", "r");
char *buf = NULL;
size_t len = 0;
TreeNode** root = NULL;
if (!pFile){
printf("File not found");
} else{
root = (TreeNode**)malloc(sizeof(TreeNode*));
*root = NULL;
while (getline(&buf,&len,pFile) > 0){
char * pch;
pch = strtok(buf, " !@#$%^&*?.,:;\n");
while (pch !=NULL){
insert_word(root, pch);
pch = strtok(NULL, " !@#$%^&*,:;?.\n");
}
}
free(buf);
fclose(pFile);
traverse_tree(*root);
}
cleanup_tree(*root);
free(root);
}
return 0;
}
This is my wordFreq.h file:
#ifndef _BST_H_
#define _BST_H_
// The definition of the tree structure
typedef struct TreeNode_st {
char *word; // the word held in this node
unsigned int frequency; // how many times it has been seen
struct TreeNode_st *left; // node's left child
struct TreeNode_st *right; // node's right child
} TreeNode;
// FUNCTIONS ARE REQUIRED TO IMPLEMENT
// insert_word()
// Dynamically build BST by allocating nodes from the heap
//
// args -
// root - a pointer to the pointer to the root of the tree
// to build this tree on to.
// word - string containing the word to be inserted
void insert_word( TreeNode** root, const char *word );
// traverse_tree()
// Recursively traverses the tree and prints the value of each
// node.
//
// args -
// root - a pointer to the root of the tree to traverse
void traverse_tree( const TreeNode* root );
// cleanup_tree()
// Cleanup all memory management associated with the nodes on the heap
//
// args
// root - the current root of the tree
void cleanup_tree( TreeNode* root );
#endif // BST_H
This is the input file (named input.1):
This is one input line. This is another input line, don't you agree? Another input line, don't you agree? This is yet another input line, don't you agree? I think we need this additional line for the road.
Compile Commands:
root@comp:~/Desktop/Homeworks/5$ gcc -ggdb -std=c99 -Wall -Wextra -pedantic -c wordFreq.c root@comp:~/Desktop/Homeworks/5$ gcc -ggdb -std=c99 -Wall -Wextra -pedantic -o wordFreq wordFreq.o -lm
Valgrind Test: I also tested the code in valgrind using the command:
I got no errors... here's the link to test on page 2: Valgrind Test Link
You have some issues in your code:
You include non-standard file <strings.h>, but not <stdlib.h> where malloc() and free() are declared.
You never check malloc() return value. If the test system has very little memory or is configured to make malloc() fail early, which is doable, your program will crash instead of reporting the error.
Do not use strncpy((*root)->word, word, len) to copy the string to allocated memory. Just use strcpy since you allocated enough memory with strlen(word) + 1 bytes, or use memcpy((*root)->word, word, len + 1) or better: use strdup(). strncpy does not do what you think! it has very error prone and widely misunderstood semantics. Never use this function.
In the main() function, you should use a TreeNode *root; variable and pass its address to insert_word() instead of allocating a pointer.
The only serious issue is the second point above, although it is unlikely to explain the observed behavior.