C program This assignment asks you to sort the lines of an input file (or from s
ID: 3806863 • Letter: C
Question
C program
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 the following command line arguments:
% bstsort [-c] [-o output_file_name] [input_file_name]
If -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:
1. 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 were included. 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 node exists, 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.
2. 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 line and 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.
3. 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.
4. 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.
5. Before the program ends, it must reclaim the tree! You can do this by performing a post-order
traversal, i.e., reclaiming the children nodes before reclaiming the node itself. Make sure you
also reclaim the memory occupied by the string as well.
6. It is required that 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 string comparison functions instead of using the corresponding libc
functions.
Here's an example:
bash$ cat myfile
bob is working.
david is a new hire.
alice is bob's boss.
charles doesn't like bob.
bash$ ./bstsort myfile
alice is bob's boss.
bob is working.
charles doesn't like bob.
david is a new hire.
You should submit the source code and the Makefile. One should be able to create the executable by simply 'make'. The Makefile should also contain a 'clean' target for cleaning up the directory (removing all temporary files, object files and executable files). Make sure you don't include intermediate files: *.o, executables, *~, etc., in your submission. (There'll be a penalty for including unnecessary intermediate files). Only three files should be included unless permission is given for more, those would be bstsort.c, bstsort.h, and Makefile.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>
#define ARRAYSIZE 50
typedef struct NODE
{
char *string;
int counter;
struct NODE * left;
struct NODE * right;
}NODE;
NODE * insertNode(NODE * node, char * string, int caseFlag);
NODE * createNode(char * stringData);
int stringCompCaseSen (char *string, char *string2);
void inOrder(NODE * root);
int stringCompCaseIns (char *string, char *string2);
void deallocateMem(NODE * node);
char * copyString (char * string);
void printString (char * string);
NODE * readFromStdin(NODE * root, int caseFlag);
NODE * readFromFile(NODE * root, char ** fileName, int caseFlag);
void printToStdout(NODE * node);
void printToFile(NODE * node, char * fileName);
int main (int argc, char **argv)
{
int option; //Holds getopt return value
int caseSenFlag = 0; //1 if comparison is case sensitive, otherwise 0 if is case insensitive
int outputFlag = 0; //1 if there is an outputfile, otherwise 0
int inputFlag = 0; //1 if there is an inputfile, otherwise 0
char * outPtr = NULL; //Points to the output file name
char ** inPtr = NULL; //Points to the pointer holding the input file name
struct NODE *root = NULL ;
//Gets all the options specified by the optstring
//Creates flags to handle the options specified by the user
while ((option = getopt(argc, argv, "co:h")) != -1)
{
switch (option) {
case 'c':
caseSenFlag = 1;
break;
case 'o':
outPtr = optarg;
outputFlag = 1;
break;
case 'h' :
printf("USAGE: %% bstsort [-c] [-o output_file_name] [input_file_name]");
break;
default:
printf("USAGE: %% bstsort [-c] [-o output_file_name] [input_file_name]");
break;
}
}
//Checks to see if there is an inputfilename argument given, if there is then sets the appropriate flag
if (*(inPtr = (argv + optind )))
inputFlag = 1;
//Recieved inputs in the way the user specified
if (inputFlag)
root = readFromFile(root, inPtr, caseSenFlag);
else
root = readFromStdin(root, caseSenFlag);
//Outputs the correct format the user has specified
if (outputFlag)
printToFile(root, outPtr);
else
printToStdout(root);
deallocateMem(root);
return 0;
}
//Read String from standard input
NODE * readFromStdin (NODE * root, int caseFlag)
{
char string[ARRAYSIZE];
int exitFlag = 0;
char e[] = "!e";
while (!exitFlag)
{
//Uses "!e" to exit
printf("Enter a word or sentence (!e to exit): ");
scanf(" %[^ ]s",string);
if ((stringCompCaseIns(string, e)) == 0)
exitFlag = 1;
else root = insertNode(root, string, caseFlag);
}
return root;
}
//Reads string from a file
NODE * readFromFile(NODE * root, char ** fileName, int caseFlag)
{
char string[ARRAYSIZE];
FILE *readPtr;
if(!(readPtr = fopen(*fileName, "r")))
{
printf("ERROR at opening %s ", *fileName);
exit(0);
}
while(fscanf(readPtr, " %[^ ]s", string) != EOF)
{
root = insertNode(root, string, caseFlag);
}
if(fclose(readPtr) == EOF)
{
printf("ERROR at closing %s ", fileName);
exit(0);
}
return root;
}
//Prints node to the standard output
void printToStdout(NODE * node)
{
if (!node)
return;
printToStdout(node->left);
int i;
for (i=0; i < node->counter;i++)
printf("%s ",node->string);
printToStdout(node->right);
return;
}
//Prints a node to a file
void printToFile(NODE * node, char * fileName)
{
FILE *writePtr;
if (!node)
return;
printToFile(node->left, fileName);
if (!(writePtr = fopen(fileName, "a")))
{
printf("ERROR at opening %s ", fileName);
exit(0);
}
int i;
//Prints as many times as the counter
for (i = 0; i < node->counter; i++)
fprintf(writePtr,"%s ",node->string);
if (fclose(writePtr) == EOF)
{
printf("ERROR at closing %s ", fileName);
exit(0);
}
printToFile(node->right, fileName);
return;
}
//Inserts node on the right place on the tree, check if nodes are equal
NODE * insertNode(NODE *node, char * string, int caseFlag)
{
if (node == NULL)
return(createNode(string));
if (caseFlag)
{
if (stringCompCaseSen(string, node->string) < 0)
node->left = insertNode(node->left, string, caseFlag);
else if (stringCompCaseSen(string, node->string) > 0)
node->right = insertNode(node->right, string, caseFlag);
//No need to deallocate node if is equal since it only increments a counter
else if (stringCompCaseSen(string, node->string) == 0)
node->counter = node->counter + 1;
}
else
{
if (stringCompCaseIns(string, node->string) < 0)
node->left = insertNode(node->left, string, caseFlag);
else if (stringCompCaseIns(string, node->string) > 0)
node->right = insertNode(node->right, string, caseFlag);
else if (stringCompCaseIns(string, node->string) == 0)
node->counter = node->counter + 1;
}
return node;
}
//Creates node with a specified string data
NODE * createNode(char * stringData)
{
NODE * newNode = (NODE*) malloc(sizeof(NODE));
if (!newNode)
exit(0);
//Stores only a copy of the string
newNode->string = copyString(stringData);
newNode->left = NULL;
newNode->right = NULL;
newNode->counter = 1;
return newNode;
}
//In order traversal to print the value on the tree
void inOrder (NODE * node)
{
if (node == NULL)
return;
inOrder(node->left);
int i;
for (i=0; i < node->counter;i++)
printf("inOrder: %50s ",node->string);
inOrder(node->right);
return;
}
//Does a post order traversal while freeing allocated memory
void deallocateMem(NODE * node)
{
if (node == NULL)
return;
deallocateMem(node->left);
deallocateMem(node->right);
free(node->string);
free(node);
return;
}
//Creates a copy of a string by dynamically allocating it
char * copyString(char * string)
{
char * strPtr = (char*)calloc(ARRAYSIZE, sizeof(char));
if (!strPtr)
exit(0);
int i = 0;
while(string[i] != '')
{
strPtr[i] = string[i];
i++;
}
strPtr[i] = '';
return strPtr;
}
//Helper method to print String
void printString( char * string)
{
int i = 0;
while (string[i] != '')
{
printf("%c", string[i]);
i++;
}
printf(" ");
return;
}
//Returns 0 if they are equal, 1 if string > string2, -1 if string < string2
int stringCompCaseSen(char *string, char *string2)
{
int i = 0;
//Uses compare string until it find the NULL character
//Uses ASCCII numerical values to compare them
while(string[i] != '' || string2[i] != '')
{
if(string[i] > string2[i])
return i+1;
if(string[i] < string2[i])
return -i-1;
i++;
}
return 0;//If equal returns 0
}
//Case Insensitive String Compare
int stringCompCaseIns (char *string, char *string2)
{
int i;
for (i = 0;string[i] != '' || string2[i] != ''; i++)
{
//Covert all letter to lower case in order to compare
if (tolower(string[i]) > tolower(string2[i]))
return i + 1;
if (tolower(string[i]) < tolower(string2[i]))
return -i-1;
}
return 0;
}
makefile
BTreeSort: main.o
gcc -o bstsort main.c
clean:
rm main.o bstsort *.txt
run:
./bstsort -c -o output.txt input.txt
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.