i need help with this code Assignment #1: Sorting with Binary Search Tree Throug

ID: 3598112 • Letter: I

Question

i need help with this code

Assignment #1:

Sorting with Binary Search Tree

Through this programming assignment, the students will learn to do the following:

Know how to process command line arguments.

Perform basic file I/O.

Use structs, pointers, and strings.

Use dynamic memory.

This assignment asks you to sort the lines of an input file (or from standard input) and print the sorted lines to an output file (or

standard output). Your program, called bstsort(binary search tree sort), will take thefollowing command line arguments:

% bstsort [-c] [-o output_file_name] [input_file_name]

c is present, the program needs to compare the strings case

sensitive; otherwise, it's case

insensitive. If the output_file_name

is given with the

o option, the program will

output the sorted

lines to the given output file;

otherwise, the output shall be the standard output. Similarly, if

the

input_file_name is given, the program will read from the input file;

otherwise, the input will be

from the standard input. You must use

getopt() to

parse the command line arguments to determine

the cases.

All strings will be no more than 100 characters long.

In addition to parsing and processing the command line arguments, your program needs

to do the

following:

You need to construct a binary search tree as you read from input. A binary search tree is a binary tree. Each node can have at most two child nodes (one on the left and one on the right), both or either one can be empty. If a child node exists, it's the root of a binary search tree (we call subtree). Each node contains a key (in our case, it's a string)and a count of how many of that string wereincluded

.If the left subtree of a node exists, it contains only nodes with keys less than the node's key. If the right subtree of a nodeexists, it contains only nodes with keys greater than the node's key. You can look up binary search tree on the web or in your Data Structure textbook. Note that you do not need to balance the binary search tree (that is, you can ignore all those rotation operations) in this assignment.

Initially the tree is empty(that is, the root is null). The program reads from the input file (or stdin) one line at a time; If the line is not an empty lineand the line is not already in the tree, it should create a tree node that stores

a pointer to the string (or optionally a copy of the string) and a count of 1 indicating this is the first occurrence of that string, and then insert the tree node

to the binary search tree

.An empty line would indicate the end of input for stdin, an empty line or end

of file would indicate the end of input for an input file. If the line is not an empty line and the line is already in the tree, increase the count for that node indicating that there are multiple instances of that line.

You must develop two string comparison functions, one for case sensitive and the other for case insensitive. You must not use strcmp() and strcasecmp() functions provided by the C library. You must implement your own version.

Once the program has read all the input (when EOF is returned), the program then performs an in-order traversal of the binary search tree to print

out all the strings one line at a time to the output file or stdout.If there are duplicates than include all duplicates.If the selection was for case insensitive then you can include whatever the case was for the first occurrence

Before the program ends, it must reclaim the tree! You can dothis by performing a post-order traversal, i.e., reclaiming thechildren nodes before reclaiming the node itself. Make sure you also reclaim the memoryoccupied by the string as well.

It is required tat you use getopt for processing the command line and use malloc/free functions for dynamically allocating and deallocating nodes and the buffers for the strings. It is required that you implement your own stringcomparison functions instead of using the corresponding libc functions.

this is what i have but my output is wrong

typedef struct bst_node
{
   char *word;
   int count;
   struct bst_node *left;
   struct bst_node *right;
}
node;
//case sensitive compare
int stringCompare(char *str1, char *str2)
{
   int i = 0;
   char c1, c2;
   while(str1[i] != '' && str2[i] != '')
   {
       c1 = str1[i];
       c2 = str2[i];
       if(c1 != c2)
       {
           return c1-c2;
           i++;
       }
       if(str1[i] == '' && str2 != '')
       {
           return str2[i];
       }
       else if(str1 != '' && str2 == '')
       {
           return str1[i];
       }
       else
       {
           return 0;
       }
   }
}

int stringCompare2(char *str1, char *str2)
{
   int i = 0;
   char c1, c2;
   while(str1[i] != '' && str2[i] != '')
   {
       c1 = str1[i];
       c2 = str2[i];
       if(c1 >= 'A' && c1 <= 'Z')
       {
           c1 = c1 - 'A' + 'a';
       }
       if(c2 >= 'A' && c2 <= 'Z')
       {
           c2 = c2 - 'A' + 'a';
       }

       if(c1 != c2)
       {
           return c1 - c2;
           i++;
       }
       if(str1[i] == '' && str2 != '')
       {
           return str2[i];
       }
       else if(str1 != '' && str2 == '')
       {
           return str1[i];
       }
       else
       {
           return 0;
       }
   }
}
node* createNode(char *str)
{
   node* n = (node*) malloc(sizeof(node));
   n->word = (char*) malloc(strlen(str));
   n->count = 1;
   strcpy(n->word, str);

   n->left = NULL;
   n->right = NULL;
   return n;
}
void insert(node **root, char *str, int caseSensitive)
{
   node *current;
   int compare;
   if(*root == NULL)
   {
       *root = createNode(str);
   }
   else
   {
       current = *root;
       while(current != NULL)
       {
           if(caseSensitive)
           {
               compare = stringCompare(str, current->word);
           }
           else
           {
               compare = stringCompare2(str, current->word);
           }

           if(compare == 0)
           {
               current->count++;
               return;
           }
           else if(compare <0)
           {

               if(current->left == NULL)
               {
                   current->left = createNode(str);
                   return;
               }
                   current = current->left;
           }
           else
           {
               current->right = createNode(str);
               return;
           }
           current->right;
       }
   }
}
void inOrder(FILE *outFile, node *node)
{
   if(node == NULL)
   {
       return;
   }
   inOrder(outFile, node->left);
   fprintf(outFile, "%s[%d] ", node->word, node->count);
   inOrder(outFile, node->right);
}

void freeNode(node *root)
{
   if(root == NULL)
   {
       return;
   }
   freeNode(root->left);
   freeNode(root->right);
   free(root->word);
   free(root);
}

#include
#include
#include
#include "bstsort.h"

int main(int argc, char **argv)
{
   extern char *optarg;
   extern int optind;
   int c, err = 0;
   int cflag=0, oflag=0;
   int caseSensitive = 0;
   char string[100], temp[100], ch;
   node *root = NULL;
   int results = 1, i;
   char *output_file_name, *input_file_name;
   FILE* inFile = stdin;
   FILE* outFile = stdout;
   static char usage[] = "usage: %bstsort [-c] [-o output_file_name][input_file_name] ";

   while ((c = getopt(argc, argv, "co:")) != -1)
       switch (c) {
       case 'c':
           cflag = 1;
           break;
       case 'o':
           oflag = 1;
           output_file_name = optarg;
           break;
       case '?':
           err = 1;
           break;
       }

   if(cflag == 1)
   {
       caseSensitive = 1;
   }
   if(oflag == 1)
   {
       if((outFile = fopen(output_file_name, "r")) == NULL)
       {
           //...the user is promted of the error
           printf("Could not open file. ");
           //...the user is also promted to make sure the proper file extension was included
           printf("Make sure the file's extension is included in file name. ");
           //... the progam is exited
           exit(1);

       }

   }
   if(optind > argc)
   {
       input_file_name = argv[optind];

       if((inFile = fopen(input_file_name, "r")) == NULL)
       {
           //...the user is promted of the error
           printf("Could not open file. ");
           //...the user is also promted to make sure the proper file extension was included
           printf("Make sure the file's extension is included in file name. ");
           //... the progam is exited
           exit(1);

       }
   }

   while(fgets(string, 100, inFile) != NULL)
   {
       if(stringCompare(" ", string) == 0)
       break;
       //remove newline from the end of line
       string[strlen(string) - 1] = '';
       insert(&root, string, caseSensitive);
   }
   fclose(inFile);
   inOrder(outFile, root);
   fclose(outFile);
   freeNode(root);
   exit(0);
}

:~/bstsort 44% ./bstsort

**what i typed

apple

peach

house

building

***what printed im missing the others

apple[1]

building[1]

Explanation / Answer

Dear Student,

I can see problems following problems.

1. String comparision function is not implemented well. a) condition check at the time of exit are places inside the loop. b) also use of string vaues is not a good idea as you only want to signal greater or lesser in alphabatical order so use -1, 0 and +1 as return values. c) also you were using string pointers without index to compare that is meaningless. Following is the correct code.

2. In similar way you could mofidy stringCompare2 as well. I am writing the code below.

int stringCompare2(char *str1, char *str2)
{
   int i = 0;
   char c1, c2;
   while(str1[i] != '' && str2[i] != '')
   {
       c1 = str1[i];   c2 = str2[i];
       if(c1 >= 'A' && c1 <= 'Z') c1 = c1 - 'A' + 'a';
       if(c2 >= 'A' && c2 <= 'Z') c2 = c2 - 'A' + 'a';
       if(c1 != c2) return -1;
       i++;
   }
   if(str1[i] == '' && str2 != '') return 0;
   else if(str1[i] != '' && str2[i] == '') return 1;
        else return -1;
}

3. Create node has a small issue. Since size of string is one greater than the actual displayed characters to accomodate end of string character that is 0. Please increase 1 as I have done in code below.

node* createNode(char *str)
{
   node* n = (node*) malloc(sizeof(node));
   n->word = (char*) malloc(strlen(str)+1); // Add 1 here as it needs one char to put end of string, that is 0
   n->count = 1;
   strcpy(n->word, str);

   n->left = NULL;
   n->right = NULL;
   return n;
}

4. There was serious flaw in insert function. a) Checking for right side being null was not implemented but a neww node was inserted. b) current->right was not assigned to current. Correct code is below. Please modify the code accordingly and go ahead with the programming

void insert(node **root, char *str, int caseSensitive)
{
   node *current;   int compare;
   if(*root == NULL) *root = createNode(str);
   else
   {
       current = *root;
       while(current != NULL)
       {
           if(caseSensitive) compare = stringCompare(str, current->word);
           else compare = stringCompare2(str, current->word);

           if(compare == 0)
           {
               current->count++;
               return;
           }
           else if(compare <0)
           {
               if(current->left == NULL)
               {
                   current->left = createNode(str);
                   return;
               }
                   current = current->left;
           }
           else
           {
               if(current->right == NULL)
               {
                   current->right = createNode(str);
                   return;
               }
               current =current->right;
           }
       }
   }
}

##[Following was the code on my computer] ####################################

#include<string.h>
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>

typedef struct bst_node
{
   char *word;
   int count;
   struct bst_node *left;
   struct bst_node *right;
}
node;
//case sensitive compare

int stringCompare(char *str1, char *str2)
{
   int i = 0;
   char c1, c2;
   while(str1[i] != '' && str2[i] != '')
   {
       c1 = str1[i];   c2 = str2[i];
       if(c1 != c2) return -1;
       i++;
   }
   if(str1[i] == '' && str2 != '') return 0;
   else if(str1[i] != '' && str2[i] == '') return 1;
        else return -1;
}

int stringCompare2(char *str1, char *str2)
{
   int i = 0;
   char c1, c2;
   while(str1[i] != '' && str2[i] != '')
   {
       c1 = str1[i];   c2 = str2[i];
       if(c1 >= 'A' && c1 <= 'Z') c1 = c1 - 'A' + 'a';
       if(c2 >= 'A' && c2 <= 'Z') c2 = c2 - 'A' + 'a';
       if(c1 != c2) return -1;
       i++;
   }
   if(str1[i] == '' && str2 != '') return 0;
   else if(str1[i] != '' && str2[i] == '') return 1;
        else return -1;
}

void inOrder(FILE *outFile, node *node)
{
   if(node == NULL)
   {
       return;
   }
   inOrder(outFile, node->left);
   fprintf(outFile, "%s[%d] ", node->word, node->count);
   inOrder(outFile, node->right);
}

void freeNode(node *root)
{
   if(root == NULL)
   {
       return;
   }
   freeNode(root->left);
   freeNode(root->right);
   free(root->word);
   free(root);
}

Navigate

i need help with this block of code. Im having trouble figuring out if there are

i need help with this code in c, i have: #include <stdio.h> int main() { int cou

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

i need help with this code Assignment #1: Sorting with Binary Search Tree Throug

Question

Explanation / Answer

Related Questions

Navigate